跟隨變異立子擾動變化的慣性權(quán)重PSO算法

【信息科學(xué)與控制工程】

跟隨變異粒子擾動變化的慣性權(quán)重PSO算法

邢煥革1，衛(wèi)一熳1,2

(1.海軍工程大學(xué)，武漢430033； 2. 68215部隊,青海 民和810800)

摘要：針對困擾粒子群算法“早熟”和收斂慢的2大難題，提出了一種跟隨變異粒子擾動變化的慣性權(quán)重策略，將粒子群體一致性變化趨勢與粒子變異操作相關(guān)聯(lián)，以此來增加粒子的多樣性；根據(jù)粒子變異程度的大小對慣性權(quán)重作出相應(yīng)調(diào)整，使粒子在提高全局尋優(yōu)能力的同時，又很好地改善了收斂精度和收斂速度，避免因慣性權(quán)重單邊非線性變化而導(dǎo)致粒子群全局尋優(yōu)能力穩(wěn)定性不佳的問題。仿真對比表明，改進(jìn)的算法較好地避開了局部最優(yōu)解的干擾問題，具有收斂速度快、尋優(yōu)精度高等優(yōu)勢。

關(guān)鍵詞：變異粒子；慣性權(quán)重；粒子群算法

收稿日期：2014-09-22

基金項目：軍隊研究生課題(2011JY002-422)的資助

作者簡介：邢煥革(1967—)，男，副教授，主要從事裝備保障指揮、軍事復(fù)雜網(wǎng)絡(luò)系統(tǒng)研究;衛(wèi)一熳(1986—)，女，研究生，主要從事裝備保障指揮研究。

doi:10.11809/scbgxb2015.01.030

中圖分類號：TP18

文章編號：1006-0707(2015)01-0106-05

本文引用格式：邢煥革，衛(wèi)一熳.跟隨變異粒子擾動變化的慣性權(quán)重PSO算法[J].四川兵工學(xué)報，2015(1):106-110.

Citation format:XING Huan-ge, WEI Yi-man.Inertia Weight Particle Swarm Optimization Algorithm with Mutation Particle Disturbance Changes[J].Journal of Sichuan Ordnance,2015(1):106-110.

Inertia Weight Particle Swarm Optimization Algorithm with

Mutation Particle Disturbance Changes

XING Huan-ge1, WEI Yi-man1,2

(1.Navy University of Engineering, PLA, Wuhan 430033, China;

2.The 68215thTroop of PLA, Minhe 810800, China)

Abstract:Aiming at the problems of the particle swarm algorithm “premature” and slow convergence, the inertia weight adjustment strategy with the mutation particles disturbance change was presented. In order to increase the diversity of the particles, the consistent of the particles group changing tendency was related with the particle mutation. The inertia of the weight of the particles was put forward with a corresponding adjustment according to the degree of variation the mutation particles, and the global searching ability of the particles is not only improved, but also that the convergence precision and speed of the particles are advanced, the poor stability problem of the particles swarm optimization ability, which is generated due to the inertia weight unilateral nonlinear change, is avoided. Simulation results show that the improved algorithm has the advantages of fast convergence speed, high precision optimization and so on.

Key words: mutation particle; inertia weight; particle swarm optimization

粒子群算法(particle swarm optimization,PSO)是一種群體智能優(yōu)化算法[1]。該算法以其簡單、調(diào)整參數(shù)少、容易實現(xiàn)等優(yōu)勢已被廣泛運用于函數(shù)優(yōu)化、模式識別、系統(tǒng)控制等領(lǐng)域。然而，該算法在實現(xiàn)過程中常會陷入局部尋優(yōu)，容易出現(xiàn)“早熟”現(xiàn)象，同時還會產(chǎn)生收斂速度較慢等問題[2,3]。針對這些不足，許多學(xué)者提出了很多改進(jìn)方案，歸納起來有：慣性權(quán)重改進(jìn)算法[4]、學(xué)習(xí)因子改進(jìn)算法[5]、拓?fù)浣Y(jié)構(gòu)改進(jìn)算法[6]、混合算法[7]、小生境PSO改進(jìn)算法[8]、離散型PSO改進(jìn)算法等[9]。以上算法僅在某一方面改善了粒子群算法的不足，但是要想到達(dá)全局尋優(yōu)，又不出現(xiàn)“早熟”現(xiàn)象，而且收斂速度還要快，需要通過與其他算法或技術(shù)融合在一起才能實現(xiàn)整體尋優(yōu)效果。

