协同微粒群算法研究综述

杜盼盼++陈潮

摘要：微粒群算法（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