粒子群优化算法：发展,应用程序和资源

粒子群优化算法：发展，应用程序和资源RussellC.Eberhart YuhuiShiPurdueSchoolofEngineeringandTechnology EDSEmbeddedSystemsGroup799WestMichiganStreet I401E.HofferStreetIndianapolis,IN46202USA Kokomo,IN46982USAEberhart@ Yuhui.Shi@EDS.com摘要-本文重点工程和计算机科学方面的发展、应用程序和相关的粒子群优化的资源。对1995年以来的粒子群算法提出到现在的发展进行探讨。包括收缩因素，惯性权重，以及跟踪动态系统的简短的讨论。应用方面，无论是对于已发展的和对未来的潜力应用领域进行探讨。最后，涉及到粒子群优化的资源列出，包括书籍，网站和软件。粒子群优化的书目是在文末。一、 引言粒子群优化（PSO）是由Kennedy和Eberhart在1995年开发的进化计算技术（1995年Kennedy和Eberhart埃伯哈特和肯尼迪，1995年，辛普森埃伯哈特和杜宾斯1996年）。因此，在撰写本文的时候，PSO算法产生刚刚超过五年。目前，它正在十多个国家研究并使用。现在是一个适当的时候退后一步，看看对于粒子群的研究我们处在哪里，我们是如何研究到这个程度，以及将来这项研究可能会朝着哪个方向。本文是关于这个起源于1995年PSO算法的发展、应用和相关资源的介绍。这是从工程和计算机科学的角度来展望和分析的，并不意味着是在社会科学等领域的全面概括。以下的介绍，是关于起源于1995年在粒子群算法的主要发展及探讨。首先提出的是原始算法，接下来是对于收缩因素，惯性权重，及跟踪动态系统的简短的讨论。其次，在应用方面，无论是对于已发展的和对未来的潜力应用领域进行探讨。已开发的包括人力震颤分析，电力系统的负荷稳定和产品结构的优化。最后，介绍粒子群优化资源上市。包括书籍，网站和软件。获得免费的软件也包括在内，可参见文末。二、 发展2.1原始版本粒子群的概念起源是模拟一个简化的社会制度。原意是测绘一个鸟群优美而不可预知的图形编排的模拟。最初模拟进行了纳入最近相邻速度匹配的修改，为了消除辅助变量，纳入距离的多维搜索和加速（1995年Kennedy和Eberhart，埃伯哈特和肯尼迪1995年）。在该算法的一些点有演变即实现概念模型，事实上来说是一个优化。经过一系列的试验，与算法无关的优化参数被淘汰，结果就表现为很简单的原始算式。（埃伯哈特，辛普森和杜宾斯1996年）PSO与遗传算法（GA）很相仿，算法系统是以群体的随机解初始化。然而，不同于GA算法的是它不像GA给每一个潜在的解也被分配一个随机速度。潜在的解，称为粒子，然后认为粒子在问题空间“飞行”。每个粒子保持追踪它在问题空间是的坐标，用以选取当前最优解（同时最优解被保存）。此值称为Pbett。另一个“最优值”，是由粒子群优化的全局方面跟踪目前整体上最佳的值及其位置，这个位置称为g晒。粒子群优化的概念组成，在每次迭代，向Pbet和gbet位置（全局版本PSO）改变每个粒子的速度（加速）。加速的加权时间是随机的，以不一定相同的随机数值向Pbet和gb曲位置加速。还有另一种版本的pso,除了Pbs中，还有y，达到在本地粒子拓扑范围内每个粒子不断的趋于最优。全局版本的PSO（原始方法）的算法过程如下：1） 初始化一个粒子在d维问题空间中的的随机位置和速度的类（阵列）。2） 每个粒子，评估d维方程所期望的最优值。3）将粒子当前最优值与粒子的Pbet比较。如果当前值比Peett更好，贝0重置Pbs值等于在d维空间中的当前值。4）比较当前最优值与全局最优值。如果当前最优值大于8蜘，则重置8必.值等于当前粒子阵列的相应索引值。5）根据方程（1）和（2）,分别更改粒子的速度和位置:v=v+c•rand()•(p-x)+c•Rand()•(p-x)idid1u'JidJ2 uwgdidJ(2)6）循环步骤2,直到某一个标准得到满足，通常是一个足够好的最优值或者到达最大迭代次数（generations）o每个维度粒子的速度将被钳位到一个最高速度Vmax。如果加速度的总和会导致该维度的速度超过Vmax，则该维粒子的速度将被钳位到一个最高速度Vmax。因此，Vmax是一个重要的参数。它决定了当前的位置和目标位置（到目前为止最好的）之间的区域进行搜索的解（最优值）。如果Vmax太高，粒子解就可能超越了最优解。但如果Vmax是太小了，粒子可能陷入局部最优解，而得到不充分解。事实上，他们可能会成为被困在局部最优，在问题空间远远无法达到更好的位置。方程（1）中加速常数-和匕代表推向P和g位置的每个粒子随机加速阶段的比重。1 2 bestbest因此，调整变化这些常数是系统中的“重要”所在。较低值时允许粒子在目标区域漫游之前被拽回，对于高值则做突然运动走向目标地区或上一次的目标区域。根据粒子群优化的早期经验（主要是试验和错误）使我们几乎对所有的应用程序加速常数c1和c2默认等于2.0。因此，Vmax是我们经常调整的唯一参数，我们经常会设置有关的每个维度变量的动态范围在10-20%左右。基于社会模拟的结果，除其他事项外，这是决定设计一个“本地”版本的粒子群。这个版本中，粒子具有信息只属于自己和邻居的最优值，而不是整个粒子群的。与趋于Pbet和gbs（整个组群的最佳位置）的统计平均恰恰相反，粒子趋于被定义为Pbs和“L”的点，这是粒子邻域的最好评价指标点。如果邻域大小定义为2。例如，比较粒子（i）、粒子（i-1）和粒子（i+1）的最优值。相邻粒子被定义为拓扑型；邻域粒子在运算过程中不改变。对于邻域的版本，前的六个步骤中定义的过程，在方程（1）中唯一的变化是Pd的替代，即附近最好的位置替代为Pgd（全局最好的位置）。早期经验（当然，主要是试验和错误）导致许多应用程序正在使用的人口规模约15%的邻里大小。因此，作为人口为40粒子，6个街道，换言之每边三个拓扑的邻居，是通常不会出现的情况。所选择的人口规模是问题的关键。最常见的人口规模大多是20-50人。据了解，在人口规模较小（如人口规模几代人）而需要获得充分解的情况而尽量减少参数时，与常见其他进化算法（如遗传算法和进化规划）比较，PSO算法为最佳的。2.2惯性权重最大速度Vmax作为一个约束来控制一个粒子群的全局搜索能力。如前所述，一个更大的Vmax有利于全局搜索，而较小的Vmax有利于本地搜索。惯性权重的概念，引申为更好地控制探索和分析。目的是能够消除需要Vmax这一参量。在1998年的文献，粒子群优化算法

