粒子群算法鄰域拓?fù)浣Y(jié)構(gòu)研究

摘要：粒子群算法（PSO算法）是一種啟發(fā)式全局優(yōu)化技術(shù)。PSO的鄰域拓?fù)浣Y(jié)構(gòu)是決定粒子群優(yōu)化算法效果的一個很重要的因素，不同鄰域拓?fù)浣Y(jié)構(gòu)的粒子群算法，效果差別很大。文章分析了鄰域拓?fù)浣Y(jié)構(gòu)與PSO算法的關(guān)系，闡述了粒子群算法鄰域拓?fù)浣Y(jié)構(gòu)研究現(xiàn)狀，提出了未來可能的研究方向。

關(guān)鍵詞：粒子群算法；PSO算法；鄰域拓?fù)浣Y(jié)構(gòu)；啟發(fā)式

中圖分類號：F235文獻(xiàn)標(biāo)識碼：A文章編號：1009-2374（2009）16-0036-02

粒子群優(yōu)化算法PSO（Particle Swarm Optimization，簡稱PSO）是由Kennedy 和Eberhart于1995年提出的一種啟發(fā)式全局優(yōu)化技術(shù)。由于PSO概念簡單，易于實(shí)現(xiàn)，因而短期內(nèi)得到很大發(fā)展，迅速得到了國際演化計(jì)算研究領(lǐng)域的認(rèn)可，并在很多領(lǐng)域得到應(yīng)用，如電力系統(tǒng)優(yōu)化、TSP問題、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、數(shù)字電路優(yōu)化、函數(shù)優(yōu)化、交通事故探測、參數(shù)辨識等。

PSO算法在多維空間函數(shù)尋優(yōu)、動態(tài)目標(biāo)尋優(yōu)等方面有著收斂速度快、解質(zhì)量高、魯棒性好等優(yōu)點(diǎn)。但是，隨著迭代次數(shù)的增加，其易于陷入局部最優(yōu)的缺點(diǎn)就暴露無疑，因此，近年來很多學(xué)者均致力于PSO算法的改進(jìn)工作。目前，對粒子群優(yōu)化算法的改進(jìn)主要體現(xiàn)在以下幾個方面：參數(shù)的改進(jìn)和優(yōu)化、慣性權(quán)值和加速因子的改進(jìn)、混合PSO、領(lǐng)域拓?fù)浣Y(jié)構(gòu)等。

PSO的拓?fù)浣Y(jié)構(gòu)是指整個群體中所有粒子之間相互連接的方式，而PSO的鄰域結(jié)構(gòu)是指單個粒子如何與其它粒子相連。前者是整體性質(zhì)，后者是局部性質(zhì)，鄰域結(jié)構(gòu)決定了拓?fù)浣Y(jié)構(gòu)。潘峰等人的研究表明，鄰域結(jié)構(gòu)是決定粒子群優(yōu)化算法效果的一個很重要的因素，不同鄰域結(jié)構(gòu)的粒子群優(yōu)化算法，效果會有很大的差別。鄰域拓?fù)浣Y(jié)構(gòu)的改進(jìn)是粒子群優(yōu)化算法研究的一個很重要的方面。

一、鄰域拓?fù)浣Y(jié)構(gòu)與PSO算法的關(guān)系

目前，對于種群鄰域拓?fù)浣Y(jié)構(gòu)的研究大多基于如下五種模式：

1．全局（gbest）：種群中所有個體相互通信。該模式中，信息傳遞的速度比較快，所以收斂速度也比較快，但是也較容易陷入到局部極小點(diǎn)。

2．局部（lbest）：種群中相鄰個體之間通信。局部模式中所有粒子排成一個環(huán)狀結(jié)構(gòu)，這種結(jié)構(gòu)信息傳遞得比較慢，收斂速度較慢，但是也較不容易陷入局部極值點(diǎn)。

3．4 類（four clusters）：整個粒子群中有4個類組成，各個類內(nèi)部相互完全通信，類間通信較少。

