協同微粒群算法研究綜述

杜盼盼++陳潮

摘要：微粒群算法（Particle Swarm Optimization，PSO）收斂速度慢，精度不高，收斂過程中降低了種群多樣性，易陷入局部最優。為此，提出協同微粒群算法。協同微粒群算法采用維數劃分重新組合的協同模型，收斂速度快，搜索范圍大，收斂精度較高。“孤島模型”和“鄰域模型”是協同微粒群算法采用較多的兩種模型。“孤島模型”的協同微粒群算法要等到所有子種群全部達到更新周期后才進行比較，將此時的全局最優值作為共享信息。“鄰域模型”的協同微粒群算法每隔R代，相鄰兩個子種群之間就進行信息交換。基于“鄰域模型”的協同微粒群算法收斂效率更快。為了在全局開發和局部搜索之間實現較好平衡，在協同微粒群算法基礎上引入綜合學習策略，以有效利用共享信息實現更好的搜索結果。

關鍵詞：協同進化；微粒群算法；共享周期；綜合學習策略

DOIDOI：10.11907/rjdk.162625

中圖分類號：TP301

文獻標識碼：A文章編號：16727800（2017）010021304

0引言

微粒群算法（Particle Swarm Optimization，PSO）[1]將每個個體看成D維搜索空間中的一個沒有質量和體積的微粒，并以一定速度飛行。該飛行速度由個體的飛行經驗和群體的飛行經驗進行動態調整[2]。PSO將微粒的位置與速度模型化，給出一組顯式的進化方程[3]，見式（1）和式（2）。

Vi（t+1）=ωVi（t）+c1r1（Pi（t）-Xi（t））+c2r2（Pg（t）-Xi（t））（1）

Xi（t+1）=Vi（t+1）+Xi（t）（2）

協同微粒群算法[4]受協同進化啟發而產生。所謂協同進化是指將解空間中的群體劃分為若干子群體，每個子群體代表求解問題的一個子目標，所有子群體在獨立進化的同時，基于信息遷移與知識共享，共同進化[5]。本文中的協同類似一種種間協同，各子群之間通過信息共享和信息交互來提高種群適應值，進而達到一種共同進化的結果[6]。

1協同微粒群算法

1.1協同微粒群算法收斂性分析

作為一種隨機優化算法，標準微粒群算法已被證明不具有全局收斂性。但協同微粒群算法通過引入趨同、協同以及逃逸等搜索行為，證明其能依概率1收斂[7]。

在協同微粒群算法中，子群體和群體的生存狀態分為成長、偽成熟和成熟3種情形，對應3種不同的生存狀態[4]，算法的具體搜索分為趨同搜索，記為Oper1（）；協同搜索，記為Oper2（）；逃逸，記為Oper3（）。

在協同微粒群算法中，整個群體被劃分為若干個子群體并進行搜索。對于任意子群體，有以下定理成立：

定理1處于成長狀態的任意子群體通過趨同搜索Oper1（），最終收斂于解空間中的某一點。

定理2多個子群體的并行趨同搜索不屬于全局搜索算法。

定理3子群體的趨同搜索Oper2（）屬于局部搜索算法。

定理4協同微粒群算法依概率1全局收斂。

1.2協同進化微粒群算法對比分析

多粒子群協同優化算法[8]中引入兩層結構和擾動策略，實驗證明該算法性能較傳統的微粒群算法及改進的微粒群算法性能更好，擺脫了局部最優，加快了收斂速度。此算法中每個子群的粒子狀態更新是獨立的，不能很好地共享粒子間的搜索信息，一旦陷入局部最優就無法擺脫。

基于兩層模型的多子種群和自適應多態雜交微粒群免疫算法（mulitisub population adaptive polymorphic crossbreeding particle swarm optimiza tion immune algorithm，NAPCPSOI）[9]，在進化過程中很好地保持了多樣性，從而能更大概率找到全局最優值。但該算法尋優過程耗時較長，影響了收斂速度。

在基本微粒群算法中引入多種群和改進協同微粒群算法[1011]，證實了在防止陷入局部最優的同時具有更快的收斂速度。

基于綜合學習策略的動態多子群微粒群算法（DMSPSO with cooperative learning strategy，DMSPSOCLS）[12]，引入綜合學習策略，能在全局開發和局部搜索之間實現較好平衡。此算法使共享信息得到充分利用，有效提高了收斂速度和準確率。在解決復雜的多模函數時，能夠避免陷入局部最優，更快地收斂到全局最優解。

2協同微粒群算法研究現狀

將協同原理應用在微粒群算法，能克服微粒群算法收斂效率低、易于陷入局部最優的不足。

