協(xié)同微粒群算法研究綜述

杜盼盼++陳潮

摘要：微粒群算法（Particle Swarm Optimization，PSO）收斂速度慢，精度不高，收斂過(guò)程中降低了種群多樣性，易陷入局部最優(yōu)。為此，提出協(xié)同微粒群算法。協(xié)同微粒群算法采用維數(shù)劃分重新組合的協(xié)同模型，收斂速度快，搜索范圍大，收斂精度較高?！肮聧u模型”和“鄰域模型”是協(xié)同微粒群算法采用較多的兩種模型?！肮聧u模型”的協(xié)同微粒群算法要等到所有子種群全部達(dá)到更新周期后才進(jìn)行比較，將此時(shí)的全局最優(yōu)值作為共享信息。“鄰域模型”的協(xié)同微粒群算法每隔R代，相鄰兩個(gè)子種群之間就進(jìn)行信息交換?；凇班徲蚰Ｐ汀钡膮f(xié)同微粒群算法收斂效率更快。為了在全局開(kāi)發(fā)和局部搜索之間實(shí)現(xiàn)較好平衡，在協(xié)同微粒群算法基礎(chǔ)上引入綜合學(xué)習(xí)策略，以有效利用共享信息實(shí)現(xiàn)更好的搜索結(jié)果。

關(guān)鍵詞：協(xié)同進(jìn)化；微粒群算法；共享周期；綜合學(xué)習(xí)策略

DOIDOI：10.11907/rjdk.162625

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：16727800（2017）010021304

0引言

微粒群算法（Particle Swarm Optimization，PSO）[1]將每個(gè)個(gè)體看成D維搜索空間中的一個(gè)沒(méi)有質(zhì)量和體積的微粒，并以一定速度飛行。該飛行速度由個(gè)體的飛行經(jīng)驗(yàn)和群體的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整[2]。PSO將微粒的位置與速度模型化，給出一組顯式的進(jìn)化方程[3]，見(jiàn)式（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）

協(xié)同微粒群算法[4]受協(xié)同進(jìn)化啟發(fā)而產(chǎn)生。所謂協(xié)同進(jìn)化是指將解空間中的群體劃分為若干子群體，每個(gè)子群體代表求解問(wèn)題的一個(gè)子目標(biāo)，所有子群體在獨(dú)立進(jìn)化的同時(shí)，基于信息遷移與知識(shí)共享，共同進(jìn)化[5]。本文中的協(xié)同類似一種種間協(xié)同，各子群之間通過(guò)信息共享和信息交互來(lái)提高種群適應(yīng)值，進(jìn)而達(dá)到一種共同進(jìn)化的結(jié)果[6]。

1協(xié)同微粒群算法

1.1協(xié)同微粒群算法收斂性分析

作為一種隨機(jī)優(yōu)化算法，標(biāo)準(zhǔn)微粒群算法已被證明不具有全局收斂性。但協(xié)同微粒群算法通過(guò)引入趨同、協(xié)同以及逃逸等搜索行為，證明其能依概率1收斂[7]。

在協(xié)同微粒群算法中，子群體和群體的生存狀態(tài)分為成長(zhǎng)、偽成熟和成熟3種情形，對(duì)應(yīng)3種不同的生存狀態(tài)[4]，算法的具體搜索分為趨同搜索，記為Oper1（）；協(xié)同搜索，記為Oper2（）；逃逸，記為Oper3（）。

在協(xié)同微粒群算法中，整個(gè)群體被劃分為若干個(gè)子群體并進(jìn)行搜索。對(duì)于任意子群體，有以下定理成立：

定理1處于成長(zhǎng)狀態(tài)的任意子群體通過(guò)趨同搜索Oper1（），最終收斂于解空間中的某一點(diǎn)。

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

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

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

1.2協(xié)同進(jìn)化微粒群算法對(duì)比分析

多粒子群協(xié)同優(yōu)化算法[8]中引入兩層結(jié)構(gòu)和擾動(dòng)策略，實(shí)驗(yàn)證明該算法性能較傳統(tǒng)的微粒群算法及改進(jìn)的微粒群算法性能更好，擺脫了局部最優(yōu)，加快了收斂速度。此算法中每個(gè)子群的粒子狀態(tài)更新是獨(dú)立的，不能很好地共享粒子間的搜索信息，一旦陷入局部最優(yōu)就無(wú)法擺脫。

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

