自適應小世界粒子群優化算法

龔月姣，嵇智源

（1.中山大學 計算機科學系，廣東 廣州510006；2.科技部 高技術研究發展中心，北京100044）

0 引 言

粒子群優化 （particle swarm optimization，PSO）［1－3］解決問題的關鍵來自群體中粒子的相互作用。一個粒子自身幾乎沒有能力解決任何問題。因此，粒子群體不僅僅是一組粒子的集合，而是一個在某種社會通信網絡或拓撲組織上建立的互動的群體。PSO 算法所采用的網絡拓撲對算法的搜索行為起著重要的決策作用。傳統PSO 算法分為全局和局部兩種版本，它們都采用了簡化的社會模式，即采取了完全規則的網絡拓撲結構。已有研究結果表明使用全局拓撲的PSO 算法收斂速度非常快，但很可能陷入局部最優；而采用局部拓撲的PSO 算法則有更多的機會找到全局最優，但收斂速度較慢。因此，粒子群優化算法的全局和局部版本各有長處與短處，適用于解決各種不同的問題。

考慮到上述問題，本文提出了一種自適應小世界拓撲結構的PSO，用于進一步提高PSO 的算法性能及對實際問題的適用性。考慮到PSO 是一種在現實社會群體行為啟發下誕生的算法，而自然世界中的大部分網絡 （如生物、學術、和社會網絡）都不是完全規則的。網絡中的頂點不僅頻繁與它們的近鄰進行溝通，還會偶然地與一些遠處的節點進行通訊。在這種情況下，網絡具有 “小世界”的特征，即網絡中的任意兩個節點可以通過一個較小的跳數實現信息傳遞。受此啟發，在本文提出的拓撲結構中，每個粒子會在大多數情況下與近鄰連接，并通過一定概率重新連接到一些隨機的粒子。后面我們會介紹到，小世界拓撲同時具有大的群聚系數和小的特征路徑長度。因此，相應的PSO 算法能夠保留局部版本PSO 算法良好的全局探索能力，同時又具有全局版本PSO 算法收斂速度快的特性。

此外，不同于傳統的PSO 拓撲中整個群體共享一個單一的拓撲圖，本文提出的拓撲結構是細粒度的，每個維度的群體分配一個特定的粒子網絡。由不同維度的粒子構成一個鄰域引導向量，進而用來指導粒子的速度和位置更新。通過使用這樣一種細粒度的拓撲結構，粒子群體的搜索更加多樣化，進一步提高了該算法的全局探索能力。同時，在上述拓撲結構的基礎上，我們進一步根據種群的收斂狀態對網絡結構進行自適應調整。首先定義了整個群體的停滯系數，再基于這個系數對網絡中頂點度數和小世界重置概率進行調整，以平衡粒子群體的全局探索和局部開發能力。通過采用這種拓撲結構自適應機制，PSO 的搜索效率可以進一步提高。

1 背 景

1.1 小世界網絡

圖1 網絡結構

一般來說，復雜網絡 （complex network）可分為3類。第一類網絡是完全規則的，比如著名的完全圖、環狀圖、網格、分形圖等等。相比之下，第二類網絡是一些通過特定的概率模型完全隨機生成的圖如ER 圖。然而，研究人員發現，許多真實世界的網絡，如生物、技術和社會網絡并不屬于這兩種極端之一。相反，其介于完全規則和完全隨機的網絡之間，同時具有規則網絡和隨機網絡的特性。這類網絡通常被認為是第三類網絡，其中，小世界網絡（small－world network）吸引了越來越多的關注［4，5］。

小世界網絡的靈感來自于Milgram 的 “六度分離”理論：一個社會網絡的特征路徑長度 （characteristic path length，又稱直徑）不大于6，即通過6跳可以實現任意兩個人的消息傳遞。文獻 ［6］仿照這個小世界現象建立了小世界網絡模型，后稱WS模型。WS是最初的小世界網絡模型，它非常簡單，由一個規則網絡作為起始，以一定概率對網絡中的邊進行擾亂。如圖1所示，建立一個具有N 個頂點的環圖，環中每個頂點連接到其K 個最近鄰；對于每個頂點的每條邊，以一個概率P 對其進行重置，使得其重新連接到整個圖中的一個隨機選擇的頂點。這種隨機擾亂的過程不會改變在網絡中的頂點或邊的數目。但是重連產生的邊很可能引入一些連接兩個較遠頂點的 “長程邊”。只用具有少數的長程邊，圖的特征路徑長度可以被大為減少，并同時保持大的集聚系數 （clustering coefficient）。