Ben Niu （2007年）[1314]提出了一種多種群協作微粒群算法（Multiswarm cooperation particle swarm optimization，簡稱MCPSO），該算法建立了一個masterslave模型（一個master種群和多個slave種群）。slave種群各自獨立執行標準微粒群算法以保持個體多樣性，而master種群則依據自身及slave種群知識來更新。MCPSO算法中slave swarms搜索完畢后把最優值共享給master swarm，slave swarms之間沒有信息共享，降低了種群搜索過程中的收斂效率。J.J.Liang和P.N.Suganthan[15]提出了一種動態多微粒群優化算法，此算法開始時將微粒群劃分為多個小規模子種群，每個子群體獨立進化，每隔一定的代數這些子群體就會隨機重組為新的子群體。Potter提出協同進化模型（Cooperative Coevolutionary Genetic Algorithm，簡稱CCGA）[1617]，將解空間按維數劃分，重新組合。針對上述協同模型中個體獨立性差的不足，學者提出了基于種群個數劃分的協同PSO算法[1819]，此算法能以較大的幾率收斂于全局最優解，但計算量大。Ben Niu[18]提出了基于中心交互機制的MCPSO（An improved MCPSO with Center Communication，MCPSOCC），此算法引入一個只有位置沒有速度的粒子來指導各子群進化。Ben Niu提出了基于中心學習策略的多子群微粒群算法（Multiswarm Particle Swarm Optimization wi th a Center Learning Strategy，MPSOCL）[20]，引入一個中心學習因子實現子群之間信息共享。李愛國[21]提出一種兩層結構的多粒子群協同優化算法，底層用多個粒子群相互獨立地搜索解空間以擴大搜索范圍，上層用1個粒子群追逐當前全局最優解，以加快算法收斂。endprint

3協同微粒群算法理論及應用研究趨勢

3.1協同微粒群算法理論研究趨勢

基于協同進化的微粒群算法及改進版本，都只是針對子群之間信息共享進行改進的，雖然可以達到提高收斂效率的作用，但各子群之間共享信息過于單一，且群體進化過程中，沒有考慮各子群在搜索范圍內的搜索進度，采用統一的更新公式，加大了種群搜索過程中的計算量，降低了收斂率[22]。kmeans聚類算法具有聚類后子群內部相似度高，子群之間相似度低的優點，所以種群劃分時采用kmeans方法。基于鄰域模型的協同進化微粒群算法[2330]種群之間信息交互的共享機制如圖1所示。為了避免各子群在搜索過程中過早收斂，各子群采用微粒群算法（Attractive and Repulsive Particle Swarm Optimizer，ARPSO）獨立搜索[3133]。搜索過程中各子群速度和位置按公式（1）、公式（2）更新。設定一個更新周期R，當子群進化到第R代，子群1將搜索到的最優值Pg1傳遞給子群2，子群2在子群1搜索到最優值的引導下，其速度和位置更新方程見式（5）、式（6）。子群2繼續搜索，到達周期R時，將子群2搜索到的最優值Pg2傳遞給子群3，子群3按式（5）、式（6）繼續搜索，依次進行。如此循環，直到滿足算法的終止條件[2530]。

圖1基于鄰域模型的協同微粒群信息交流

若周期較短，子種群之間的信息交流就過于頻繁，雖然可及時共享信息，但以較大的計算量為代價；若周期選取較大，群體之間信息得不到及時共享，則影響算法收斂性能。

現有協同PSO是基于各子群搜索的最優值進行共享，這樣可以加快搜索進度，使子群之間有更多的信息交流，在此基礎上引入共享信息交互機制[31]。共享信息不僅包括相鄰子群之間搜索到的最優值，還應引入種群多樣性、種群搜索能力等其它對種群搜索過程產生影響的因素。

將綜合學習策略和自適應變異協同微粒群算法相結合，可有效解決局部最優的不足[32]。綜合學習策略是一種使所有粒子彼此相連的共享機制，能夠使子群之間達到快速優化。

協同微粒群算法流程：

（1）依照初始化過程，對整個微粒群種群的隨機位置和速度進行初始設定。

（2）采用kmeans算法對整個種群聚類為k個子群，計算每個子群中各微粒的適應值，初始化各子群搜索過程中的歷史最優位置和全局最優位置。

（3）到達更新周期R之前，各子群同時搜索，且根據式（3）、式（4）對各子群中微粒的速度和位置進行優化。若此時滿足結束條件，則輸出結果。否則，進化到第R代，子群1將搜索到的最優值傳遞給子群2，此時子群2根據式（7）、式（8）對子群2中微粒的速度和位置進行優化，依次進行。