在基本微粒群算法中引入多種群和改進(jìn)協(xié)同微粒群算法[1011]，證實(shí)了在防止陷入局部最優(yōu)的同時(shí)具有更快的收斂速度。

基于綜合學(xué)習(xí)策略的動(dòng)態(tài)多子群微粒群算法（DMSPSO with cooperative learning strategy，DMSPSOCLS）[12]，引入綜合學(xué)習(xí)策略，能在全局開(kāi)發(fā)和局部搜索之間實(shí)現(xiàn)較好平衡。此算法使共享信息得到充分利用，有效提高了收斂速度和準(zhǔn)確率。在解決復(fù)雜的多模函數(shù)時(shí)，能夠避免陷入局部最優(yōu)，更快地收斂到全局最優(yōu)解。

2協(xié)同微粒群算法研究現(xiàn)狀

將協(xié)同原理應(yīng)用在微粒群算法，能克服微粒群算法收斂效率低、易于陷入局部最優(yōu)的不足。

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

3協(xié)同微粒群算法理論及應(yīng)用研究趨勢(shì)

3.1協(xié)同微粒群算法理論研究趨勢(shì)

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

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

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

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

將綜合學(xué)習(xí)策略和自適應(yīng)變異協(xié)同微粒群算法相結(jié)合，可有效解決局部最優(yōu)的不足[32]。綜合學(xué)習(xí)策略是一種使所有粒子彼此相連的共享機(jī)制，能夠使子群之間達(dá)到快速優(yōu)化。

協(xié)同微粒群算法流程：

（1）依照初始化過(guò)程，對(duì)整個(gè)微粒群種群的隨機(jī)位置和速度進(jìn)行初始設(shè)定。

（2）采用kmeans算法對(duì)整個(gè)種群聚類為k個(gè)子群，計(jì)算每個(gè)子群中各微粒的適應(yīng)值，初始化各子群搜索過(guò)程中的歷史最優(yōu)位置和全局最優(yōu)位置。

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

（4）對(duì)每個(gè)微粒，將其適應(yīng)值與所經(jīng)歷的最好位置適應(yīng)值進(jìn)行比較。若較好，則將其作為當(dāng)前的最好位置。

（5）對(duì)每個(gè)微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置適應(yīng)值進(jìn)行比較。若較好，則將其作為當(dāng)前的全局最好位置。

（6）如未達(dá)到結(jié)束條件，則返回步驟（2），否則輸出結(jié)果。

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）

多樣性函數(shù)為：

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協(xié)同微粒群算法應(yīng)用研究趨勢(shì)

協(xié)同微粒群算法在多目標(biāo)函數(shù)的測(cè)試上相比微粒群算法，具有更快的收斂速度和更優(yōu)的收斂精度。協(xié)同微粒群算法[33]的慣性權(quán)重自適應(yīng)機(jī)制和多種群協(xié)同進(jìn)化機(jī)制，保持了種群的多樣性，使其不易于陷入局部極值，更易從極值點(diǎn)逃離并繼續(xù)搜索尋優(yōu)，以獲得更好的結(jié)果。

鑒于基本PSO算法在收斂過(guò)程中會(huì)降低種群的多樣性，陷入局部最優(yōu)的不足，將協(xié)同微粒群算法應(yīng)用在基因表達(dá)譜上，進(jìn)行篩選基因、診斷疾病等工作成為一種趨勢(shì)。

4結(jié)語(yǔ)

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

多種群微粒群算法避免了標(biāo)準(zhǔn)微粒群算法只能單一使用一種方式對(duì)空間進(jìn)行搜索的局限，可通過(guò)對(duì)種群的劃分實(shí)現(xiàn)全局和局部之間的平衡，以提高搜索速率。

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

參考文獻(xiàn)參考文獻(xiàn)：

[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].北京：科學(xué)出版社，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]李愛(ài)國(guó).多粒子群協(xié)同優(yōu)化算法[J].復(fù)旦大學(xué)學(xué)報(bào)：自然科學(xué)版，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]高平安，蔡自興，余伶俐.一種基于多子群的動(dòng)態(tài)優(yōu)化算法[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，40（3）：7374.

責(zé)任編輯（責(zé)任編輯：杜能鋼）endprint