改進的粒子群優(yōu)化算法

閆文靜, 鄒書蓉, 張洪偉

（成都信息工程學院計算機學院,四川成都 610225）

0 引言

粒子群優(yōu)化算法（Particle Swarm Optimization,PSO）是由Kennedy和Eberhart（1995年）首次提出的一種基于迭代的尋優(yōu)算法[1],源于對生物界中鳥群覓食行為的研究,是一個基于群體智能（Swarm Intelligence,SI）的優(yōu)化算法。PSO算法具有簡潔性,易于實現(xiàn),收斂速度快,需要調(diào)節(jié)的參數(shù)少等優(yōu)點,一經(jīng)提出便得到快速的發(fā)展。PSO算法已經(jīng)在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓練、模式分類、模糊系統(tǒng)控制、求解大規(guī)模組合優(yōu)化問題等各個領(lǐng)域的取得了大量的有效成果[2]。

在對PSO算法的研究過程中發(fā)現(xiàn)其存在易于陷入局部最優(yōu)及早熟收斂等缺陷,針對這些問題許多學者提出了一些改進方案,例如w線性遞減策略[3],通過反復(fù)試驗,建議w=0.9線性遞減到0.4的策略,這樣使得粒子群算法早期具有良好的全局搜索能力,能快速定位到接近全局最優(yōu)點的區(qū)域,后期則具有良好的局部搜索能力,能精確得到全局最優(yōu)解。雜交PSO模型[4]將進化算法中的交叉操作引入PSO算法,使后代繼承了雙親粒子的優(yōu)點,加強了粒子間區(qū)域的搜索能力,有效擺脫局部最優(yōu)。混沌粒子群優(yōu)化模型[5],以目前整個粒子群所搜索到的最優(yōu)位置為基礎(chǔ),利用混沌運動的遍歷性去產(chǎn)生一個混沌序列,然后將產(chǎn)生序列中的最優(yōu)位置的粒子隨機地代替目前粒子群中的一個粒子,這樣可以使粒子能有效地擺脫局部極值點,提高算法尋找全局最優(yōu)點的能力。免疫粒子群優(yōu)化算法[6]中機體能特異的識別“非己”和“自己”的刺激,保留記憶反應(yīng)的能力,可以避免粒子群算法陷入局部最優(yōu)的缺點。

針對PSO算法易于陷入局部最優(yōu)的缺陷,提出了一種在引入自適應(yīng)慣性權(quán)重基礎(chǔ)上的新的進化模型的粒子群優(yōu)化算法（New mode Particle Swarm Optimization,NPSO）。通過仿真實驗與其他改進算法的比較表明,提出的新算法具有很好的收斂精度,能有效避免陷入局部最優(yōu)及早熟收斂現(xiàn)象。

1 粒子群算法的基本原理

粒子群優(yōu)化算法的基本概念源于鳥群捕食的過程,在PSO算法中,每個優(yōu)化問題的解都看作是搜索空間中一個粒子,所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)度值。PSO算法先初始化一群隨機粒子,每個粒子的屬性由速度vi（vi=（v1,v2,…,vD））,位置 xi（xi=（x1,x2,…,xD））來描述。在下一個時間點到來的時候,所有的粒子都是通過跟蹤兩個“極值”來更新其速度,這兩個極值分別為個體局部極值（pbest）即粒子自身找到的最優(yōu)解;全局極值（gbest）即整個群體找到的最優(yōu)解。再通過優(yōu)化問題所決定的適應(yīng)度函數(shù)去評價新的粒子的優(yōu)劣程度。粒子更新速度和位置公式如下:

2 粒子群算法的改進

2.1 PSO算法局部收斂性判斷

全局最優(yōu)值取決于個體最優(yōu)值的變化,在迭代過程中,當前迭代的全局最優(yōu)值總是要優(yōu)于或至少等于上一次迭代所得的全局最優(yōu)值。PSO算法在迭代過程中,粒子都是通過跟蹤兩個極值更新自己。即在找到這兩個最優(yōu)值后,粒子按照式（1）和（2）確定自己下一時刻的速度和位置。常規(guī)的粒子群算法中粒子都是向著一個方向在飛行,假如在飛行過程中遇到了局部極值點,全體粒子的速度將快速的下降為零從而聚集在局部最優(yōu)停止飛行,這樣粒子就陷入了局部極值點。為此改進PSO算法時,引入進化速度因子h,如果優(yōu)化目標是尋極大值,F（gbestk）≥F（gbestk-1）,則定義h=F（gbestk-1）/F（gbestk）;反之,F（gbestk）≤F（gbestk-1）,則定義進化速度因子h=F（gbestk）/F（gbestk-1）;于是

