李 眩，吳曉兵，方婷婷

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

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

1 標(biāo)準(zhǔn)PSO 算法及性能提升分析

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

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

2 帶沖撞和制動(dòng)的APSO 算法

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

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

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

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

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

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

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

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

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

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

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

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

3 改進(jìn)算法性能仿真分析

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

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

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

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

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

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

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

圖3 函數(shù)f2 圖像

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

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

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

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

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

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

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