基于幾何速度穩(wěn)定性的最優(yōu)覓食微粒群算法

樊衛(wèi)兵(山西中醫(yī)學(xué)院，太原 030024)

微粒群算法[1-2](Particle Swarm Optimization，PSO)是一種模擬鳥(niǎo)群飛行、魚(yú)群游動(dòng)等社會(huì)行為的群體智能優(yōu)化算法，該算法由于速度較快、編程簡(jiǎn)單，現(xiàn)已廣泛應(yīng)用于許多實(shí)際問(wèn)題[3-5]。

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

(1)

vij(t+1)=wvij(t)+c1r1(pij(t)-xij(t))+
c1r1(pgj(t)-xij(t))

(2)

標(biāo)準(zhǔn)微粒群算法較為簡(jiǎn)單，它僅僅粗步模擬了鳥(niǎo)群的覓食行為，但經(jīng)過(guò)自然界數(shù)以萬(wàn)年的發(fā)展，鳥(niǎo)類(lèi)一般都具有些特定的覓食模式，比如最優(yōu)覓食策略。為此，Y Chu等人將最優(yōu)覓食策略引入微粒群算法，提出了最優(yōu)覓食微粒群算法[7-8]。本文針對(duì)最優(yōu)覓食微粒群算法，討論其穩(wěn)定性條件，并給出了慣性權(quán)重的隨機(jī)選擇策略。

1 最優(yōu)覓食微粒群算法

經(jīng)過(guò)億萬(wàn)年的演化，動(dòng)物的食物源一般均不是唯一的，因此，在覓食過(guò)程中就有一個(gè)食物選擇的問(wèn)題。經(jīng)過(guò)動(dòng)物學(xué)家的研究，我們發(fā)現(xiàn)動(dòng)物在覓食過(guò)程中，鳥(niǎo)群總是選擇最有利的食物，而不是最喜歡吃的食物[9]，這就是最優(yōu)覓食策略，該策略表明，動(dòng)物在選擇食物時(shí)，總是趨于耗費(fèi)更低的能量而獲得更多地能量，以達(dá)到能效最優(yōu)，從而提高生存概率。 在微粒群算法中，每個(gè)微粒都在搜索空間中覓食，它們一般傾向于搜索食物源較多的位置，而這一點(diǎn)顯然與上述的最優(yōu)覓食策略相悖。因此，從這個(gè)角度出發(fā)，我們將最優(yōu)覓食策略引入微粒群算法。

由于適應(yīng)值函數(shù)表示食物源的多寡，可定義微粒群中某一微粒i受到的能效吸引為它和其它個(gè)體的適應(yīng)值差別與兩個(gè)體之間距離的比值，即:

(3)

其中，F(xiàn)ik表示微粒i對(duì)微粒k的能效作用力，F(xiàn)ik>0表示微粒i受到微粒k的能效吸引，F(xiàn)ik<0表示微粒i能效排斥微粒k，F(xiàn)ik=0表示微粒i與微粒k處于能效平衡狀態(tài)。稱(chēng)其它微粒對(duì)微粒i的最大能效作用力為Fi,max，即:

Fi,max=arg max{Fis(t)|s=1,2,…,D}

(4)

基于上述結(jié)論，Chu YF等人提出了下面的速度更新方式：

vij(t+1)=ωvij(t)+c2r2(pgj(t)-xij(t))+
c3r3(aij(t)-xij(t))

(5)

2 基于幾何速度穩(wěn)定性的參數(shù)選擇

考慮如下動(dòng)態(tài)系統(tǒng)：

2)如果收斂具有指數(shù)速度，即存在正數(shù)θ<1和K1,K2使得:

下面就利用上述定理來(lái)分析最優(yōu)覓食微粒群算法的幾何速度穩(wěn)定性。為了方便起見(jiàn)，設(shè)φ2=c2r2，φ3=c3r3，φ=φ2+φ3，則最優(yōu)覓食微粒群算法的速度與位置進(jìn)化方程可改寫(xiě)為：

