張其文，尉雅晨

蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，蘭州 730050

1 引言

粒子群算法（particle warm optimization，PSO）[1]是由Kennedy 和Eberhart 博士于1995 年共同提出來(lái)的一種模仿鳥(niǎo)類群體行為的智能優(yōu)化算法。該算法已得到了廣泛的應(yīng)用[2-3]。粒子群算法具有實(shí)現(xiàn)簡(jiǎn)單、控制參數(shù)少等優(yōu)點(diǎn)，粒子群算法的收斂性能取決于“勘探”與“開(kāi)發(fā)”之間的平衡，而算法中參數(shù)的合理選擇對(duì)粒子群算法平衡“勘探”與“開(kāi)發(fā)”起重要作用。典型的參數(shù)調(diào)整包括：慣性權(quán)重、學(xué)習(xí)因子、最大速度、收縮因子等。Zhang 等[4]提出利用貝葉斯技術(shù)根據(jù)粒子的位置自適應(yīng)調(diào)整慣性權(quán)重，提高了算法在多維復(fù)雜函數(shù)中的收斂精度及速度。Taherkhani等[5]提出了基于穩(wěn)定性的自適應(yīng)慣性權(quán)重，且學(xué)習(xí)因子根據(jù)慣性權(quán)重自適應(yīng)調(diào)整，算法的求解質(zhì)量和收斂速度都有明顯的提高。Tian 等[6]提出了一種介于線性與非線性之間的自適應(yīng)改變慣性權(quán)重的方法，使算法具有更好地平衡“勘探”與“開(kāi)發(fā)”的能力。董紅斌等人[7]提出了一種動(dòng)態(tài)調(diào)整慣性權(quán)重的粒子群算法，使算法具有跳出局部最優(yōu)的能力。蔣麗等[8]在二階振蕩粒子群算法的基礎(chǔ)上改進(jìn)振蕩環(huán)節(jié)的參數(shù)取值，采用互不相同的參數(shù)取值調(diào)節(jié)了粒子群算法的全局與局部搜索能力，提高了種群多樣性。黃洋等[9]提出了一種基于S 型函數(shù)的自適應(yīng)粒子群算法，算法根據(jù)倒S 型函數(shù)的特點(diǎn)對(duì)慣性權(quán)重進(jìn)行非線性調(diào)整，有效平衡了算法的全局搜索與局部搜索能力。張?chǎng)蔚萚10]提出利用鎖定因子及當(dāng)前粒子的位置自適應(yīng)調(diào)整慣性權(quán)重的自適應(yīng)簡(jiǎn)化粒子群算法，實(shí)驗(yàn)結(jié)果表明算法具有較好的收斂能力。此外，Liang等[11]將綜合學(xué)習(xí)策略應(yīng)用于粒子群算法中，使用粒子的歷史最佳位置來(lái)更新粒子的速度，維持種群的多樣性，有效地防止算法過(guò)早收斂。Tanweer 等[12]提出自調(diào)節(jié)粒子群算法，采用最佳粒子的慣性權(quán)重自調(diào)節(jié)和其余粒子通過(guò)對(duì)全局最佳位置的感知來(lái)確定搜索方向的兩種學(xué)習(xí)策略，算法在大多數(shù)問(wèn)題上表現(xiàn)出良好的收斂能力。李煒等[13]提出一種改進(jìn)粒子群算法，該算法通過(guò)結(jié)合特征聚類信息改進(jìn)了種群的初始化策略，且根據(jù)粒子在決策空間中的密度，對(duì)粒子進(jìn)行交互操作，保持種群的多樣性，避免過(guò)早收斂。

目前，大部分改進(jìn)粒子群算法均在不同程度上提高了算法的收斂性能，但它們?cè)趨?shù)設(shè)置方面均基于種群，沒(méi)有考慮粒子與粒子間進(jìn)化能力的差異及種群整體的進(jìn)化情況，在進(jìn)化的每一代中所有粒子的參數(shù)設(shè)置是相同的，這樣全局搜索與局部搜索就很難達(dá)到平衡。針對(duì)這一問(wèn)題，本文提出了獨(dú)立自適應(yīng)參數(shù)調(diào)整的粒子群優(yōu)化算法，通過(guò)獨(dú)立粒子的進(jìn)化能力、種群進(jìn)化能力及進(jìn)化率來(lái)動(dòng)態(tài)調(diào)整每個(gè)粒子的參數(shù)，增強(qiáng)算法平衡全局搜索與局部搜索的能力。同時(shí)加入粒子重構(gòu)策略使進(jìn)化能力較弱的粒子通過(guò)向進(jìn)化能力較強(qiáng)的粒子進(jìn)行學(xué)習(xí)生成新粒子，這既增加了種群多樣性，也使算法能跳出局部最優(yōu)。