為了進(jìn)一步改善粒子群算法的不足，近年來，進(jìn)化算法中的變異操作也引入到粒子群算法之中。該方法通過保持種群的多樣性來避免算法陷入局部尋優(yōu)，在一定程度上增強了算法的全局尋優(yōu)能力。例如文獻(xiàn)[10]中在改善算法早熟收斂的問題上，對群體粒子的最優(yōu)解采取隨機擾動策略，使其變異，從而提高了全局尋優(yōu)能力，避免算法陷入局部尋優(yōu)。但該方法在進(jìn)行變異操作時采用的是單一均勻變異方式，減弱了粒子的逃逸能力，導(dǎo)致粒子的多樣性變化不足，致使全局尋優(yōu)能力不強。

針對以上不足，本文提出一種跟隨變異粒子擾動變化的慣性權(quán)重PSO算法。該算法引入了粒子的變異操作，將粒子群體一致性變化趨勢與粒子變異操作相關(guān)聯(lián)。在整個尋優(yōu)迭代過程中，一旦粒子趨于一致，則對整個粒子群產(chǎn)生變異操作，從而增加了粒子的多樣性。同時，根據(jù)粒子變異程度的大小對慣性權(quán)重作出相應(yīng)調(diào)整，使粒子在提高全局尋優(yōu)能力的同時，又很好地改善了收斂精度和收斂速度，避免因慣性權(quán)重單邊非線性變化而導(dǎo)致粒子群全局尋優(yōu)能力穩(wěn)定性不佳的問題。

1標(biāo)準(zhǔn)粒子群算法[11]

在N維的搜索空間里，有M個粒子組成的群體，其中第i個粒子表示為一個N維的向量xi=(xi1,xi2,…,xiN)，i=1,2,…,M。即第i個粒子在N維搜素空間里的位置是xi，每個粒子的位置都是一個潛在的解。將這個潛在的解代入目標(biāo)函數(shù)，就可計算出其對應(yīng)的適應(yīng)度值，根據(jù)適應(yīng)度值的大小來衡量解的優(yōu)劣。設(shè)第i個粒子的“飛行”速度用一個N維的向量表示為vi=(vi1,vi2,…,viN)，i=1,2,…,M。在迭代過程中，第i個粒子搜索到的當(dāng)前個體粒子最優(yōu)位置為pi=(pi1,pi2,…,piN)，i=1,2,…,M，粒子群搜索到的當(dāng)前整體最優(yōu)位置為pq=(pq1,pq2,…,pqN)。粒子通過追蹤個體和整體粒子當(dāng)前的最優(yōu)位置來更新自己的位置和速度。

vij=wvij+c1r1(pij-xij)+c2r2(pqj-xij)

(1)

xij=xij+viji=1,2,…,M；j=1,2,…,N

(2)

式中：w稱為慣性權(quán)重，影響著粒子的收斂速度，大量研究表明，較大的w全局尋優(yōu)能力較強，較小的w局部尋優(yōu)能力較強；c1和c2是學(xué)習(xí)因子，可以調(diào)整個體最優(yōu)和群體最優(yōu)的比例大小，使粒子具有向群體最優(yōu)個體學(xué)習(xí)的能力，通常c1和c2均取2；r1和r2是0～1的隨機數(shù)。

2跟隨變異粒子擾動變化的慣性權(quán)重PSO算法

2.1算法思想

通過對標(biāo)準(zhǔn)PSO算法的研究發(fā)現(xiàn)，眾多學(xué)者認(rèn)為慣性權(quán)重w的確定對算法性能和效率的提高起著至關(guān)重要的作用。較大的w全局尋優(yōu)最好，搜索速度快，但收斂精度較低；較小的w局部搜索能力強，收斂精度較高。經(jīng)過實驗證明，無論是標(biāo)準(zhǔn)PSO算法中w線性遞減策略，還是文獻(xiàn)[10]中算法中w的非線性單邊變化慣性權(quán)重策略，其簡單、直觀的特點，在尋優(yōu)過程中有較好的表現(xiàn)，但沒能充分協(xié)調(diào)好PSO算法的全局和局部搜索能力。隨著w的減小，粒子在趨于一致的同時，很容易陷入局部尋優(yōu)無法跳出。為克服以上不足，充分運用w的特性，引入進(jìn)化算法中的粒子變異思想，采取跟隨變異粒子擾動變化的慣性權(quán)重策略來改善PSO算法。其基本思想是：在尋優(yōu)過程中，一旦粒子趨于一致時，對粒子就進(jìn)行擾動操作，使粒子發(fā)生變異，以便粒子在搜索空間內(nèi)保持多樣性特點，從而避免了粒子陷入局部尋優(yōu)，消除算法“早熟”現(xiàn)象；同時，根據(jù)粒子變異程度的大小對慣性權(quán)重作出相應(yīng)調(diào)整，使改進(jìn)后的算法在全局尋優(yōu)能力上更加穩(wěn)定。

