一種動態調整慣性權重的簡化均值粒子群優化算法

黃 洋，魯海燕，2，許凱波，沈莞薔，2

1(江南大學 理學院，江蘇 無錫 214122)2(江南大學 無錫市生物計算工程技術研究中心，江蘇 無錫 214122)

1 引 言

粒子群優化(particle swarm optimization，PSO)算法[1]是一種基于對群體捕食行為進行模擬研究的群體智能優化算法.自1995年提出以來，PSO算法已受到眾多學者的關注并已在現實優化問題當中得到了廣泛的應用[2-4].然而，PSO算法也存在早熟收斂以及在算法搜索后期收斂速度慢等不足.為了改善這些不足，國內外眾多學者提出了不同改進策略的粒子群優化算法.其中，對粒子群優化算法中更新公式的改進成為眾多研究熱點之一.文獻[5]通過對粒子群優化算法中慣性權值遞減策略的研究，分析了4種常用的慣性權重調整策略的性能特點.文獻[6]提出了一種隨機權重取值的粒子群優化算法，改進后的算法不但改善了求解的精度，而且也能夠提高求解的速度.姜建國等[7]采用余弦函數對慣性權重進行非線性調整，提高了算法的搜索效率，能夠有效地改善早熟現象.Clerc等[8]將壓縮因子加入到算法速度更新公式當中，從而提高算法的收斂性能.文獻[9]提出了一種只有位置更新公式的簡化粒子群優化算法，并證明了改進算法的收斂性，算法變得更加簡單高效.Deep等[10]通過利用個體最優位置和全局最優位置的線性組合來修正速度公式中的個體最優位置和全局最優位置，使算法的收斂速度和全局收斂能力得到提高.

本文結合對上述改進粒子群優化算法的分析以及文獻[7、9、10]中算法的改進思想，提出了一種動態調整慣性權重的簡化均值粒子群優化算法.為了進一步平衡算法的全局和局部搜索能力，慣性權重在滿足非線性遞減策略的基礎上，加入貝塔分布的隨機調整策略.同時，在簡化粒子群優化算法的基礎上，分別用個體最優位置和全局最優位置的線性組合取代算法速度公式中的個體最優位置和全局最優位置，從而提高算法的收斂速度以及全局收斂性能.并將本文改進的算法與線性遞減慣性權重粒子群優化算法(LPSO)[11]、均值粒子群優化算法(MPSO)、簡化粒子群優化算法(SPSO)以及新近或相關改進算法進行對比實驗，證明了本文新算法的有效性.

2 粒子群優化算法

粒子群優化算法是對群體捕食行為進行模擬的數學模型.該算法的具體數學描述為：假設目標搜索空間的維數為D，粒子種群規模為N，Xi=(xi1，xi2，…，xiD)表示第i個粒子在D維搜索空間中的位置，Vi=(vi1，vi2，…，viD)表示第i個粒子的速度，其中i=1，…，N.pbest表示第i個粒子自身經歷過的最優位置，gbest表示整個群體經歷過的最優位置.在算法的整個進化過程當中，每個粒子通過不斷更新pbest和gbest來更新自身的速度和位置，從而尋找到達到最優適應度值時粒子的最佳位置，即為待優化問題的解[12].粒子的速度和位置更新公式為：

(1)

(2)

其中w為慣性權重；c1和c2為學習因子，通常取值為2；r1和r2為分布在[0，1]內的隨機數；t為粒子當前的迭代次數.

3 貝塔分布

貝塔分布(Beta Distribution)是指一組定義在(0，1)區間的連續概率分布，它又作為多元統計分析中一類重要的基礎分布，在數理統計學等領域具有廣泛的應用.貝塔分布的概率密度函數的表達式為：

(3)

式(3)中的分母是貝塔函數，其表達式為：

(4)

圖1 貝塔分布概率密度函數圖像Fig.1 Image of the Beta density distribution

4 改進的粒子群優化算法

4.1 簡化粒子群優化算法

文獻[9]在標準粒子群優化算法的基礎上，通過去除算法中粒子的速度項，提出了一種簡化粒子群優化算法(SPSO)，算法位置更新公式如式(5)所示：

(5)

簡化粒子群優化算法能夠在僅有粒子位置項的情況下進行迭代，使優化方程從二階變為一階，算法變得更簡單高效，從而避免了由速度引起的粒子發散造成的算法在搜索后期收斂速度變慢等不足[9].

4.2 改進的簡化粒子群優化算法

