自適應群體結構的粒子群優化算法

孫文新，穆華平

(1.鶴壁職業技術學院電子信息工程學院，河南鶴壁458030;2.鶴壁職業技術學院 公共基礎教研部，河南 鶴壁458030)

粒子群優化算法(particle swarm optimization，PSO)是一種啟發式全局優化算法，由Kennedy和Eberhart[1]于1995年首次提出，其基本思想源于他們早期對鳥類群體行為的規律性研究.由于粒子群優化算法概念簡單、參數少，且能根據當前的搜索情況動態調整搜索策略，已經在電力、化工、通訊和醫學等[2-4]眾多領域成功應用.然而在處理復雜環境中大規模的優化問題時，效果仍不能盡如人意.

研究證明[5]，粒子群算法中粒子間的關聯形式能夠直接影響到算法的優化性能.楊雪榕等[6]提出了一種多鄰域的粒子群優化算法，粒子按照索引號劃分成若干鄰域，每個鄰域的第1個粒子接受全局信息，其他粒子只接受鄰域內的信息，這樣就增加了鄰域內粒子搜索的獨立性;Matsushita等[7]基于WS、NW小世界網絡模型和BA無標度模型，研究了靜態群體結構與粒子群算法搜索性能之間的關系;穆華平等[8]提出一種基于小世界模型動態演化鄰域的微粒群算法，群體結構從環形規則網絡逐步進化為小世界網絡，前期保證了種群的多樣性，后期加快了收斂速度;彭虎等[9]提出一種動態鄰域混合粒子群優化算法，將隨機拓撲和馮諾依曼拓撲相結合形成動態鄰域，使用粒子鄰域全面學習搜索策略，提高算法的全局搜索能力.zhang等[10]根據微粒的度、適應值和微粒間的距離構建了一個動態的無標度結構演化過程.

從復雜網絡的形成過程中受到啟發，提出一種基于自適應群體結構的粒子群優化算法，粒子群體的結構模式以粒子的實際尋優過程和適應值為動力來引導形成.

1 粒子群優化算法概述

粒子群優化算法是一種基于迭代模式的優化方法，算法中引入“群體”和“進化”的概念，粒子根據適應值大小采用“速度－位置”模型進行搜索.群體中的每個粒子代表解空間中的一個解，解的優劣程度由適應函數決定.粒子群優化算法的數學描述如下[11]:

假設有N個沒有體積和重量的粒子組成的群體在D維搜索空間中以一定的速度飛行，每個粒子在搜索時，考慮到了自己搜索到的歷史最好位置和群體內(或鄰域內)其他粒子的歷史最好位置，在此基礎上變化位置，尋找最優解.其中第i個粒子的當前位置Xi=[xi1xi2… xid];飛行速度Vi=[vi1vi2… vid];粒子 i 所經歷的最好位置Pi=[pi1pi2… pid]，個體的最好位置Pig=[pig1pig2… pigd]代表鄰域i內所有粒子經歷過的最好位置.粒子在找到個體最優位置和全局最優位置后，根據式(1)和(2)更新自己的速度和位置:

式中:w稱為慣性權重，用來調整粒子的全局和局部搜索能力;c1、c2為學習系數，使粒子具有自我總結和向群體中優秀個體學習的能力，從而向自己的歷史最優位置以及群體內或領域內的全局最優靠攏;r1、r2是(0，1)的隨機數，使算法具有一定的隨機性.上述模型為粒子群優化算法的局部最優模型(Lbest模型)，若式(1)中第3部分的趨向位置是全局最優位置時為全局最優模型(Gbest模型).

2 自適應群體結構的粒子群優化算法

2.1 自適應群體結構思想

盡管粒子群優化算法在許多優化問題上都取得了很好的優化性能，但依然存在后期搜索速度慢和“早熟收斂”的問題.這是因為算法在搜索后期，眾多粒子都擁擠在歷史最好位置周圍，無法逃離局部最優而不斷進行重復性的無效搜索.為了提高算法的空間搜索能力，同時又保留局部快速收斂的優良性能，本文根據粒子群體在不同階段搜索模式的要求，采用自適應群體結構來調整算法的搜索能力.

觀察現實中的許多網絡，發現大多數網絡的形成過程往往是從最初的孤立節點開始，由于某種稱為“擇優連接”的動力學原因而關聯在一起，最終形成了復雜網絡.結合粒子群優化算法的搜索特性，考慮將復雜網絡形成過程中凸顯的這種現象移植到粒子群優化算法中.為避免早熟收斂，將多樣性函數做簡單改進[8]，用鄰域內最優位置代替群體平均位置，具體定義如式(3):

式中:|S|為鄰域內粒子的個數，|L|為搜索空間的最長對角線的長度，N為問題的維數，pij為第i個粒子的第j維分量，pgj為鄰域內的最優位置的第j維分量.