2.2體方法

根據(jù)以上算法的基本思想，本文將針對PSO算法中粒子容易陷入局部尋優(yōu)、出現(xiàn)“早熟”現(xiàn)象，以及收斂速度慢等問題提出的具體方法是：在尋優(yōu)過程中首先判斷粒子是否趨于一致，如果趨于一致，則在搜索范圍內(nèi)對粒子進(jìn)行隨機擾動操作，以增加粒子的多樣性，使其跳出局部尋優(yōu)；然后根據(jù)變異粒子擾動的程度大小改變算法的慣性權(quán)重，這樣不僅提高了算法尋優(yōu)搜索能力，而且使算法在全局尋優(yōu)能力上更加穩(wěn)定，同時還加快了單次迭代尋優(yōu)算法的收斂速度；最后，通過尋優(yōu)結(jié)果收斂性判斷，即可得到最優(yōu)解。

1) 粒子趨于一致性判定方法

在PSO算法中，粒子一致的判定直接影響著最優(yōu)解的確定。如何判定粒子趨于一致是關(guān)系到算法搜尋到目標(biāo)函數(shù)最優(yōu)解的關(guān)鍵，本文將根據(jù)粒子散布位置的相似度來判斷粒子是否趨于一致。具體方法是通過粒子xi散布的均方差來判斷粒子是否趨于一致，其公式表示為

(3)

式中：k是表示粒子數(shù)量；d表示粒子散布的均方差。當(dāng)d小于一定閾值時，粒子趨于一致。

2) 粒子變異操作處理方法

隨著PSO算法迭代次數(shù)的增加，粒子趨于一致，出現(xiàn)“早熟”現(xiàn)象，此時算法很可能陷入局部尋優(yōu)狀態(tài)。對此，本文引入變異操作思想，即對當(dāng)前粒子狀態(tài)施加擾動，并確保變異后的粒子狀態(tài)處在搜索范圍內(nèi)。其擾動操作可用下式表示

xinew=xiold+δ

(4)

式中：δ是隨機擾動量；xinew表示變異操作后的粒子狀態(tài)。

3) 慣性權(quán)重的變化處理方法

在慣性權(quán)重的改進(jìn)方案研究上，大多數(shù)文獻(xiàn)是通過迭代次數(shù)的增加對慣性權(quán)重采用線性或非線性單邊變化策略，雖然在一定程度上平衡了粒子局部和全局尋優(yōu)能力，但全局尋優(yōu)能力的穩(wěn)定性不佳。本文將采用跟隨變異粒子擾動程度來調(diào)整慣性權(quán)重的大小，使算法在全局尋優(yōu)能力上更加穩(wěn)定，同時還加快了單次迭代尋優(yōu)算法的收斂速度。其公式表示為

(5)

慣性權(quán)重函數(shù)w的變化曲線如圖1所示。

圖1　慣性權(quán)重w的變化曲線

從圖1可以看出，w值是在0～1的范圍內(nèi)變化。在單次尋優(yōu)過程中，隨著迭代次數(shù)的增加，粒子趨于一致，粒子相似度增加，粒子散布減小。當(dāng)小于給定的閾值時，就可認(rèn)為粒子趨于一致，w隨之減小，此時對粒子進(jìn)行變異操作，使粒子在搜索范圍內(nèi)隨機散布，以此增加粒子的多樣性，同時調(diào)整w的大小，使之跟隨變異粒子進(jìn)行操作，再一次進(jìn)入全局尋優(yōu)狀態(tài)。經(jīng)過多次這樣的循環(huán)，直到滿足最優(yōu)收斂條件，得到最優(yōu)解，尋優(yōu)過程結(jié)束。

