具有自適應(yīng)行為的粒子群算法研究

丁知平，劉 超，牛培峰

（1.清遠(yuǎn)職業(yè)技術(shù)學(xué)院 信息技術(shù)與創(chuàng)意設(shè)計(jì)學(xué)院，廣東 清遠(yuǎn) 511510；2.貴州航天電器股份有限公司，貴陽 550009；3.燕山大學(xué) 工業(yè)計(jì)算機(jī)控制工程河北省重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004）

0 引言

近年來，越來越多的啟發(fā)式智能算法被應(yīng)用于解決復(fù)雜高維數(shù)值函數(shù)優(yōu)化問題[1]。PSO（particle swarm optimization，PSO）算法是由Kennedy等受鳥群覓食行為啟發(fā)而提出的一種基于種群的仿生類智能優(yōu)化算法[2,3]，PSO算法中每一個(gè)粒子代表一個(gè)可行的解決方案，食物源的位置就是全局最優(yōu)的位置點(diǎn)。PSO具有搜索多樣性強(qiáng)、操作簡單和調(diào)節(jié)參數(shù)少等優(yōu)點(diǎn)，一經(jīng)提出就得到廣泛應(yīng)用[4]。針對(duì)復(fù)雜優(yōu)化問題的求解，PSO算法易陷入局部最小值，收斂精度較低等不足[5]。

為了更好平衡PSO算法的全局探索能力和局部開采能力，提高算法的收斂速度和收斂精度，本文提出了一種基于自適應(yīng)慣性權(quán)重的粒子群算法（AIW-PSO），該算法能夠有效平衡原粒子位置和飛行速度對(duì)新粒子位置的影響。仿真實(shí)驗(yàn)表明，AIW-PSO算法具有較高的收斂精度和收斂速度。

1 基本的粒子群算法(PSO)

PSO算法基本思路是對(duì)飛鳥的捕食過程進(jìn)行模擬，每個(gè)粒子在解空間中進(jìn)行運(yùn)動(dòng)，記錄各個(gè)粒子搜索到的最優(yōu)點(diǎn)和所有粒子搜索到的全局最優(yōu)點(diǎn)，粒子根據(jù)自身最優(yōu)點(diǎn)及全局最優(yōu)點(diǎn)不斷地更新自己的速度和位置。

假設(shè)在D維搜索空間中，粒子群的種群大小為N，第i個(gè)粒子的位置為飛行的速度為vi=[vi1，vi2，…，viD]。在進(jìn)行第t次迭代時(shí)，粒子自身的歷史最優(yōu)位置為pbest，全局粒子最優(yōu)位置為gbest。則粒子飛行速度和位置更新的計(jì)算公式表述如下：

2 基于自適應(yīng)慣性權(quán)重的粒子群算法

為了提高PSO算法的全局尋優(yōu)能力和搜索精度，本文在原始PSO算法的基礎(chǔ)上提出了一種基于自適應(yīng)慣性權(quán)重的粒子群算法(AIW-PSO)。具體描述如下：

PSO算法全局探索能力和局部開采能力相互矛盾，不易找到平衡點(diǎn)，為了有效地改善算法的優(yōu)化能力，在粒子位置更新公式（2）的基礎(chǔ)上引入了兩個(gè)自適應(yīng)慣性權(quán)重wj和w'j。其中，wj用于控制原粒子位置對(duì)新粒子位置的影響度，w'j用于平衡粒子飛行速度對(duì)新位置的影響權(quán)重。改進(jìn)后的粒子位置更新公式表述如下：

式中，wj和w'j既能保持粒子種群的多樣性，又能增強(qiáng)算法尋優(yōu)過程中跳出局部最優(yōu)的能力。

wj和w'j的數(shù)學(xué)表達(dá)式如下：式中，f(j)表示第j個(gè)粒子的適應(yīng)度值，u表示在第一次迭代計(jì)算中粒子種群中最佳的適應(yīng)度值，iter表示當(dāng)前的迭代次數(shù)。

AIW-PSO算法搜索的具體步驟如下：

