羅 華

(上海理工大學(xué) 光電信息與計(jì)算機(jī)學(xué)院，上海 200093)

一種慣性權(quán)重自適應(yīng)的粒子群優(yōu)化算法

羅 華

(上海理工大學(xué) 光電信息與計(jì)算機(jī)學(xué)院，上海 200093)

針對基本粒子群算法的早熟收斂性，在尋優(yōu)過程中易陷入局部極值。提出一種自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法，該算法利用了粒子聚集度、迭代次數(shù)來動態(tài)的改變慣性權(quán)重，以此來平衡局部尋優(yōu)能力和全局尋優(yōu)能力，使達(dá)到自適應(yīng)，并使用典型測試函數(shù)Griewank和Sphere進(jìn)行了仿真測試，以此驗(yàn)證改進(jìn)策略的效果。實(shí)驗(yàn)表明，對于多峰函數(shù)，與基本粒子群相比較，改進(jìn)的粒子群優(yōu)化算法在收斂速度和收斂精度上均高于基本粒子群算法以及一些常見的改進(jìn)算法。

粒子群優(yōu)化；自適應(yīng)；慣性權(quán)重；聚集度

粒子群算法的思想源于對鳥類覓食運(yùn)動行為的模擬，對鳥群簡化社會模型的研究。1987年，Reynolds 根據(jù)鳥類群體飛行的特點(diǎn)，提出用于模擬鳥類聚集飛行的行為，Reynolds提出了3個規(guī)則來作為鳥群個體的簡單行為：(1)避免碰撞。避免和臨近的個體相碰撞；(2)速度一致。盡量和臨近個體在速度上保持協(xié)調(diào)一致；(3)向中心聚集。盡量試圖向自己所認(rèn)為的群體中心靠近。1995年，Eberhart和Kennedy受到Biod模型的啟發(fā)，對模型進(jìn)行深入研究，提出了粒子群優(yōu)化算法[1]，粒子群算法是典型的智能優(yōu)化算法，自從提出以來，易實(shí)現(xiàn)和可調(diào)參數(shù)較少等優(yōu)點(diǎn)吸引了大批學(xué)者進(jìn)行研究，已經(jīng)逐漸應(yīng)用到很多行業(yè)當(dāng)中，但是粒子群算法本身也存在容易陷入局部極值、進(jìn)化后期的收斂速度慢、精度低、易早熟收斂等缺點(diǎn)，目前主要集中在算法的改進(jìn)和算法研究上[1-6]，所以出現(xiàn)了諸多改進(jìn)的粒子群算法，有線性遞減慣性權(quán)重策略(LDIW)[7]、非線性慣性權(quán)重策略(NLIW)[8]、模糊慣性權(quán)重策略(FIW)[9]、隨機(jī)慣性權(quán)重策略(RIW)[10]等，不同策略在實(shí)現(xiàn)起來都在一定程度上使粒子群收斂速度加快，但還是避免不了陷入局部極值中。

本文在非線性慣性權(quán)重策略基礎(chǔ)下，基于基本粒子群算法引入了慣性權(quán)重自適應(yīng)、聚集距離、迭代次數(shù)相結(jié)合的概念。并且通過經(jīng)典測試函數(shù)仿真驗(yàn)證，在迭代過程中動態(tài)改變慣性權(quán)重，使其能夠擺脫局部極值的干擾，在加快了算法收斂的速度的同時，跟其他優(yōu)化算法比起來還保持了精度。

1 基本粒子群算法和慣性權(quán)重的分析

Eberhart和Kennedy提出基本的粒子群算法如下v(t+1)v(t)+c1r1(pbestij-xij)+c2r2(gbestij-xij)

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

Shi等人在Eberhart和Kennedy提出的粒子群算法的基礎(chǔ)上在速度項(xiàng)中增加了慣性權(quán)重系數(shù)來平衡全局搜索和局部搜索能力，修改后的新的粒子群算法如[6]

v(t+1)=ωv(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestij-x(t))

(3)

位置更新公式如下

xij(t+1)=xij(t)+vij(t+1)

(4)式中，ω是慣性權(quán)重，慣性權(quán)重是最重要的進(jìn)化參數(shù)，其決定了粒子先前飛行速度對當(dāng)前飛行速度的影響程度，當(dāng)慣性權(quán)重較大時，整體的全局搜索能力加強(qiáng)，局部搜索能力減弱；當(dāng)慣性權(quán)重較小時，整體的局部搜索能力加強(qiáng)。因此可通過調(diào)整慣性權(quán)重的值來實(shí)現(xiàn)粒子全局搜索和局部搜索，恰當(dāng)?shù)恼{(diào)整慣性權(quán)重可以調(diào)高算法性能，提高尋優(yōu)能力，同時還能減少迭代次數(shù)[11]。vij(t+1)代表當(dāng)前迭代的速度，pbestij(t)和gbestij(t)分別代表個體當(dāng)前找到的最有位置和整體粒子目前找到的最優(yōu)位置；c1、c2是非負(fù)的學(xué)習(xí)因子；r1、r2是[0，1]區(qū)間的隨機(jī)數(shù)。因此，如何尋找合適的慣性權(quán)重值，使之在搜索精度和搜索速度方面起到恰當(dāng)?shù)膮f(xié)調(diào)作用，成為業(yè)界學(xué)者的一個焦點(diǎn)，主要分為線性策略和非線性策略兩種[12]。