vij(t+1)=wvij(t)-φxij(t)+φ3aij(t)+φ2pgj(t)

xij(t+1)=wvij(t)+(1-φ)xij(t)+φ3aij(t)
+φ2pgj(t)

轉(zhuǎn)換為矩陣形式：

考慮歐式空間的∞范數(shù)，則有:

而

|φ3aij(t)+φ2pgj(t)|≤(c1+c2)·max{xmax,-xmax}

其中，[xmin,xmax]D為定義域空間，取c=(c1+c2)·max{xmax，-xmin},則定理中的c存在且非負(fù)。

假設(shè)θ=0.9，此時(shí)可進(jìn)行如下討論：

1)當(dāng)0<φ<0.5時(shí)，ω+φ<ω+1-φ<0.9<1，即0<ω<φ-0.1；

2)當(dāng)0.5≤φ<1時(shí)，ω+1-φ<ω+φ<0.9<1，即0<ω<0.9-φ；

3)當(dāng)φ>1時(shí)，不成立；

綜上所述，ω和φ的參數(shù)選擇為:

(6)

為了和其他的算法進(jìn)行區(qū)別，因此將本文中的改進(jìn)算法稱(chēng)為基于幾何速度穩(wěn)定性的最優(yōu)覓食微粒群算法(optimal foraging particle swarm optimization with geometric speed stability，簡(jiǎn)稱(chēng)OFPSO_GSS).

下面給出具有幾何速度穩(wěn)定性的最優(yōu)覓食微粒群算法(OFPSO_GSS)的流程：

1)依照初始化過(guò)程，對(duì)粒子群的隨機(jī)位置和速度進(jìn)行初始設(shè)定；

2)按照式(6)中得到的慣性權(quán)重ω進(jìn)行設(shè)置；

3)利用最優(yōu)覓食微粒群算法的進(jìn)化方程更新各微粒的速度及位置向量；

4)計(jì)算每個(gè)微粒的適應(yīng)值；

5)更新各微粒的個(gè)體歷史最優(yōu)位置與群體歷史最優(yōu)位置；

6)如未達(dá)到結(jié)束條件通常為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)設(shè)最大迭代次數(shù)，則返回步驟2.

3 仿真實(shí)驗(yàn)

為了能提供更加準(zhǔn)確的分析，考慮兩種距離度量，分別為歐氏距離和邏輯距離，其歐氏距離定義為：

相應(yīng)地，邏輯距離為：

dij=|j-i|

在算法比較中，考慮歐氏距離為度量標(biāo)準(zhǔn)的最優(yōu)覓食算法(optimal foraging particle swarm optimization with Euclid distance，OFPSOED)、邏輯距離為度量的最優(yōu)覓食算法(optimal foraging particle swarm optimization with logical distance，OFPSOLD)、標(biāo)準(zhǔn)微粒群算法(standard particle swarm optimization，SPSO)、帶時(shí)間帶時(shí)間加速常數(shù)的微粒群算法[11](MPSO_TVAC)及被動(dòng)聚集微粒群算法(Particle swarm optimization with passive congregation，PSOPC)[12]進(jìn)行比較，并選擇如下5個(gè)典型的測(cè)試函數(shù)進(jìn)行測(cè)試：

表1 300維算法性能比較

Rosenbrock Function：

Schwefel Problem 2.26 Function：

min(f2)=f2(420.968 7，…,420.968 7)=-418.982 9n

Rastrigin Function：

-5.12≤xi≤5.12,min(f3)=f3(0,…,0)=0.Ackley Function：

min(f4)=f4(0,…，0)=0

Penalized Function：

sin2(3πxi+1)]+(xn-1)2[1+sin2(2πx30)]}+

min(f7)=f7(1,…,1)=0,其中：