4)尋優(yōu)結(jié)果收斂性判斷方法

判斷算法是否收斂，是確定目標(biāo)函數(shù)最優(yōu)值的關(guān)鍵步驟。本文設(shè)定在有限次迭代尋優(yōu)過程中有l(wèi)次最優(yōu)結(jié)果是相似的，且最優(yōu)結(jié)果是連續(xù)出現(xiàn)的，對l次最優(yōu)結(jié)果求均方差，其均方差小于設(shè)定的閾值σ1，同時l次尋優(yōu)過程中保存的粒子最優(yōu)解與其平均最優(yōu)解也小于設(shè)定的閾值σ2，說明算法收斂，得到目標(biāo)函數(shù)的最優(yōu)解。該方法確保了算法在全局尋優(yōu)時的穩(wěn)定性能。其公式表示為

(6)

2.3現(xiàn)步驟

步驟1初始化粒子的位置和速度，本文取c1、c2=2，w=0.7，迭代次數(shù)、搜索空間可以根據(jù)函數(shù)的不同進(jìn)行調(diào)整；

步驟2計算當(dāng)前粒子位置；

步驟3計算每個粒子的適應(yīng)值；

步驟4保存單個粒子適應(yīng)值的最優(yōu)解，將保存的單個粒子位置的最優(yōu)解pi設(shè)為當(dāng)前位置；

步驟5尋找粒子群體的最優(yōu)值pq設(shè)為初始種群的最優(yōu)位置；

步驟6利用式(3)判斷粒子是否趨于一致；

步驟7當(dāng)d≤0.1時，利用式(4)，更新xi，按照式(5)調(diào)整慣性權(quán)重w，按照式(1)和式(2)更新粒子的速度和位置，更新pi和pq。

步驟8利用式(6)判斷粒子是否搜索到最優(yōu)值，若滿足，輸出結(jié)果pq，算法結(jié)束；否則返回步驟2。

3仿真與結(jié)果分析

為了測試分析跟隨變異粒子擾動變化的慣性權(quán)重PSO算法的性能，文中選用了3種經(jīng)典測試函數(shù)作為目標(biāo)函數(shù)，并且將改進(jìn)的算法與標(biāo)準(zhǔn)PSO算法和文獻(xiàn)[10]中所用到的算法(以下簡稱文獻(xiàn)算法)進(jìn)行對比。

3.1測試函數(shù) [12]

1)Sphere函數(shù)

(7)

2)Rastrigrin函數(shù)

(8)

3)Rosenbrock函數(shù)

(9)

3.2實驗參數(shù)設(shè)置 [10]

在進(jìn)行3種算法測試時，取20個數(shù)作為種群粒子數(shù)；對3個典型測試函數(shù)分別從10、20、30維，對應(yīng)的最大迭代次數(shù)分別為500、1 000、1 500次進(jìn)行測試。對標(biāo)準(zhǔn)PSO算法，設(shè)置初始慣性權(quán)重w=0.9，隨著迭代次數(shù)的增加，w線性遞減至0.4，學(xué)習(xí)因子c1和c2設(shè)為2；文獻(xiàn)算法初始慣性權(quán)重w從1.2非線性遞減到0.4，學(xué)習(xí)因子c1和c2設(shè)為2.05；改進(jìn)算法設(shè)置初始慣性權(quán)重w=0.7，隨著迭代次數(shù)的增加，粒子在尋優(yōu)過程中的變異擾動使w在0～1之間波動變化，學(xué)習(xí)因子c1和c2設(shè)為2。實驗在Matlab7.11.0(R2010b)的運行環(huán)境中進(jìn)行，3個典型的測試函數(shù)用上述3種算法在10、20、30維的情況下分部運行50次，以其平均值作為優(yōu)化結(jié)果。其中，最優(yōu)值是整個尋優(yōu)過程中所搜索到的最優(yōu)值；均值是指50次運行求得的最優(yōu)值的平均值。

3.3實驗結(jié)果與分析

通過3個典型的測試函數(shù)對3種算法進(jìn)行測試，對表1、表2和表3的數(shù)據(jù)進(jìn)行比較，可以看出無論是在最優(yōu)值，還是均值方面文獻(xiàn)算法比標(biāo)準(zhǔn)PSO算法都更具有優(yōu)越性，但改進(jìn)算法相比較前2種算法的精度都要高，其探索解的能力更強，獲得解的總體質(zhì)量較好。

