粒子釋放與速度動態(tài)變化的改進粒子群算法

馬欣 閆莉

（西安工業(yè)大學機電工程學院 陜西省西安市 710021）

粒子群算法(PSO)是Kennedy[1]等人于1995年受鳥群捕食行為啟發(fā)而提出的一種基于群體行為協(xié)作的隨機搜索算法。粒子群算法具有算法原理簡單易理解、參數(shù)少、算法收斂快、魯棒性好、且易于程序實現(xiàn)等優(yōu)點，并適用于很多工程實踐問題；因此，PSO 自提出以來受到眾學者的關注。PSO 已經在自動化技術、神經網絡訓練、電力工業(yè)優(yōu)化、參數(shù)辨識等諸多領域得到了廣泛應用。多年來，針對PSO 的研究成果眾多。

經閱讀文獻[2-23]并對其總結可知對PSO 的改進大致包括以下幾方面：

（1）對初始種群的產生方法的改進；

（2）對PSO 自身的參數(shù)進行改進；

（3）對粒子鄰域拓撲結構的改進。

粒子群算法的收斂性和多樣性之間的矛盾關系是：如果粒子快速收斂，將不可避免地導致粒子的逐漸同一性，從而限制了粒子的搜索范圍，并且算法容易陷入局部最優(yōu)。如果增加了粒子的多樣性，打破此限制以擴大搜索范圍可以改善粒子落入局部最優(yōu)的情況，但同時也會降低算法的收斂速度，甚至可能出現(xiàn)結果發(fā)散和計算誤差增加的現(xiàn)象。根據(jù)文獻研究，如果要平衡兩者之間的關系，當前有效的解決方案是在算法的早期階段增加粒子的多樣性，以便可以在更大的搜索范圍內搜索粒子；在算法的后期，粒子速度不斷變化以減少每個粒子對全局最優(yōu)解位置的搜索次數(shù)提高了算法的后期收斂性。

為改善標準粒子群算法的不足，本文提出一種粒子釋放與粒子速度動態(tài)變化的改進粒子群算法（PR&SDC-PSO）。測試結果表明PR&SDC-PSO 可以改善標準粒子群算法收斂慢、搜索精度低、易陷入局部最優(yōu)等缺點。

1 粒子群算法原理

標準粒子群算法是基于對鳥類群覓食行為的研究。它是對群體行為的模型抽象，并用于解決實際的優(yōu)化問題。標準粒子群算法的優(yōu)化過程可以描述為：每個粒子通過判斷其自身的歷史最佳位置和其他個體的歷史最佳位置以及連續(xù)迭代的總體趨勢來連續(xù)調整其下一個搜索速度和位置。

假設在D 維搜索空間中有一組N 個粒子，則t 代的第i 個粒子的位置可以表示為：

粒子速度可以表示為：

那么，第t+1 代第i 個粒子速度與粒子位置的第d 維，可以按式（3）和（4）進行更新。

其中：i=1,2,…n，d=1,2,…D；ω 為慣性權重；c1 和c2 為學習因子，是非負常數(shù)；r1 和r2 為(0，1)內均勻分布的隨機數(shù)；pid和pgd分別表示個體最優(yōu)位置和種群全局最優(yōu)位置；vmax是常數(shù)。

2 粒子釋放—速度動態(tài)變化的粒子群算法

為了有效地提高PSO 性能，提出粒子釋放[7]和粒子速度動態(tài)變化的結合策略，實現(xiàn)當算法陷入局部最優(yōu)時增加粒子的多樣性，當粒子過于發(fā)散提高算法的收斂性的綜合效果。用于釋放粒子的條件是：當檢測到最佳適應度值在設定的迭代步數(shù)內沒有更新時，該算法將被判斷為陷入局部最優(yōu)。在這種情況下，當前的最優(yōu)粒子全局搜索能力差。為了改善目前的停滯狀態(tài)，釋放粒子到搜索的空間邊界，以增加粒子的全局搜索潛力附近，粒子釋放公式為：

其中：xid 與vid 為粒子i 第d 維的位置與速度，ud 為第d 維空間的上限，ld 為第d 維空間的下限。

釋放粒子后，如果在一定數(shù)量的迭代步數(shù)中檢測到最佳適應度值沒有更新，則算法將再次執(zhí)行粒子釋放操作。為了在增加粒子多樣性的同時確保算法的最終收斂效果，有必要避免發(fā)生粒子的釋放速度大于粒子的收斂速度的情況。因此，引入速度動態(tài)變化策略是為了使釋放的粒子迅速再次收斂到最優(yōu)種群附近，從而確保算法的最終收斂效率。

