多慣性權(quán)重的自適應(yīng)粒子群優(yōu)化算法

楊博雯，錢(qián)偉懿

（渤海大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 錦州121013）

0 引言

粒子群算法（particle swarm optimization，PSO）是由Eberhart和Kennedy于1995年提出的一種群智能優(yōu)化算法［1］.由于PSO算法具有操作簡(jiǎn)單，參數(shù)少，易于實(shí)現(xiàn)等特點(diǎn)，因而自從PSO提出后得到了許多學(xué)者的認(rèn)可，并得到迅速地發(fā)展.PSO算法中的一個(gè)重要參數(shù)就是慣性權(quán)重，其關(guān)鍵作用能夠平衡PSO算法局部搜索和全局搜索能力，從而能夠提高PSO的尋優(yōu)性能，因此許多學(xué)者對(duì)PSO算法的慣性權(quán)重進(jìn)行了廣泛研究.目前關(guān)于PSO算法的慣性權(quán)重的研究主要集中如下四個(gè)方面：（1）常值和隨機(jī)的慣性權(quán)重［2-4］，（2）時(shí)變慣性權(quán)重［5-9］，（3）混沌慣性權(quán)重［10-11］，（4）自適應(yīng)慣性權(quán)重［12-15］.雖然不同形式的慣性權(quán)重在一定程度上能夠提高PSO算法的性能，但是根據(jù)“沒(méi)有免費(fèi)午餐”定理［16］，任何一種帶有慣性權(quán)重的PSO算法不能對(duì)所有問(wèn)題都有效，本文的思想是：如何合理選用慣性權(quán)重使得算法對(duì)更多的優(yōu)化問(wèn)題有效.本文提出一種多個(gè)慣性權(quán)重的自適應(yīng)PSO算法，首先我們定義一個(gè)算法K步進(jìn)化度的概念，選取一些已知的慣性權(quán)重構(gòu)成慣性權(quán)重集，從慣性權(quán)重集中隨機(jī)選取一個(gè)慣性權(quán)重作為當(dāng)前的慣性權(quán)重，當(dāng)算法進(jìn)化度不高時(shí)更換當(dāng)前的慣性權(quán)重，使得適合解決某一問(wèn)題的慣性權(quán)重能夠被多次使用，從而提高算法解決該問(wèn)題的性能.最后把本文所提出的算法應(yīng)用到典型的測(cè)試問(wèn)題中，并與其他算法進(jìn)行比較分析，另外采用了Wilcoxon符號(hào)秩檢驗(yàn)和Friedman檢驗(yàn)兩個(gè)非參數(shù)檢驗(yàn)對(duì)算法的性能進(jìn)行了分析.結(jié)果表明所提出的算法是有效的.

1 標(biāo)準(zhǔn)PSO算法

在粒子群算法中，每個(gè)粒子看作D維空間中的一個(gè)點(diǎn)，即表示優(yōu)化問(wèn)題的一個(gè)解.設(shè)t時(shí)刻粒子i的位置和速度分別為表示粒子i在t時(shí)刻所經(jīng)歷的歷史最好位置表示群體在t時(shí)刻所經(jīng)歷的歷史最好位置.粒子i的位置和速度更新公式為：

其中ω是慣性權(quán)重，c1和c2為加速度因子，r1和r2是［0，1］內(nèi)的均勻隨機(jī)數(shù).

2 改進(jìn)的PSO算法

設(shè)慣性權(quán)重集W={ω1，ω2，…，ωs}，其中每個(gè)權(quán)重在解決某些問(wèn)題上具有較好的表現(xiàn).對(duì)某一個(gè)當(dāng)前慣性權(quán)重ω∈W，若算法進(jìn)化較好，我們?nèi)允褂卯?dāng)前慣性權(quán)重，否則，從集合Wω中隨機(jī)選取一個(gè)慣性權(quán)重作為當(dāng)前的慣性權(quán)重，為了評(píng)價(jià)算法進(jìn)化的程度，對(duì)于極小優(yōu)化問(wèn)題，我們定義算法的K步進(jìn)化度如下：

其中fit(·)表示適應(yīng)值函數(shù)，為了使f it(·)＞0，本文取f it(x)=F(x)-a，F(xiàn)(x)為優(yōu)化問(wèn)題的目標(biāo)函數(shù)，而a為優(yōu)化問(wèn)題允許的最小值.對(duì)任意所以由式（3）看出，r(t)∈[0，1)，且r(t)越大表明算法進(jìn)化的越好，r(t)越小表明算法進(jìn)化的越差，特別當(dāng)r(t)=0時(shí)，全局最優(yōu)位置沒(méi)有改善，為此，當(dāng)r（t）＜c（c為閾值）時(shí)，更新當(dāng)前慣性權(quán)重，否則保留當(dāng)前慣性權(quán)重.基于上述思想，我們給出多個(gè)慣性權(quán)重自適應(yīng)粒子群優(yōu)化算法，算法過(guò)程如下：