為了加快粒子群優化算法的收斂速度，且避免出現早熟現象，結合文獻[10]提出的均值粒子群算法的思想，本文在簡化粒子群優化算法的基礎上利用線性組合(pbest+gbest)/2和(pbest-gbest)/2取代式(5)中的Pbest和gbest，因此式(5)可變為：

(6)

其中式(6)右邊的第二項可以引導粒子由當前位置向粒子個體最優位置和全局最優位置的平均位置方向偏移；第三項可以引導粒子由當前位置向粒子個體最優位置方向和全局最優位置負方向的平均位置方向偏移[13].

在簡化粒子群優化算法的基礎上，利用個體最優位置和全局最優位置的線性組合取代位置更新公式當中的粒子個體自身最優位置部分和群體全局最優位置部分，這種改進策略充分利用了粒子自身和全局位置的有用信息，可以更好地調整粒子飛行方向與當前最好位置方向的偏移，使粒子更快地尋找到全局最優位置，從而有效地避免算法早熟收斂的問題.

4.3 動態慣性權重

從改進的簡化粒子群優化算法模型中的式(6)可以看出，慣性權重依舊是平衡算法全局和局部搜索能力的重要參數之一.姜建國等[7]采用余弦函數來控制慣性權值的變化，提出一種動態改變慣性權重的策略，慣性權重變化公式可表示為：

w=[(wmax-wmin)/2]cos(πt/Tmax)+(wmax+wmin)/2

(7)

其中wmax，wmin分別為慣性權重的最大值和最小值，Tmax為粒子最大迭代次數.

上述慣性權重的改進策略為非線性地減小w的取值，改進的算法在一定程度上不僅可以提高算法的搜索效率，同時還能夠改善早熟問題.由式(7)可知，雖然改進的慣性權重策略可以提高算法的尋優性能，但是在算法搜索后期，種群中的粒子都向最優解方向靠近，群體的多樣性也會逐漸缺失，這樣就會導致算法在搜索后期的收斂速度明顯變慢[14].針對上述問題，本文借鑒文獻[7，15]中對慣性權重的改進思想，提出一種動態調整慣性權重的策略，慣性權重的具體表達式為：

w=wmin+(wmax-wmin)×cos(πt/2Tmax)+σ×betarnd(a，b)

(8)

其中σ為慣性調整因子，betarnd生成服從貝塔分布的隨機數，且貝塔分布能夠擬合出均勻分布、正態分布等多種分布形式[16].慣性權重w表達式中的第一項和第二項通過余弦函數的改變，使得慣性權重的取值區間為[0.4，0.9]，相關實驗表明，在此區間變化的慣性權值，算法能夠取得較好的尋優性能[11].第三項利用貝塔分布調整慣性權重整體取值的分布，并在betarnd前加入慣性調整因子，控制w的偏離程度，從而使得對慣性權重取值的調整更加合理.

由式(8)可知，這種改進方式使得慣性權重在總體上呈非線性變化，且滿足在整個搜索過程當中慣性權值遞減的要求；同時再加入服從貝塔分布的隨機調整策略，一方面在搜索初期慣性權值減小過快時，可能產生較大的調整值，增強算法在搜索初期的全局搜索能力，并增加粒子種群的多樣性；另一方面，在搜索后期能夠有機會獲得較大的慣性權值，從而提高算法的搜索精度.

綜合4.1-4.3小節所述，本文提出了一種動態調整慣性權重的簡化均值粒子群優化算法(A Simplified Mean Particle Swarm Optimization Algorithm with Dynamic Adjustment of Inertia Weight，DSMPSO)，該算法的具體步驟為：

Step1. 參數初始化：初始化粒子數量，最大迭代次數等，并隨機初始化每個粒子的位置以及粒子的速度；

Step2. 根據給定的目標函數計算所有粒子的適應度值；

Step3. 比較群體中所有粒子的適應度值與其經歷過的最優位置的適應度值的優劣，如果前者更優，則用粒子的當前位置替代粒子的個體歷史最優位置；

Step4. 比較群體中所有粒子的適應度值與整個群體經歷過的最優位置的適應度值的優劣，如果前者更優，則更新全局最優位置；

Step5. 利用公式(6)和公式(8)更新每個粒子的位置；

Step6. 判斷是否達到實驗設置的終止條件，若達到，則算法停止并輸出最優值；否則轉至Step 2.

5 實驗結果及分析

5.1 基本測試函數

