一種動(dòng)態(tài)調(diào)整慣性權(quán)重的簡化均值粒子群優(yōu)化算法

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

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

1 引 言

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

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

2 粒子群優(yōu)化算法

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

(1)

(2)

其中w為慣性權(quán)重；c1和c2為學(xué)習(xí)因子，通常取值為2；r1和r2為分布在[0，1]內(nèi)的隨機(jī)數(shù)；t為粒子當(dāng)前的迭代次數(shù).

3 貝塔分布

貝塔分布(Beta Distribution)是指一組定義在(0，1)區(qū)間的連續(xù)概率分布，它又作為多元統(tǒng)計(jì)分析中一類重要的基礎(chǔ)分布，在數(shù)理統(tǒng)計(jì)學(xué)等領(lǐng)域具有廣泛的應(yīng)用.貝塔分布的概率密度函數(shù)的表達(dá)式為：

(3)

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

(4)

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

4 改進(jìn)的粒子群優(yōu)化算法

4.1 簡化粒子群優(yōu)化算法

文獻(xiàn)[9]在標(biāo)準(zhǔn)粒子群優(yōu)化算法的基礎(chǔ)上，通過去除算法中粒子的速度項(xiàng)，提出了一種簡化粒子群優(yōu)化算法(SPSO)，算法位置更新公式如式(5)所示：

(5)

簡化粒子群優(yōu)化算法能夠在僅有粒子位置項(xiàng)的情況下進(jìn)行迭代，使優(yōu)化方程從二階變?yōu)橐浑A，算法變得更簡單高效，從而避免了由速度引起的粒子發(fā)散造成的算法在搜索后期收斂速度變慢等不足[9].

4.2 改進(jìn)的簡化粒子群優(yōu)化算法

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

(6)

其中式(6)右邊的第二項(xiàng)可以引導(dǎo)粒子由當(dāng)前位置向粒子個(gè)體最優(yōu)位置和全局最優(yōu)位置的平均位置方向偏移；第三項(xiàng)可以引導(dǎo)粒子由當(dāng)前位置向粒子個(gè)體最優(yōu)位置方向和全局最優(yōu)位置負(fù)方向的平均位置方向偏移[13].

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

4.3 動(dòng)態(tài)慣性權(quán)重

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

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

(7)

其中wmax，wmin分別為慣性權(quán)重的最大值和最小值，Tmax為粒子最大迭代次數(shù).

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

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

(8)

其中σ為慣性調(diào)整因子，betarnd生成服從貝塔分布的隨機(jī)數(shù)，且貝塔分布能夠擬合出均勻分布、正態(tài)分布等多種分布形式[16].慣性權(quán)重w表達(dá)式中的第一項(xiàng)和第二項(xiàng)通過余弦函數(shù)的改變，使得慣性權(quán)重的取值區(qū)間為[0.4，0.9]，相關(guān)實(shí)驗(yàn)表明，在此區(qū)間變化的慣性權(quán)值，算法能夠取得較好的尋優(yōu)性能[11].第三項(xiàng)利用貝塔分布調(diào)整慣性權(quán)重整體取值的分布，并在betarnd前加入慣性調(diào)整因子，控制w的偏離程度，從而使得對(duì)慣性權(quán)重取值的調(diào)整更加合理.

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

綜合4.1-4.3小節(jié)所述，本文提出了一種動(dòng)態(tài)調(diào)整慣性權(quán)重的簡化均值粒子群優(yōu)化算法(A Simplified Mean Particle Swarm Optimization Algorithm with Dynamic Adjustment of Inertia Weight，DSMPSO)，該算法的具體步驟為：

Step1. 參數(shù)初始化：初始化粒子數(shù)量，最大迭代次數(shù)等，并隨機(jī)初始化每個(gè)粒子的位置以及粒子的速度；

Step2. 根據(jù)給定的目標(biāo)函數(shù)計(jì)算所有粒子的適應(yīng)度值；

Step3. 比較群體中所有粒子的適應(yīng)度值與其經(jīng)歷過的最優(yōu)位置的適應(yīng)度值的優(yōu)劣，如果前者更優(yōu)，則用粒子的當(dāng)前位置替代粒子的個(gè)體歷史最優(yōu)位置；

Step4. 比較群體中所有粒子的適應(yīng)度值與整個(gè)群體經(jīng)歷過的最優(yōu)位置的適應(yīng)度值的優(yōu)劣，如果前者更優(yōu)，則更新全局最優(yōu)位置；

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

Step6. 判斷是否達(dá)到實(shí)驗(yàn)設(shè)置的終止條件，若達(dá)到，則算法停止并輸出最優(yōu)值；否則轉(zhuǎn)至Step 2.

5 實(shí)驗(yàn)結(jié)果及分析

5.1 基本測試函數(shù)

為了測試本文提出的DSMPSO算法的有效性，本文選取12個(gè)測試函數(shù)[14，17]與線性遞減慣性權(quán)重粒子群優(yōu)化算法(LPSO)、均值粒子群優(yōu)化算法(MPSO)和簡化粒子群優(yōu)化算法(SPSO)進(jìn)行對(duì)比實(shí)驗(yàn)測試.12個(gè)測試函數(shù)的數(shù)學(xué)表達(dá)式如下：