1）初始化：設(shè)群體規(guī)模N，最大迭代步為T(mén)，給出加速度因子c1、c2，閾值c及常數(shù)K，選擇慣性權(quán)重集合W=｛ω1，ω2，…，ωs｝，隨機(jī)初始化粒子的初始位置和初始速度

3）從慣性權(quán)重集合W=｛ω1，ω2，…，ωs｝中隨機(jī)選取一個(gè)當(dāng)前慣性權(quán)重ω；

4）按式（1）和（2）更新每個(gè)粒子的速度和位置；

5）計(jì)算每個(gè)粒子的適應(yīng)值，并更新每個(gè)粒子的歷史最優(yōu)位置和全局最優(yōu)位置，得

6）若tmodK=0，則計(jì)算算法進(jìn)化度r(t+1)，若r(t+1)＜c，則從慣性權(quán)重集合Wω中隨機(jī)選取當(dāng)前慣性權(quán)重ω，否則當(dāng)前慣性權(quán)重不更新；

7）若t＞T，則停，否則令t=t+1，轉(zhuǎn)4）.

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

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

為了評(píng)價(jià)本文算法（記為IPSO）的性能，我們從文獻(xiàn)［17］中選取13個(gè)高維測(cè)試函數(shù)，具體如下：

表1 單峰測(cè)試函數(shù)

表2 多峰測(cè)試函數(shù)

表1中F1～F7為高維單峰函數(shù)，表2中F8～F13為高維多峰函數(shù)，本文選取的13個(gè)函數(shù)維數(shù)D=30.

3.2 權(quán)重集的選取

從常值慣性權(quán)重，隨機(jī)慣性權(quán)重，時(shí)變慣性權(quán)重，混沌慣性權(quán)重和自適應(yīng)慣性權(quán)重5個(gè)類(lèi)型中選取12個(gè)慣性權(quán)重，分別是具有常值慣性權(quán)重CONSTANT［2］算法，隨機(jī)慣性權(quán)重RAND［3］算法，時(shí)變慣性權(quán)重EXP1［6］算法，EXP2［6］算法，LDIW［5］算法和SUGENO［7］算法，混沌慣性權(quán)重CHAOTIC［10］算法和RANDCHAOTIC［10］算法，自適應(yīng)慣性權(quán)重AIWPSO［12］算法，DAPSO［13］算法，SSRDIW1［14］算法和SSRDIW2［14］算法.對(duì)這12個(gè)算法取c1=c2=2，除了算法CONSTANT，RAND，RANDCHAOTIC和SSRDIW2外，取ωmax=0.9，ωmin=0.4，此外，CONSTANT算法取ω=0.7298，所有算法取最大迭代步T=1000，群體規(guī)模取N=50，所有算法的程序都是由MATLAB2007實(shí)現(xiàn)，且每個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行30次，平均適應(yīng)值的實(shí)驗(yàn)結(jié)果見(jiàn)表3和表4.

表3 AIWPSO，CHAOTIC，CONSTANT，DAPSO，EXP1和EXP2獲得的平均目標(biāo)函數(shù)值

表4 LDIW，RAND，RANDCHAOTIC，SSRDIW1，SSRDIW2和SUGENO獲得的平均目標(biāo)函數(shù)值

表4續(xù)

文［18］提出了用非參數(shù)統(tǒng)計(jì)檢驗(yàn)確定一種群智能優(yōu)化算法是否優(yōu)于其他算法的方法.本文用該方法選取求解單峰函數(shù)優(yōu)化問(wèn)題和多峰函數(shù)優(yōu)化問(wèn)題的較好算法，我們把12個(gè)算法得到的平均適應(yīng)值與真實(shí)最優(yōu)解誤差作為樣本，采用Friedman非參數(shù)檢驗(yàn)方法進(jìn)行綜合比較分析，結(jié)果見(jiàn)表5和表6.

表5 單峰函數(shù)的Friedman檢驗(yàn)結(jié)果

表6 多峰函數(shù)的Friedman檢驗(yàn)結(jié)果

從表5和表6可以看出，P-值幾乎等于0，表明12種算法在顯著水平0.05下求解單峰函數(shù)優(yōu)化問(wèn)題和多峰函數(shù)優(yōu)化問(wèn)題存在顯著差異.由于本文求極小問(wèn)題，所以平均秩越小表明算法尋優(yōu)能力越強(qiáng).由表5可知，求解單峰函數(shù)優(yōu)化問(wèn)題較好的前3個(gè)算法是：EXP1，AIWPSO，SSRDIW2，由表6可知，求解多峰函數(shù)優(yōu)化問(wèn)題較好的前3個(gè)算法是：CHAOTIC，AIWPSO，SUGENO，因此本文選取AIWPSO，CHAOTIC，EXP1，SSRDIW2，SUGENO五個(gè)算法的慣性權(quán)重作為本文實(shí)驗(yàn)的慣性權(quán)重集.

