混合鄰域結(jié)構(gòu)的粒子群算法

張澤星

（石家莊經(jīng)濟學(xué)院網(wǎng)絡(luò)信息安全實驗室，河北石家莊 050031）

粒 子 群 算 法（particle swarm optimization，PSO）是KENNEDY 和EBERHART 兩位博士于1995年提出的新型進化算法［1］，因其具有易于實現(xiàn)、精度高、收斂快等優(yōu)點，且在解決實際問題中表現(xiàn)優(yōu)異，自提出以來便受到了學(xué)術(shù)界的廣泛重視［2－3］。然而，標準PSO 算 法 的 缺 點 也 是 明 顯 的［4］，首先容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象。其次，PSO 的性能也依賴于算法參數(shù)。為此，研究人員分別采用粒子群初始化、鄰域拓撲、參數(shù)選擇和混合策略等改進措施克服上述不足［4］。

為避免由于粒子向自身歷史最佳位置和群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)現(xiàn)象，在分析不同拓撲結(jié)構(gòu)對算法性能影響的基礎(chǔ)上，結(jié)合全局模型，同時使用無標度網(wǎng)絡(luò)作為局部鄰域拓撲，在標準測試函數(shù)上的實驗結(jié)果表明，該方法可有效平衡算法的開采和挖掘能力，性能良好。

1 全局模型與局部模型

1.1 標準粒子群算法（SPSO）

基本粒子群算法的數(shù)學(xué)表示如下：設(shè)搜索空間為D維，由n個粒子組成種群；用Xti和Vti分別表示第i個粒子在第t步迭代時所處的位置和飛行速度：Xti＝（xti1，xti2，…，xtiD），Vti＝（vti1，vti2，…，vtiD）；記pti和ptg分別為到第t次迭代為止，第i個粒子自身經(jīng)歷的最佳位置和種群經(jīng)歷的最佳位置。

每個粒子的位置按如下公式變化：

式中：w為慣性因子；d＝1，2，…，D；i＝1，2，…，n；t為當前迭代次數(shù)；c1，c2為正的常數(shù)，稱為加速因子；r1和r2為［0，1］區(qū)間內(nèi)的均勻隨機數(shù)。

式（1）將其他全部粒子視為當前粒子的鄰域，pgd是該鄰域中粒子的歷史最佳位置，該模型被稱為全局模型。除了全局模型外，EBERHART［5］等最早提出了局部版的粒子群算法。局部模型將式（1）中的pgd替換為pld，pld代表當前粒子的拓撲鄰域中所有粒子的最優(yōu)位置。目前，已被廣泛接受的結(jié)論是：鄰域結(jié)構(gòu)是決定PSO 算法效果的極重要因素，這是因為鄰域結(jié)構(gòu)決定了優(yōu)秀等位基因的傳播和混合，從而影響到搜索性能［6］。前人的研究表明［7］，全局模型收斂速度較快，具有較強的局部搜索能力，但魯棒性較差；局部模型收斂速度較慢，但具有較強的全局搜索能力，魯棒性較好。本文將這2種模型結(jié)合在一起，設(shè)計了一種新的混合模型。

1.2 鄰域拓撲分析

式（1）被稱為全局模型，該模型中，粒子i的鄰域集合為P－｛i｝，其中，P為全體粒子。也就是說，任何2個粒子之間均存在著“聯(lián)系”，從而，全局模型的鄰域拓撲為一個完全圖。

局部模型的鄰域拓撲主要有［7－8］1）環(huán)形拓撲：所有粒子首尾互連構(gòu)成一個環(huán)。2）星形拓撲：以其中一個粒子為中心，該中心與相鄰的其他粒子進行信息交換，且其他粒子之間互不聯(lián)系。3）塔形拓撲：也稱K面體結(jié)構(gòu)，粒子分布在K面體的K個頂點上，然后所有K面體再相互連接起來。4）馮·諾依曼拓撲：用三維網(wǎng)格的形式把粒子與它上下左右4個最鄰近的粒子相互連接，形成立體網(wǎng)狀結(jié)構(gòu)。