2 粒子群算法

1998 年Shi 和Eberhart[14]首次提出將慣性權(quán)重添加到粒子群算法的速度更新公式當(dāng)中去，如下所示：

其中，t為當(dāng)前迭代次數(shù)，r1、r2為[0,1]之間的隨機(jī)數(shù)，用來(lái)維持種群的多樣性。Pb為個(gè)體歷史最優(yōu)位置，Gb為群體歷史最優(yōu)位置，c1、c2為學(xué)習(xí)因子。ω稱為慣性權(quán)重，它用于表示粒子上一代的速度對(duì)當(dāng)前粒子運(yùn)動(dòng)行為的影響。目前使用較多的慣性權(quán)重的設(shè)置方式是隨迭代次數(shù)的增加而線性減小：

其中，ωinit為初始權(quán)重，ωend為最終權(quán)重，T為最大迭代次數(shù)。

3 參數(shù)的調(diào)整

在進(jìn)化過(guò)程中，粒子與粒子之間的進(jìn)化能力、種群的整體進(jìn)化能力、求解的問(wèn)題均不同，因此本文在對(duì)參數(shù)的設(shè)置方面充分考慮了這些不同之處，使參數(shù)能在不同的情況下進(jìn)行自適應(yīng)調(diào)整。

定義1（粒子進(jìn)化能力）在進(jìn)化過(guò)程中，將粒子進(jìn)化能力定義為該粒子相較于其他粒子能找到的較好解的能力。

定義2（種群進(jìn)化能力）在進(jìn)化過(guò)程中，將種群進(jìn)化能力定義為種群中所有粒子能找到比當(dāng)前最優(yōu)解更好解的能力。

粒子的進(jìn)化能力與種群的進(jìn)化能力計(jì)算公式如下：

定義3（進(jìn)化率）在進(jìn)化過(guò)程中，將粒子的進(jìn)化率定義為粒子在種群中進(jìn)化能力變化程度的大小。

粒子在種群中進(jìn)化能力的進(jìn)化率計(jì)算如下：

若粒子進(jìn)化能力及種群進(jìn)化能力都較強(qiáng)時(shí)，粒子進(jìn)化率較小，則粒子在下一代會(huì)較多地繼承上一代粒子的進(jìn)化能力，反之亦然。

3.1 自適應(yīng)慣性權(quán)重

本文根據(jù)粒子進(jìn)化能力與種群的進(jìn)化能力為每個(gè)粒子設(shè)置自適應(yīng)慣性權(quán)重，這樣既保證了粒子的多樣性，又方便粒子更好地在空間中進(jìn)行搜索。獨(dú)立粒子的慣性權(quán)重設(shè)置公式如式（7）所示：

綜上所述，在t+1 代時(shí)每個(gè)粒子慣性權(quán)重的調(diào)整都由第t代時(shí)粒子進(jìn)化能力和種群進(jìn)化能力共同決定。群體中的粒子能否發(fā)現(xiàn)比當(dāng)前全局最優(yōu)更好的解決定了粒子的搜索范圍，而粒子本身進(jìn)化能力的強(qiáng)弱則是設(shè)置獨(dú)立粒子慣性權(quán)重的關(guān)鍵。

3.2 自適應(yīng)學(xué)習(xí)因子