步驟1：對(duì)粒子群的初始位置進(jìn)行初始化，并對(duì)種群規(guī)模N，學(xué)習(xí)因子c1和c2，最大迭代次數(shù)M，初始飛行速度v和維數(shù)D等參數(shù)進(jìn)行設(shè)置；

步驟2：計(jì)算每個(gè)粒子的適應(yīng)度值，并找出初始全局最優(yōu)gbest和個(gè)體最優(yōu)pbest；

步驟3：用公式（1）更新粒子的飛行速度v；

步驟4：用公式（4）和公式（5）更新自適應(yīng)慣性權(quán)重wj和w'j；

步驟5：用公式（3）更新粒子的位置；

步驟6：計(jì)算新產(chǎn)生位置的適應(yīng)度值，更新全局最優(yōu)gbest和個(gè)體最優(yōu)pbest，重復(fù)步驟3至步驟6，直到達(dá)到最大迭代次數(shù)M，算法尋優(yōu)結(jié)束；

步驟7：輸出最優(yōu)粒子個(gè)體，即算法找到的最優(yōu)解。

3 數(shù)值實(shí)驗(yàn)與分析

為了更好地評(píng)價(jià)AIW-PSO算法的可行性和有效性，將AIW-PSO算法與生物地理優(yōu)化算法（BBO）[6]磷蝦群算法（KH）[7]、原始PSO算法及其它PSO改進(jìn)算法進(jìn)行比較，并分析實(shí)驗(yàn)結(jié)果。

3.1 測(cè)試函數(shù)與參數(shù)設(shè)定

為了檢驗(yàn)AIW-PSO算法的性能，引入8組基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，所采用的測(cè)試函數(shù)見表1。在表1中，f1至f4為單峰測(cè)試函數(shù)，f5至f8為多峰測(cè)試函數(shù)。f3的理論最優(yōu)位置為[1]n，f4的理論最優(yōu)位置為[-0.5]n，其余6組測(cè)試函數(shù)的理論最優(yōu)位置為[0]n，n表示優(yōu)化問題的維數(shù)，f1至f8的理論最優(yōu)值均為0。

表1 基準(zhǔn)測(cè)試函數(shù)

實(shí)驗(yàn)中設(shè)置PSO和AIW-PSO算法的學(xué)習(xí)因子c1=c2=2；BBO算法的突變概率Mu=0.005；KH算法的最大感應(yīng)速度Nmax=0.01m/s，覓食速度Vf=0.02m/s，最大擴(kuò)散速度Dmax=0.005m/s。為了比較的統(tǒng)一，四種算法的種群規(guī)模N=40，最大迭代次數(shù)M=500。算法在每組測(cè)試函數(shù)上獨(dú)立運(yùn)行20次，并對(duì)20次運(yùn)行的平均值和均方差進(jìn)行記錄，標(biāo)黑部分表示最好結(jié)果。所有的仿真實(shí)驗(yàn)均在Windows XP系統(tǒng)上使用Matlab 2009a進(jìn)行。

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

表2為四種算法對(duì)8組基準(zhǔn)測(cè)試函數(shù)尋優(yōu)的結(jié)果統(tǒng)計(jì)，表中分別給出了算法在30維和50維問題上的搜索精度和穩(wěn)定性測(cè)試，即20次獨(dú)立運(yùn)行的平均值和均方差。

表2 四種算法對(duì)基準(zhǔn)測(cè)試函數(shù)的運(yùn)行結(jié)果

從表2中可以看出，無論是對(duì)于單峰測(cè)試函數(shù)，還是多峰測(cè)試函數(shù)，本文提出的AIW-PSO算法在30維和50維問題上均表現(xiàn)出了較好的搜索性能。相比于BBO算法，AIW-PSO算法在8組測(cè)試函數(shù)上的尋優(yōu)精度和穩(wěn)定性均更好；相比于KH算法，AIW-PSO算法除去f3在30維的情況下，對(duì)其他情況下的測(cè)試函數(shù)均表現(xiàn)出了較高的搜索效果；相比于原始的PSO算法，AIW-PSO算法的搜索性能得到了很大的提高，有些甚至能優(yōu)化到最優(yōu)值或接近理論最優(yōu)值。綜上所述，本文提出的AIW-PSO算法引入自適應(yīng)慣性權(quán)重，能夠有效的提高PSO算法的全局搜索精度和跳出局部最優(yōu)的能力。