小世界網絡的邊重置概率P 是一個非常重要的參數，決定著網絡規則性和無序性的相對比重。如果P＝0，網絡便成為一個特征路徑長度與網絡規模N 成正比例的規則圖。另一方面，P＝1時網絡是一個具有極小的集聚系數的稀疏隨機圖。滿足0＜P＜1的小世界網絡則界于完全規則和完全隨機的網絡之間，文獻 ［7、8］分別對小世界網絡的特征路徑長度與集聚系數進行了分析，驗證了小世界網絡同時擁有小的特征路徑長度和高的集聚系數。圖2是一個特征路徑長度L（P）與集聚系數C（P）隨著P 的變化的示意圖，它清晰表明了小世界網絡同時克服了規則網絡特征路徑長度較大與隨機網絡集聚系數較小的缺點。通過調節P，小世界網絡適用于許多真實世界的網絡。

1.2 粒子群優化算法

在粒子群優化算法中，每個粒子i維持一個速度向量Vi＝ （vi1，vi2，…，viD），一個當前位置向量Xi＝ （xi1，xi2，…，xiD）和一個歷史最優位置向量PBesti＝ （pi1，pi2，…，piD）。速度向量Vi決定了粒子i 當前飛行的速率和方向；位置向量Xi表示粒子i 當前在搜索空間中所處的位置，是評估它所表示的解的質量的基礎；歷史最優位置向量pBesti記錄著粒子i 在搜索過程中發現的最優位置 （對應于最好的解評估值的位置），用于保存粒子i的搜索經驗信息。此外，整個群體維持一個全局最優位置向量gBest＝（g1，g2，…，gD），它是所有粒子的pBest中最優的那個，也就是整個群體在進化過程中發現的最好位置，用于保存群體的搜索經驗信息。粒子根據自身搜索的經驗信息和群體搜索的經驗信息調整飛行速度，最終所有的粒子收斂到問題空間的全局最優解位置。PSO 的基本步驟主要包括：

（1）初始化：隨機產生群體中每個粒子的Vi和Xi；將Xi復制給pBesti；將最優的pBesti復制給gBest。

（2）速度更新 （學習的過程）：每個粒子i根據當前的pBesti和gBest對Vi進行更新，如式 （1）所示

圖2 網絡特征路徑長度與集聚系數

式中：ω是慣量權重 （inertia weight），可被認為是粒子運動空間中介質的流動度［9］。它常常被初始化為一個較大的值 （如0.9），此時粒子在運動空間中較快地飛行，有利于加強算法初期的全局探索能力，隨著群體的進化，可將ω逐漸減小到一個較小的值 （如0.4），以牽引粒子收斂到局部最優解；c1和c2被稱為加速因子 （acceleration coefficient），它們決定著pBest和gBest 指導粒子更新時力度的大小；rand1和rand2是兩個均勻采樣于 ［0，1］區間的隨機數。

（3）位置更新 （飛行的過程）：每個粒子i根據自己當前的位置Xi和速度Vi對Xi進行更新，如式 （2）所示

（4）解評估：對每個粒子i計算Xi對應的目標函數值，即粒子的適應值；如果粒子i當前的適應值比歷史最優要好，將Xi復制給pBesti；如果粒子i的歷史最優比全局最優要好，將pBesti復制給gBest。

（5）若滿足算法結束條件，輸出gBest；否則，跳轉執行第 （2）步。

1.3 粒子群優化算法的種群拓撲研究

