自適應小世界粒子群優(yōu)化算法

龔月姣，嵇智源

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

0 引 言

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

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

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

1 背 景

1.1 小世界網(wǎng)絡

圖1 網(wǎng)絡結(jié)構(gòu)

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

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

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

1.2 粒子群優(yōu)化算法

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

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

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

圖2 網(wǎng)絡特征路徑長度與集聚系數(shù)

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

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

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

（5）若滿足算法結(jié)束條件，輸出gBest；否則，跳轉(zhuǎn)執(zhí)行第 （2）步。

1.3 粒子群優(yōu)化算法的種群拓撲研究

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

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

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

2 自適應小世界粒子群優(yōu)化算法

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

2.1 小世界拓撲的生成

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

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

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

2.2 粒子更新

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

圖3 提出的ASWPSO算法中拓撲結(jié)構(gòu)更新過程的偽代碼

圖4 傳統(tǒng)更新機制下的粒子震蕩

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

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

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

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

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

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

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

2.3 拓撲自適應機制

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

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

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

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

2.4 整體流程

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

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

3 實驗研究

3.1 實驗設置

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

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

圖6 ASWPSO 算法的流程

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

3.2 結(jié)果與比較

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

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

表1 標準測試函數(shù)

圖7 兩個多峰函數(shù)的解空間地形

表2 3種算法的結(jié)果統(tǒng)計及對比

表3 顯著性檢驗結(jié)果

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

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

圖8 3種算法在優(yōu)化多峰函數(shù)時的盒圖對比

3.3 參數(shù)調(diào)研

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

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

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

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

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

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

4 結(jié)束語

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

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

［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）.［王雪飛，王芳，邱玉輝.一種具有動態(tài)拓撲結(jié)構(gòu)的粒子群算法研究 ［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）.［穆華平，曾建潮.基于小世界模型動態(tài)演化鄰域的微粒群算法 ［J］.系統(tǒng)仿真學報，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）. ［穆華平，曾建潮，焦長義.基于小世界鄰域結(jié)構(gòu)的微粒群算法研究 ［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.