4．金字塔（pyramid）：三角形線框的金字塔結(jié)構(gòu)，即四面體結(jié)構(gòu)，粒子分布在四面體的四個頂點(diǎn)上，然后所有這樣的四面體相互連接起來。

5．馮諾以曼（Von Neumann）：四方網(wǎng)格，頂點(diǎn)相連形成環(huán)面，即每個粒子與上下左右四個最鄰近的粒子相互連接，形成一種網(wǎng)狀的結(jié)構(gòu)。

（一）影響拓?fù)浣Y(jié)構(gòu)的主要因素

影響拓?fù)浣Y(jié)構(gòu)的因素比較多，但是有兩個最重要的特征可以量化，一是與單個粒子直接相連的粒子的個數(shù)k，k的大小決定了單個粒子的鄰域大小，從而影響信息在粒子間傳遞的速度，通常k值比較大的群體收斂比較快，反之比較慢。第二個影響因素是整個群體中類的個數(shù)c，一個類定義為互為鄰域的粒子的集合，每個類中的粒子之間相互連接數(shù)為k。類的個數(shù)與信息在粒子之間的傳遞通常是減函數(shù)關(guān)系。

根據(jù)watts的研究結(jié)果，信息在粒子構(gòu)成的網(wǎng)絡(luò)中流動時，決定它的傳遞速度的一個很重要的因素是從一個粒子到另一個相鄰粒子的平均最短距離，而平均最短距離和k以及c有高度的相關(guān)性。

（二）鄰域結(jié)構(gòu)和迭代式之間的對應(yīng)關(guān)系

鄰域結(jié)構(gòu)和粒子群的迭代式之間存在著對應(yīng)關(guān)系，不同的鄰域結(jié)構(gòu)影響種群中當(dāng)前粒子的速度和位置。當(dāng)前粒子位置的定義隨著鄰域大小的改變而改變，整個系統(tǒng)的最后輸出解為所有當(dāng)前粒子位置中的最優(yōu)值。

二、鄰域拓?fù)浣Y(jié)構(gòu)的研究進(jìn)展

（一）基于粒子劃分的鄰域結(jié)構(gòu)

局部模式PSO中粒子的鄰域是基于粒子序號劃分的。每個粒子僅與其附近的兩個粒子相互交流信息，從而能有效地保證種群的多樣性。此外，這里的鄰域僅與粒子的下標(biāo)有關(guān)，而與粒子的真實(shí)位置無關(guān)，從而可以有效地對搜索空間進(jìn)行搜索，但有時會影響算法效率。作為該結(jié)構(gòu)的推廣，隨機(jī)環(huán)形結(jié)構(gòu)針對環(huán)形結(jié)構(gòu)的鄰域僅由粒子的下標(biāo)決定的缺點(diǎn)做了一定調(diào)整，其鄰域雖然主體仍由下標(biāo)決定，但存在兩個粒子的鄰域可以隨機(jī)選擇，從而在一定程度上提高了算法效率。

Suganthan提出了基于粒子的空間位置劃分的方案。在迭代中，計(jì)算每一個粒子與群中其他粒子的距離，記錄任何2個粒子間的最大距離為dmax。對每一粒子按照‖Xa-Xb‖/dmax計(jì)算比值，其中‖Xa-Xb‖是當(dāng)前粒子a到粒子b的距離。而選擇閾值e根據(jù)迭代次數(shù)而變化。當(dāng)另一粒子b滿足‖Xa-Xb‖/dmax＜閾值e時，則b成為當(dāng)前粒子的鄰域。所有滿足該條件的粒子組成Ni，其他同原局部版PSO。應(yīng)用改進(jìn)的鄰域規(guī)則，且采用時變ω的PSO在絕大多數(shù)測試中都取得了比全局版PSO更優(yōu)良的性能。

（二）動態(tài)的鄰域結(jié)構(gòu)

