楊博雯，錢偉懿

（渤海大學 數學科學學院，遼寧 錦州121013）

0 引言

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

1 標準PSO算法

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

其中ω是慣性權重，c1和c2為加速度因子，r1和r2是［0，1］內的均勻隨機數.

2 改進的PSO算法

設慣性權重集W={ω1，ω2，…，ωs}，其中每個權重在解決某些問題上具有較好的表現.對某一個當前慣性權重ω∈W，若算法進化較好，我們仍使用當前慣性權重，否則，從集合Wω中隨機選取一個慣性權重作為當前的慣性權重，為了評價算法進化的程度，對于極小優(yōu)化問題，我們定義算法的K步進化度如下：

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

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

3）從慣性權重集合W=｛ω1，ω2，…，ωs｝中隨機選取一個當前慣性權重ω；

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

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

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

7）若t＞T，則停，否則令t=t+1，轉4）.

3 數值實驗

3.1 測試函數

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

表1 單峰測試函數

表2 多峰測試函數

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

3.2 權重集的選取

從常值慣性權重，隨機慣性權重，時變慣性權重，混沌慣性權重和自適應慣性權重5個類型中選取12個慣性權重，分別是具有常值慣性權重CONSTANT［2］算法，隨機慣性權重RAND［3］算法，時變慣性權重EXP1［6］算法，EXP2［6］算法，LDIW［5］算法和SUGENO［7］算法，混沌慣性權重CHAOTIC［10］算法和RANDCHAOTIC［10］算法，自適應慣性權重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實現，且每個實驗獨立運行30次，平均適應值的實驗結果見表3和表4.

表3 AIWPSO，CHAOTIC，CONSTANT，DAPSO，EXP1和EXP2獲得的平均目標函數值

表4 LDIW，RAND，RANDCHAOTIC，SSRDIW1，SSRDIW2和SUGENO獲得的平均目標函數值

表4續(xù)

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

表5 單峰函數的Friedman檢驗結果

表6 多峰函數的Friedman檢驗結果

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

3.3 實驗結果比較

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

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

從表7和表8可以看出，對于“平均目標函數值”來說，IPSO與AIWPSO相比，IPSO在函數F1，F2，F5，F7，F8，F9，F10，F11，F12，F13上比AIWPSO尋優(yōu)性能好，在函數F6上與AIWPSO性能相同，在函數F3，F4上不如AIWPSO，但是對于“最差目標函數值”來說，IPSO優(yōu)于AIWPSO；IPSO與CHAOTIC相比，IPSO在函數F1，F2，F3，F4，F5，F7，F10，F11，F13上優(yōu)于CHAOTIC，在函數F6上與CHAOTIC有相同尋優(yōu)性能，在函數F8，F9，F12上劣于CHAOTIC，但是對于“最好目標函數值”來說，IPSO在函數F12上優(yōu)于CHAOTIC；IPSO與EXP1相比，IPSO在函數F2，F5，F8，F9，F10，F11，F13上優(yōu)于EXP1，在函數F6上與EXP1有相同尋優(yōu)性能，在函數F1，F3，F4，F7，F12上比EXP1尋優(yōu)性能差，但是IPSO在函數F1上也能夠尋找到較好的最優(yōu)解，在F7上與EXP1尋優(yōu)能力幾乎相同；IPSO與SSRDIW2相比，IPSO在函數F3，F4，F5，F7，F8，F9，F10，F11，F12，F13上的尋優(yōu)能力優(yōu)于SSRDIW2，在函數F6上與SSRDIW2尋優(yōu)能力相同，在函數F1，F2上劣于SSRDIW2，但是IPSO在函數F1，F2上也能夠尋找到較好的最優(yōu)解；IPSO與SUGENO相比，除了函數F6外，IPSO在其余的12個測試函數上尋優(yōu)能力都優(yōu)于SUGENO，在函數F6上與SUGENO有相同的尋優(yōu)能力.總之，IPSO具有較好的尋優(yōu)能力，也充分說明IPSO整合5種算法的有效性.

表7 AIWPSO，CHAOTIC，EXP1，SSRDIW2，SUGENO和IPSO對單峰函數實驗結果

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

表8 AIWPSO,CHAOTIC,EXP1,SSRDIW2,SUGENO和IPSO對多峰函數實驗結果

表9 測試函數的Wilcoxon符號秩檢驗結果

表10 測試函數的Friedman檢驗結果

從表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)于其他比較算法.

為了更清楚且直觀地比較各種算法的收斂性，我們分別從高維單峰函數和高維多峰函數中各選取三個函數進行收斂曲線分析，圖1-圖3分別表示測試函數F1，F3和F7的收斂曲線，圖4-圖6分別表示測試函數F9，F10和F13的收斂曲線.

圖1 函數F1的收斂曲線

圖2 函數F3的收斂曲線

圖3 函數F7的收斂曲線

圖4 函數F9的收斂曲線

圖5 函數F10的收斂曲線

圖6 函數F13的收斂曲線

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

4 結論

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