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

閆文靜, 鄒書蓉, 張洪偉

（成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川成都 610225）

0 引言

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

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

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

1 粒子群算法的基本原理

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

2 粒子群算法的改進(jìn)

2.1 PSO算法局部收斂性判斷

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

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

2.2 粒子的聚集度

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

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

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

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

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

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

2.4 改進(jìn)的粒子群進(jìn)化模型

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

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

3 算法流程

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

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

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

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

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

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

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

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

4 算法仿真實(shí)驗(yàn)

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

表1 測(cè)試函數(shù)

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

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

從表2可以看出,新算法相對(duì)于其他兩個(gè)算法在平均最佳適應(yīng)值上有明顯提高,這說(shuō)明新算法的優(yōu)化能力得到了明顯的提高。為了反映新算法性能的改善,對(duì)這4個(gè)經(jīng)典的函數(shù)分別進(jìn)行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)了改進(jìn)的優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

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

[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] 段富,蘇同芬.免疫粒子群算法的改進(jìn)及應(yīng)用[J].計(jì)算機(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] 劉懷亮,高鷹,許若寧,等.一種新的改進(jìn)粒子群優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46.

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

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