Suganthan提出了一種具有可變鄰域算子的微粒群算法，該算法初始階段微粒的鄰域?yàn)樗陨?，隨著進(jìn)化代數(shù)的增長，鄰域逐漸擴(kuò)大至整個群體。在此基礎(chǔ)上，孔麗丹等提出了基于動態(tài)鄰域的量子行為的粒子群優(yōu)化算法（NQPSO）。在NQPSO中，為了定義一個鄰域，根據(jù)粒子的空間位置，在每次迭代中，種群中一個粒子（中心粒子）到其他粒子之間的距離都被計(jì)算出來，并且用變量max_dist來標(biāo)記該中心粒子與其他粒子之間距離的最大值。對于每一個粒子i來說，利用粒子間的距離，可以獲得一個比值dist[i]/max_dist，dist[i]是粒子i到中心粒子的距離，這個比值可用來作為選擇相鄰粒子的依據(jù)，利用較大比值或較小比值作為選擇依據(jù)。在定義好一個鄰域后，要確定其局部最優(yōu)解Lbest，再利用進(jìn)化方程進(jìn)行進(jìn)化，此時進(jìn)化方程中所有粒子中目前取得的最優(yōu)解被當(dāng)前鄰域的局部最優(yōu)解替代。NQPSO算法具有強(qiáng)的全局搜索能力，在解決高維的優(yōu)化問題中能獲得較好的效果。但由于加入了鄰域定義，運(yùn)算量增大。另外Richards和Ventura提出一種鄰域結(jié)構(gòu)隨算法逐步由局部結(jié)構(gòu)模式向全局結(jié)構(gòu)模式進(jìn)化的微粒群算法，結(jié)果發(fā)現(xiàn)該方法對局部極值點(diǎn)較多的函數(shù)能起到更好的作用。

（三）引入有向圖概念的鄰域結(jié)構(gòu)模型

Mohais等將有向圖的概念引入鄰域結(jié)構(gòu)模型，提出了兩種動態(tài)改變鄰域結(jié)構(gòu)的方法：

1．隨機(jī)邊遷移，即隨機(jī)選擇節(jié)點(diǎn)度大于1的節(jié)點(diǎn)移除一條邊，同時選擇一個節(jié)點(diǎn)度小于N（節(jié)點(diǎn)個數(shù)）的節(jié)點(diǎn)與之建立連接。

2．鄰域重構(gòu)，該方法每間隔一定時間段就對鄰域結(jié)構(gòu)進(jìn)行完全初始化，整個過程保持鄰域大小和節(jié)點(diǎn)出度保持不變。實(shí)驗(yàn)結(jié)果證明這兩種方法能夠取得較von Neumann等其它鄰域模型相當(dāng)甚至更好的效果。

（四）基于小世界的鄰域結(jié)構(gòu)模型

從社會結(jié)構(gòu)學(xué)角度來看鄰域結(jié)構(gòu)。社會結(jié)構(gòu)定義為人與人之間的連接關(guān)系，小世界（Small world）理論認(rèn)為，此類關(guān)系分為兩種基本類型，一是強(qiáng)連接關(guān)系，二是弱連接。前者是指個人之間產(chǎn)生的緊密的、穩(wěn)定的連接，后者是指偶然產(chǎn)生的、不穩(wěn)定的連接。強(qiáng)連接關(guān)系基本決定了群體的結(jié)構(gòu)，而弱連接關(guān)系則非常顯著的改變?nèi)后w間信息流動的快慢。在一個具有穩(wěn)定結(jié)構(gòu)的群體中，隨機(jī)的加上幾個弱連接關(guān)系，將大大的提高群體間信息流動和傳遞的速度，從而也將加快收斂的速度。

穆華平和曾建潮提出了基于“小世界”模型的鄰域動態(tài)演化的微粒群算法（DSWN-PSO）。算法將每個微?？醋饕粋€節(jié)點(diǎn)，采用NW模型構(gòu)造微粒間的鄰域關(guān)系。算法初始階段將種群中的每個微粒按照編號構(gòu)造成為一個環(huán)形規(guī)則網(wǎng)絡(luò)，每個節(jié)點(diǎn)都與它左右相鄰的k/2（k