SPSO與OFPSO_GSS的加速度常數(shù)均為2.0，SPSO與MPSO_TVAC的慣性參數(shù)ω從0.9線(xiàn)性遞減至0.4.而OFPSO_GSS的慣性權(quán)重按照公式(6)進(jìn)行選擇。對(duì)于MPSO_TVAC而言，其認(rèn)知系數(shù)從2.5線(xiàn)性遞減至0.5，而社會(huì)系數(shù)則從0.5線(xiàn)性遞增至2.5.

表1為五個(gè)算法在五個(gè)測(cè)試函數(shù)中的性能比較，結(jié)果表明對(duì)于高維多峰優(yōu)化問(wèn)題，兩種最優(yōu)覓食微粒群算法都優(yōu)于其它三種算法，并且歐氏距離為度量標(biāo)準(zhǔn)的最優(yōu)覓食算法性能更佳。

4 結(jié)論

最優(yōu)覓食微粒群算法是一種高效的改進(jìn)微粒群算法，該算法通過(guò)引入動(dòng)物的最優(yōu)覓食策略，較為真實(shí)地模擬了動(dòng)物的覓食行為。本文利用幾何速度穩(wěn)定性分析了最優(yōu)覓食微粒群算法的穩(wěn)定性，給出了穩(wěn)定性條件。為驗(yàn)證其性能，本文選取了五個(gè)算法在5個(gè)典型測(cè)試函數(shù)下進(jìn)行性能比較，仿真結(jié)果證明了該策略的有效性。

參考文獻(xiàn)：

[1] KENNEDY J，EBERHART R C.Particle swarm optimization[C]∥Pro-ceeding of1995 IEEE International Conference on Neural Net-works.USA：New York：NY，1995.1942-1948.

[2] EBERHARTR C，KENNEDY J.A new optimizer using particle swarm theory[C]∥Proceedings of the Sixth International Symposiumon MicroMachine and Human Science.USA：New York，NY，1995.39-43.

[3] 郭研，李南，李興森.多模式多資源均衡及基于動(dòng)態(tài)種群的多目標(biāo)微粒群算法[J].控制與決策，2013，28(1)：131-136.

[4] 江善和，紀(jì)志成，張日東，等.基于種群年齡模型的動(dòng)態(tài)粒子數(shù)微粒群優(yōu)化算法[J].系統(tǒng)工程理論與實(shí)踐，2012，32(11)：2550-2556.

[5] 劉朝華，章兢，李小花，等.免疫協(xié)同微粒群進(jìn)化算法的永磁同步電機(jī)多參數(shù)辨識(shí)模型方法[J].自動(dòng)化學(xué)報(bào)，2012，38(10)：1698-1708.

[6] 崔志華，曾建潮.微粒群優(yōu)化算法[M].北京：科學(xué)出版社，2011.

[7] CHU YF，CUI Z H.Neighborhood sharing particle swarm optimization[C]∥Proceedings of the 8th IEEE International Conference on Cognitive Informatics.Hong Kong，2009:521-526.

[8] CUI ZH，CHU Y F.Nearest neighbor interaction PSO based on small-world model[C]∥Proceedings of the 10 International Conference on Intelligent Data Engineering and Automated Learning.Spain，2009:633-640.

[9] 尚玉昌.行為生態(tài)學(xué)[M].北京：北京大學(xué)出版社，2001.

[10] 朱偉.時(shí)變離散動(dòng)態(tài)系統(tǒng)的漸近穩(wěn)定性和幾何速度穩(wěn)定性[J].應(yīng)用科學(xué)學(xué)報(bào)，2004，22(2)：252-254.

[11] RATNAWEERA A，HALGAMUGE S K ，WATSON H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].Transactions on Evolutionary Computation，2004，8(3)：240-255.

[12] HE S，WU Q H.A particle swarm optimizer with passive congregation[J].BioSystems，2004，78(1)：135-147.