經典的全局版本PSO 算法采用規則的完全圖作為它的拓撲結構，群體中任何兩個粒子都能直接連接，因此每個粒子都受到整個種群的全局最優粒子gBest的影響。另一方面，其它一些規則的網絡，如環、網格等，被廣泛運用于各類局部版本的PSO 算法中，每個粒子i受到其近鄰粒子中最優秀粒子lBesti＝ （li1，li2，…，liD）的影響，如式（3）所示。此外，一些最新開發的PSO 變種，如 “動態多群體 PSO （DMS－PSO）”［10］和 “標準 PSO 2011（SPSO2011）”［11］，使用的完全隨機圖

然而，由上述可知，現實世界中的生物社會網絡既不是完全規則的，也不是完全隨機的。由于PSO 是一種模擬鳥群或魚群的仿生學算法，開展基于小世界拓撲的PSO 是合理可行的。在文獻 ［12］中，Kennedy進行了實驗，發現一定數量的小世界隨機化可以對PSO 算法的性能產生顯著的影響。之后，一些基于小世界網絡的PSO 變種相繼被提出，包括 “網絡結構PSO （NS－PSO）”［13］和 “小世界局部PSO （SWLPSO）”［14］。近年來，國內也對基于小世界拓撲的PSO 給予了充分的關注［15－17］。

本文，提出一種自適應小世界PSO 算法（adaptive small－world PSO，ASWPSO）。與以前的相關工作相比，其創新點在于：①使用一種 “單指導”的粒子學習機制；②采用一種細粒度的拓撲結構，單個粒子的不同維度可有不同的網絡連接情況；③拓撲圖中鄰域大小K 和小世界網絡因子P 基于群體的收斂狀態在優化過程中自適應調整。

2 自適應小世界粒子群優化算法

ASWPSO 采用 “單指導”的粒子學習機制以及一種細粒度、自適應的小世界網絡拓撲結構，以克服過去PSO 算法早熟收斂、抑或是搜索效率不足的缺陷。

2.1 小世界拓撲的生成

本文在WS小世界網絡模型的基礎上開發了一種新型的局部拓撲PSO 算法。最初，群體中每個粒子i連接K 個直接后繼粒子 （i＋1），（i＋2），…，（i＋K），K 為每個節點的度數，亦即鄰域規模 （neighborhood size）。然后，對每個粒子的每一條邊，我們以一個概率P 將其重新連接至一個隨機的粒子，這一過程稱作小世界重置 （small－world randomization），P 即為小世界重置概率。此外，這個拓撲結構的新穎之處在于，它是基于維度的細粒度拓撲：對于粒子的每一個維度，上述的小世界網絡產生過程執行一次。這樣一來，PSO 為其種群的每個維度分配一個特定的拓撲網絡。

在此細粒度拓撲結構的基礎上，對于每個粒子i，生成一個鄰域引導向量Neii＝ （neii1，neii2，…，neiiD），這個引導向量將在粒子更新時被使用，其中neiij是粒子i 在第j維拓撲網絡中的當前引導粒子的索引，它可能來自：①i的K 個近鄰；②小世界重置產生的隨機鄰居；③i本身。為簡單起見，我們將算法中小世界網絡的構建和鄰域引導向量Neii的生成合并成一個單一的過程稱為 “拓撲更新”。

本文提出的PSO拓撲更新過程的偽代碼如圖3所示：對于粒子的每一個維度，首先產生一個 （0，1）隨機數r，如果r小于小世界重置概率P，neiij是從整個粒子群體中隨機選擇的一個粒子的索引；否則，在i的K 個近鄰中隨機產生一個粒子k，比較pBestk與pBesti，隨后將neiij賦值為k和i中具有較好歷史搜索經驗信息的那個。這種操作的機制帶來的優勢將在下一小節中描述完粒子更新過程后詳細分析。

2.2 粒子更新

傳統上，全局和局部版本的PSO 算法分別采用式 （1）和式 （3）進行速度更新，隨后采用式 （2）進行位置更新。每個粒子i都存在pBesti和gBest （或lBesti）兩個引導向量。但這可能造成種群的震蕩現象：如圖4所示，當兩種歷史最優位置落于粒子當前位置Xi的兩個相反方向時，粒子可能始終在pBesti和gBest（或lBesti）之間一個較差的區域徘徊。這造成個體評估的浪費以及算法搜索效率的低下。

圖3 提出的ASWPSO算法中拓撲結構更新過程的偽代碼