學(xué)習(xí)因子是體現(xiàn)粒子向自身歷史最優(yōu)學(xué)習(xí)與向群體歷史最優(yōu)學(xué)習(xí)能力的兩個(gè)參數(shù)。本文在將學(xué)習(xí)因子c1設(shè)計(jì)為遞減函數(shù)、c2設(shè)計(jì)為遞增函數(shù)的基礎(chǔ)上根據(jù)粒子進(jìn)化能力的變化率去調(diào)整每一代中每個(gè)粒子的學(xué)習(xí)因子。這樣的設(shè)置方式與其他經(jīng)典學(xué)習(xí)因子的取值方式相比，不但能在迭代初期保證粒子的學(xué)習(xí)能力，加強(qiáng)全局搜索；在迭代后期保證粒子的社會(huì)學(xué)習(xí)，利于局部精準(zhǔn)搜索，還通過(guò)獨(dú)立粒子之間不同的進(jìn)化率，對(duì)學(xué)習(xí)因子進(jìn)行調(diào)整，使粒子結(jié)合自身情況調(diào)整學(xué)習(xí)模式。調(diào)整公式如下所示：

其中，c1max表示學(xué)習(xí)因子的最大值；c2min表示學(xué)習(xí)因子的最小值。粒子在迭代初期應(yīng)該具有較強(qiáng)的自我學(xué)習(xí)能力，此時(shí)的c1值較大，c2值較小。若某粒子i的進(jìn)化率較小，那么該粒子相比其他粒子的c1稍大、c2稍小，更有利于該粒子進(jìn)行全局搜索。隨著迭代次數(shù)的增加，粒子應(yīng)該具有較強(qiáng)的社會(huì)學(xué)習(xí)能力，此時(shí)的c1值較小，c2值較大。若粒子i的進(jìn)化率較大，那么該粒子相比其他粒子的c1稍小、c2稍大，更有利于該粒子進(jìn)行局部搜索。本文中，每個(gè)粒子的學(xué)習(xí)因子均根據(jù)粒子進(jìn)化能力的變化率進(jìn)行自適應(yīng)調(diào)整。式中的參數(shù)取值c1max=2,c2min=0.8。

4 粒子重構(gòu)策略

為了進(jìn)一步保障種群多樣性，使粒子有跳出局部最優(yōu)的能力，本文采用粒子重構(gòu)策略，它的主要思想是從種群中選擇出部分進(jìn)化能力較弱的粒子向進(jìn)化能力較強(qiáng)的粒子進(jìn)行學(xué)習(xí)，重新構(gòu)造出新粒子。

4.1 粒子的選擇

由式（4）可知，在進(jìn)化過(guò)程中，粒子的進(jìn)化能力與該粒子的適應(yīng)度值相關(guān)，因此本文將粒子適應(yīng)度值的好壞作為評(píng)判粒子進(jìn)化能力強(qiáng)弱的標(biāo)準(zhǔn)。在使用粒子重構(gòu)策略前，先將種群中的粒子按照適應(yīng)度值進(jìn)行排序，選擇出末尾的個(gè)粒子作為進(jìn)化能力較弱的粒子，這部分粒子將進(jìn)行重構(gòu)操作。剩余的個(gè)粒子為進(jìn)化能力較強(qiáng)的粒子，是進(jìn)化能力較弱的粒子進(jìn)行重構(gòu)時(shí)需要學(xué)習(xí)的范例。其中由式（10）、式（11）進(jìn)行確定：

其中，N表示種群的總規(guī)模。被選擇重構(gòu)的粒子數(shù)是隨著迭代次數(shù)t的增加而增長(zhǎng)的，被選擇重構(gòu)的粒子數(shù)最大可達(dá)到種群總規(guī)模的80%。

4.2 粒子的重構(gòu)

最后將新生成的粒子與進(jìn)化能力較強(qiáng)的粒子合并后一起進(jìn)行下一次迭代。該策略的優(yōu)勢(shì)在于它既能有效地拓寬種群的搜索范圍，又能保證算法的收斂精度與速度。

5 獨(dú)立自適應(yīng)調(diào)整參數(shù)的粒子群優(yōu)化算法

5.1 算法的收斂性分析

算法參數(shù)的選取和算法的收斂性是決定粒子群算法性能與效率的重要因素，因此對(duì)算法的收斂條件及滿足收斂時(shí)參數(shù)的取值范圍進(jìn)行分析是十分有必要的。為了使下面對(duì)粒子群算法的分析更加方便直觀，在不失一般性的條件下，將粒子的速度與位置的維數(shù)從D維簡(jiǎn)化為1 維，令Pi為粒子i自身找到的最好的位置，Pg為整個(gè)種群找到的最好位置，令：

