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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]．自動(dòng)化學(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]孔麗丹，須文波，孫?。趧?dòng)態(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]穆華平，曾建潮．基于小世界模型動(dòng)態(tài)演化鄰域的微粒群算法[J]．系統(tǒng)仿真學(xué)報(bào)，2008，20（15）．

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