上述提到的拓撲結(jié)構(gòu)特點主要有2個：靜態(tài)性和規(guī)則性，即拓撲結(jié)構(gòu)是事先給定的規(guī)則圖?？紤]到個體交互的隨機性，研究人員將動態(tài)變化或非規(guī)則的拓撲結(jié)構(gòu)引入局部模型，做法分為3類：第1類是從空間距離的角度劃分鄰域。早在1999年，SUGANTHAN［9］引入一個時變的歐氏空間鄰域算子：在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴展到整個種群。再如：范成禮［10］等提出了帶審斂因子的變鄰域粒子群算法，有效避免了常規(guī)PSO 算法在復(fù)雜多峰函數(shù)的求解過程中容易陷入早熟收斂的問題，提高了全局搜索能力。第2類單純從粒子的社會關(guān)系角度進行鄰域動態(tài)或非規(guī)則劃分，如：彭虎［11］等將隨機拓撲和馮·諾依曼拓撲相結(jié)合形成動態(tài)社會關(guān)系鄰域；GONGSUN［12］等將基于小世界網(wǎng)絡(luò)的鄰域結(jié)構(gòu)引入到粒子群優(yōu)化求解中。還有一類借助子群或簇來建立信息交換的拓撲結(jié)構(gòu)，如：郭文忠［13］等基于“簇”思想，對粒子間距離進行重新定義并給出了相應(yīng)的動態(tài)鄰域PSO 算法。再如：倪慶劍［14］等引入了一種粒子群信息共享方式——多簇結(jié)構(gòu)，進而提出了動態(tài)可變拓撲策略以協(xié)調(diào)動態(tài)概率粒子群優(yōu)化算法的勘探和開采能力。針對不同的優(yōu)化問題，這些拓撲的性能表現(xiàn)各異；但總的來說，隨機拓撲往往對大多數(shù)問題能表現(xiàn)出較好的性能［4］。

2 混合拓撲模型

2.1 使用混合拓撲的PSO

使用復(fù)雜網(wǎng)絡(luò)作為局部鄰域首先要解決的問題是建立復(fù)雜網(wǎng)絡(luò)。建立復(fù)雜網(wǎng)絡(luò)的算法有許多，本文采用無標度網(wǎng)絡(luò)作為鄰域拓撲，建立該類型網(wǎng)絡(luò)的最知名的算法莫過于BA 網(wǎng)絡(luò)模型。BA 模型具體描述如下［15］。

假設(shè)網(wǎng)絡(luò)最初有m0個節(jié)點。每一次加入一個新節(jié)點，每次加入的新節(jié)點通過m（m≤m0）條新加入的連接邊與網(wǎng)絡(luò)中已有的m個節(jié)點相連。每個新節(jié)點與節(jié)點i相連的概率∏（ki）依賴于節(jié)點i的度ki，且該概率服從如下規(guī)則：

重復(fù)加入t個節(jié)點后，將得到一個有N＝t＋m0個節(jié)點和mt條邊的網(wǎng)絡(luò)。

其次，需要建立粒子與網(wǎng)絡(luò)節(jié)點之間的映射，映射的方法有2種：1）當節(jié)點數(shù)與粒子數(shù)相等時，可以采用一對一的映射；2）當節(jié)點數(shù)大于粒子數(shù)時，可以采用多對一的映射，即一個粒子對應(yīng)網(wǎng)絡(luò)上多個節(jié)點。本文采用的是第2種方式。不妨設(shè)映射函數(shù)為f：i→N（i），它將粒子i映射到網(wǎng)絡(luò)節(jié)點集N（i）上，N（i）＝｛N1（i），N2（i），…，N｜N（i）｜（i）｝；其中，網(wǎng)絡(luò)節(jié)點Nj（i）（j＝1，2，…，｜N（i）｜）的鄰居集合為｛Nj1（i），Nj2（i），…，N｜Nj（i）｜（i）｝。在迭代時，按如下步驟確定粒子i的鄰域。

步驟1：借助映射函數(shù)，確定i對應(yīng)的網(wǎng)絡(luò)節(jié)點集合N（i）；

步驟2：隨機從N（i）中取一個元素，不妨設(shè)為Nj（i）；

步驟3：將Nj（i）的鄰居作為i的鄰域。

基于無標度網(wǎng)絡(luò)鄰域結(jié)構(gòu)的粒子群算法的主體流程如下。

步驟1：初始化運行參數(shù)；

步驟2：初始化速度和位置；

步驟3：計算適應(yīng)度；

步驟4：創(chuàng)建無標度網(wǎng)絡(luò)；

步驟5：建立粒子與網(wǎng)絡(luò)節(jié)點的映射關(guān)系；

步驟6：WHILE（滿足迭代條件）；

6.1 如果最優(yōu)解沒有更新；

6.1.1 為每個粒子產(chǎn)生鄰域；