為了測試本文提出的DSMPSO算法的有效性，本文選取12個測試函數[14，17]與線性遞減慣性權重粒子群優化算法(LPSO)、均值粒子群優化算法(MPSO)和簡化粒子群優化算法(SPSO)進行對比實驗測試.12個測試函數的數學表達式如下：

(1)Sphere函數

(2)Schwefel′s P2.21函數

f2(x)=max{|xi|，1≤i≤n}

(3)Schwefel′s P2.22函數

(4) Step函數

(5) Schaffers函數

(6) Rastrigin函數

(7) Griewank函數

(8) Ackely函數

(9) Schaffer函數

(10) Branin函數

(11) Six-Hump Camel-back函數

(12) Goldstein-price函數

其中在12個測試函數當中，f1-f9的理論最優值都為0，f10、f11和f12的理論最優值分別為：0.3979、-1.0316、3.

5.2 仿真實驗結果分析

在實驗中不同的PSO算法設置了相同的群體規模N=40，最大迭代次數為Tmax=500，學習因子c1=c2=2，其他參數設置與原文獻保持一致，在DSMPSO算法中：wmin=0.9、wmin=0.4、σ=0.1；在betarnd(a，b)函數中：a=1、b=2.

為了測試算法的性能，實驗分為兩組，算法中的維數分別設置為30和50，4種算法分別獨立運行50次，各個算法在平均值(MEAN)和標準差(STD)上的比較結果如表1、表2和表3所示.圖2給出了部分測試函數的適應度值曲線.其中f9-f12為2維的測試函數，實驗最好結果用粗體表示.

表1 4種算法的測試結果(D=2)Table 1 Experimental results of four algorithms (D=2)

由表1的實驗結果可知，對于f11-f12這2個2維函數來說，4種算法都能夠尋找到理論最優值，這說明算法的尋優精度無差別.但是對于病態復雜的、很難找到理論最優值的Schaffer函數來說，DSMPSO和SPSO算法都能夠尋找到理論最優值.從2維測試函數的對比結果可知，DSMPSO算法的尋優性能優勢并不明顯.

表2 4種算法的測試結果(D=30)Table 2 Experimental results of four algorithms (D=30)

為了進一步比較算法尋優性能的差異，對f1-f8這8個可變維的測試函數在不同的維數下進行對比實驗.從表2和表3的對比結果可以得到，DSMPSO算法在8個測試函數上，不管是30維還是50維，DSMPSO算法與其他三種改進的PSO算法相比，對測試函數的優化效果都有進一步的提高.對于單峰問題f1-f3以及多峰問題f5，DSMPSO 算法的平均值均小于其他三種算法，說明本文算法具有更好的尋優精度.尤其是對于一般用來測試算法收斂速度的單峰函數f1和f4來說，DSMPSO算法都能夠尋找到理論最優解0，并且由圖2(a)、圖2(e)可以看出，DSMPSO算法只需要較少的迭代次數就可以收斂到最優解.同時對于非線性多峰函數f6-f8來說，MPSO、SPSO和DSMPSO這三種算法在函數f6和f8上達到了相同的尋優精度，且SPSO和DSMPSO這兩種算法在函數f6-f7上都能夠尋找到理論最優解0，但是由圖2可以看出，DSMPSO算法需要的迭代次數更少，因此具有更快的收斂速度.從表2和表3的結果也可以看出，DSMPSO算法的標準差均小于其他三種算法，因此算法具有更好的穩定性.由此可得，DSMPSO算法與其他三種算法相比，不管是在單峰或者多峰函數問題上(尤其是維數較高的測試函數問題)，本文改進的算法都能夠具有很高的尋優精度和很快的收斂速度.

表3 4種算法的測試結果(D=50)Table 3 Experimental results of four algorithms (D=50)

圖2 不同測試函數在不同維數下的收斂曲線Fig.2 Convergence curves of different test functions under different dimensions

5.3 T檢驗和Friendman檢驗

由表1、表2和表3可知，SPSO和DSMPSO算法在12個測試函數上有8個測試函數的尋優精度相同，為了進一步明確算法之間是否存在顯著性差異，本文從統計學角度來討論算法的性能，引入T檢驗[18]和Friendman檢驗[19]，對4種算法在12個測試函數上的性能進行測試，實驗結果見表4.T檢驗結果表明，LPSO算法與DSMPSO算法性能差異明顯；DSMPSO與MPSO算法相比，在7個測試函數上的性能更優，4個無差異，1個更差；DSMPSO與SPSO算法相比，4個函數更優，6個無差異，2個更差.由Friendman檢驗可知算法性能越好則秩均值越小.由4種算法的Friendman檢驗結果可得，DSMPSO算法的秩均值最小，在4種算法中性能最好.綜合兩種檢驗結果可知，DSMPSO算法的性能比其他三種算法更優.其中“+”表示DSMPSO算法優于其他算法，“=”表示算法之間無明顯差異，“-”表示劣于其他算法，w/t/l分別表示這三種比較結果的統計數目.