已有線性調(diào)整和非線性慣性權(quán)重策略。即隨進(jìn)化過程，線性的減少ω的值。這樣可使算法在進(jìn)化初期探索能力較強(qiáng)，能在較大范圍的解空間內(nèi)搜索，并不斷搜索新的區(qū)域，然后到后期逐漸收斂到較好的區(qū)域并進(jìn)行更精細(xì)地搜索，以加快收斂速度[13]

ω=(ω1-ω2)×(T-t)/T+ω2

(5)

其中，ω1和ω2分別是慣性權(quán)重的初始值和終端值；T和t分別是當(dāng)前進(jìn)化代數(shù)和最大進(jìn)化代數(shù)。Shi等人的研究表明，當(dāng)ω從0.9線性減小到0.4時粒子群算法可以獲得滿意的優(yōu)化結(jié)果[14]。

為了改善遞減策略中存在的缺陷，提出了先增后減的策略[15]

(6)

經(jīng)過實(shí)驗(yàn)分析，像這樣的先增后減的策略，前期有較快的收斂性，后期的局部搜索能力也不錯。

2 本文提出的慣性權(quán)重調(diào)整策略

本文提出的調(diào)整策略利用到了已有的平均聚集距離和最大聚集距離[8]

(8)

(9)

其中，Mean代表平均聚集距離；Max代表最大聚集距離；m代表粒子群的粒子個數(shù)；D代表每個粒子的維數(shù)；pid代表粒子群目前搜索到的最優(yōu)位置；xid代表每個粒子目前搜索到的最優(yōu)位置。

在整個粒子群尋優(yōu)過程中迭代次數(shù)也在影響著最后尋優(yōu)的結(jié)果，所以本文在改進(jìn)的時候就利用了迭代次數(shù)對尋優(yōu)過程的影響，將迭代的影響與聚集度結(jié)合起來，來實(shí)現(xiàn)慣性權(quán)重的動態(tài)調(diào)整。由于傳統(tǒng)的非線性策略要么只是考慮到迭代對算法的影響，要么就利用迭代次數(shù)再給定一個控制因子來動態(tài)的調(diào)整慣性權(quán)重，這樣雖然能優(yōu)化算法，但沒有真正的智能化，利用聚集距離來及時的判斷與全局最優(yōu)的距離，如果最大聚集距離Mean過大，說明整個粒子群是分散的，就需要增大ω，增強(qiáng)粒子群的全局搜索能力，相反，若Mean在減小，說明粒子群整體在收斂，這時就要減小ω，增強(qiáng)它的局部搜索能力。在此，提出一個定理

(10)

(11)

步驟 1 隨機(jī)初始化每個粒子的位置和速度;

步驟 2 先計(jì)算每個粒子的適應(yīng)值，然后初始化個體極值和全局極值;

步驟 3 根據(jù)式(8)，式(9)計(jì)算平均聚集距離和最大聚集距離，根據(jù)式(10)計(jì)算出聚集距離變化率，再根據(jù)式(11)計(jì)算慣性權(quán)重ω;

步驟 4 根據(jù)式(3)，式(4)來更新粒子的速度與位置，迭代次數(shù)加1;

步驟 5 若未滿足循環(huán)結(jié)束的條件，則繼續(xù)步驟2，若滿足，則退出循環(huán)，并輸出全局最優(yōu)值。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證改進(jìn)的可行性，使用了兩個最典型的測試函數(shù)進(jìn)行實(shí)例計(jì)算并且與基本粒子群算法作比較，來證明改進(jìn)的效果。在實(shí)驗(yàn)中，取粒子數(shù)m=30，學(xué)習(xí)因子c1=c2=1.496 2，D=50，改進(jìn)的粒子群算法和基本粒子群算法參數(shù)一樣，分別迭代500次，測試函數(shù)如下。

表1 實(shí)驗(yàn)所用測試函數(shù)和相關(guān)參數(shù)

(1)Griewank函數(shù)

(12)

Griewank 函數(shù)仿真結(jié)果如下。

與基本粒子群相比，改進(jìn)的粒子群算法收斂速度更快了，在迭代約為10次時便可達(dá)到收斂，找到最優(yōu)解，算法尋優(yōu)效果大幅加強(qiáng)。

圖2 改進(jìn)的粒子群算法尋優(yōu)過程