6.2 對每個粒子；

6.2.1 從其鄰域中找到最優(yōu)個體；

6.2.2 更新速度與位置；

6.3 更新個體最優(yōu)歷史；

6.4 更新種群最優(yōu)歷史；

步驟7：返回最優(yōu)個體。

上述算法中，速度更新公式如下：

式中：Px，Pl，Pg分別代表粒子的歷史最優(yōu)、鄰域最優(yōu)及種群最優(yōu)；w，c分別為慣性因子和加速因子；r1，r2，r3分別為［0，1］內(nèi)的3個隨機數(shù)。

位置更新公式如下：

2.2 算法分析

全局模型的拓撲是一個完全圖（規(guī)則圖）；大量研究結(jié)果表明：使用隨機拓撲的粒子群算法效果良好。然而，現(xiàn)實中的網(wǎng)絡(luò)即非規(guī)則圖也非隨機圖，大多數(shù)現(xiàn)實網(wǎng)絡(luò)都呈現(xiàn)無標度特性。因此，使用無標度網(wǎng)絡(luò)作為鄰域拓撲使粒子的交互結(jié)構(gòu)更貼近現(xiàn)實。從式（4）來看，速度更新考慮了粒子自身的歷史、鄰域和種群三方面信息，從另外一個角度來說，本文設(shè)計的是介于全局和局部模型之間的混合模型。

從上面的描述來看，粒子的鄰域是動態(tài)變化的，粒子i映射的網(wǎng)絡(luò)節(jié)點集為N（i）＝｛N1（i），N2（i），…，N｜N（i）｜（i）｝，粒子的鄰域取決于：1）從N（i）中隨機抽取的是哪個網(wǎng)絡(luò)節(jié)點；2）隨機抽取的網(wǎng)絡(luò)節(jié)點（不妨設(shè)為Nj（i））的度及其相鄰節(jié)點。

由于無標度網(wǎng)絡(luò)符合冪律分布，設(shè)在網(wǎng)絡(luò)中隨機抽取到度為k的節(jié)點概率為p（k），可以證明［15］：

該式說明，度越大的節(jié)點出現(xiàn)在網(wǎng)絡(luò)中的概率越小。也就是說，大多數(shù)粒子的鄰域規(guī)模都比較小。

在空間和時間復(fù)雜度方面，與標準粒子群算法相比，本文算法空間上需要額外存儲復(fù)雜網(wǎng)絡(luò)；時間上增加了尋找粒子鄰域的支出。收斂性方面，由于并未從根本上改變粒子群算法的流程，因此，本文算法的收斂性證明與標準粒子群算法一致。

3 實驗結(jié)果

借助實驗，需要探究的問題包括：1）算法的性能比較；2）算法的收斂情況；3）不同維度與不同運行參數(shù)下的算法性能；4）復(fù)雜網(wǎng)絡(luò)節(jié)點數(shù)與算法性能的關(guān)系；5）運行時間的比較分析等等。由于篇幅關(guān)系，本文僅針對于問題1）和問題2）進行詳細的實驗及其結(jié)果分析。

3.1 實驗設(shè)計

實驗采用的3個經(jīng)典測試函數(shù)分別描述如下。

這3個函數(shù)各有特點，如圖1所示，f1有明顯的全局最優(yōu)，梯度變化明顯；f2在相對“平坦”的區(qū)域有許多局部最優(yōu)；f3的梯度變化不明顯。相比之下，f1的全局最優(yōu)最容易尋找；f2和f3尋全局最優(yōu)解則都比較困難，分別要求算法具有較強的逃逸局部最優(yōu)的能力（也可以說是勘探能力）和持續(xù)進化的能力（或說是開采能力）。

比較算法來自于SPSO2011［16］，其源代碼從文獻［17］獲取。每個測試函數(shù)上獨立運行10次，分別記錄：在所有運行中找到最好解（記為HB）、每次獨立運行最優(yōu)解的平均值和方差（分別記為MEAN和STD）。從某種程度上講，HB越好則算法的開采能力越強。平均數(shù)反應(yīng)的是數(shù)據(jù)的集中趨勢，越集中說明算法性能越穩(wěn)定；方差反映的是離散程度，從某種意義上講，越離散說明算法魯棒性越差。

圖1 測試函數(shù)圖形Fig.1 Figure of test functions

3.2 實驗結(jié)果及分析