（4）對每個微粒，將其適應值與所經歷的最好位置適應值進行比較。若較好，則將其作為當前的最好位置。

（5）對每個微粒，將其適應值與全局所經歷的最好位置適應值進行比較。若較好，則將其作為當前的全局最好位置。

（6）如未達到結束條件，則返回步驟（2），否則輸出結果。

Vi（t+1）=ω×Vi（t）+dir×[c1×r1×（Pi（t）-Xi（t））+c2×r2×（Pg（t）-Xi（t））]（3）

Xi（t+1）=Xi（t）+Vi（t+1）（4）

dir=-1diversitydhigh（5）

多樣性函數為：

diversity（）=1Np×L×∑Npi=1∑Dj=1（pij-pj）2（6）

Vi（t+1）=ω×Vi（t）+c1×r1×（Pi（t）-Xi（t））+

c2×r2×（Pgk（t）-Xi（t））（7）

Xi（t+1）=Xi（t）+Vi（t+1）（8）

3.2協同微粒群算法應用研究趨勢

協同微粒群算法在多目標函數的測試上相比微粒群算法，具有更快的收斂速度和更優的收斂精度。協同微粒群算法[33]的慣性權重自適應機制和多種群協同進化機制，保持了種群的多樣性，使其不易于陷入局部極值，更易從極值點逃離并繼續搜索尋優，以獲得更好的結果。

鑒于基本PSO算法在收斂過程中會降低種群的多樣性，陷入局部最優的不足，將協同微粒群算法應用在基因表達譜上，進行篩選基因、診斷疾病等工作成為一種趨勢。

4結語

多種群微粒群算法是將協同進化原理融入到微粒群算法中的一種新型算法。此算法既能保證種群之間的信息及時交流，也能保持種群內部的多樣性。此算法在一定程度上加快了搜索速率，提高了搜索精度。

多種群微粒群算法避免了標準微粒群算法只能單一使用一種方式對空間進行搜索的局限，可通過對種群的劃分實現全局和局部之間的平衡，以提高搜索速率。

此算法雖然可以適當提高搜索精度，但種群之間信息交流存在一個滯后時間。下一步工作是在種群搜索過程中引入并行算法，以在保證搜索精度的同時提高搜索效率。

參考文獻參考文獻：

[1]EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C].In Proc. of Int. Sym. Micro Mach. Hum. Sci.，Nagoya， Japan，1995：3943.

[2]KENNEDY J， EBERHART R C.Particle swarm optimization[C].roc. of IEEE Int. Conf. on Neural Networks， Piscataway， NJ，1995：9421948.

[3]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學出版社，2004：108115.

[4]F VAN DEN BERGH， A P ENGELBRECHT. Training product unit networks using cooperative particle swarm optimizers [R].IEEE International Joint Conference on Neural Networks， Washington DC， USA，2001：126131.

[5]LOVBJERG， RASMUSSEN K， KRINK T. Hybrid particle swarm optimizer with breeding and subpopulations[C]. Proceedings of the Genetic and Evolutionary Computation Conference. San Fransisco： Morgan Kaufmann Publishers Inc，2001：469476.

[6]Y SHI， R KROHLING. Coevolutionary particle swarm opti mization to solving minmax problems[C]. In Proc. IEEE Congress on Evolutionary Computation， Honolulu， Hawaii，may 2002：16821687.

[7]NIU B， LI L. An improved MCPSO with center communication[C]. In： Proceedings of 2008 International Conference on Computational Intelligence and Security，2008：5761.

[8]J J LIANG， P N SUGANTHAN. Dynamic multiswarm particle swarm optimizer with local search[C]. In： Proceedings of the IEEE Congress on Evolutionary Computation，2005：522528.

[9]BEN NIU， YUNLONG ZHU， XIAOXIAN HE. Multipopulation cooperative partical swarm optimization[C]. Proceedings of the 8th European Conference on Advances in Artificial Life， ECAL 2005， Canterbury， UK，2005：874883.

[10]MITCHELL A POTTER，KENNETH A DE JONG.A cooperative coevolutionary approach to function optimization[C].In：The Third Parallel Problem Solving from Nature，Jerusalem，Israel， pringerVerlag，1994：249257.

[11]VAN DEN BERGH F，ENGELBRECHT A P.Effects of swarm sizeon cooperative particle swarm optimizers[J].In：Proceeding of the Genetic and Evolutionary Coputation Conference.San Francisco，USA，2001（7）：892899.

[12]EN NIU， LI LI. An improved MCPSO with center communication[C]. 2008 International Conference on Computational Intelligence and Security，2008：5761.