因此可以將PSO 的速度與位置公式簡(jiǎn)化如下：

再令：

可將式（13）、式（14）表示為：

定義4（平衡點(diǎn)）將R*定義為動(dòng)態(tài)系統(tǒng)R(t+1)=A*R(t)的平衡點(diǎn)，在本文中，平衡點(diǎn)R*必須滿足條件：?t≥0 均滿足R(t+1)=R(t)。

根據(jù)李亞普諾夫的穩(wěn)定性可知，系統(tǒng)收斂到平衡點(diǎn)的充分必要條件是A的全部特征值均要小于或等于1。

|A-λE|=0 稱為矩陣A的特征方程。矩陣A的特征值為特征方程λ2-(ω+1-φ)λ+ω=0 的解，因此解得線性系統(tǒng)R的兩個(gè)特征值為：

其中Δ=(ω+1-φ)2-4ω

對(duì)Δ=0,Δ＞0,Δ＜0 分別討論后，得出系統(tǒng)R(t)的收斂域?yàn)椋?/p>

系統(tǒng)收斂的充分必要條件為：

本文根據(jù)粒子自身進(jìn)化與種群進(jìn)化能力對(duì)每個(gè)粒子進(jìn)行自適應(yīng)獨(dú)立參數(shù)設(shè)置，其中參數(shù)的取值為ωinit=0.9,ωend=0.4,c1max=c2max=2,c1min=c2min=0.8。根據(jù)式（4）～式（9）可得：

由此可得IAP-PSO 中關(guān)于參數(shù)的設(shè)置滿足算法的收斂條件，證明該算法具有在搜索空間中收斂到局部最優(yōu)點(diǎn)甚至是全局最優(yōu)點(diǎn)的能力。

5.2 算法的具體流程

IAP-PSO 算法的基本步驟：

步驟1 隨機(jī)初始化N個(gè)粒子，初始化參數(shù)ωinit、ωend、c1max、c2max、c1min、c2min，最大迭代次數(shù)T，問(wèn)題維度D等。

步驟2 計(jì)算粒子的適應(yīng)度值，找出個(gè)體最優(yōu)Pb與全局最優(yōu)Gb。

步驟3 根據(jù)式（1）、式（2）更新粒子的速度與位置。

步驟4 計(jì)算粒子的適應(yīng)度值，更新個(gè)體最優(yōu)與全局最優(yōu)。

步驟5 根據(jù)式（4）～式（9）計(jì)算出粒子i在第t+1代時(shí)的慣性權(quán)重及學(xué)習(xí)因子。

步驟6 選擇出進(jìn)化能力較弱的粒子，根據(jù)式（12）向進(jìn)化能力較強(qiáng)的粒子進(jìn)行學(xué)習(xí)，重構(gòu)新粒子，將新粒子與進(jìn)化能力較強(qiáng)的粒子合并。

步驟7 判斷算法是否達(dá)到終止條件，若滿足，則算法停止并輸出最優(yōu)值；若不滿足，跳轉(zhuǎn)到步驟3 繼續(xù)執(zhí)行。

5.3 時(shí)間復(fù)雜度分析

由IAP-PSO 算法可知，其主要包括如下部分：（1）初始化，時(shí)間復(fù)雜度為O(N×D)；（2）粒子進(jìn)行速度與位置的更新，時(shí)間復(fù)雜度為O(N×D)；（3）計(jì)算粒子適應(yīng)度值，更新個(gè)體最優(yōu)及全局最優(yōu)的時(shí)間復(fù)雜度為O(N×D)；（4）自適應(yīng)調(diào)整粒子的慣性權(quán)重與學(xué)習(xí)因子，時(shí)間復(fù)雜度均為O(N×D)；（5）計(jì)算粒子的進(jìn)化能力，選出需要重構(gòu)的粒子進(jìn)行粒子重構(gòu)，時(shí)間復(fù)雜度為O(N×D)；（6）判斷迭代是否停止的時(shí)間復(fù)雜度為O(1)。因此，IAP-PSO 算法的時(shí)間復(fù)雜度為O(N×D)。