表4 4種算法的T檢驗和Friendman檢驗結果Table 4 Results of T test and Friendman test for four algorithms

5.4 指定精度下的平均迭代次數

由5.2小節的實驗結果可知，表2和表3給出了在指定迭代次數下，算法尋優精度的實驗結果比較.為了全面分析算法的性能，本小節給出了4種算法對8個測試函數(f1-f8)在指定精度10-10下進行測試，維數為30，各個算法分別獨立運行50次的平均迭代次數如表5所示.

表5 指定精度下的平均迭代次數Table 5 Average number of iterations under the specified accuracy

由表5的實驗結果可知，LPSO算法只在一個測試函數上達到指定精度，MPSO算法在8個函數上有6個達到指定精度，而SPSO和DSMPSO算法在所有測試函數上都達到了指定精度.并且與其他三種算法相比，DSMPSO算法都能夠以最少的迭代次數達到指定精度，平均迭代次數在4-34之間，這表明DSMPSO算法的收斂速度優勢明顯，具有較高的尋優性能，從而也進一步說明了改進的簡化均值粒子群優化算法具有收斂速度快的特性.

5.5 與新近或相關改進算法的對比實驗

為了整體綜合比較DSMPSO算法的性能，本文與新近相關改進的算法做了兩組對比實驗.實驗1：與新近相關改進的粒子群算法(基于隨機慣性權重的簡化粒子群優化算法，SIWSPSO)[15]的比較；實驗2：與新近其他兩種改進的人工智能算法(動態調整慣性權重的自適應蝙蝠算法(DAWBA)[14]和自擾動人工蜂群算法(IGABC)[17])的比較.

5.5.1 與SIWSPSO算法比較

DSMPSO和SIWSPSO算法在文獻[15]中的六個測試函上進行測試，兩種算法的最大迭代次數為Tmax=500，維數D=30，其他參數設置與原文獻保持一致，算法獨立運行50次取最優值平均值(MEAN)，達到最優值的平均迭代次數(AI)作為最終比較結果，具體結果如表6所示.

表6 SIWSPSO與DSMPSO算法實驗結果Table 6 Experimental results of SIWSPSO and DSMPSO

由表6可知，兩種算法在5個測試函數上的尋優精度相同，1個測試函數上的尋優精度略低于SIWSPSO算法.且在4個函數上都找到了理論最優值，同時DSMPSO算法在這4個測試函數上收斂到理論最優值的平均迭代次數明顯少于SIWSPSO算法，這也說明 DSMPSO算法具有收斂速度快的優勢.

5.5.2 與DAWBA和IGABC算法比較

DSMPSO與DAWBA和IGABC算法在其所測試的函數上選取五個常用測試函數，與DAWBA算法在最優值和平均值上作對比，與IGABC算法在最優值平均值和標準差上作對比，DAWBA和IGABC算法的實驗數據結果均來自原文獻，具體比較結果見表7和表8.

表7 DAWBA和DSMPSO算法實驗結果Table 7 Experimental results of DAWBA and DSMPSO

由表7的實驗結果可得，DSMPSO算法的尋優精度均優于與DAWBA算法，說明本文算法的尋優精度高.由表8可知，兩種算法在函數Rastrigin和Griewank上的尋優性能相同，在其他3個測試函數上的尋優結果優于IGABC算法.

表8 IGABC 和DSMPSO算法實驗結果Table 8 Experimental results of DAWBA and DSMPSO

綜合上述2組對比實驗結果可知，不管是與新近的相關改進粒子群算法相比，還是與其他新近的人工智能算法相比，DSMPSO算法都具有良好的尋優優勢.

6 結 論

本文在簡化粒子群優化算法的基礎上，提出一種動態調整慣性權重的簡化均值粒子群優化算法.通過對算法速度公式中個體最優位置和全局最優位置的修正，以及對慣性權重加入貝塔分布的動態調整，既增加了種群的多樣性，又使得算法具有良好的全局收斂能力.仿真實驗結果表明，本文改進的算法具有較快的收斂速度，以及較高的尋優精度.同時改進的算法對解決維數較高的多峰函數問題，具有良好的性能和潛在的應用價值.