帶沖撞和制動的自適應粒子群優化算法

李 眩，吳曉兵，方婷婷

（銅陵職業技術學院經貿系，安徽銅陵 244061）

粒子群優化（particle swarm optimization，PSO）算法源于對鳥類覓食行為的研究，受其啟發運用群體協作和個體間信息共享解決優化問題的智能隨機搜索算法，其應用從最初數學領域的函數最值求解擴展到如今的工程領域的過程優化、模糊系統的控制、圖像處理等更加廣闊的領域〔1〕。PSO 算法誕生較晚，但有易理解、易實現、收斂速度快的優點。雖然PSO 算法在一些領域應用中有著不錯的表現，但隨著應用范圍的拓展，發現標準PSO 算法在解決一些復雜特定問題時效果還有待提升，譬如多目標動態規劃存在早熟收斂、維數災難、后期趨同導致多樣性不足等問題〔2〕，因此改進PSO 算法，提升其解決實際問題的效率十分有意義。在自適應粒子群優化（adaptive particle swarm optimization，APSO）算法的基礎上，借鑒沙丁魚受刺激加速游動避免死亡的原理，引入沖撞機制對標準PSO 算法進行改進，以此來提高算法擺脫局部最優的束縛和全局尋優能力。另外，為了兼顧算法的全局探索和局部精細搜索能力，在粒子群搜索過程中，引入一個動態變化的制動算子來控制粒子的速度，這樣可有效避免粒子群過早喪失全局探索能力和后期速度過大錯失全局最優解的情況出現，從而提高算法的整體效率。

1 標準PSO 算法及性能提升分析

PSO 算法是受鳥群覓食行為啟發而提出的智能優化算法，PSO 算法通過粒子相互之間的信息交互和配合使得整個群體達到和諧統一，實現在復雜搜索空間中協同尋優〔3〕。

在PSO 算法前期，較大的粒子速度有助于在限定的時間內盡可能遍歷全部可行區域，從而提高算法的收斂速度和全局收斂的能力，而在進化后期在最優解鄰域內進行探索時，粒子速度不能過快，因為較小的粒子速度便于粒子在全局最優解附近精細搜索，同時又能防止粒子飛行慣性過大逃離最優解區域而錯失全局最優解，因此必須遵循算法需要全程適時地對粒子速度進行有效適當的掌控和約束〔4〕。而標準PSO 算法缺乏對粒子速度的動態調整，容易陷入局部最優或者不易收斂，為了滿足算法性能提升要求，本研究引入制動算子實時控制粒子速度。另外針對PSO 算法存在易陷入局部最優的缺陷，受刺激沙丁魚加速游動避免死亡案例的啟發，在算法陷入局部最優時，引入一個沖撞算子激發粒子群運動活性使其有效擺脫局部最優的困擾。同時，在動態APSO 算法基礎上結合非線性變化的制動因子，來適時適當調整粒子的飛行速度改善算法的性能。

2 帶沖撞和制動的APSO 算法

人們發現PSO 算法采用自適應變化的動態參數比固定取值的參數更有助于提高算法的性能和效率〔5〕。PSO 算法的慣性權重設置不當對算法的性能產生不利影響，雖然慣性權重的動態非線性自適應調整比固定權重或線性變化權重能更好地提升PSO 算法性能，但僅用單一策略進行優化，對算法性能的提升相對有限〔6〕。因此本研究在自適應調整慣性權重的基礎上，同時考慮到算法要具備快速擺脫局部極值束縛的能力以及兼顧算法全局探索和局部精細搜索的能力，再進一步整合沖撞和制動多項策略改進算法來盡可能深度挖掘算法性能。因此在本研究中采用反正切函數對慣性權重進行改進，使其隨進化過程體現出非線性遞減特征，調整如式（1）所示：

反正切函數是一個單調函數，隨著自變量的增加，函數值變化步長逐漸減少。自變量等于1.56 時，函數值等于1，在進化過程中，慣性權重值前期減少的速度比較慢，后期減少的速度較快，在保證前期收斂速度的同時保證了搜索能力，能較好避開局部最優的現象出現，運用反正切函數改良后的動態非線性慣性權重符合PSO 算法性能的提升要求〔2〕。wstart=0.9，wend=0.4。當t=1 時，w（t）=wstart=0.9，當達到最大迭代次數tmax時，w（t）=wend=0.4。k 為控制因子，影響w（t）變化曲線的平滑度，k 取0.3，算法能取得較好的穩定性。