表1　3種算法對 Sphere函數(shù)的仿真結(jié)果

表2　3種算法對 Rastrigrin函數(shù)的仿真結(jié)果

表3　3種算法對 Rosenbrock函數(shù)的仿真結(jié)果

圖2、圖3和圖4指標(biāo)準(zhǔn)PSO算法、文獻(xiàn)算法和改進(jìn)算法對3種測試函數(shù)在粒子數(shù)為20、維數(shù)為20、迭代次數(shù)為1 000的情況下，隨迭代次數(shù)的增加，相應(yīng)函數(shù)適應(yīng)值的變化曲線圖?？梢钥闯?，在迭代次數(shù)相同的情況下，改進(jìn)算法的收斂速度要明顯快于標(biāo)準(zhǔn)PSO算法和文獻(xiàn)算法的收斂速度。

圖2　 Sphere函數(shù)測試結(jié)果

圖3　 Rastrigrin函數(shù)測試結(jié)果

圖4　 Rosenbrock函數(shù)測試結(jié)果

總之，通過3種算法對上述3種典型測試函數(shù)的測試結(jié)果進(jìn)行對比表明，改進(jìn)算法在收斂精度和收斂速度方面比文獻(xiàn)算法和標(biāo)準(zhǔn)PSO算法都要高。

4結(jié)論

本文針對困擾粒子群算法“早熟”和收斂慢的2大難題，提出一種跟隨變異粒子擾動變化的慣性權(quán)重PSO算法，使慣性權(quán)重隨變異粒子的擾動變化而變化，提高了算法的全局搜索能力，穩(wěn)定性更強。通過跟標(biāo)準(zhǔn)PSO算法和文獻(xiàn)算法對3個典型測試函數(shù)進(jìn)行測試分析，結(jié)果表明改進(jìn)算法能夠避開局部最優(yōu)解的干擾，收斂速度快，尋優(yōu)精度高。

參考文獻(xiàn)：

[1]KennedyJ,EberhartR.ParticleSwarmOptimization[C]//ProceedingoftheIEEEInternationalConferenceonNetworks．[S.l.]:[s.n.],1995：1942-1948.

[2]ParsopoulosKE,VrahatisMN.Onthecomputationofallglobalminimizersthroughparticleswarmoptimization[J].IEEETrans.onEvolutionaryComputation,2004,8(3):211-224.

[3]MendesR,KennedyJ,NevesJ.Thefullyinformedparticleswarm:Simpler,mayberbetter[J].IEEETrans.OnEvolutionaryComputation,2004,8(3):204-210.

[4]周俊，陳璟華，劉國祥，等．粒子群優(yōu)化算法中慣性權(quán)重綜述[J]．廣東電力，2013,26(7)：6-12.

[5]王克華，?；?，張亞南，等．一種參數(shù)自適應(yīng)調(diào)整和邊界約束的粒子群算法[J]．電子設(shè)計工程，2011,19(21)：46-50.

[6]KennedyJ.Stereotyping.ImprovingParticleSwarmPerformancewithClusteranalysis[C]//ProceedingsoftheCongressonEvolutionaryComputing.Piscatawat,2000,NJ:1507-1512.

[7]張捍東，方玲，岑豫皖，等．三種混合粒子群算法比較[J]．自動化與儀表，2011(7)：10-13.

[8]史哲文，白雪石，郭禾，等．基于改進(jìn)小生境粒子群算法的多模函數(shù)優(yōu)化[J]．計算機應(yīng)用研究，2012,29(2)：465-468.

[9]李志，陳年生，郭小珊，等．粒子群算法及其改進(jìn)技術(shù)研究[J]．湖北師范學(xué)院學(xué)報:自然科學(xué)版，2011，31(2)：104-108.

[10]邵洪濤，秦亮曦，何瑩．帶變異算子的非線性慣性權(quán)重PSO算法[J]．計算機技術(shù)與發(fā)展，2012,22(8)：30-34.

[11]姜長元，趙曙光，沈士根，等．慣性權(quán)重正弦調(diào)整的粒子群算法[J]．計算機工程與應(yīng)用，2012,48(8)：40-42.

[12]劉志雄，梁華．粒子群算法中隨機數(shù)參數(shù)的設(shè)置于實驗分析[J]．控制理論與應(yīng)用，2010，27(11)：1489-1496．

(責(zé)任編輯楊繼森)