圖4 傳統更新機制下的粒子震蕩

為了克服這一問題，本文采用了一種單指導學習機制，這種機制最早在全面學習PSO 算法 （fully informed particle swarm，FIPS）［18］中被提出，其核心思想是將pBesti和gBest （或lBesti）通過一定策略整合成一個向量來指導粒子更新，從而防止雙指導作用下粒子的震蕩。

在本文提出的ASWPSO 算法中，粒子i的第j 維速度更新過程定義為

式中：ω和c是慣性權重和加速系數，k＝neiij表示粒子i第j個維度的作用粒子，它通過2.1小節中描述的拓撲更新過程產生。隨后粒子仍然采用式 （2）進行位置更新。為了使粒子平穩地搜索于一個有前景的方向，我們允許粒子在一定代數內采用一個不變的鄰域引導向量直到粒子停滯。具體的實現方法是：對于粒子i，當且僅當它的最優位置pBesti停滯更新的代數si大于一個停滯閾值Sg 時，它才執行一次拓撲更新過程以生成一個新的鄰域引導向量指導搜索。

不同于傳統PSO 算法使用個體最優pBesti和整個群體的歷史最優gBest （或鄰域lBesti）更新粒子速度和位置，本文的算法通過構造一個基于小世界拓撲的鄰域引導向量來指導搜索。根據該向量的生成過程，不難發現粒子的每一維在大多數情況下被其附近一個比較好的粒子 （包括其本身）引導，在其它時候，則以概率P 受到整個群體中的一個隨機粒子的影響。這種粒子更新方式的優勢總結如下：

（1）由于小世界重置概率P 一般都設置為一個較小的值，在大多數情況下，粒子都只受其K 近鄰影響，從而允許不同的粒子鄰域對空間進行并行搜索 （類似于傳統局部版本的PSO，具有較高的集聚系數），有利于探索解空間的不同區域，提高算法局部尋優的能力，并且防止粒子群體在gBest的牽引下早熟收斂。

（2）通過引入小世界隨機邊，拓撲圖的特征路徑長度大大減少，粒子能與較遠的粒子進行溝通，以一種 “弱聯結 （weak tie）”的方式。盡管粒子通過 “強聯結 （strong ties）”與近鄰頻繁進行互動，在鄰域內共享的信息可能是有局限性的或過時的。相比之下，弱聯結可以注入更加多樣化的信息 （常常具有高信息熵），這非常有可能為小鄰域里的粒子帶來一種 “革新”，有助于算法跳出局部最優。同時，由于網絡的特征路徑長度的減小，粒子間具有更快的信息傳播速度，整個粒子群體的收斂速度也能得到提高，從而有效克服傳統局部版本PSO 搜索效率較低的問題。

（3）細粒度的拓撲結構允許粒子在不同維度向不同的鄰居節點進行學習，從而避免了單個優秀鄰居的過度統治。通過這種方式，整個群體中所有粒子的搜索信息能更充分地被使用。因此，相比傳統的粗粒度PSO，本文提出的ASWPSO 具有更好的多樣性和全局探索能力。

2.3 拓撲自適應機制

小世界網絡拓撲結構的采用為算法引入了兩個新的參數：鄰域規模K 和小世界重置概率P。一方面，這降低了算法實際應用的簡單性——需要事先設置參數；另一方面，對于不同的實際問題、甚至是同一問題的不同優化階段，最適宜的參數設置可能不同，這將影響到算法的搜索性能。因此，不同于過去算法采用固定的K 和P，本文提出一種拓撲結構自適應機制，在算法對問題的求解過程中，根據群體的收斂狀態動態、自適應地調整參數K 和P，使其滿足不同優化問題在不同階段的需求。本文提出的ASWPSO的拓撲結構自適應調整機制描述如下：

首先定義一個整個群體停滯系數Sc，為當前群體中所有粒子停滯代數的平均值除以閾值Sg

式中：N——種群規模，si——每個粒子i的停滯的代數。不難看出Sc反映了整個粒子群體的停滯狀態，如果群體中沒有粒子停滯，那么停滯系數Sc為最小值0；如果群體中所有粒子都嚴重停滯，Sc為1。基于Sc的值，參數K 和P根據如式 （6）和式 （7）自適應地調整，式 （6）和式 （7）的曲線被繪制在圖5中