算法首先將粒子群體初始化為具有少量連接的隨機網絡，每個粒子都帶有一個搜索標志flag，并且初始化狀態 flag=1.若當前搜索優于前一次搜索，表明本次搜索成功，則flag=l，否則設置flag=0，此時檢測該粒子鄰域的群體多樣性，如果粒子過于集中在pgj附近，導致多樣性過低，即diversity(Si)＜dLow時，在種群中隨機選擇該鄰域以外的其他粒子建立連接，否則原有連接保持不動.

這樣，在算法初期，群體結構松散，有利于保持群體的多樣性，可以獲取盡可能多的候選解;隨著新連接的不斷加入，由于受到最優位置的引導，群體中部分粒子以接近Gbest模型的尋優方式進行搜索，多數粒子以接近Lbest模型的尋優方式進行搜索，在全局搜索和局部搜索之間獲得了很好的折衷;到了算法后期，算法基本圍繞在全局最優附近搜索，此時群體連接更加密集，形成高連通度的群體結構，有利于粒子對最優解所在的空間內進行深度的細致搜索，進而保證算法以較快的速度搜索到全局最優位置.

2.2 慣性權重的調整

在粒子群優化算法中，搜索陷入局部極值，往往表現為算法重復進行無效的搜索，而粒子的位置幾乎靜止不變.為了充分發揮自適應群體結構的效能，本文根據適應函數值的不同采用不同的慣性權重，以求全局最小值為例，群體中的粒子按適應值fi的變化情況分為以下3種情況:

1)群體中滿足fi＜f'arg的粒子已經比較接近全局最優，此時應賦予較小的慣性權重，以促進快速收斂于全局最優.因此將此集合中的粒子的慣性權重調整為

取ωmin=0.5，由式(4)可以看出，粒子的適應值越好，其對應的慣性權重就越小，進而加強了局部尋優的能力.

2)如果粒子滿足f'arg＜fi＜farg，則說明這些粒子具有較好的局部和全局的尋優能力，此時應保證在前期粒子進行“開發”性搜索，獲得較多候選解，后期進行“勘探”性搜索，探索出全局最優.因此考慮這部分粒子采用經典的慣性權重線性遞減的調整方法.

3)對于群體中較差的粒子，即fi＞farg時，借鑒吳浩揚等[12]提出的變異方法來調整慣性權重:

當群體搜索到的最優位置長時間未發生變化時，群體根據粒子的分布特點來調整慣性權重.若粒子分布較為分散，則Δ取較大的值來降低粒子的慣性權重，加強局部尋優，使群體趨于收斂;若粒子分布較為聚集，算法陷入局部最優，則Δ取較小的值增加粒子的慣性權重，促使粒子有效地跳出局部最優.其中參數k主要用來調整慣性權重的上限，文中取 k=1.5.

2.3 算法流程

根據以上分析，基于 SPS-PSO(particle swarm optimization based on self-adaptive population structure，SPS-PSO)的基本步驟為:先初始化種群;設置初始化的狀態標志flag=1;計算每個粒子的適應值，并且評估個體的歷史最好位置和全局最好位置;果當前位置優于前一次搜索，則flag=l，否則設置flag=0;若連續t次flag的值始終為0，此時檢測該粒子鄰域的群體多樣性，與最優粒子建立新的連接，并依據適應值重新計算ω的值，然后更新粒子的速度和位置，進行下一步的搜索.

SPS-PSO算法的流程圖如圖1.

圖1 SPS-PSO算法流程Fig.1 Flow chart of SPS-PSO algorithm

3 仿真實驗

3.1 測試函數和參數設置

為了測試新算法對復雜問題尋優的有效性，本文選取了3個Benchmark測試函數進行仿真實驗.實驗環境為Intel CPU 2.1 GB，Windows XP操作系統、1.0 GB 內存，Visual C++6.0 環境下進行編程.為確保實驗結果的可信度，每個算法運行20次實驗，初始化種群個數為100，問題維數30維，最大進化代數為1 000.算法中，加速因子 c1、c2均取 1.5，ω的初始值取 0.9，dLow取5 ×10－6.

1)Sphere函數.

Sphere函數為可分離的單峰函數，用于測試算法的收斂精度，函數在xi=0處到達全局極小值0.

2)Rastrigrin函數.

Rastrigrin函數是不可分離的多峰函數，較難優化，全局最小值在變量為0時到達，該函數有10n個局部極小點.

3)Griwank函數.

Griwank函數也是不可分離的多峰優化函數，函數在xi=0時到達全局最小值，該函數有2n個局部極小值.

3.2 實驗結果與分析

為了測試新算法的優化性能，本文將標準PSO算法、DSWN-PSO(particle swarm optimization with dynamic evolutionary neighbourhood of small-world model)[8]和 DNH-PSO(dynamic neighborhood hybrid-PSO)[9]進行對比分析.圖2顯示了Sphere函數的優化對比結果.通過比較可以看出，SPS-PSO算法始終保持較快的收斂速度，并且最終獲得了比DSWNPSO算法和DNH-PSO算法更好的優化性能.