（五）其它改進(jìn)

Kenney提出了混和空間鄰域和環(huán)形拓?fù)浞椒ǖ牧硪粋€局部PSO版本，稱為社會趨同法。因?yàn)樯钪腥藗兺窃噲D追隨一個群體的共同觀點(diǎn)，而不是群體中某個人的立場。將該思想應(yīng)用到PSO中，即不用每個粒子的經(jīng)驗(yàn)而是用它所屬空間聚類的共同經(jīng)驗(yàn)來更新自己。

三、進(jìn)一步的研究方向

種群鄰域拓?fù)浣Y(jié)構(gòu)對PSO算法性能的影響主要有兩個層面:其一，可選取不同粒子的局部鄰域結(jié)構(gòu)；其二，可定義不同的局部鄰域之間的通信方式。PSO算法中粒子分布的鄰域拓?fù)浣Y(jié)構(gòu)的改進(jìn)，不僅可提高尋優(yōu)解的精度，而且可加快收斂速度。拓?fù)浣Y(jié)構(gòu)的研究對PSO的發(fā)展具有重要的意義。

1．在實(shí)際的應(yīng)用中很多問題都是隨時間動態(tài)變化的，因而將PSO應(yīng)用到動態(tài)問題領(lǐng)域具有重要的現(xiàn)實(shí)意義。

2．不同的粒子群鄰域拓?fù)浣Y(jié)構(gòu)是對不同類型社會的模擬，研究不同拓?fù)浣Y(jié)構(gòu)的適用范圍，對PSO算法推廣和使用有重要意義。

3．使用鄰域帶來的一個問題是增加了配置算法的難度，可能導(dǎo)致研究者不敢輕易嘗試使用PSO算法。一個有前途的研究方法是自動產(chǎn)生不同種群大小的鄰域拓?fù)浣Y(jié)構(gòu)。

4．引入帶權(quán)圖，研究不同個體粒子所攜帶的信息對其他粒子的影響程度，從而控制信息流動是值得研究的。

5．魯棒性是系統(tǒng)在異常和危險(xiǎn)情況下系統(tǒng)生存的關(guān)鍵。如何改進(jìn)拓?fù)浣Y(jié)構(gòu)以提高魯棒性是值得研究的。

參考文獻(xiàn)

[1]Kennedy J，Eberhart R.C．Particle Swarm Optimization.In:Proccedings of the IEEE International Conference on Neural networks，Perth Australia，1995．

[2]潘峰，陳杰，甘明剛．粒子群優(yōu)化算法模型分析[J]．自動化學(xué)報(bào)，2006，32（3）．

[3]D.J.watts.Small Worlds:The Dynamics of Network Between Oder and Randomness，Princeton university Press，1999.

[4]Baskar S，Suganthan P N.A Novel Concurrent Particle Swarm Optimization[C]// Proceedings of the 2004 Congress on Evolutionary Computation．Piscataway，NJ：IEEE Press，2004．

[5]Suganthan P N.Particle swarm optimizer with neighborhood operator[C]．Proc Con Evolutionary Computation，Washington DC，1999，（7）．

[6]孔麗丹，須文波，孫?。趧討B(tài)鄰域的QPSO算法[J]．計(jì)算機(jī)工程與應(yīng)用，2008，44（13）.

[7]Mohais A S，Mendes R， Ward C，Posthoff C. Neighborhood ReStructuring in Particle Swarm Optimization[C]．Australian Conference on Artificial Intelligence. Heidelberg，Germany:Springer Berlin，2005．

[8]穆華平，曾建潮．基于小世界模型動態(tài)演化鄰域的微粒群算法[J]．系統(tǒng)仿真學(xué)報(bào)，2008，20（15）．

作者簡介：楊道平（1973－），男，遵義師范學(xué)院計(jì)算機(jī)科學(xué)系講師，碩士，研究方向：智能計(jì)算、最優(yōu)化理論。