基于群体多样性反馈控制的自组织微

基于群体多样性反馈控制的自组织微粒群算法*介婧，曾建潮，韩崇昭([e-mail])摘要：群体多样性是影响微粒群算法全局优化性能的关键因素。为克服微粒群算法的早熟问题，提出了自组织微粒群算法。将微粒群体视为自组织系统，引入负反馈机制。基于多样性的反馈控制，把群体多样性作为个体微粒可感知的群体动态信息，用于动态调整惯性权重或加速度系数，通过不同的特性参数实现微粒的集聚或分散，使群体维持适当的多样性水平以利于全局搜索。用于复杂函数优化问题的求解，并与其它典型改进算法进行了性能比较。仿真结果表明，基于多样性控制的自组织微粒群算法可以有效避免早熟问题，提高微粒群算法求解复杂函数的全局优化性能。关键词：微粒群算法，群体多样性，反馈控制，早熟中图分类号TP18Self-organizedParticleSwarmOptimizationBasedonFeedbackControlofSwarm-diversityJIEJing，ZENGJian-Chao，HANChong-Zhao1SchoolofElectronicandInformationEngineering,Xi’anJiaotongUniversity,Xi’an7100492DivisionofSystemSimulation&ComputerApplication,TaiyuanUniversityofScience&TechnologyTaiyuan030024([e-mail])Abstract:Swarm-diversityisakeyfactorinfluencingtheglobalperformancesofparticleswarmoptimization(PSO).Inordertoovercometheprematureconvergence,thepaperdevelopsaself-organizedPSO(SOPSO).SOPSOregardstheswarmasaself-organizedsystemandintroducesanegativefeedbackmechanism.Basedonthefeedbackcontrolofthediversity,thesystemadoptsswarm-diversityasmaindynamicinformationtocontrolthetuningofinertiaweighoraccelerationcoefficients,whichinturncanmodifytheparticlestodivergeorconvergeadaptivelyandcontributetoasuccessfulglobalsearch.TheproposedmethodswereappliedtosomecomplexfunctionoptimizationsandcomparedwiththeothernotableimprovedPSO.SimulationresultsshowSOPSObasedonfeedbackcontrolofswarm-diversityisafeasiblemethod,whichcanalleviatetheprematureconvergencevalidlyandimprovetheglobalperformancesofPSOinsolvingthecomplexfunctions.Keywords:particleswarmoptimization,swarmdiversity，feedbackcontrolandprematureproblem1引言微粒群算法(particleswarmoptimization，PSO)是一种典型的群智能优化算法，最早是由美国心理学家J.Kennedy和电气工程师R.Eberhart于1995年共同提出的[1]。算法将鸟群类比为一群没有体积及质量的微粒，鸟群飞向的目的地类比为优化问题目标解的位置。在飞行过程中，通过认知、记忆及信息交互，每一微粒可以根据自身及周围微粒的飞行经验，动态调整自己的速度及飞行方向，进而促使整个群体逐步向着优化问题的可能解区域逼近。微粒群算法模拟了简单生物群体所表现的智能涌现现象，即简单个体通过协作及信息交互从而表现出复杂的智能行为。算法采用自下而上的设计方式，模型简单、操作便捷，具有较强的自学习、自组织和自适应性。因此，微粒群算法一经*本文资助项目：国家自然科学基金（60674104），山西省教育科技项目（20051310），山西省自然科学基金（2007011046）问世，便迅速成为智能计算领域的一个研究热点，并被广泛应用于各种优化问题及工程领域[2-6]。然而，随着求解问题复杂性的增加，现有微粒群算法模型同样面临着早熟、收敛效率低、全局收敛性能差等问题的挑战。为了提高微粒群算法的全局收敛性，诸多学者提出了各种各样的改进策略。YShi与RCEberhart在基本微粒群算法中引入惯性权重因子ω，并提出线性递减惯性权重(linearlydecreasedinertiaweigh,LDIW)[7]、随机惯性权重[8]、模糊调整惯性权重[9]等策略用以更好协调算法的局部开采与全局探测；M.Clerc[10]则提出了收缩因子的概念用于保证算法收敛。借鉴线性递减惯性权重策略，ARatnaweera等人利用时变加速系数的方法(time-varyingaccelerationcoefficients,TVAC)以改善算法的收敛性能[11]。为了保证进化过程中群体微粒的多样性，MLovbjerg[12]等人将遗传算法中的子群体及繁殖的概念引入微粒群算法中。XDLi提出了基于物种的邻域自适应选择方案[13]来保证群体多样性。JRiget则通过“吸引（attraction）”和“扩散(repulsion)”算子控制群体多样性[14]。JCZeng提出利用模拟退火算法和禁忌算法等策略在群体中产生随机微粒以保证算法的全局收敛性[15]。RHe等人则引入自适应逃逸算子来克服算法早熟问题[16]。JJLiang等提出了全面学习的微粒群算法(ComprehensiveLearningPSO,CLPSO)[17]，在该算法中，各个微粒将不再总是记忆自己的历史最佳，而是以一定概率学习其它微粒的历史经验。上述算法一定程度上改善了算法的收敛性能，但却很难在提高搜索速度和克服早熟之间达到平衡。众所周知，对基于群体搜索的随机优化算法而言，其搜索动态是难以预知的，但是要想较好地克服早熟问题，就必须能够对搜索过程中的群体动态进行洞察和监测，判断群体出现早熟的时间和范围。通常，算法出现过早收敛是由于群体多样性过早缺失所致。因此，能否在搜索的不同状况下维持正确的群体多样性水平，将从根本上影响算法全局收敛性的好坏。在微粒群算法中，群体所经历的最佳位置作为唯一共享的群体信息，被所有微粒所感知并引导微粒快速朝着此位置所在的方向飞行，这种单趋向的微粒聚集行为，直接导致了群体多样性的快速缺失。如果全局最优解存在于群体最佳位置的路线附近，则算法有可能快速收敛至全局最优解；否则，算法将有很大的可能收敛于某一非最优点，这正是微粒群算法难以保证全局收敛的问题所在。为此，本文从微粒群算法的模拟机理出发，将微粒群体视为自组织系统，把群体多样性作为影响个体微粒行为的关键因素和描述群体动态的重要指标，引入多样性反馈机制来控制群体的进化动态，提出了一种自组织微粒群算法模型(SOPSO)。通过分析算法参数对个体微粒行为的不同影响，提出了多样性控制惯性权重和加速系数的两种策略，来实现微粒群体多样性的增加和减少。相关的实验研究表明，SOPSO能够有效地改善整个搜索期间群体的多样性水平，并根据搜索动态适当地调整群体的可进化性，从而有效克服算法的过早收敛。本文第2节介绍了标准微粒群算法的基本原理，第3节描述了自组织微粒群算法的思想及模型；第4节给出了基于典型复杂测试函数的仿真实验及分析；最后一节给出了本文的结论及后续工作。2标准微粒群算法考虑如下全局优化问题：min()..nfXstXSσ=∈R⊂(1)当微粒群算法用于求解上述优化问题时，首先在问题的解空间随机产生一组候选解构成微粒群体（swarm），其中每一候选解即为一个微粒（particle），每一微粒的飞行状态可以通过n维的速度与位置向量来描述，其更新方程如下：()()1122(1)()()()()()ididididgdidvtvtcrPtxtcrPtxtω+=+−+−(2)(1)()(1)idididxtxtvt+=++(3)其中，Xi和Vi分别代表第i个微粒的位置与速度向量，Pi代表该微粒所经历的历史最佳位置，Pg则代表微粒群体所经历过的历史最佳位置。ω为惯性权重（inertiaweight），c1和c2为两个加速系数，r1和r2为两个[0，1]范围内以均匀分布产生的随机数。算法的速度更新方程可分成三项：第一项为动量部分，表示微粒以先前速度所进行的惯性运动；第二项为“认知”部分，代表微粒对自己历史经验的认知和肯定，鼓励微粒飞向自身所发现的最佳位置。第三项为“社会”部分，表示微粒对群体社会信息的共享和学习，引导微粒飞向群体所经历的最佳位置。上述三个部分以不同的权重相互协调和制约，第一部分为微粒的飞行提供了必要的动量，第二部分和第三部分则对算法的局部和全局搜索有一定的平衡作用。显而易见，算法参数设置的有效性和合理性将直接影响其搜索性能。3自组织微粒群算法3.1自组织微粒群算法模型的提出微粒群算法是一种隐喻的群智能算法，其中的微粒群体可被视为一种自组织系统。在微粒群体中，没有发号施令的领导，不存在着集中控制，但每个微粒却能够依据简单的行为规则相互协作及交互，促使整个群体突现出一种复杂的协调和适应能力。这种群智能的涌现，正是由于群体内部存在着大量的正负反馈机制，使得微粒能够不断从群体环境中获取信息来调整自身的行为。因此，要想从根本上改善微粒群算法的性能，我们应该从群体和个体两个角度出发去考察算法模型。考虑到优化问题，我们则可以将目标问题的全局解视为群体系统的期望输出：一方面，希望群体在寻优过程中保持较好的可进化性，以较大的概率收敛于目标问题的全局解；另一方面，希望每一个体微粒能够感知有效的群体状态信息并正确调整自身的行为，以促进更高质量的系统输出。在基本微粒群算法中，群体的最佳位置被作为唯一的共享信息来引导个体微粒的飞行，导致了微粒的一种单趋向聚集行为，造成了群体多样性的快速缺失，使算法易于陷入局部极值而难以逃逸。为了有效的克服早熟问题，则必须对群体的多样性加以监控，而在实际的鸟群系统中，群体的分布密度及多样性，往往是影响个体行为的一个关键因素，例如：飞行中的鸟可根据群体的拥挤程度，及时调整自己的速度以避免相互冲撞，而觅食的鸟则会根据群体的密度大小来判断分享食物的可能性，从而选择加速或逃逸。基于以上分析，我们把微粒群体作为一个自组织系统，把群体多样性作为影响个体微粒行为的关键因素，引入反馈机制来控制群体的进化动态，提出了如下的自组织控制微粒群模型。图1自组织微粒群算法模型Fig.1ModelofSelf-organizedParticleSwarmOptimization在上述模型中，Di代表群体多样性的参考输入，Do表示群体的实际多样性输出，Pgo则表示群体所经历的最佳位置，系统最终的稳定输出即作为目标问题的全局解。显而易见，自组织控制微粒群算法模型利用反馈机制，模拟了微粒群体中存在的信息感知及交互，是一种典型的负反馈控制系统。系统主要包括多样性控制器(Diversitycontroller)，微粒群优化器(PSOOptimizer)和微粒群体(Swarm)三个部分，其中微粒群体由一定群体规模的微粒组成，其多样性信息直接反馈于多样性控制器，而多样性控制器根据群体实时的多样性信息和参考输入的偏差，来确定群体多样性增加或减小的策略，优化器则按照多样性控制器输出的规则或指令，通过调整个体微