(1)Sphere函數(shù)

(2)Schwefel′s P2.21函數(shù)

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

(3)Schwefel′s P2.22函數(shù)

(4) Step函數(shù)

(5) Schaffers函數(shù)

(6) Rastrigin函數(shù)

(7) Griewank函數(shù)

(8) Ackely函數(shù)

(9) Schaffer函數(shù)

(10) Branin函數(shù)

(11) Six-Hump Camel-back函數(shù)

(12) Goldstein-price函數(shù)

其中在12個(gè)測試函數(shù)當(dāng)中，f1-f9的理論最優(yōu)值都為0，f10、f11和f12的理論最優(yōu)值分別為：0.3979、-1.0316、3.

5.2 仿真實(shí)驗(yàn)結(jié)果分析

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

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

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

由表1的實(shí)驗(yàn)結(jié)果可知，對(duì)于f11-f12這2個(gè)2維函數(shù)來說，4種算法都能夠?qū)ふ业嚼碚撟顑?yōu)值，這說明算法的尋優(yōu)精度無差別.但是對(duì)于病態(tài)復(fù)雜的、很難找到理論最優(yōu)值的Schaffer函數(shù)來說，DSMPSO和SPSO算法都能夠?qū)ふ业嚼碚撟顑?yōu)值.從2維測試函數(shù)的對(duì)比結(jié)果可知，DSMPSO算法的尋優(yōu)性能優(yōu)勢并不明顯.

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

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

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

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

5.3 T檢驗(yàn)和Friendman檢驗(yàn)

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

表4 4種算法的T檢驗(yàn)和Friendman檢驗(yàn)結(jié)果Table 4 Results of T test and Friendman test for four algorithms

5.4 指定精度下的平均迭代次數(shù)

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

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

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

5.5 與新近或相關(guān)改進(jìn)算法的對(duì)比實(shí)驗(yàn)

為了整體綜合比較DSMPSO算法的性能，本文與新近相關(guān)改進(jìn)的算法做了兩組對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)1：與新近相關(guān)改進(jìn)的粒子群算法(基于隨機(jī)慣性權(quán)重的簡化粒子群優(yōu)化算法，SIWSPSO)[15]的比較；實(shí)驗(yàn)2：與新近其他兩種改進(jìn)的人工智能算法(動(dòng)態(tài)調(diào)整慣性權(quán)重的自適應(yīng)蝙蝠算法(DAWBA)[14]和自擾動(dòng)人工蜂群算法(IGABC)[17])的比較.

5.5.1 與SIWSPSO算法比較

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

表6 SIWSPSO與DSMPSO算法實(shí)驗(yàn)結(jié)果Table 6 Experimental results of SIWSPSO and DSMPSO

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

5.5.2 與DAWBA和IGABC算法比較

DSMPSO與DAWBA和IGABC算法在其所測試的函數(shù)上選取五個(gè)常用測試函數(shù)，與DAWBA算法在最優(yōu)值和平均值上作對(duì)比，與IGABC算法在最優(yōu)值平均值和標(biāo)準(zhǔn)差上作對(duì)比，DAWBA和IGABC算法的實(shí)驗(yàn)數(shù)據(jù)結(jié)果均來自原文獻(xiàn)，具體比較結(jié)果見表7和表8.

表7 DAWBA和DSMPSO算法實(shí)驗(yàn)結(jié)果Table 7 Experimental results of DAWBA and DSMPSO

由表7的實(shí)驗(yàn)結(jié)果可得，DSMPSO算法的尋優(yōu)精度均優(yōu)于與DAWBA算法，說明本文算法的尋優(yōu)精度高.由表8可知，兩種算法在函數(shù)Rastrigin和Griewank上的尋優(yōu)性能相同，在其他3個(gè)測試函數(shù)上的尋優(yōu)結(jié)果優(yōu)于IGABC算法.

表8 IGABC 和DSMPSO算法實(shí)驗(yàn)結(jié)果Table 8 Experimental results of DAWBA and DSMPSO

綜合上述2組對(duì)比實(shí)驗(yàn)結(jié)果可知，不管是與新近的相關(guān)改進(jìn)粒子群算法相比，還是與其他新近的人工智能算法相比，DSMPSO算法都具有良好的尋優(yōu)優(yōu)勢.

6 結(jié) 論

本文在簡化粒子群優(yōu)化算法的基礎(chǔ)上，提出一種動(dòng)態(tài)調(diào)整慣性權(quán)重的簡化均值粒子群優(yōu)化算法.通過對(duì)算法速度公式中個(gè)體最優(yōu)位置和全局最優(yōu)位置的修正，以及對(duì)慣性權(quán)重加入貝塔分布的動(dòng)態(tài)調(diào)整，既增加了種群的多樣性，又使得算法具有良好的全局收斂能力.仿真實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)的算法具有較快的收斂速度，以及較高的尋優(yōu)精度.同時(shí)改進(jìn)的算法對(duì)解決維數(shù)較高的多峰函數(shù)問題，具有良好的性能和潛在的應(yīng)用價(jià)值.