的惯性权重首次列入文献（ShiandEberhart1998a,1998b）。方程（3）和（4）中描述随着惯性权重更新的速度和位置。由此可以看出，这些方程是相同的方程（1）和（2），除了方程（3）以乘性因子v讯作为一个惯性权重w。使用的惯性权重w优化了的许多应用的性能。按照最初的开发，在运行过程中，w往往是约呈线性从0.9至0.4的降低。选择合适的惯性权重，提供了一个全局和局部的探索和分析之间的平衡，整体结构上减少了平均迭代的次数，从而找到一个充分最优解。［一种不同w的形式，目前正由作者之一（RE）的使用］v=w-v+c-rand()-(p一尤)+c-Rand()-(p一尤)id id1 idid2 gdid7idididididid在惯性权重的一些试验后发现，代表最大速度的因子Vmax不能在任何情况都被剔除。如果用Vmax设置的每个变量值的动态范围（每个维度），则粒子群算法的效果很好。因此，需要思考每次如何使粒子群算法设置淘汰Vmax。另一种方法使用惯性权重的是在一个模糊系统使其适应。第一篇论文有关此方法用于不对称初始化为基准功能Rosenbrock函数（ShiandEberhart2000）。模糊系统包括9个规则，有两个输入和一个输出。每个输入和输出三个模糊集定义。一个输入是当前迭代的全局最优值；另一个输入是目前的惯性权重。输出是惯性权重的变化。使用模糊自适应惯性权重的文件报告的结果表明，粒子群优化算法的性能可以得到显着改善，平均最优值可在给定的迭代次数中实现。2.3压缩因子由于粒子群优化算法源于的社会制度模式，而一个彻底的数学基础的方法不是在该算法诞生的同时开发出来的。在过去的几年，已经开始为建立这个基础做了一些尝试。最近Clerc（1999）所做的工作表明，用以确保粒子群算法的收敛，使用一个收缩因子的可能是必要的。一个收缩的因子的详细讨论超出了本文的范围，但它的一个简化方法在方程（5）可看到，其中K是一个反映（6）中c1和c2的功能方程。v，d=K*[v，d+ci*rand()*(p，d-x.d)+c2*Rand()*(pd-xd)](6)K= : -，其中9=ci+c2,中〉4(6)通常情况下，Clerc的收缩方法是使用如下，9设置为4.1，乘因子K常数设定为0.729。前一次的速度结果乘以0.729,（P-X）每两项乘以0.729*2.05=1.49445（0和1之间的一个随机数）。在最初的Clerc的收缩的方法是使用时的实验和应用。Vmax是10万，因为他们刚开始认为Vmax是没有必要设置的。然而，从随后的实验和应用（EberhartandShi.2000已经得出一个更好的结论，作为使用的“经验法则”，就是要限制Vmax为Xmax，即限制每个维度的每个变量的动态范围，根据方程（5）和（6）选择c1、c2和巧。2.4动态系统，跟踪和优化大部分应用程序的进化算法是用于解决静态问题的。然而，许多现实中的系统，经常（或连续）改变状态。这些系统频繁的状态的变化导致有时几乎要求连续的重复优化。它已被证明，粒子群优化算法，可成功地应用于跟踪并优化动态系统（EberhartandShi2001a）。稍作调整惯性权重可实现这一目的。方程（3）惯性权重巧的设置为［0.5+（Rnd/2.0）］。这将产生0.5和1之间的随机变化的数字，平均值为0.75。这是选用在上文所述的Clerc的收缩因子的思想，如上所述，这时巧设置为0.729。（3）式中的常数c1和c2也可根据Clerc的收缩因子分别设置为1.494。惯性权重是个随机组成部分，当跟踪一个动态系统，它不能在任何时间预测搜索应该选用一个较大的惯性权重或较小的惯性权重。一种惯性权重的变化只能粗略的在我们以前应用的范围内解决。对于这个限定的测试（EberhartandShi2001a）使用抛物线函数。粒子群优化算法在所有测试条件下的性能可与其他进化算法（更快的转换，更有效的最优值）媲美。跟踪10维函数的能力即可证明。3应用粒子群优化算法是有吸引力的的原因之一是有极少数的参数进行调整。一个版本，可以在各种广泛的应用中很轻微的变化（或根本没有）。粒子群优化算法已可以被用于跨范围的广泛的应用，以及具体要求中的具体应用中。在这简短的一节，我们不可能描述所有粒子群的应用，或描述具体单个应用程序中的细节。不过，我们总结了一个小样本。第一个应用程序的方法，可用于许多应用：不断发展的人工神经网络。粒子群优化算法不仅可被用来拓展网络的权重，而且还可以分析网络结构。（EberhartandShi1998a,Kennedy,EberhartandShi2001）该方法很简单有效，如对于传统的神经网络反向传播训练范例，我们已经几乎完全停止使用，取而代之的是利用粒子群拓展我们的网络。该方法对任何网络架构都有效。以拓展神经网络为例，粒子群优化算法已被应用到人类震颤分析。人类震颤包括帕金森氏症和原发性震颤的诊断是一个非常具有挑战性的的领域°PSO算法已被用于形成一种神经网络用以区分正常人和震颤人。网络的输入是从的一个活动变化记录系统中获取被规范化的运动幅度。该方法快速、准确(EberhartandHu1999)。另一个例子，端铣(立铣)是一个在制造环境中经常遇到的基本的和的金属切除手术。尽管电脑数控机床的发展，大大提高生产力，使操作优化。以往开发的算法，大多数情况下没有广泛充分的高准确度的应用。一个新的成功的做法，涉及使用过程仿真及多维优化PSO算法的人工神经网络。实现该应用程序是以计算机辅助设计和计算机辅助制造(CAD/CAM)和其他标准的工程开发工具作为平台。(Tandon2000)。另一个应用是日本电力使用粒子群优化算法的无功功率和电压控制(Yoshidaetal.,1999)。在这里，粒子群优化算法是用来确定一个连续和离散控制变量的策略，造成一种混合二进制和实值算法的版本。以一个连续潮流技术实现系统电压的稳定。粒子群优化算法与BP算法结合，可产生一个为电动汽车使用的电池组充电状态估计的神经网络。充电电池组状态的测定在电动和混合动力/电动汽车技术的发展方面是一个重要的问题。充电状态基本上是根据电动汽车的燃油压力表确定。一个方法是基于粒子群优化算法和BP算法相结合来训练神经网络。一个创新是使用这种组合优化训练数据集。我们对此不能说太多，因为此应用程序是专有的，但可以肯定的是结果大大超过任何其他方法所提供的准确性。(Eberhart,SimpsonandDobbins1996)最后，PS。的最令人兴奋的应用之一是一个美国大公司对于成分结构的优化。在这项工作中，“成分组合”是针对于生产种植菌种的微生物，自然分泌或制造感兴趣的东西成分的混合物。在这里，PSO算法与传统产业的优化方法同时使用。PSO算法提供了一个优化的成分组合，在成分空间一个极为寻常的位置提供比传统的方法两倍以上的最优混合使用。PSO算法被证明具有鲁棒性：发生的一个成分受污染，阻碍了搜索几次迭代，但最终并没有产生不如意的结果。PSO算法的特性决定其比传统方法在问题空间有更大的搜索比例。一般来说，粒子群优化算法如其他的进化计算算法一样，可应用于解决最优化问题以及可以转化为优化问题的问题。其中最有潜力的应用领域包括系统设计、多目标优化、分类、模式识别、生物系统建模、计划(规划)、信号处理、游戏、机器人应用、决策、模拟和鉴定。例如包括模糊控制器的设计，车间作业调度，机器人实时路径刨，图像分割，脑电信号的模拟，语音识别，时频分析，对抗生素耐药性的传播建模，烧伤诊断，手势识别和自动目标检测等等。3资源第一本有关部分粒子群优化的书是出自埃伯哈特、辛普森和杜宾斯(1996)。Kennedy和Eberhart(1999)有对PSO算法讨论的书的章节。现在已经有一整本书以粒子群算法主题的：群体智能(Kennedy,EberhartandShi2001)。其中讨论有关社会、心理学、工程和计算机科学群体智能方面的问题。有关粒子群优化相关的各种资源的指导书的网站是/~eberhart/web/PSObook.html包括在网上运行的Java小程序可以说明各种基准功能的优化。用户可以选择各种参数。同时在网站上是可以下载用C++、VisualBasic和Java语言编写PSO的软件。还提供各种其他网站的链接。鸣谢感谢JimKennedy对相关知识的奉献和评论，本文的部分内容改编自摩根考夫曼出版社在2001年3月出版的《群体智能》。6章的其他部分改编学术专业出版社1996年出版的《计算智能电脑工具》。感谢他们的许可使用这些材料。粒子群优化参考书目Carlisle,A.,andDozier,G.(2001).Anoff-the-shelfPSO.ProceedingsoftheWorkshoponParticleSwarmOptimization.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,IUPUl(inpress).Clerc,M.(1999).Theswarmandthequeen:towardsadeterministicandadaptiveparticleswarmoptimization.?roc.I999CongressonEvolutionaryComputation,Washington,DC,ppI951 1957.Piscataway,NJ:IEEEServiceCenter.Eberhart,R.C.,andHu,X.(1999).Humantremoranalysisusingparticleswarmoptimization.Proc.CongressonEvolutionaryComputationl9Y9,Washington,DC,pp1927-1930.Piscataway,NJ:IEEEServiceCenter.Eberhart,R.C.,andKennedy,J.(1995).Anewoptimizerusingparticleswarmtheory.ProceedingsqftheSixthInternationalSymposiumonMicroMachineandHumanScience,Nagoya,Japan,39-43.Piscataway,NJ:IEEEServiceCenter.Eberhart,R.C.,Simpson,P.K.,andDobbins,R.W.(1996).CompufationalIntelligencePCTools.Boston,MA:AcademicPressProfessional.Eberhart,R.C.,andShi,Y.(1998)(a).Evolvingartificialneuralnetworks.Proc.1998lnt’(ConfonNeuralNehuorksandBrain,Beijing,P.R.C.,PL5-PLl3.V.W.Porto,N.Saravanan,D.Waagen,andA.E.Eiben,Eds.EvolutionuiyProgrammingVll:Proc.7IhAnn..Con!onEvolutionaryProgrammingCon$,SanDiego,CA.Berlin:Springer-Verlag.Eberhart,R.C.,andShi,Y.(2000).Comparinginertiaweightsandconstrictionfactorsinparticleswarmoptimization.Proc.CongressonEvolutionaryComputation2000,SanDiego,CA,pp84-88.Eberhart,R.C.,andShi,Y.(2001)(a).Trackingandoptimizingdynamicsystemswithparticleswarms.Proc.CongressonEvolutionaryComputation2001,Seoul,Korea.Piscataway,NJ:IEEEServiceCenter.(inpress)Eberhart,R.C.,andShi,Y.(2001)(b).Particleswarmoptimization:developments,applicationsandresources.Proc.CongressonEvolutionaryComputation2001,Seoul,Korea.Piscataway,NJ:IEEEServiceCenter.(inpress)Fan,H.-Y.,andShi,Y.(2001).StudyofVmaxoftheparticleswarmoptimizationalgorithm.ProceedingsoftheWorkshoponParticleSwarmOptimization.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,lUPUl(inpress).FukuyamaY.,Yoshida,H.(2001).AParticleSwarmOptimizationforReactivePowerandVoltageControlinElectricPowerSystems,Proc.CongressonEvolutionaryComputation2001,Seoul,Korea.Piscataway,NJ:IEEEServiceCenter.(inpress)He,Z.,Wei,C.,Yang,L.,Gao,X.,Yao,S.,Eberhart,R.,andShi,Y.(1998).Extractingrulesfromfuzzyneuralnetworkbyparticleswarmoptimization,Proc.IEEEInternationalConferenceonEvolutionaryComputation,Anchorage,Alaska,USAKennedy,J.(1997).Theparticleswarm:socialadaptationofknowledge.Proc.Intl.Conf:onEvolutionaryComputation,Indianapolis,IN,303-308.Piscataway,NJ:IEEEServiceCenter.Kennedy,J.(I998).Methodsofagreement:inferenceamongtheeleMentals.Proc.1998Intl.Symp.onIntelligentControl.Piscataway,NJ:IEEEServiceCenter.Kennedy,J.(I998).Thebehaviorofparticles.InV.W.Porto,N.Saravanan,D.Waagen,andA.E.Eiben,Eds.EvolutionaryProgrammingVII:Proc.l”Ann.ConfonEvolutionaryProgrammingConfSanDiego,CA,81-589.Berlin:Springer-Verlag.Kennedy,J.(I998).Thinkingissocial:experimentswiththeadaptiveculturemodel.JournalofConflictResolution,42(I),56-76.Kennedy,J.(1999).Smallworldsandmega-minds:effectsofneighborhoodtopologyonparticleswarmperformance.Proc.CongressonEvolutionaryComputation1999,1931-1938.Piscataway,NJ:IEEEServiceCenter.CongressonEvolutionaryComputation,SanDiego,CA.Piscataway,NJ:IEEEPress.Kennedy,J.(2001).Outofthecomputer,intotheworld:externalizingtheparticleswarm.ProceedingsoftheWorkshoponParticleSwarmOptimization.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,IUPUl(inpress).Kennedy,J.andEberhart,R.C.(I995).Particleswarmoptimization.Proc.IEEEInt’l.ConfonNeuralNetworks,IV,1942-1948.Piscataway,NJ:IEEEServiceCenter.Kennedy,J.andEberhart,R.C.(1997).Adiscretebinaryversionoftheparticleswarmalgorithm.Proc.1997ConfonSystems,Man,andCybernetics,41044109.Piscataway,NJ:IEEEServiceCenter.Kennedy,J.,andEberhart,R.C.(1999).Theparticleswarm:socialadaptationininformationprocessingsystems.InCorne,D.,Dorigo,M.,andGlover,F.,Eds.,NewfdeasinOptimizution.London:McGraw-Hill.Kennedy,J.,Eberhart,R.C.,andShi,Y.(2001).SwarmIntelligence,SanFrancisco:MorganKaufmannPublishers.Kennedy,J.andSpears,W.M.(1998).Matchingalgorithmstoproblems:anexperimentaltestoftheparticleswarmandsomegeneticalgorithmsonthemultimodalproblemgenerator.Proc.Intl.Cot$onEvolutionaryComputation,78-83.Piscataway,NJ:IEEEServiceCenter.Mohan,C.K.,andAI-kazemi,B.(2001).Discreteparticleswarmoptimization.ProceedingsoftheWorkshoponParticleSwarmOptimization.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,IUPUI(inpress).Naka,S.,Grenji,T.,Yura,T.,Fukuyama,Y.(2001).PracticalDistributionStateEstimationUsingHybridParticleSwarmOptimization.Proc.ofIEEEPESWinterMeeting,Columbus,Ohio,USA.Ozcan,E.,andMohan,C.(1999).Particleswarmoptimization:surfingthewaves.Proc.1999CongressonEvolutionaryComputation,1939-1944.Piscataway,NJ:IEEEServiceCenter.Parsopoulos,K.E.,Plagianakos,V.P.,Magoulas,G.D.andVrahatis,M.N.(2001).Stretchingtechniqueforobtainingglobalminimizersthroughparticleswarmoptimization.ProceedingsoftheWorkshoponParticleSwarmOptimization.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,IUPUl(inpress).Secrest,B.R.,andLamont,G.B.(2001).Communicationinparticleswarmoptimizationillustratedbythetravelingsalesmanproblem.ProceedingsoftheWorkshoponParticleSwarmOptimiEation.Indianapolis,IN:PurdueSchoolofEngineeringandTechnology,IUPUl(