[13]NIU， H L HUANG， L J TAN， et al. Multiswarm particle swarm optimization with a center learning strategy[C]. In： Proceedings of the Advances in Swarm Intelligence，2013：7278.

[14]RENATO A KROHLING，LEANDRO DOS SANTOS COELHO.Coevolution ary particle swarm optimization using gaussian distribution for solving constrained optimization problems[J].IEEE Transaction on Systems， Man， and Cybernetics， Part B，2006（12）：14071416.

[15]李愛國.多粒子群協同優化算法[J].復旦大學學報：自然科學版，2004，43（5）：923925.

[16]ANDI ASMARA， RENATO A KROHLING， FRANK HOFFMANN. Parameter tuning of a computedtorque controller for a 5 degree of freedom robot arm using coevolutionary particle swarm optimization[C]. Proceedings of 2005 IEEE Conference on Swarm Intelligence Symposium，2005：162168.endprint

[17]F VALDEZ， P MELIN， O CASTILLO. Modular neural networks architecture optimization with a new nature inspired method using a fuzzy combination of particle swarm optimization and genetic algorithms[J]. Appl， Soft Comput，2014（270）：143153.

[18]MALDONADO，O CASTILLO， P MELIN. Particle swarm optimization of interval type2 fuzzy systems for FPGA applications， Appl[J]. Soft Comput. 2013，13 （1）：496508.

[19]P MELIN， F OLIVAS， O CASTILLO， et al. Optimal design of fuzzy classification systems using PSO with dynamic parameter adaptation through fuzzy logic[J]. Exp， Syst， Appl， 2013，40（8）：31963206.

[20]A NICKABADI， M M EBADZADEH， R SAFABAKHSH. A novel particle swarm optimization algorithm with adaptive inertia weight[J]. Appl， Soft Compute， 2011，11（4）：36583670.

[21]M NASIR， S DAS， D MAITY， et al. SUGANTHAN， A dynamic neighborhood learning based particle swarm optimizer for global numerical optimization[J]. Inf. Sci. 2012（209）：1636.

[22]J Z ZHANG， X M DING. A multiswarm selfadaptive and cooperative particle swarm optimization[J]. Eng， Appl， Artif， Intell， 2011，24（6）：958967.

[23]B NIU， Y L ZHU， X X HE， et al. MCPSO： a multiswarm cooperative particle swarm optimizer[J]. Appl， Math， Comput， 2007，185 （2）：10501062.

[24]S MUKHOPADHYAY， S BANERJEE. Global optimization of an optical chaotic system by chaotic multi swarm particle swarm optimization[J]. Exp， Syst， Appl， 2012（39）：917924.

[25]S Z ZHAO， J J LIANG， P N SUGANTHAN， et al. Dynamic multiswarm particle swarm optimizer with local search for large scale global optimization[C]. In： Proceedings of the IEEE Congress on Evolutionary Computation， 2008：38453852.

[26]S Z ZHAO， P N SUGANTHAN， Q K PAN， et al. Dynamic multiswarm particle swarm optimizer with harmony search[J]. Exp， Syst， Appl， 2011，38（4）：37353742.

[27]S Z ZHAO， P N SUGANTHAN， S DAS.Dynamic multiswarm particle swarm optimizer with subregional harmony search[C]. In： Proceedings of the IEEE Congress on Evolutionary Computation， 2010：18.

[28]R C EBERHART， Y SHI.Comparing inertia weights and constriction factors in particle swarm optimization[C]. In： Proceedings of the IEEE Congress on Evolutionary Computation，2000：8488.

[29]XIA XU，YINGGAN TANG，JUNPENG LI，et al.Dynamic multiswarm particle swarm optimizer with cooperative learning strategy[J]. Applied Soft Computing，2015（29）：169183.

[30]KENNEDY. Small worlds and megaminds： effects of neighborhood topology on particle swarm performance[C]. In： Proceedings of the IEEE Congress on Evolutionary Computation，1999：19311938.

[31]K TANG， X D LI， P N SUGANTHAN， et al. Benchmark functions for the CEC 2010 special session and competition on largescale global optimization[C]. in： Proceedings of the Nature Inspired Computation and Applications Laboratory， 2010.

[32]JINJIE YAO.Esearch on target localization based on improved multiswarm particle swarm optimization algorithm[C]. In 2010 6th International Conference on Wireless Communications Networking and Mobile Computing （WiCOM），2010.

[33]高平安，蔡自興，余伶俐.一種基于多子群的動態優化算法[J].中南大學學報：自然科學版，2009，40（3）：7374.

責任編輯（責任編輯：杜能鋼）endprint