在圖5 （a）可以觀察到，隨著Sc的增加，K 的值由2增長至7。這意味著，粒子群體停滯越嚴重，單個粒子的鄰域越大。在這種情況下，粒子可以有一個更廣闊的視野，并有可能因此跳出局部最優。根據式 （6），每個粒子被分配有特定的小世界重置概率Pi，這使得各個粒子的搜索習慣更具有多樣性。另一方面，如圖5 （b）中所示，隨著停滯系數Sc的增加，從1到N 的每個粒子具有范圍從0.05到0.2遞增的P。這說明，群體停滯越嚴重，小世界重置的概率被加大。隨機邊的增加有助于帶來革新的信息，從而拉動粒子小鄰域跳出局部最優。

2.4 整體流程

在本文中，我們提出了一個具有自適應小世界拓撲結構的ASWPSO 算法，其流程如圖6所示。除了傳統粒子群優化算法的一般過程，每當一個粒子停滯到達Sg 代時，算法將進行一次拓撲更新操作。在操作中，一個基于小世界拓撲的鄰域引導向量被構建，并在之后指導粒子進行搜索。并且，小世界拓撲中的參數K 和P 將根據整個粒子群體的停滯系數進行自適應調整。在下一章，我們將對提出的ASWPSO 算法進行實驗分析與驗證。

圖5 鄰域大小K 和小世界重置概率P 的調整曲線

3 實驗研究

3.1 實驗設置

在本文的實驗中，13個具有不同特性的基準函數被用來測試ASWPSO的性能［19］。這些函數列在表1，其中f1至f5是單峰函數；f6是一個階梯函數；f7是一個帶噪聲的4次函數；f8至f13的是具有很多局部最優值的多峰函數。圖7是f8和f9兩個多峰函數在二維環境下的解空間地形（landscape）示意圖。

在ASWPSO 中，慣性權重ω 和加速系數c 分別設置為0.7298和1.49618，停滯閾值設置為Sg＝5。進一步我們將該算法與現有的兩個PSO 變種進行比較：VNPSO 是采用規則馮諾依曼拓撲結構的PSO 算法，而DMS－PSO 在算法運行的前90%時間里使用完全隨機的拓撲，并在后10%的時間里采用全局拓撲進行最終收斂［10］。這兩個算法中的參數設置都依據對應的參考文獻。

圖6 ASWPSO 算法的流程

所有的算法都采用種群規模30和函數評估300 000進行測試，函數維度被設置為30。對于每個函數，都進行30次獨立的實驗，在相同情況下對DMS－PSO，VNPSO 和ASWPSO 的統計結果進行對比。

3.2 結果與比較

表2是由VNPSO，DMS－PSO 及本文提出的ASWPSO在13個標準測試函數上返回誤差的平均值、最優值和標準差。可以觀察到，ASWPSO 性能相比VNPSO 和DMS－PSO更為優秀。一方面，在優化單峰函數時，該算法可以獲得比VNPSO 和DMS－PSO 更高的求解精度；另一方面，在優化多峰函數時，ASWPSO 相比其它兩種算法具有更強的全局探索能力，能夠找到更優秀的峰。

此外，我們還采用了非參數假設檢驗方法 “Wilcoxon秩和檢驗”［20］來對比不同算法求得結果之間的差異是否具有顯著性的差別。在檢驗中，顯著度α被設置為0.05。表3展示了ASWPSO 與VNPSO 和DMS－PSO 的顯著性檢驗對比結果，可見在ASWPSO 在大多數函數上能夠取得顯著優秀的實驗結果。

表1 標準測試函數

圖7 兩個多峰函數的解空間地形

表2 3種算法的結果統計及對比

表3 顯著性檢驗結果

進一步用 “盒圖”比較3種算法在多峰函數上的性能，如圖8所示。該圖生動地描繪了所得結果的最小值、下四分位數、中位數、上四分位數、最大值和奇異點。由圖8可以看出，對于多峰函數，ASWPSO 的結果都優于VNPSO 和DMS－PSO。圖8還顯示了該算法的魯棒性，因為它可以始終在一個狹窄的誤差范圍內獲得優秀的優化結果。