3.3 實(shí)驗(yàn)結(jié)果比較

本小節(jié)把IPSO算法與AIWPSO，CHAOTIC，EXP1，SSRDIW2，SUGENO五個(gè)算法進(jìn)行性能比較分析，并用Wilcoxon符號(hào)秩檢驗(yàn)方法進(jìn)行IPSO算法與其他比較算法兩兩統(tǒng)計(jì)分析，用Friedman非參數(shù)檢驗(yàn)方法進(jìn)行所有算法綜合統(tǒng)計(jì)分析.

所有算法的參數(shù)設(shè)置如下：c1=c2=2，ωmax=0.9，ωmin=0.4，取最大迭代步T=2000，群體規(guī)模N=50，IPSO算法中的閾值c=0.1.所有算法的程序都是由MATLAB2007實(shí)現(xiàn)，且每個(gè)算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次，實(shí)驗(yàn)結(jié)果見(jiàn)表7和表8.

從表7和表8可以看出，對(duì)于“平均目標(biāo)函數(shù)值”來(lái)說(shuō)，IPSO與AIWPSO相比，IPSO在函數(shù)F1，F(xiàn)2，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)9，F(xiàn)10，F(xiàn)11，F(xiàn)12，F(xiàn)13上比AIWPSO尋優(yōu)性能好，在函數(shù)F6上與AIWPSO性能相同，在函數(shù)F3，F(xiàn)4上不如AIWPSO，但是對(duì)于“最差目標(biāo)函數(shù)值”來(lái)說(shuō)，IPSO優(yōu)于AIWPSO；IPSO與CHAOTIC相比，IPSO在函數(shù)F1，F(xiàn)2，F(xiàn)3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)10，F(xiàn)11，F(xiàn)13上優(yōu)于CHAOTIC，在函數(shù)F6上與CHAOTIC有相同尋優(yōu)性能，在函數(shù)F8，F(xiàn)9，F(xiàn)12上劣于CHAOTIC，但是對(duì)于“最好目標(biāo)函數(shù)值”來(lái)說(shuō)，IPSO在函數(shù)F12上優(yōu)于CHAOTIC；IPSO與EXP1相比，IPSO在函數(shù)F2，F(xiàn)5，F(xiàn)8，F(xiàn)9，F(xiàn)10，F(xiàn)11，F(xiàn)13上優(yōu)于EXP1，在函數(shù)F6上與EXP1有相同尋優(yōu)性能，在函數(shù)F1，F(xiàn)3，F(xiàn)4，F(xiàn)7，F(xiàn)12上比EXP1尋優(yōu)性能差，但是IPSO在函數(shù)F1上也能夠?qū)ふ业捷^好的最優(yōu)解，在F7上與EXP1尋優(yōu)能力幾乎相同；IPSO與SSRDIW2相比，IPSO在函數(shù)F3，F(xiàn)4，F(xiàn)5，F(xiàn)7，F(xiàn)8，F(xiàn)9，F(xiàn)10，F(xiàn)11，F(xiàn)12，F(xiàn)13上的尋優(yōu)能力優(yōu)于SSRDIW2，在函數(shù)F6上與SSRDIW2尋優(yōu)能力相同，在函數(shù)F1，F(xiàn)2上劣于SSRDIW2，但是IPSO在函數(shù)F1，F(xiàn)2上也能夠?qū)ふ业捷^好的最優(yōu)解；IPSO與SUGENO相比，除了函數(shù)F6外，IPSO在其余的12個(gè)測(cè)試函數(shù)上尋優(yōu)能力都優(yōu)于SUGENO，在函數(shù)F6上與SUGENO有相同的尋優(yōu)能力.總之，IPSO具有較好的尋優(yōu)能力，也充分說(shuō)明IPSO整合5種算法的有效性.

表7 AIWPSO，CHAOTIC，EXP1，SSRDIW2，SUGENO和IPSO對(duì)單峰函數(shù)實(shí)驗(yàn)結(jié)果