6 實(shí)驗(yàn)分析與結(jié)果

6.1 算法的多樣性分析

粒子群算法易陷入局部最優(yōu)點(diǎn)的主要原因就是種群在迭代后期種群多樣性下降。以函數(shù)Schwefel為例，將IAP-PSO、PSO 算法進(jìn)行多樣性對(duì)比。圖1為兩個(gè)算法在迭代初期進(jìn)行初始化時(shí)的種群分布圖，圖2 為迭代后期兩個(gè)算法迭代到全局最優(yōu)值為3 000 左右（算法還未收斂）時(shí)的種群分布圖。

由圖1 可知兩算法在迭代初期粒子分布都較為均勻。從圖2 中可以看出，兩種算法迭代到后期時(shí)，IAP-PSO 算法仍保持著較高的多樣性，粒子分布均勻，具有強(qiáng)的進(jìn)化能力。而PSO 算法的多樣性明顯劣于IAP-PSO 算法，已呈現(xiàn)出聚集狀態(tài)。

6.2 測(cè)試函數(shù)

對(duì)CEC2013 標(biāo)準(zhǔn)測(cè)試函數(shù)集中的10 個(gè)基準(zhǔn)函數(shù)進(jìn)行仿真實(shí)驗(yàn)，用于測(cè)試IAP-PSO 算法的性能，測(cè)試函數(shù)的具體信息如表1 所示。

Fig.1 Initial population distribution圖1 初始種群分布

Fig.2 Population distribution in later stages圖2 后期種群分布

Table 1 10 test functions used in experiment表1 實(shí)驗(yàn)中使用的10 個(gè)測(cè)試函數(shù)

6.3 對(duì)比算法

為了驗(yàn)證IAP-PSO 算法在求解復(fù)雜問(wèn)題時(shí)的性能，將IAP-PSO 算法與動(dòng)態(tài)調(diào)整慣性權(quán)重的粒子群算法（particle swarm optimization algorithm for dynamic adjustment of inertia weight，DIW-PSO）[7]、綜合學(xué)習(xí)粒子群算法（comprehensive learning particle swarm optimiser，CLPSO）[11]、自調(diào)整粒子群算法（self regulating particle swarm optimization algorithm，SRPSO）[12]及標(biāo)準(zhǔn)PSO[13]進(jìn)行對(duì)比實(shí)驗(yàn)。為了保證測(cè)試的公平性，算法的參數(shù)設(shè)置均相同：種群規(guī)模為40，迭代次數(shù)為1 000，分別在D=10、30、50 時(shí)獨(dú)立運(yùn)行30次。實(shí)驗(yàn)環(huán)境為：Intel i5 CPU 2.50 GHz，RAM 4 GB，Windows 7操作系統(tǒng)，Matlab R2016a。

6.4 算法性能測(cè)試的實(shí)驗(yàn)結(jié)果與分析

表2～表4 分別是D=10,30,50 時(shí)PSO、CLPSO、SRPSO、DIW-PSO 與IAP-PSO 算法在測(cè)試函數(shù)上的結(jié)果，其中包括最優(yōu)解、最差解、平均值和標(biāo)準(zhǔn)偏差。借鑒文獻(xiàn)[15]的數(shù)據(jù)統(tǒng)計(jì)與分析方法，采用顯著性水平為0.05 的Wilcoxon 秩檢驗(yàn)方法來(lái)判斷算法性能。其中“+”“-”“～”分別表示IAP-PSO 算法的結(jié)果優(yōu)于、劣于、相當(dāng)于對(duì)應(yīng)算法的測(cè)試結(jié)果。

從表2～表4 結(jié)果中得出，與其他算法相比，IAPPSO無(wú)論在低維還是高維，均能在單峰函數(shù)、多峰函數(shù)和組合函數(shù)中找到更好的結(jié)果。從表5的Wilcoxon結(jié)果來(lái)看，在α=0.05 時(shí)IAP-PSO 算法在測(cè)試函數(shù)上相較于對(duì)比算法均獲得了明顯的優(yōu)勢(shì)。值得說(shuō)明的是，相較其他算法IAP-PSO 算法在求解高維問(wèn)題時(shí)具有突出優(yōu)勢(shì)。此外，在圖3～圖8 中分別展示了算法在部分函數(shù)上收斂情況，從圖中可以清晰地觀察出IAP-PSO 算法在收斂速度與收斂精度上均具有顯著優(yōu)勢(shì)。雖然IAP-PSO 算法自身也存在不足，當(dāng)維數(shù)增加時(shí)，算法的穩(wěn)定性相比其他算法略顯不足，但總的來(lái)說(shuō)，IAP-PSO 算法與其他算法相比，在優(yōu)化結(jié)果上都大有提升。