圖2 30維Sphere函數優化對比Fig.2 Comparison of optimizing on 30-D Sphere

從圖3中可以看出，對于Rastrgin函數來說，SPS-PSO算法能在較短的時間內獲得明顯的優化效果，并且仍然呈向全局最優的趨勢.算法在400～600代時，有一個相對平坦的優化過程，這說明算法在此期間停留在局部最優位置上徘徊不前，但最終因為網絡形成過程中根據適應值擇優連接的過程，使得算法能及時從局部最優位置跳出來，突破了局部最優的束縛，繼續向全局最優位置靠近.

圖3 30維Rastrgin函數優化對比Fig.3 Comparison of optimizing on 30-D Rastrgin

Griewank函數是一個多峰、存在許多局部極小值且自變量之間互相影響的、典型的非線性多模態函數，極易陷入局部最優，從圖4中可以看出，SPSPSO算法能以較快的速度收斂于全局最優，并且在實驗中發現其收斂成功率為100%.其原因在于新連接的加入能適應算法的收斂狀態，使得算法具有較強的抗早熟能力，能夠突破中期短暫的停滯階段，獲得正確的搜索方向.

圖4 30維Griewank函數優化對比Fig.4 Comparison of optimizing on 30-D Griewank

從實驗中發現，SPS-PSO算法的執行效率要高于DSWN-PSO算法，這是因為SPS-PSO算法中，搜索前期的粒子在空間中分布較為均勻，因此通過flag參數作為閾值參數來檢測粒子的搜索狀態，避免了前期不必要的多樣性檢測，提高了算法的效率，中后期多樣性函數的檢測一定程度上避免了算法的局部收斂，促使算法進一步向全局最優靠近.

4 結束語

本文將復雜網絡形成過程中的動力學機制引入粒子群優化算法中，并根據搜索狀態調整慣性權重以適應搜索要求，提出了一種自適應群體結構的粒子群優化算法.隨著算法的搜索，利用多樣性函數檢測鄰域多樣性，使群體結構從低連通度的分散結構進化為連通度較高的復雜網絡，由于其進化過程符合粒子群優化算法對信息共享模式的要求，因此極大地提高了算法的性能.下一步工作將通過對最終形成的群體結構的特性做詳細研究，以探索更符合粒子間信息交流的群體結構.

[1]KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proc IEEE International Conference on Neural Networks.Perth，Australia，1995:1942-1948.

[2]POLI R.An analysis of publications on particle swarm optimization applications[R].London:Department of Computer Science，University of Essex，2007.

[3]POLI R，KENNEDY J，BLACKWELL T.Particle swarm optimization:an overview[J].Swarm Intelligence，2007，1(1):33-57.

[4]KENNEDY J，MENDES R.Population structure and particle swarm performance[C]//Proceedings of the IEEE Congress on Computation Intelligence.Honolulu，USA，2002:1671-1675.

[5]錢曉山.一種改進的混沌粒子群優化混合算法[J].應用科技，2012，39(1):5-8.QIAN Xiaoshan.A hybrid algorithm of the improved chaotic particle swarm optimization[J].Applied Science and Technology，2012，39(1):5-8.

[6]楊雪榕，梁加紅，陳凌，等.多鄰域改進粒子群算法[J].系統工程與電子技術，2010，32(11):2453-2458.YANG Xuerong， LIANG Jiahong，CHEN Ling， et al.Multi-neighborhood improved particle swarm optimization algorithm[J].Systems Engineering and Electronics，2010，32(11):2453-2458.

[7]MATSUSHITA H，NISHIO Y.Network-structured particle swarm optimizer with various topology and its behaviors[J].Lecture Notes in Computer Science，2009，5629:163-171.

[8]穆華平，曾建潮.基于小世界模型動態演化鄰域的微粒群算法[J].系統仿真學報，2008，20(15):3940-3943.MU Huaping，ZENG Jianchao.Particle swarm optimization with dynamic evolutionary neighbourhood of small-world model[J].Journal of System Simulation，2008，20(15):3940-3943.

[9]彭虎，張海，鄧長壽.動態鄰域混合粒子群優化算法[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.

[10]ZHANG Chengong，YI Zhang.Scale-free fully informed particle swarm optimization algorithm[J].Information Sciences，2011，181(20):4550-4568.

[11]曾建潮，介婧，崔志華.微粒群算法[M].北京:科學出版社，2004:5-10.

[12]吳浩揚，朱長純，常炳國，等.基于種群過早收斂程度定量分析的改進自適應遺傳算法[J].西安交通大學學報，1999，33(11):27-30.WU Haoyang，ZHU Changchun，CHANG Bingguo，et al.Adaptive genetic algorithm to improve group premature convergence[J].Journal of Xi’an Jiaotong University，1999，33(11):27-30.