劉昕1,2，皮建勇1,2
?。?.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 云計算與物聯網研究中心，貴州 貴陽550025）
摘要：針對標準粒子群算法易陷入局部極值和優化精度較低的缺點，結合復雜系統理論提出一種多層次粒子群算法，通過在算法結構中引入中間結構層，分別定義了進行大范圍的較優值搜索的粒子和在較優值周圍進行精細搜索的粒子，增加了粒子群的多樣性，有效協調了粒子的尋優能力。采用了兩種標準測試函數對算法性能進行了實驗，結果表明，該算法可有效避免陷入局部最優，并在保證運行速度的同時提高了求解精度。
中圖分類號：TP301文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.04.008
引用格式：劉昕，皮建勇.一種基于中間結構層的分層粒子群算法［J］.微型機與應用，2017,36（4）：25-28.
0引言
粒子群算法是基于群體智能理論的優化算法，其原理和機制簡單、清晰、易于實現，并且所需參數少、收斂速度快、魯棒性強，是智能優化算法中的一個研究熱點，目前已廣泛應用于函數尋優、系統建模、決策支持以及模糊系統控制等諸多領域。
粒子群算法是典型的群智能算法，而群智能系統實際上是一類復雜系統，這類系統具有自適應性、涌現性和開放性，研究者通常會引入中間結構層來研究復雜系統。中間結構層屬于一種模塊化和損害控制策略，借助中間結構層可以更容易研究復雜系統中各組成部分之間相互作用所涌現出的特性與規律。
本文基于復雜系統理論，在粒子群算法中引入中間結構層，提出了一種多層次粒子群算法，此算法改進了粒子間信息的共享方式，增強了粒子多樣性。實驗證明，該算法在保證收斂速度的同時，可以有效跳出局部極值，并提高算法的全局搜索能力和求解精度。
1標準粒子群算法
1.1標準PSO
粒子群優化算法（Particle Swarm Optimization, PSO）是人們在研究鳥類的群體行為基礎上提出的一種群智能算法，其基本思想是通過群體中個體之間的協作和信息共享來尋找最優解［1］。在算法中，每個優化問題的潛在解被抽象成D維搜索空間上的一個點，稱之為“粒子”，粒子通過跟蹤“個體極值（pbest）”和“全局極值(gbest)”來更新自己的位置。算法流程如下：
?。?）初始化一群隨機粒子(種群規模為m)，初始化內容包括粒子的速度信息與位置信息；
?。?）計算每個粒子的適應值，即目標函數值；
?。?）對每個粒子，將其適應值與其經過的最優位置作比較，適應度高的成為個體的當前Pbest；
（4）對每個粒子，將其適應值與群體所經過的最好位置作比較，適應度高的作為當前的全局最優解Gbest;
（5）根據速度和位置更新公式調整粒子速度和位置；
?。?）未達到結束條件則轉（2）。
算法終止條件一般為最大迭代次數或粒子群搜索到的最優位置，滿足預定最小適應閾值。
在PSO中，速度決定了粒子運動的方向和速率，位置則是粒子所代表的解在解空間的位置，是評估該解質量的基礎。
速度更新公式和位置更新公式如下:
![JBF{DGGD92PYZ]HG~K[_}}2.png](http://files.chinaaet.com/images/2017/03/04/6362424079297789363743146.png "JBF{DGGD92PYZ]HG~K[_}}2.png")
式(1)的第一部分表示上次速度的影響，w是慣性權重，它使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區域。第二部分來自于粒子個體的經驗，是從當前點指向粒子歷史最好點的一個矢量；第三部分是一個從當前點指向種群最好點的矢量，反映了粒子間的全局協同合作和知識共享。其中c1和c2代表加速系數，即個體經驗與社會經驗對粒子的影響程度。Rand是隨機數。m為種群規模，一般設置在20~100之間，若側重于減少運行時間，則種群規模可設為40左右，若偏向于高精度和高穩定性，則可設為60或80。
1.2相關研究
PSO算法既有深刻的智能背景、適合科學研究，又簡單易實現、適合工程應用。因此一經提出便引起信息和進化計算科學領域學者們的廣泛關注，形成了一個新的熱點，目前已有大量研究者從參數設置、拓撲結構等角度對傳統PSO進行了研究與改進。
1.2.1參數設置
粒子群算法所需參數少，但是對參數依賴性較大，因此相關參數的設定對PSO的優化性能有著重要影響。
慣性權重方面：研究表明較大的慣性權重有利于粒子群在更大的解空間內進行搜索，從而跳出局部最優值，而較小的慣性權重有利于算法的收斂。SHI等人提出了慣性權重隨著迭代次數線性遞減的模型。一般情況下將慣性權重的初始值設置為0.9，隨著迭代次數遞減到0.4，算法開始階段，大的慣性權重可以使算法不容易陷入局部最優，到算法的后期，小的慣性權重可以使收斂速度加快，使收斂更加平穩［2］。
加速系數方面：一般被設為相同的值，最常見的是2，另一個常見的取值為1.494 45。彭宇等人利用方差分析法分析了慣性權重和加速系數對算法性能的影響，并給出了這兩種參數的設置參考原則［3］。ZHAN等提出了一種使用聚類的方法對進化狀態進行判斷并且對加速系數進行相應調整的方案［4］。
1.2.2拓撲結構研究
在PSO算法中,粒子之間通過相互學習尋找最優解，這種學習通過共享粒子所發現的最優解來實現，所以粒子之間的信息共享方式對算法的性能有著至關重要的影響，粒子之間的信息共享方式體現為粒子群的鄰域拓撲結構，因此，對粒子群的鄰城拓撲結構進行研究也十分重要［5］。KENNEDY最早開始對PSO算法中的鄰域結構進行研究，提出了幾種經典的鄰域拓撲，并從小世界網絡模型出發，對PSO算法中的鄰域拓撲進行了初步的探索［6］。MENDES較為系統地分析了粒子群體中的拓撲結構對PSO性能的影響，并肯定了粒子群的拓撲結構對PSO算法的魯棒性和執行性能有直接的作用［7］，其研究發現，粒子個體間社會交互的平均連接度越高，群體中的信息傳播速度就越快，但是發生早熟收斂的風險也越大［7］。
2多層次粒子群算法
2.1中間結構層
中間結構層是處理復雜系統的一種方法。復雜系統中，在組分和系統之間經常會涌現出一些中間結構，稱為“集體”，一個集體可能具有復雜的內部結構，但外表上呈現為一個整體單位，作為一個單位與其他集體進行相互作用。
集體具有強的內聚和弱的外部耦合，比單個組分更適合作為“個體”來處理。借助集體，可能相互作用和不可能相互作用的組分之間有了一個確定的概念性區別，而集體構成的中間結構層可將復雜系統問題分解為更簡單、易處理的兩個部分：集體分析研究集體的內部結構和集體行為，系統分析研究集體對于系統整體行為的貢獻。
由于粒子群屬于一類復雜系統，本文將在粒子群系統中引入中間結構層，構成“基礎粒子層集體層系統”的多層次粒子群結構，通過定義不同類型的集體達到增加粒子多樣性的目的，并通過改進集體之間的交流方式改善粒子群算法的性能。
2.2多層次PSO算法
2.2.1算法思想
傳統粒子群算法易于過早收斂，其主要原因在于進化過程中粒子的多樣性損失過快，所有的粒子依循相同的方式飛行，很容易造成所有粒子搜尋方向雷同，所以本文通過定義不同類型的集體，使屬于不同類型集體的粒子按照不同的搜索策略進化，來增強粒子的多樣性，提升粒子的尋優能力。
首先定義F類集體，速度更新公式如下：
vk+1id=wFvkid+cF1rand()(pid-xkid)+cF2rand()(pFgbest-xkid)(3)
F類集體的目的是盡可能在解空間進行大范圍的搜索，慣性權重將保持固定的較大值，為了避免過早陷入局部極值，F類集體的搜索策略注重于個體經驗，而削弱全局經驗的影響，即它將僅受到自身經驗與集體內部產生的全局最優值的影響。
其次定義用于精細搜索的S類集體，速度更新公式如下：
S類集體的目的是幫助算法更好地收斂，慣性權重將保持固定的較小值，S類粒子參考所有類型的集體的社會經驗產生的較優值，并在其周圍進行精細搜索，最終得到全局最優值。
算法思想：由F類集體進行大范圍的較優值搜索，并產生初步最優值FGBEST反饋給S類集體；而S類集體則在初步最優值周圍進行精細搜索，并產生本次迭代的最終最優值SGBEST。之后的每次迭代中，F類集體繼續尋找其他較優值，而S類集體綜合考慮兩類集體粒子產生的最優值，并在其附近進行精細搜索。
2.2.2算法流程
?。?）初始化一群隨機粒子(種群規模為m)，初始化的內容包括粒子的速度和位置信息、粒子所屬的集體類型；
?。?）計算每個粒子的適應度（即目標函數值）；
?。?）對每個粒子，將其適應值與其經過的最優位置作比較，適應度高的成為個體的當前Pbest；
?。?）對F類粒子，將其適應值與集體所經過的最好位置作比較，適應度高的作為當前集體內的最佳位置即Fgbest，并反饋給S集體；對S類粒子，將其適應值與集體內所經過的最好位置比較，適應度高的作為集體內最佳位置即Sgbest；
?。?）根據速度和位置更新公式調整粒子速度、位置；
(6)未達到結束條件則轉(2)。
結束條件為最大迭代次數或Sgbest滿足預定最小適應閾值。
3實驗
3.1參數定義與測試函數
實驗采用兩種標準測試函數即Sphere函數、Griewank函數對算法進行性能測試，其中Sphere函數是單峰函數，主要用于測試算法的收斂速度和求解精度；Griewank函數是典型的非線性多模態函數，是具有廣泛的搜索空間并且具有大量局部最優點的多峰函數，算法很容易陷入局部最優，此函數通常被認為是優化算法很難處理的復雜多模態問題，因此本文用Griewank函數測試算法的全局搜索能力。
Sphere函數表達式如下：
3.2集體內粒子數對多層次PSO的影響
多層次粒子群算法中，粒子分為在解空間內迅速進行大范圍搜索的F集粒子、在初步較優值周圍進行精細搜索的S集粒子。本文在粒子群種群數目為30、60、90的情況下，對兩種類型粒子的數量對算法性能的影響做了實驗。實驗平臺為MATLAB2012，S集體的w=0.9，c1=c2=0.5；S集的w=0.4，c1=c2=1.494 45；算法最大迭代次數為1 000次；對每個函數的測試均運行50次，結果取平均值。實驗結果如表1、表2所示。
實驗結論：
?。?）在種群規模不變的情況下，用于快速搜索的F集粒子少于精細搜索的S集粒子時，尋優精度較高，當F集體粒子與S集體粒子數量之比為1：2時，算法精度達到最高，但當F集粒子數量繼續減少時，尋優能力會有所降低。
（2）由于兩類集體內粒子數量之比的變化不會影響粒子群總體規模，因此對運行時間沒有顯著影響。
?。?）當粒子規模逐漸增大時，解的質量會有所提高，但相應運行時間會有所增加。
3.3與標準PSO的對比實驗
圖1sphere函數對比實驗中，種群規模取100，F集體粒子數量與S集體粒子數量為1:2；最大迭代次數為500次；其他參數設定如3.2。實驗結果如圖1和表3所示。
從圖1可以看出，多層次PSO在迭代至200次左右時即找到了全局最優值，而標準PSO是在400次之后，說明多層次PSO的收斂能力強于標準PSO，并且通過表3的實驗數據可以看出多層次PSO的求解精度高于標準PSO。
從圖2中可以看出，多層次PSO在算法前期的尋優精度和速度都強于標準PSO，并且由于多峰函數具有多個局部最優點，因此標準版PSO在迭代至230代左右時陷入了局部極值，而多層次PSO可以跳出局部極值繼續尋優，從表4實驗數據可以得出多層次PSO最終得到的最優值的質量遠遠高于標準PSO。
4結論
本文提出了一種多層次的粒子群算法，通過引入中間結構層構造了不同類型的粒子，從而增加了粒子多樣性。實驗證明，此改進方法能使算法有效跳出局部極值，并在保證收斂速度的同時提高了求解精度。
參考文獻
［1］ 黃少榮.粒子群優化算法綜述［J］.計算機工程與設計, 2009, 30(8):19771980.
?。?］ 楊維，李歧強.粒子群優化算法綜述［J］.中國工程科學，2004，6（5）：87-94.
?。?］ 陳貴敏，賈建援，韓琪.粒子群優化算法的慣性權值遞減策略研究［J］.西安交通大學學報，2006，40（1）：53-56.
?。?］ 胡旺，李志蜀.一種更簡化而高效的粒子群優化算法［J］.軟件學報，2007，18（4）：861-868.
?。?］ 王偉,李枚毅,彭霞丹.一種雙層可變子群的動態粒子群優化算法［J］.小型微型計算機系統,2012, 33(1):145150.
?。?］ 朱艷偉,石新春,但揚清,等.粒子群優化算法在光伏陣列多峰最大功率點跟蹤中的應用［J］.中國電機工程學報, 2012, 32(4):42-48.
［7］ 王雪飛,王芳,邱玉輝.一種具有動態拓撲結構的粒子群算法研究［J］.計算機科學,2007, 34(3):205-207.