為了評(píng)價(jià)IPSO優(yōu)于其他比較算法的顯著性，我們把表7和表8中的平均目標(biāo)函數(shù)值與真實(shí)的最優(yōu)解的誤差作為樣本，采用Wilcoxon符號(hào)秩檢驗(yàn)和Friedman檢驗(yàn)兩個(gè)非參數(shù)檢驗(yàn)方法［18］討論IPSO的有效性.首先使用Wilcoxon符號(hào)秩檢驗(yàn)比較兩種算法的性能顯著差異，在Wilcoxon符號(hào)秩檢驗(yàn)中，R+表示第一個(gè)算法優(yōu)于第二個(gè)算法秩的和，而R-正好相反，用SPSS軟件得到的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果見(jiàn)表9.然后使用Friedman檢驗(yàn)所有比較算法的性能顯著差異，用SPSS軟件得到的Friedman檢驗(yàn)結(jié)果見(jiàn)表10.

表8 AIWPSO,CHAOTIC,EXP1,SSRDIW2,SUGENO和IPSO對(duì)多峰函數(shù)實(shí)驗(yàn)結(jié)果

表9 測(cè)試函數(shù)的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果

表10 測(cè)試函數(shù)的Friedman檢驗(yàn)結(jié)果

從表9看出，基于Wilcoxon符號(hào)秩檢驗(yàn)，IPSO優(yōu)于其他比較算法，在顯著水平0.05下IPSO顯著優(yōu)于SSRDIW2和SUGENO兩種算法，在顯著水平0.1下，IPSO顯著優(yōu)于AIWPSO，但是IPSO與CHAOTIC和EXP1沒(méi)有顯著差異.從表10看出，基于Friedman檢驗(yàn)，在顯著水平0.05下IPSO顯著優(yōu)于其他比較算法.

為了更清楚且直觀地比較各種算法的收斂性，我們分別從高維單峰函數(shù)和高維多峰函數(shù)中各選取三個(gè)函數(shù)進(jìn)行收斂曲線分析，圖1-圖3分別表示測(cè)試函數(shù)F1，F(xiàn)3和F7的收斂曲線，圖4-圖6分別表示測(cè)試函數(shù)F9，F(xiàn)10和F13的收斂曲線.

圖1 函數(shù)F1的收斂曲線

圖2 函數(shù)F3的收斂曲線

圖3 函數(shù)F7的收斂曲線

圖4 函數(shù)F9的收斂曲線

圖5 函數(shù)F10的收斂曲線

圖6 函數(shù)F13的收斂曲線

從圖1-圖6中可以看出，對(duì)于函數(shù)F1，SSRDIW2求解精度最好，EXP1與IPSO求解精度相差不大僅次于SSRDIW2，但是SSRDIW2對(duì)于函數(shù)F9，F(xiàn)10和F13求解精度不好.對(duì)于函數(shù)F3，AIWPSO求解精度最好，IPSO僅次于AIWPSO和EXP1，但是AIWPSO對(duì)于函數(shù)F1和F9求解精度較差.對(duì)于函數(shù)F7，EXP1求解精度較好，IPSO次之，但是EXP1對(duì)于函數(shù)F10和F13求解精度較差.對(duì)于函數(shù)F9，CHAOTIC求解精度相對(duì)最好，IPSO次之，但是CHAOTIC對(duì)于函數(shù)F1，F(xiàn)3和F7求解精度不好.對(duì)于函數(shù)F10和F13，IPSO求解精度最好，優(yōu)于其他比較算法.總之，雖然某一算法對(duì)某一問(wèn)題解決較好，但是對(duì)于其他一些問(wèn)題解決不好，相對(duì)其他比較算法，IPSO對(duì)所有問(wèn)題能夠得到最好或較好的結(jié)果，這說(shuō)明IPSO在解決問(wèn)題時(shí)能夠利用某些算法的優(yōu)點(diǎn)，同時(shí)克服某些算法的缺點(diǎn)，從而得到比較滿意的結(jié)果，這正是本文所提出算法的宗旨.

4 結(jié)論

本文提出了一種新的自適應(yīng)粒子群優(yōu)化算法，其宗旨試圖從已知的慣性權(quán)重中通過(guò)自適應(yīng)方法選取對(duì)求解某一問(wèn)題較好的慣性權(quán)重來(lái)解決該問(wèn)題，以提高所提出的算法能夠比較好地解決大多數(shù)優(yōu)化問(wèn)題的性能.該算法實(shí)現(xiàn)簡(jiǎn)單，推廣性較強(qiáng).為了對(duì)該算法進(jìn)行評(píng)價(jià)，本文采用兩個(gè)非參數(shù)檢驗(yàn)對(duì)結(jié)果進(jìn)行驗(yàn)證.實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法具有優(yōu)于其他比較算法的顯著性能.但是該算法不足之處在于如果慣性權(quán)重集中的慣性權(quán)重不能解決的問(wèn)題，該算法也不能解決，所以在未來(lái)的工作中，研究新的慣性權(quán)重，并與其他求解某問(wèn)題較好的慣性權(quán)重組合方式來(lái)實(shí)現(xiàn)本文目的.