此外，在優化的單峰函數f1，f3，f5和多峰函數f8至f10的過程中3種算法的收斂曲線繪制在圖9。該圖清晰地表明，ASWPSO 收斂速度在3個算法中最快，從而獲得最高的解精度。總的來說，通過使用自適應的小世界拓撲結構，本文提出的ASWPSO 不論從解精度、搜索效率、還是魯棒性方面都是非常有競爭力的一個算法。

圖8 3種算法在優化多峰函數時的盒圖對比

3.3 參數調研

本文提出一種基于小世界網絡拓撲的PSO 算法，其中，小世界網絡的參數K 和P 在算法收斂過程中基于種群收斂狀態自適應調整。此外，本文提出的ASWPSO 算法引入了一個新的參數，即停滯閾值Sg。從第2章算法描述部分可知，Sg 不僅影響著算法的搜索平穩程度，而且影響著小世界拓撲結構自適應調整的頻率。本小節將對這一參數進行調研，研究在Sg＝3，5，7，10和15這5種情況下算法的性能，表4報告了它們在不同函數上所取得的結果的平均值；圖10則以單峰函數f1和多峰函數f13為例分析不同參數設置下算法的收斂特征。

由表4和圖10 發現，當Sg 取較小值 （Sg＝3）時，算法的求解精度較差，其在單峰函數f1上僅能獲得10－26數量級的精度是5 種參數設置下最差的結果；另一方面，在優化多峰函數f13時，盡管沒有陷入局部最優，但精度仍比Sg＝5時要差。因為當Sg 過小時，粒子將過于頻繁地更換搜索的方向，造成粒子震蕩、不能進行平穩地 “爬坡”，從而導致對峰值的逼近能力降低。因此推薦使用Sg≥5。

下面對比Sg≥5 時情況，由表4 和圖10 不難發現，當Sg≥5時算法不論是算法的收斂速度還是全局尋優能力，都會隨著Sg 的增加而降低。首先，當Sg 過大時，粒子的引導向量更新較慢，導致粒子可能一直沿著一個次優的方向進行搜索，從而降低了粒子群體的搜索效率和算法的收斂速度。其次，Sg 的增大同樣帶來了K 和P 這兩個拓撲參數自適應調節帶來的效果的滯后。前面分析到，根據種群的停滯狀態調節K 和P 有助于種群跳出局部最優，因此，較大的Sg 設置使種群更易于陷入局部最優無法跳出。綜上所述，我們建議ASWPSO 算法中的停滯閾值參數Sg 設置為5。

圖9 3種算法的收斂曲線對比

圖10 不同參數Sg 設置下ASWPSO 的收斂曲線

表4 不同參數Sg 設置下ASWPSO 的性能比較

4 結束語

本文提出一種自適應小世界拓撲粒子群優化算法（ASWPSO）。其中，每個粒子都與其最近鄰緊密連接，且通過小世界隨機化，粒子可能會隨機重連到整個群體中的其它粒子。小世界隨機連接過程中產生的長程邊使得拓撲圖的特征路徑長度減小，從而改善整個群體的收斂速度。此外，使用了細粒度的拓撲結構，允許不同維度的粒子采用不同的小世界網絡拓撲，這有助于粒子的搜索更加多樣化，提高PSO全局尋優能力。在算法的執行過程中，小世界拓撲結構中的參數將根據整個粒子群體的停滯狀態自適應地進行調整，通過這種方式，粒子群體搜索的有效性和效率得到提高。

在本文的實驗部分，所提出的ASWPSO 算法在13個基準函數上進行了測試，其性能與使用規則拓撲結構的VNPSO和使用隨機拓撲結構的DMS－PSO進行了比較。實驗結果驗證了所提出的自適應小世界拓撲的高效性和魯棒性。

［1］Gong Y－J，Zhang J，Chung H S－H，et al.An efficient resource allocation scheme using particle swarm optimization ［J］.IEEE Trans Evolut Comput，2012，16 （6）：801－816.