粒子速度有規律地變化能極大提升算法的效率和性能，并且其變化規律是可控的，因此適時地對粒子速度進行適量制動可以提升算法性能。在粒子位置更新公式中引入一個隨算法迭代不斷減小的制動算子ρ（t），實現對粒子速度逐漸增強的制動約束作用，來平衡算法的全局探索和局部精細搜索能力。制動算子值越小，對粒子的速度制動作用就越強，粒子速度減少值就越大。但要注意的是算法沒有結束或全局收斂前，不能對粒子群進行徹底制動，讓其完全停止搜索沒有運動，因為粒子停止運動，意味著無法繼續搜索最優解，所以制動算子值的變化應從某個較大值逐漸減少為某個最小值，但不能減少為0。

制動算子變化規律按照式（2）進行調整：

其中，ρmax設為1.6，ρmin設為0.4，α 為常數，設為0.009，tmax為最大迭代次數，t 為當前尋優次數。如此，粒子位置更新按式（3）調整：

如此設計的制動算子值隨迭代呈現先大后小非線性遞減的變化特征，但最終并不減少為0。由此可見，按照式（2）設計的制動算子完全滿足算法改進的要求。但在粒子加速沖撞跳脫局部極值陷阱的特殊情況下不能受制動影響，加入制動因子會逐漸降低粒子的運動速度，這一情況在后面會進行詳細闡述。

自然界沙丁魚生性懶惰，不愛游動，長時間運輸幾乎全部死亡。但當受到外部刺激譬如鯰魚追趕，沙丁魚會加速游動，運動量大大增加，很少出現缺氧死亡的情況。同理，標準PSO 算法一旦落入局部極值鄰域內就很難跳出，體現出運動惰性，尋優過程將會停滯，極易早熟收斂。為了激活陷入局部極值陷阱時粒子群的運動活性，受到沙丁魚受外部刺激加速游動避免死亡的案例啟發，以粒子群當前最優值與前幾代群體最優值相等為觸發條件，通過給粒子群一個比較大的瞬間沖量，相當于給予一個較大的外部刺激改變其惰性停滯狀態，驅動粒子突然加速沖出局部最優鄰域進入新一輪的探索，從而防止算法早熟收斂，增強其全局尋優能力。

當算法未達到終止條件而陷入局部最優停頓時，表現為粒子群當前最優適應度值一直保持不變，以此來構造算法受局部極值影響陷入停頓的判斷條件，其表述如下：

其中，i 表示當前的迭代次數，gb（i）表示群體當前最佳的適應度值，n 表示參照當前回溯的迭代次數。在本研究中取n=5，意為連續5 次迭代群體當前最優值保持不變時，即可認定算法停頓。

算法滿足所設置的局部最優觸發條件時，引入沖撞驅動算子強行驅動粒子重新搜索，此情況下粒子速度更新公式按式（4）進行更新：

其中，rand（）*k+k 稱為沖撞算子，rand（）為位于［0，1］區間的隨機數，w×vij（t）+c1×r1×［pij（t）-xij（t）］+c2×r2×［pgj（t）-xij（t）］表示正常情況下的速度更新，常數k 表示沖撞強度，本研究中取k=5，意為算法未結束而停滯時，當前粒子速度隨機增大到理論更新速度的5 到10 倍，以此來強行突破局部最優束縛。但要考慮到算法陷入局部極值，沖撞加速擺脫困境的情況下，不能同時又受制動的影響，那樣粒子速度會減緩，勢必會削弱沖撞效果，所以約定在算法陷入局部極值粒子加速沖撞時，其位置更新公式中不帶入制動因子，仍然采用原來方式xij（t+1）=xij（t）+vij（t+1）進行更新。

如上所述，改進后的PSO 算法具有較好的算法性能，陷入局部極值時仍然具有較高的運動活性而不至于出現搜索停滯，同時在算法實現過程中，可以對粒子進行自適應的制動，很好地協調平衡粒子全局探索和局部搜索能力，既不會過早放棄對全部解空間的探索，又同時防止粒子慣性大越過最優解區域從而錯失全局最優解。