根據(jù)上面的定義,進化速度因子0＜h≤1。在整個迭代過程中進化速度因子h的值與進化速度成反比,即h值越小,進化速度越快。一定迭代次數(shù)后,若h=1,代表算法找到了最優(yōu)解或者停滯陷入了局部最優(yōu)。此時將得到的最優(yōu)解gbest與理論全局最優(yōu)解（或期望最優(yōu)解）做比較,可以判斷出此時得到的最優(yōu)解是否為陷入局部最優(yōu)的解。大量的實驗數(shù)據(jù)表明,h大于Δ（如0.2～0.5）時判斷粒子陷入局部最優(yōu)的可能性最大,在此應(yīng)設(shè)法使粒子跳出局部最優(yōu)的位置,使粒子能在搜索空間里繼續(xù)搜索尋優(yōu)。

2.2 粒子的聚集度

根據(jù)上面的定義粒子聚集度因子0＜s≤1,s值能有效反映當前所有粒子的聚集程度,同時也可反映出粒子的多樣性。大量實驗數(shù)據(jù)表明s的值與粒子的聚集程度成正比,即s值越大,粒子群的聚集度越大,這樣表明粒子多樣性越小。若s的值為1,則斷定粒子群中的所有粒子具有同一性,如果驗證此時的粒子為陷入局部最優(yōu),粒子將很難跳出該極值點。

2.3 自適應(yīng)的慣性權(quán)值

慣性權(quán)重w是PSO算法中的一個重要參數(shù),被用于調(diào)節(jié)粒子過去對現(xiàn)在的影響程度。Shi和Eberhart研究慣性權(quán)重w對優(yōu)化性能的影響發(fā)現(xiàn):較大的慣性權(quán)重能增強全局探索能力,較小的慣性權(quán)重能提高局部發(fā)掘能力有利于算法收斂。為此進行了大量的研究工作,先后提出了隨機慣性權(quán)值（RIW）策略[7]、線性遞減權(quán)值（LDW）策略[8]和模糊慣性權(quán)值（FIW）策略[9]。目前比較流行的做法是線性遞減策略LDW,公式如下所示:

上式中,ws和we表示慣性因子的初始值和結(jié)束值,t表示當前次數(shù),tmax表示迭代的最大次數(shù)。在優(yōu)化方程性能上有明顯效果,但是LDW中的w只與迭代的次數(shù)線性相關(guān),因此不能適應(yīng)算法運行中的非線性變化、復(fù)雜等特性。

研究w發(fā)現(xiàn),慣性權(quán)重的值應(yīng)該伴隨著粒子群進化速度和粒子的聚集程度而變化[10],所以w可以表示為h和s的函數(shù),即 w=f（h,s）。分析可知如果粒子群的進化速度降低時,此時減小 w的值,使算法在小空間范圍內(nèi)進行搜索,這樣能較快地找到算法的最優(yōu)解。如果粒子群的進化速度加快時,加大 w的值,使得粒子群在較大的空間內(nèi)持續(xù)搜索尋優(yōu)。若粒子在搜索空間里分布的比較分散,此時粒子群就不易陷入到局部最優(yōu),但是伴隨著粒子群聚集度的逐漸升高,粒子將很容易陷入到局部最優(yōu),此時為提高粒子群的全局尋優(yōu)能力應(yīng)及時地加大粒子群搜索的空間。根據(jù)上面的分析可知,w值大小應(yīng)該伴隨著粒子的聚集度的加快而增大,相應(yīng)的,也應(yīng)伴隨著粒子群進化速度的減慢而減小,w可以表示為:

wini為w 的初始值,通常 wini的值為1。由于0＜h≤1,0＜s≤1,wini-wh＜w ＜wini+ws。

2.4 改進的粒子群進化模型

為了使PSO算法避免“早熟”收斂現(xiàn)象[11],提出將陷入局部最優(yōu)的粒子向群體最優(yōu)的反方向飛行,這樣便于粒子跳出局部最優(yōu)并在解空間大范圍飛行尋優(yōu)。其速度迭代公式不變,位置迭代進化更新公式如下所示:

式（7）即是改變粒子尋優(yōu)的飛行方向[12],使粒子能在大范圍開拓搜索空間中尋優(yōu)。提出的改進的粒子群優(yōu)化算法的流程如下,粒子群迭代先是按照標準模型即式（1）、（2）進化,判斷h值的大小,若發(fā)現(xiàn)粒子陷入局部收斂時,立即使用式（1）、（7）迭代進化,使粒子能及時跳出局部最優(yōu),在解空間里大范圍搜索尋優(yōu)。這樣處理可以有效地防止“早熟”收斂,提高算法的全局收斂性能。

3 算法流程

綜上所述,新算法流程如下:

（1）初始化。設(shè)定PSO算法的參數(shù)（N,c1,c2,ws和we等）,隨機產(chǎn)生初始種群及每個粒子的速度和位置,計算每個粒子的適應(yīng)值并排序。并初始化種群的全局最優(yōu)值和個體最優(yōu)值,并將粒子的pbest設(shè)置為當前位置,gbest設(shè)置為初始群體中最佳粒子的位置。

（2）根據(jù)式（1）、（2）更新每個粒子的速度和位置。

