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

羅 華

(上海理工大學 光電信息與計算機學院，上海 200093)

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

羅 華

(上海理工大學 光電信息與計算機學院，上海 200093)

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

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

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

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

1 基本粒子群算法和慣性權重的分析

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

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

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

(5)

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

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

(6)

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

2 本文提出的慣性權重調整策略

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

(8)

(9)

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

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

(10)

(11)

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

步驟 2 先計算每個粒子的適應值，然后初始化個體極值和全局極值;

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

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

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

3 實驗與分析

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

表1 實驗所用測試函數(shù)和相關參數(shù)

(1)Griewank函數(shù)

(12)

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

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

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

(2)Sphere函數(shù)

(13)

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

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

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

4 結束語

從仿真結果來看，改進的粒子群算法不論在收斂速度還是精度上均遠高于基本粒子群算法，所以可證明本文所提出的利用聚集距離的變化和迭代次數(shù)對尋優(yōu)的影響來實現(xiàn)改進粒子群算法的方法是可行的。將慣性權重用非線性的方式表示同時利用聚集距離的變化，通過自適應的調整，來使整個粒子群尋優(yōu)時可不斷的修正目標值，防止陷入局部收斂，使整個群體更具有了目的性。同時本文提出的改進算法在精度上比起基本粒子群算法也有所提升，實驗證明改進的算法在高緯時尋優(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)化算法與多目標優(yōu)化[M].北京:北京理工大學出版社,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] 任子暉,王堅.一種動態(tài)改變慣性權重的自適應粒子群算法[J].計算機科學,2009,36(2):227-229.

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

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

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

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

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

[13] 邢萬波,楊圣奇,王樹平,等.一種改進的自適應鄰域粒子群優(yōu)化算法[J].計算機應用,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