6.5 算法運(yùn)行時(shí)間對(duì)比

為進(jìn)一步說(shuō)明IAP-PSO 算法在尋優(yōu)速度上的優(yōu)勢(shì)，使算法在相同的實(shí)驗(yàn)環(huán)境下獨(dú)立運(yùn)行20 次，粒子數(shù)均為40，記錄算法達(dá)到指定收斂精度時(shí)的運(yùn)行時(shí)間。如果迭代到200 000 次后仍達(dá)不到要求的精度，則用“—”表示，如表6 所示。

Table 2 Optimized results of comparison algorithms on test functions(D=10)表2 對(duì)比算法對(duì)測(cè)試函數(shù)的優(yōu)化結(jié)果（D=10）

Table 3 Optimized results of comparison algorithms on test functions(D=30)表3 對(duì)比算法對(duì)測(cè)試函數(shù)的優(yōu)化結(jié)果（D=30)

Table 4 Optimized results of comparison algorithms on test functions(D=50)表4 對(duì)比算法對(duì)測(cè)試函數(shù)的優(yōu)化結(jié)果(D=50）

Table 5 Results obtained by Wilcoxon test表5 通過(guò)Wilcoxon 的測(cè)試得到結(jié)果

Table 6 Running time of algorithm to achieve specified accuracy表6 算法達(dá)到指定精度的運(yùn)行時(shí)間 s

Fig.3 Convergence curve of f1（D=30）圖3 函數(shù)f1的收斂曲線（D=30）

Fig.4 Convergence curve of f1（D=50）圖4 函數(shù)f1的收斂曲線（D=50）

Fig.5 Convergence curve of f6（D=30）圖5 函數(shù)f6的收斂曲線（D=30）

Fig.6 Convergence curve of f6（D=50）圖6 函數(shù)f6的收斂曲線（D=50）

Fig.7 Convergence curve of f10（D=30）圖7 函數(shù)f10的收斂曲線（D=30）

Fig.8 Convergence curve of f10（D=50）圖8 函數(shù)f10的收斂曲線（D=50）

由表6 知，在實(shí)驗(yàn)環(huán)境相同的情況下，IAP-PSO算法達(dá)到指定精度要求時(shí)所運(yùn)行的時(shí)間要比標(biāo)準(zhǔn)粒子群算法及其改進(jìn)算法的運(yùn)行時(shí)間更優(yōu)，從運(yùn)行時(shí)間方面再次驗(yàn)證了IAP-PSO 算法的有效性。

7 結(jié)束語(yǔ)

為更好地達(dá)到粒子群算法局部搜索與全局搜索之間的平衡，本文提出獨(dú)立自適應(yīng)調(diào)整參數(shù)的粒子群算法。算法利用粒子進(jìn)化能力與種群進(jìn)化能力的不同，自適應(yīng)地調(diào)整每個(gè)粒子的慣性權(quán)重和學(xué)習(xí)因子。算法中還加入粒子重構(gòu)策略，使每一代粒子中進(jìn)化能力較弱的粒子向進(jìn)化能力較強(qiáng)的粒子進(jìn)行學(xué)習(xí)，并重新構(gòu)造出新粒子，這既增加了種群的多樣性，也提高了算法的收斂性能。實(shí)驗(yàn)結(jié)果表明，在解決高維復(fù)雜問(wèn)題時(shí)該算法在收斂速度與收斂精度上都有明顯的優(yōu)勢(shì)。在部分測(cè)試函數(shù)中IAP-PSO 算法的穩(wěn)定性有待提高，并且算法應(yīng)在實(shí)際應(yīng)用問(wèn)題中驗(yàn)證其有效性，以上問(wèn)題將是下一步研究的主要內(nèi)容。