實驗一：性能比較。函數(shù)維度D＝20，網(wǎng)絡(luò)節(jié)點數(shù)取為100，粒子個數(shù)為30。公平起見，其他參數(shù)設(shè)置同所比較的SPSO2011 代碼［17］。實驗結(jié)果見表1，方便起見，以下將本文算法簡記為NPSO。表1中，指標值更好的結(jié)果用黑體表示。不難看出，本文算法全面超過了SPSO。

表1 性能比較結(jié)果Tab.1 Compared results of performance

從表1來看，在f1上，NSPO 取得的STD 非常小且其MEAN 接近HB，說明NPSO 總能為f1找到非常優(yōu)異的解。這得益于f1僅有一個全局最優(yōu)，而且梯度變化明顯（見圖1）。但盡管如此，SPSO 僅能找到7.752 574e－05這樣的解，遠次于NPSO 的7.230 542e－133。這可能是因為在f1的“底部”，地勢較平坦，盡管全局不存在局部最優(yōu)，但SPSO 在較平坦的底部地形上，“前進”非常困難，而NPSO針對于這樣的地形，尋優(yōu)能力優(yōu)越。

在f2上，NSPO 的HB指標值遠優(yōu)于SPSO，但兩者均值相差不大。實驗中發(fā)現(xiàn)，NSPO 在f2上，多數(shù)情況下能找到10－15這一數(shù)量級的解，偶爾找到100這一數(shù)量級的差解。對應(yīng)的，SPSO 最好解的數(shù)量級在10－5，最差解的數(shù)量級為100。這反應(yīng)出NSPO 跳出局部最優(yōu)解的能力要強于SPSO。但由于f2存在大量的局部最優(yōu)，盡管NSPO 的勘探能力強于SPSO，但仍有很大提升空間。

在f3上，NSPO 的STD 大于SPSO，但HB 小于SPSO，說明NSPO 具備找到更好解的能力。由于f3的梯度信息不明顯甚至存在“誤導(dǎo)”的梯度信號，比如：從當前位置向左尋找確實能使得解得以進化，但如果正確的方向應(yīng)該是向下，則“向左”的梯度可能會誤導(dǎo)算法走向錯誤的方向。如此，則會大大降低算法的搜索效率。正因為此，最好情況下，NSPO只找到了10－4這一數(shù)量級的解。

實驗二：收斂性實驗。收斂性結(jié)果可以從某種程度上反應(yīng)出算法是否早熟；從某種程度上揭示參數(shù)對收斂性及性能的影響等。圖2給出了NPSO與SPSO 一次獨立運行中收斂結(jié)果的比較示意圖，本實驗采用的運行參數(shù)完全同于實驗一。圖2a），c），e）分別是NSPO 在f1，f2，f3上的收斂示意圖；圖2b），d），f）分別是SPSO 在3個測試函數(shù)上的收斂示意圖。

圖2b）明顯反應(yīng)出SPSO 在f1上存在早熟或停滯現(xiàn)象，最優(yōu)解僅僅進化了100余次。從圖2a）看出，NSPO 在f1上進化了近2 000次。

在f2上，要求算法必須不斷地逃逸出局部最優(yōu)。圖2c）和圖2d）顯示，NSPO 的進化次數(shù)是SPSO 的3倍多。這說明NSPO 的逃逸能力要強于SPSO，但終究還是在進化了500余次后陷入了無法逃出的某個局部解。這種情況下，增加迭代次數(shù)對提高算法性能顯然是無益地。

圖2 收斂對比結(jié)果Fig.2 Compared results of convergence

在f3上，不存在局部最優(yōu)解，但存在大量的“誤導(dǎo)”梯度。從圖2d）和圖2f）可以看出，2種算法均進化了3 000 余次，在一定的迭代次數(shù)內(nèi)，無論是NSPO 還是SPSO，算法總能進化，但這種持續(xù)的進化最終使得2種算法均出現(xiàn)“南轅北轍”的現(xiàn)象。但總體上，NSPO 克服“誤導(dǎo)”梯度的能力要更強一些。

4 結(jié) 語

本文提出的算法綜合了全局和局部模型，粒子的局部鄰域拓撲根據(jù)無標度網(wǎng)絡(luò)的結(jié)構(gòu)確定。實驗結(jié)果表明，借助無標度網(wǎng)絡(luò)作為鄰域拓撲是可行的。與標準PSO 的全局模型相比，本文算法在避免早熟、陷入局部最優(yōu)、停滯這些缺點上，有較好的改善。新算法的適應(yīng)性、魯棒性更強，具有較強的可應(yīng)用性和拓展性。