3 改進算法性能仿真分析

為驗證應用自適應調整、沖撞和制動組合策略提升PSO 算法性能的有效性，選擇幾個典型非線性多模態和高維函數最小值的求解對算法進行實驗研究。如果優化算法能較為滿意地解決這些標準測試問題，則可認為在解決優化問題上有比較滿意的效果。第一個測試函數是較簡單的三維函數f1，其表達式為：

函數三維圖像見圖1，該函數圖像存在一個局部極值點，一旦粒子群掉落其中，很難跳出。

圖1 函數f1 三維圖像

為探究算法改進前后的效果和合理性，求函數f1在區間［-4，4］的最小值，測試過程中，取粒子群規模為100，粒子維數為2 維，最大迭代次數為200次。將標準PSO 算法（慣性權重為定值，本研究取為2）、帶沖撞和制動的APSO 算法（adaptive particle swarm optimization with strategy of collision and braking，APSO-WCB）兩者尋優過程進行對比，兩者的適應度值進化曲線見圖2。

圖2 兩種算法基于函數f1 的適應度值進化曲線

從適應度值進化曲線可以看出，采用APSOWCB 算法其適應度進化曲線較為光滑，說明不易于陷入局部最優，并且在進化初期具有較快的收斂特性，進化次數約為5 次即達到全局收斂，表明優化后的算法性能較好。而標準PSO 算法在迭代過程中陷入局部極值的頻率較多，而且多次迭代才能跳出局部極值陷阱。

第二測試函數是由正弦和余弦復合形成的復雜非線性多峰多谷函數，存在大量的凹陷、鞍點和波峰，可有效檢測算法的全局探索性能。傳統的優化算法很容易在尋找全局最優的過程中陷入局部最優。測試函數f2如式（6）所示，函數在區間［0，3π］的圖像見圖3。

圖3 函數f2 圖像

采用相同的算法參數設置，同樣將尋優過程中標準PSO 算法和APSO-WCB 算法的適應度值進化曲線進行分析對比，兩者的適應度值進化曲線見圖4。

圖4 兩種算法基于函數f2 的適應度值進化曲線

從適應度值變化情況來看，標準PSO 算法易陷入局部極值，且擺脫局部最優的能力較弱，最終沒能收斂于全局最優；APSO-WCB 算法收斂極快，得益于沖撞算子的應用，整個過程中沒有陷入局部極值的情況出現，而且收斂于全局最小值，其綜合效率比較高，同時也說明改進后給算法性能帶來的提升還是理想的。

求解高維最優化問題最能驗證智能優化算法的性能和效率，以下用一個典型的高維函數進一步測試改進后算法的性能。采用Shaffer 函數（記為f3）對其進行測試，其表達式為：

當n 取值較大時，該函數為一個典型的復雜高維函數，求解該函數最優值有助于驗證智能算法在解決高維度優化問題上的尋優效率，該函數最小值點位于x=（0，0，…，0），整個定義域內函數最小值為-1。探討10 維空間上該函數的最小值求解，所以n取值為10。仍然將標準PSO 算法和APSO-WCB 算法進行對比，兩者的適應度值進化曲線見圖5。從適應度函數值的變化來看，標準PSO 算法求解高維函數最優值的進化過程中，極易落入局部極值陷阱并難以逃脫，而且對該函數最優求解最終沒能收斂于全局最優點。但APSO-WCB 算法最終收斂位置非常接近全局最優點，且在進化初期就能探測到最優解鄰域，表明改進后的算法在復雜高維優化問題上效率亦有較大的提升。

圖5 兩種算法基于函數f3 的適應度值進化曲線

本研究對標準PSO 算法的慣性權重進行了動態的自適應改進，并加入對應的制動算子來提升算法的效率。同時針對算法易陷入局部極值難以逃脫的情況，引入沖撞算子加強粒子群對局部最優陷阱的逃脫能力。Matlab 環境下的測試實驗結果證明改進方法給PSO 算法帶來的性能提升是很顯著的。另外，對算法也可以采用其他方法（如混沌初始化、多種群協同等）進行優化改進，改進后的PSO 算法在解決復雜優化問題中性能較標準PSO 算法有較大提升，在群體智能算法中具有重要的地位和應用前景。