(2)Sphere函數(shù)

(13)

圖3 基本粒子群算法尋優(yōu)過程

圖4 改進(jìn)的粒子群算法尋優(yōu)過程

圖3與圖4是有Sphere函數(shù)仿真測試而得，兩圖相比較可以看出，改進(jìn)的粒子群算法與基本粒子群收斂精度在后期基本一致，但收斂的速度遠(yuǎn)高于基本粒子群算法的收斂速度，改進(jìn)粒子群算法在迭代約為3次便已尋找到最優(yōu)值0，而基本粒子群在將近30次在尋找到。

4 結(jié)束語

從仿真結(jié)果來看，改進(jìn)的粒子群算法不論在收斂速度還是精度上均遠(yuǎn)高于基本粒子群算法，所以可證明本文所提出的利用聚集距離的變化和迭代次數(shù)對尋優(yōu)的影響來實(shí)現(xiàn)改進(jìn)粒子群算法的方法是可行的。將慣性權(quán)重用非線性的方式表示同時利用聚集距離的變化，通過自適應(yīng)的調(diào)整，來使整個粒子群尋優(yōu)時可不斷的修正目標(biāo)值，防止陷入局部收斂，使整個群體更具有了目的性。同時本文提出的改進(jìn)算法在精度上比起基本粒子群算法也有所提升，實(shí)驗(yàn)證明改進(jìn)的算法在高緯時尋優(yōu)效果也比較穩(wěn)定，優(yōu)化效果明顯。

[1] Kennedy J,Eberhart R.Particle swarm optimization[C].IEEE lnt Conf on Neural Networks.Piscataway:IEEE Service Center，1995:1942-1948.

[2] 李麗,牛奔.粒子群優(yōu)化算法[M].北京:冶金工業(yè)出版社,2009.

[3] 潘峰,李位星,高琪,等.粒子群優(yōu)化算法與多目標(biāo)優(yōu)化[M].北京:北京理工大學(xué)出版社,2013.

[4] Salomon R.Reevaluating genetic algorithm performance under coordinate ro- tation of benchmark functions[J].Bio Systems,1996(39):263-278.

[5] Frans V D B. An analysis of particle swarm optimizers[J]. Particle Swarm Optimization,2002(5)：442-447.

[6] By Y, Eberhart R. Parameter selection in particle swarm optimization[C].Proceedings of the 7th Annual Conference on Evolutionary Programming,2010.

[7] 任子暉,王堅(jiān).一種動態(tài)改變慣性權(quán)重的自適應(yīng)粒子群算法[J].計(jì)算機(jī)科學(xué),2009,36(2):227-229.

[8] 李寧,孫德寶,岑翼剛.帶變異算子的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(17):12-14.

[9] 徐志烽.一種多粒子群的協(xié)同優(yōu)化算法[J].現(xiàn)代電子技術(shù),2007,30(1):131-133.

[10] 陳紅州,顧國昌,康望星.一種具有感覺的微粒群算法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(8):1299-1305.

[11] 竇全勝,周春光,徐中宇,等.動態(tài)優(yōu)化環(huán)境下的群核進(jìn)化粒子群優(yōu)化方法[J].計(jì)算機(jī)研究與發(fā)展,2006,43(1):89-95.

[12] 姚耀中,徐玉如.粒子群優(yōu)化算法分析[J].哈爾濱工程大學(xué)學(xué)報,2007,28(11):1242-1246.

[13] 邢萬波,楊圣奇,王樹平,等.一種改進(jìn)的自適應(yīng)鄰域粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2008,28(12):3055-3057,3088.

[14] Mendes R,Kenedy J.The full informed particle swarm: simpler maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[15] Bask S,Suganthan P N.A novel concurrent particle swarm optimization[C].Piscataway,NJ:Proceedings of the Congress on Evolutionary Computation,IEEE Press,2004.

A Inertia Weight Adaptive Particle Swarm Optimization Algorithm

LUO Hua

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093, China)

Mainly for the basic particle swarm algorithm of premature convergence, Easy to fall into local minima in the optimization process. In this paper, a particle swarm optimization algorithm of adaptive inertia weight, The algorithm use the particle concentration, The number of iterations to dynamically changing inertia weight, In order to balance the local optimization and global optimization ability, Make to achieve adaptive, And use the typical test functions Griewank and Sphere has carried on the simulation test, To verify the improvement strategy. simulation results show, For multimodal function, Compared with the basic particle swarm, The improved particle swarm optimization algorithm in convergence speed and higher than the basic particle swarm algorithm convergence precision and some of the common algorithm.

particle swarm optimization; adaptive; inertia weight; degree of aggregation

2016- 04- 16

羅華(1992-)，男，碩士研究生。研究方向：群智能等。

10.16180/j.cnki.issn1007-7820.2017.03.009

TP301.6

A

1007-7820(2017)03-030-04