具有自適應行為的粒子群算法研究

丁知平，劉 超，牛培峰

（1.清遠職業技術學院 信息技術與創意設計學院，廣東 清遠 511510；2.貴州航天電器股份有限公司，貴陽 550009；3.燕山大學 工業計算機控制工程河北省重點實驗室，河北 秦皇島 066004）

0 引言

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

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

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

PSO算法基本思路是對飛鳥的捕食過程進行模擬，每個粒子在解空間中進行運動，記錄各個粒子搜索到的最優點和所有粒子搜索到的全局最優點，粒子根據自身最優點及全局最優點不斷地更新自己的速度和位置。

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

2 基于自適應慣性權重的粒子群算法

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

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

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

wj和w'j的數學表達式如下：式中，f(j)表示第j個粒子的適應度值，u表示在第一次迭代計算中粒子種群中最佳的適應度值，iter表示當前的迭代次數。

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

步驟1：對粒子群的初始位置進行初始化，并對種群規模N，學習因子c1和c2，最大迭代次數M，初始飛行速度v和維數D等參數進行設置；

步驟2：計算每個粒子的適應度值，并找出初始全局最優gbest和個體最優pbest；

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

步驟4：用公式（4）和公式（5）更新自適應慣性權重wj和w'j；

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

步驟6：計算新產生位置的適應度值，更新全局最優gbest和個體最優pbest，重復步驟3至步驟6，直到達到最大迭代次數M，算法尋優結束；

步驟7：輸出最優粒子個體，即算法找到的最優解。

3 數值實驗與分析

為了更好地評價AIW-PSO算法的可行性和有效性，將AIW-PSO算法與生物地理優化算法（BBO）[6]磷蝦群算法（KH）[7]、原始PSO算法及其它PSO改進算法進行比較，并分析實驗結果。

3.1 測試函數與參數設定

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

表1 基準測試函數

實驗中設置PSO和AIW-PSO算法的學習因子c1=c2=2；BBO算法的突變概率Mu=0.005；KH算法的最大感應速度Nmax=0.01m/s，覓食速度Vf=0.02m/s，最大擴散速度Dmax=0.005m/s。為了比較的統一，四種算法的種群規模N=40，最大迭代次數M=500。算法在每組測試函數上獨立運行20次，并對20次運行的平均值和均方差進行記錄，標黑部分表示最好結果。所有的仿真實驗均在Windows XP系統上使用Matlab 2009a進行。

3.2 仿真實驗結果與分析

表2為四種算法對8組基準測試函數尋優的結果統計，表中分別給出了算法在30維和50維問題上的搜索精度和穩定性測試，即20次獨立運行的平均值和均方差。

表2 四種算法對基準測試函數的運行結果

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

3.3 收斂性能曲線分析

圖1 四種算法對f2(30維)的尋優曲線

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

圖2 四種算法對f8(50維)的尋優曲線

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

3.4 AIW-PSO算法與其它改進PSO算法實驗

為了進一步評價AIW-PSO算法的優化能力，將AIW-PSO 與 CLPSO、HPSO-TVAC[8]、LPSO、DMS-PSO[9]和LFPSO進行比較。具體實驗參數設定與上文相同，算法均獨立運行20次。表3給出了8組測試函數在30維問題上的實驗結果，其中，CLPSO、HPSO-TVAC、LPSO、DMS-PSO和LFPSO的實驗數據來自于文獻[10]。

表3 AIW-PSO算法與其他相關算法的實驗結果對比

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

4 結束語

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