在PSO 中存在粒子最大速度vmax來限制粒子運動步長，粒子i第d 維的速度若vmax值過大，粒子可能會越過優(yōu)質搜索區(qū)域，降低搜索精度；如果vmax值過小，那么粒子的搜索慢，導致其收斂性較差。為了改善vmax值對PSO 影響，本文提出粒子的速度動態(tài)變化策略，粒子速度可以設置為：

上式中：v'max與v'min為極限最大、最小速度限制；T 為最大迭代代數(shù)。可以看出v'max、v'min根據(jù)迭代次數(shù)從1.0 線性遞減，該策略使粒子在算法初期全局范圍內搜索，在后期可以使粒子在局部區(qū)域重點搜索，避免粒子釋放出去以后迭代過慢。從而加快算法收斂，提高算法性能。

3 算法步驟

基于粒子釋放與速度動態(tài)變化改進后的算法（PR&SDC-PSO）步驟如下，用K 來判定是否進行粒子釋放操作。

（1）粒子群初始化。設定初始粒子群的規(guī)模，隨機生成粒子的位置和速度，其中

（2）計算每個粒子適應度值，并更新每個粒子的個體歷史最優(yōu)位置和種群歷史全局最優(yōu)位置，令K=0。

（3）按照式（6）計算各個粒子的最大速度。

（4）根據(jù)式（3）（4）更新粒子速度與粒子的位置。xid如果超出了位置限制邊界，則將其位置設置為相應的邊界值。

（5）再次計算每個粒子的適應度值，并更新每個粒子的個體最優(yōu)和種群全局最優(yōu)。

（6）若全局最優(yōu)有更新，則K=0；否則K=K+1。

（7）若K=m 時，并按式（5）釋放最優(yōu)粒子。

（8）若沒有到達事先設定的最大迭代數(shù)則返回步驟（3），否則迭代停止。

4 測試函數(shù)

為了衡量改進后的算法的可行性與有效性，本文選取了三個測試函數(shù)用于算法測試。

4.1 Schaffer函數(shù)

Schaffer 函數(shù)是一個多峰函數(shù)。此函數(shù)包含無限數(shù)量的局部極值和全局極值，搜索難度很高。它通常用于驗證算法的搜索準確性，全局最小值為f(0，0)=0。全局最小值解周圍有無數(shù)的局部最小值解，因此很難尋優(yōu)。Schaffer 函數(shù)圖像如圖1所示。

4.2 Girewanks函數(shù)

該函數(shù)是單峰函數(shù)，全局最小值為f(0，0)=0。此函數(shù)的搜索難度較小，通常用于驗證算法的搜索效率。Girewanks 函數(shù)圖像如圖2所示。

4.3 Ackley函數(shù)

Ackley 函數(shù)是一種激烈的多峰函數(shù)。該函數(shù)更復雜，并且具有多個局部最小值，因此很難搜索全局最優(yōu)值。Ackley 函數(shù)圖像如圖3所示。

5 仿真實驗與性能分析

針對不同算法性能對比，將不同算法的參數(shù)統(tǒng)一設置為：粒子數(shù)量n=25，允許最大迭代次數(shù)1000 次；慣性權重采取隨時間變化的策略，慣性權重從0.9 線性遞減，達到最大迭代次數(shù)時降至0.4；學習因子c1、c2都設定為1.8。每種算法經過200 次測試，結果如表1所示。

圖1：Schaffer 函數(shù)圖像

圖2：Girewanks 函數(shù)圖像

圖3：Ackley 函數(shù)圖像

表1：測試結果

對比分析表1的測試數(shù)據(jù)可知，表1中本文改進后的PR&SDC-PSO 的尋優(yōu)性能是所列算法里最好的。對于Girewanks函數(shù)這個單峰函數(shù)來說，PR&SDC-PSO 求得了最優(yōu)值且收斂較快，說明該算法的搜索能力強。而對于另外兩個激烈的多峰函數(shù)而言，在尋優(yōu)時均取得比其他算法更精確的最優(yōu)值；與其他算法相比PR&SDC-PSO 算法具有更好的性能，驗證了改進方法的可行性與有效性。

6 結束語

針對標準粒子群算法的過早收斂以及后期搜索收斂的精度低的問題，提出了一種改進的粒子釋放-粒子速度動態(tài)變化策略。將Schaffer 函數(shù)，Girewanks 函數(shù)和Ackley 函數(shù)用作測試函數(shù)，以測試改進算法的有效性，并對結果進行分析和比較。分析結果表明，引入改進的粒子釋放和粒子速度動態(tài)速度變化來改進粒子群算法具有明顯的優(yōu)勢。