（3）重新計算粒子的適應(yīng)度,按適應(yīng)值排序,按照式（3）、（4）、（6）計算新的 h、s和w 。

（4）根據(jù)式（3）判斷進化速度因子h值的大小,若大于Δ時,轉(zhuǎn)向（4）,否則轉(zhuǎn)向（5）

（5）按式（1）、（7）更新每個粒子的速度和位置。

（6）若算法未達到最大允許迭代次數(shù),迭代次數(shù)I=I+1返回（2）,否則轉(zhuǎn)到（6）。

（7）停止優(yōu)化并輸出結(jié)果。

4 算法仿真實驗

表1給出了實驗中運用4個經(jīng)典測試函數(shù),用這4個函數(shù)來仿真測試驗證文中所提出算法的尋優(yōu)能力,并將結(jié)果與標準PSO 、LDWPSO算法、NPSO算法進行對比分析。

表1 測試函數(shù)

f 1至 f4函數(shù)的最優(yōu)值都是0,測試時4種算法的種群粒子數(shù)各取50,LDWPSO中慣性權(quán)重ws=0.8,we=0.1,c1=c2=2,h=0,s=0。測試函數(shù)維數(shù)為30,最大迭代次數(shù)500,測試3種算法所達到的精度。所有仿真實驗都是通過Java語音編程,并對仿真結(jié)果作對比。對3種算法分別進行50次實驗,表2給出了測試4個經(jīng)典函數(shù)所達到精度的平均值。

表2 4個經(jīng)典函數(shù)的測試結(jié)果

從表2可以看出,新算法相對于其他兩個算法在平均最佳適應(yīng)值上有明顯提高,這說明新算法的優(yōu)化能力得到了明顯的提高。為了反映新算法性能的改善,對這4個經(jīng)典的函數(shù)分別進行250次迭代,算法收斂圖,如圖1～4所示。

圖1 Sphere函數(shù)收斂示意圖

圖3 Rastrigrin函數(shù)收斂示意圖

圖2 Griewank函數(shù)收斂示意圖

圖4 Rosenbrock函數(shù)收斂示意圖

從圖1～4經(jīng)典函數(shù)的收斂圖可以直接看出,NPSO算法明顯優(yōu)于基本粒子群算法和LDWPSO算法。算法的收斂性優(yōu)于經(jīng)典算法,充分體現(xiàn)了改進的優(yōu)勢。

5 結(jié)束語

為有效抑制和避免PSO算法早熟收斂,提出的新進化模式的粒子群優(yōu)化算法原理為:在采用自適應(yīng)慣性權(quán)重的基礎(chǔ)上,通過判斷粒子是否陷入局部最優(yōu),對陷入局部最優(yōu)的粒子群采用新的進化模型,從而使粒子迅速跳出局部最優(yōu),在更大的空間里尋優(yōu),這樣可以保證算法能夠有效避免早熟收斂和陷入局部最優(yōu)。通過對4個經(jīng)典函數(shù)的測試,顯示出改進的粒子群優(yōu)化算法具有更好的收斂精度,能有效避免粒子陷入局部最優(yōu)。若應(yīng)用到實際優(yōu)化問題上將起到很好的推動作用。

[1] KENNEDY J,EBERHART R C.Particle Swarm Optimization Proceedings of 1995[C].IEEE International Conference on Neural Networks,1995:1942-1948.

[2] Eberhar t RC,Shi Y H.Particle swarm optimization:developments,applications and resources[A].Proceedings of the IEEE Congress on Evolutionary Computation[C].Piscataway,USA:IEEE Service Center,2001.

[3] Shi Y,Eberhart RC.Empirical study of particle swarm optimization[C].Proceedingsof the IEEE Congresson Evolutionary Computation,2009.

[4] Wetter M.and Wright J.A comparison of deterministic and probabilistic optimization algorithms for nonsmoth simulation-based optimization[J].Building and Environment.2006.

[5] 李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用,2007,14.

[6] 段富,蘇同芬.免疫粒子群算法的改進及應(yīng)用[J].計算機應(yīng)用,2010,30:1883-1884.

[7] R Eberhart,Y Shi.Tracking and optimizing dynamic systems with particle swarms[A].The IEEE Congresson Evolutionary Computation[C].San Francisco,USA:IEEE,2001.

[8] Y Shi,R Eberhart.Empirical study of particle swarm optimization[A].International Conference on Evolutionary Computation[C].Washington,USA:IEEE,2002.

[9] Y Shi,R Eberhart.Fuzzy adaptive swarm optimization[A].The IEEE Congress on Evolutionary Computation[C].San Francisco,USA:IEEE,2001.

[10] 劉懷亮,高鷹,許若寧,等.一種新的改進粒子群優(yōu)化方法[J].計算機工程與應(yīng)用,2010,46.

[11] 李寧,鄒彤,孫德寶,等.基于粒子群的多目標優(yōu)化算法[J].計算機工程與應(yīng)用,2005,41.

[12] 俞歡軍.混合粒子群游湖算法研究[J].信息與控制,2005,34.