楊博雯，錢偉懿

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

0 引言

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

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

在粒子群算法中，每個粒子看作D維空間中的一個點，即表示優(yōu)化問題的一個解.設(shè)t時刻粒子i的位置和速度分別為表示粒子i在t時刻所經(jīng)歷的歷史最好位置表示群體在t時刻所經(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}，其中每個權(quán)重在解決某些問題上具有較好的表現(xiàn).對某一個當(dāng)前慣性權(quán)重ω∈W，若算法進(jìn)化較好，我們?nèi)允褂卯?dāng)前慣性權(quán)重，否則，從集合Wω中隨機(jī)選取一個慣性權(quán)重作為當(dāng)前的慣性權(quán)重，為了評價算法進(jìn)化的程度，對于極小優(yōu)化問題，我們定義算法的K步進(jìn)化度如下：

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

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

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

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

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

6）若tmodK=0，則計算算法進(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ù)值實驗

3.1 測試函數(shù)

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

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

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

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

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

從常值慣性權(quán)重，隨機(jī)慣性權(quán)重，時變慣性權(quán)重，混沌慣性權(quán)重和自適應(yīng)慣性權(quán)重5個類型中選取12個慣性權(quán)重，分別是具有常值慣性權(quán)重CONSTANT［2］算法，隨機(jī)慣性權(quán)重RAND［3］算法，時變慣性權(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］算法.對這12個算法取c1=c2=2，除了算法CONSTANT，RAND，RANDCHAOTIC和SSRDIW2外，取ωmax=0.9，ωmin=0.4，此外，CONSTANT算法取ω=0.7298，所有算法取最大迭代步T=1000，群體規(guī)模取N=50，所有算法的程序都是由MATLAB2007實現(xiàn)，且每個實驗獨立運行30次，平均適應(yīng)值的實驗結(jié)果見表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)計檢驗確定一種群智能優(yōu)化算法是否優(yōu)于其他算法的方法.本文用該方法選取求解單峰函數(shù)優(yōu)化問題和多峰函數(shù)優(yōu)化問題的較好算法，我們把12個算法得到的平均適應(yīng)值與真實最優(yōu)解誤差作為樣本，采用Friedman非參數(shù)檢驗方法進(jìn)行綜合比較分析，結(jié)果見表5和表6.

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

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

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

3.3 實驗結(jié)果比較

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

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

從表7和表8可以看出，對于“平均目標(biāo)函數(shù)值”來說，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，但是對于“最差目標(biāo)函數(shù)值”來說，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，但是對于“最好目標(biāo)函數(shù)值”來說，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個測試函數(shù)上尋優(yōu)能力都優(yōu)于SUGENO，在函數(shù)F6上與SUGENO有相同的尋優(yōu)能力.總之，IPSO具有較好的尋優(yōu)能力，也充分說明IPSO整合5種算法的有效性.

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

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

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

表9 測試函數(shù)的Wilcoxon符號秩檢驗結(jié)果

表10 測試函數(shù)的Friedman檢驗結(jié)果

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

為了更清楚且直觀地比較各種算法的收斂性，我們分別從高維單峰函數(shù)和高維多峰函數(shù)中各選取三個函數(shù)進(jìn)行收斂曲線分析，圖1-圖3分別表示測試函數(shù)F1，F(xiàn)3和F7的收斂曲線，圖4-圖6分別表示測試函數(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中可以看出，對于函數(shù)F1，SSRDIW2求解精度最好，EXP1與IPSO求解精度相差不大僅次于SSRDIW2，但是SSRDIW2對于函數(shù)F9，F(xiàn)10和F13求解精度不好.對于函數(shù)F3，AIWPSO求解精度最好，IPSO僅次于AIWPSO和EXP1，但是AIWPSO對于函數(shù)F1和F9求解精度較差.對于函數(shù)F7，EXP1求解精度較好，IPSO次之，但是EXP1對于函數(shù)F10和F13求解精度較差.對于函數(shù)F9，CHAOTIC求解精度相對最好，IPSO次之，但是CHAOTIC對于函數(shù)F1，F(xiàn)3和F7求解精度不好.對于函數(shù)F10和F13，IPSO求解精度最好，優(yōu)于其他比較算法.總之，雖然某一算法對某一問題解決較好，但是對于其他一些問題解決不好，相對其他比較算法，IPSO對所有問題能夠得到最好或較好的結(jié)果，這說明IPSO在解決問題時能夠利用某些算法的優(yōu)點，同時克服某些算法的缺點，從而得到比較滿意的結(jié)果，這正是本文所提出算法的宗旨.

4 結(jié)論

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