［2］Gong Y－J，Zhang J，Liu O，et al.Optimizing the vehicle routing problem with time windows：a discrete particle swarm optimization approach ［J］.IEEE Trans Syst Man Cybern Part C Appl Rev，2012，42 （2）：254－267.

［3］Gong Y－J，Shen M－E，Zhang J，et al.Optimizing RFID network planning by using aparticle swarm optimization algorithm with redundant reader elimination ［J］.IEEE Trans Ind Inf，2012，8 （4）：900－912.

［4］Li M，Lee W－C，Sivasubramaniam A，et al.SSW：A smallworld－based overlay for Peer－to－Peer search ［J］.IEEE Trans Parallel Distrib Syst，2008，19 （6）：735－749.

［5］Guidoni D L，Mini R A F，Loureiro A A F.Applying the small world concepts in the design of heterogeneous wireless sensor networks ［J］.IEEE Commun Lett，2012，16 （7）：953－955.

［6］Watts D J，Strogatz S H.Collective dynamics of small－world networks［J］.Nature，1998，393：440－442.

［7］Newman M E J，Watts D J.Renormalization group analysis of the small－world network model［J］.Phys Lett A，1999，263（4）：341－346.

［8］Barrat A，Weigt M.On the properties of small－world network models［J］.Eur Phys J B，2000，13 （3）：547－560.

［9］Poli R，Kennedy J，Blackwell T.Particle swarm optimization an overview ［J］.Swarm Intell，2007 （1）：33－57.

［10］Liang J J，Suganthan P N.Dynamic multi－swarm particle swarm optimizer ［C］//Proc IEEE Swarm Intell Symp，2005：124－129.

［11］Clerc M.Standard particle swarm optimisation－from 2006to 2011.Particle swarm central［EB/OL］. ［2012－09－23］.Available：http：//www.particleswarm.info.

［12］Kennedy J.Small worlds and mega－minds：Effects of neighborhood topology on particle swarm performance ［C］//Proc IEEE Congr Evol Comput，1999：1931－1938.

［13］Matsushita H，Nishio Y.Network－structured particle swarm optimizer with small－world topology ［C］//Proc Int Symp Nonlinear Theory Appl，2009：372－375.

［14］Liu Y－M，Zhao Q－Z，Shao Z－Z，et al.Particle swarm optimizer based on dynamic neighborhood topology ［G］.LNCS 5755：Emerging Intell Comput Technol Appl，2009：794－803.

［15］WANG Xuefei，WANG Fang，QIU Yuhui.Research on a novel particle swarm algorithm with dynamic topology ［J］.Computer Science，2007，34 （3）：205－207 （in Chinese）.［王雪飛，王芳，邱玉輝.一種具有動態拓撲結構的粒子群算法研究 ［J］.計算機科學，2007，34 （3）：205－207.］

［16］MU Huaping，ZENG Jianchao.Particle swarm optimization with dynamic evolutionary neighborhood of small－world model［J］.Journal of System Simulation，2008，20 （15）：3940－3943 （in Chinese）.［穆華平，曾建潮.基于小世界模型動態演化鄰域的微粒群算法 ［J］.系統仿真學報，2008，20（15）：3940－3943.］

［17］ MU Huaping，ZENG Jianchao，JIAO Changyi.Particle swarm optimization based－on small world neighborhood structure［J］.Journal of Taiyuan University of Science and Technology，2009，30 （1）：7－12 （in Chinese）. ［穆華平，曾建潮，焦長義.基于小世界鄰域結構的微粒群算法研究 ［J］.太原科技大學學報，2009，30 （1）：7－12.］

［18］Mendes R，Kennedy J，Neves J.The fully informed particle swarm：simpler，maybe better ［J］.IEEE Trans Evolut Comput，2004，8 （3）：204－210.

［19］Yao X，Liu Y，Lin G－M.Evolutionary programming made faster［J］.IEEE Trans Evol Comput，1999，3 （2）：82－102.

［20］García S，Molina D，Lozano M，et al.A study on the use of non－parametric tests for analyzing the evolutionary algorithms’behavior：A case study on the CEC2005special session on real parameter optimization ［J］.J Heuristics，2009，15 （6）：617－644.