／References：

［1］ KENNEDY J，EBERHART R C.Particle swarm optimization［A］.Proceedings of IEEE International Conference on Neural Networks［C］.Piscataway：IEEE Press，1995：1942－1948.

［2］ RADA－VILELA J，JOHNSTON M，ZHANG M J.Deception，blindness and disorientation in particle swarm optimization applied to noisy problems［J］.Swarm Intelligence，2014，8（4）：247－273.

［3］ SHEN M，ZHAN Z H，CHEN W N，et al.Bi－velocity discrete particle swarm optimization and its application to multicast routing problem in communication networks［J］.IEEE Transactions on Industrial Electronics，2014，61（12）：7141－7151.

［4］ 戴 朝 華.粒 子 群 優(yōu) 化 算 法 綜 述［EB／OL］.http：／／www.doc88.com／p－30490875816.html，2010－05－24.DAI Zhaohua.A Suvery of Particle Wwarm Optimization［EB／OL］.http：／／www.doc88.com／p－30490875816.html，2010－05－24.

［5］ EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory［A］.Proceedings of the 6th International Symposium on Micro Machine and Human Science［C］.［S.l.］：IEEE Xplore，1995：39－43.

［6］ PAYNE J L，GIACOBINI M，MOORE J H.Complex and dynamic population structures：Synthesis，open questions，and future directions［J］.Soft Computing，2013，17（7）：1109－1120.

［7］ KENNEDY J.Small worlds and mega－minds：Effects of neighborhood topology on particle swarm performance［A］.Proceedings of the IEEE Congress on Evolutionary Computation［C］.Washington：IEEE，1999：1931－1938.

［8］ KENNEDY J，MENDES R.Population structure and particle swarm performance［A］.Proceedings of IEEE Congress on Evolutionary Computation［C］.Honolulu：［s.n.］，2002：1671－1676.

［9］ SUGANTHAN P N.Particle swarm optimiser with neighbourhood operator［A］.Proceedings of the IEEE Congress on Evolutionary Computation［C］.Piscataway： NJ，1999：1958－1962.

［10］ 范成禮，邢清華，范海雄，等.帶審斂因子的變鄰域粒子群算法［J］.控制與決策，2014，29（4）：696－700.FAN Chengli，XING Qinghua，F(xiàn)AN Haixiong，et al.Particle swarm optimization and variable neighborhood search algorithm ith convergence criterions［J］.Control and Decision，2014，29（4）：696－700.

［11］ 彭虎，張海，鄧長壽.動態(tài)鄰域混合粒子群優(yōu)化算法［J］.計算機工程，2011，37（14）：211－213.PENG Hu，ZHANG Hai，DENG Changshou.Dynamic neighborhood hybrid particle swarm optimization algorithm［J］.Computer Engineering，2011，37（14）：211－213.

［12］ GONGSUN Y J，ZHANG J.Small－world particle swarm optimization with topology adaptation［A］.Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation［C］.［S.l.］：［s.n.］，2013：25－32.

［13］ 郭文忠，陳國龍，洪玉玲.求解TSP問題的動態(tài)鄰域粒子群優(yōu)化算法［J］.漳州師范學(xué)院學(xué)報，2007，20（2）：37－41.GUO Wenzhong，CHEN Guolong，HONG Yuling.Dynamic neighborhoodd particle swarm optimization for TSP［J］.Journal of Zhangzhou Normal University，2007，20（2）：37－41.

［14］ 倪慶劍，張志政，王蓁蓁，等.一種基于可變多簇結(jié)構(gòu)的動態(tài)概率粒子群優(yōu)化算法［J］.軟件學(xué)報，2009，20（2）：339－349.NI Qingjian，ZHANG Zhizheng，WANG Zhenzhen，et al.Dynamic probabilistic particle swarm optimization based on varying multi－cluster structure［J］.Journal of Software，2009，20（2）：339－349.

［15］ BARABASI A L，ALBERT R.Emergence of scaling in random networks［J］.Science，1999，286：509－512.

［16］ CLERC M.Standard Particle Swarm Optimisation：From 2006 to 2011［EB／OL］.https：／／hal.archives－ouvertes.fr／hal－00764996，2012－09－23.

［17］ OMRAN M G H.Standard PSO Source Code Version 2011［EB／OL］.http：／／www.particleswarm.info／standard＿pso＿2011＿c.zip，2011－11－04.