帶沖撞和制動的自適應粒子群優(yōu)化算法

李 眩，吳曉兵，方婷婷

（銅陵職業(yè)技術學院經(jīng)貿(mào)系，安徽銅陵 244061）

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

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

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

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

2 帶沖撞和制動的APSO 算法

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

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

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

制動算子變化規(guī)律按照式（2）進行調(diào)整：

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

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

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

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

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

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

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

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

3 改進算法性能仿真分析

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

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

圖1 函數(shù)f1 三維圖像

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

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

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

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

圖3 函數(shù)f2 圖像

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

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

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

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

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

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

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