3.3 收斂性能曲線分析

圖1 四種算法對(duì)f2(30維)的尋優(yōu)曲線

圖1和圖2（見下頁）是BBO、KH、PSO和AIW-PSO算法分別在30維和50維問題上的部分尋優(yōu)曲線，實(shí)驗(yàn)中得到的其他尋優(yōu)曲線與給出的部分類似，因篇幅有限此處不再給出。

圖2 四種算法對(duì)f8(50維)的尋優(yōu)曲線

從圖1中可以看出，AIW-PSO算法對(duì)f2函數(shù)在30維進(jìn)行尋優(yōu)時(shí)，有多處拐點(diǎn)出現(xiàn)，證明其跳出局部最優(yōu)的能力得到了有效增強(qiáng)；進(jìn)一步也可以觀察到AIW-PSO算法收斂速度較其他三種算法更快，收斂精度也有一定的提高。對(duì)圖2進(jìn)行分析，對(duì)于f8函數(shù)（50維），AIW-PSO算法的收斂精度得到了一定幅度的提高，且尋優(yōu)過程較平穩(wěn)，穩(wěn)定性更好。綜上所述，AIW-PSO算法對(duì)多維復(fù)雜優(yōu)化問題尋優(yōu)時(shí)，相比于其他三種算法全局尋優(yōu)能力得到了有效改善且穩(wěn)定性較強(qiáng)。

3.4 AIW-PSO算法與其它改進(jìn)PSO算法實(shí)驗(yàn)

為了進(jìn)一步評(píng)價(jià)AIW-PSO算法的優(yōu)化能力，將AIW-PSO 與 CLPSO、HPSO-TVAC[8]、LPSO、DMS-PSO[9]和LFPSO進(jìn)行比較。具體實(shí)驗(yàn)參數(shù)設(shè)定與上文相同，算法均獨(dú)立運(yùn)行20次。表3給出了8組測(cè)試函數(shù)在30維問題上的實(shí)驗(yàn)結(jié)果，其中，CLPSO、HPSO-TVAC、LPSO、DMS-PSO和LFPSO的實(shí)驗(yàn)數(shù)據(jù)來自于文獻(xiàn)[10]。

表3 AIW-PSO算法與其他相關(guān)算法的實(shí)驗(yàn)結(jié)果對(duì)比

從表3中可以看出，AIW-PSO、CLPSO、HPSO-TVAC、LFPSO算法找到最優(yōu)解個(gè)數(shù)分別為 5、1、1、1，LPSO 和DMS-PSO找到的最優(yōu)個(gè)數(shù)為0，且對(duì)于f5和f7函數(shù)，AIW-PSO算法直接搜索到了理論最優(yōu)值，對(duì)于f1、f4和f6函數(shù)，AIW-PSO算法搜索的結(jié)果無限接近最優(yōu)值。實(shí)驗(yàn)結(jié)果表明，AIW-PSO算法的搜索性能更優(yōu)，特別是對(duì)于多峰函數(shù)具有較高的尋優(yōu)能力和穩(wěn)定性。綜上所述，自適應(yīng)行為的慣性權(quán)值的引入，改善了PSO算法的性能。AIW-PSO算法能夠有效解決高維復(fù)雜數(shù)值優(yōu)化問題。

4 結(jié)束語

針對(duì)粒子群算法全局尋優(yōu)能力差和易陷入局部最小值的不足，在原始粒子群算法的基礎(chǔ)上，通過引入自適應(yīng)慣性權(quán)重來平衡原粒子位置和飛行速度對(duì)新粒子位置的影響度。數(shù)值函數(shù)仿真實(shí)驗(yàn)表明，AIW-PSO算法無論是對(duì)于單峰測(cè)試函數(shù)，還是多峰測(cè)試函數(shù)，均表現(xiàn)出了較強(qiáng)的全局尋優(yōu)能力和跳出局部最優(yōu)的能力，且搜索精度也得到了較大的提升，進(jìn)一步驗(yàn)證了AIW-PSO算法的有效性。