搜索
专业文献综述题目:粒子群算法研究现状及应用综述姓名:黄若凡学院:信息科学技术学院专业:计算机科学与技术班级:计科112班学号:32311505指导教师:郭小青职称:副教授2014年5月24日南京农业大学教务处制粒子群算法研究现状及应用综述作者：黄若凡指导老师：郭小青摘要：粒子群算法是一种基于群体智能的算法。这种算法自身简单、通用性强、收敛速度快、调整参数少、容易编程实现，所以发展的十分迅速，被学者和专家广泛的研究。粒子群算法是一个非常有潜力的工具，在最近的十几年间已经成为了现代优化方法中的一个重要的组成部分，在处理高维的和缺乏领域知识的问题中尤其有用。算法的应用具体表现在在函数优化、神经网络训练、工程实践等几个大方面。本文介绍了粒子群算法的原理和思想，概述了算法的现状和改进，总结了粒子群算法的应用，展望了粒子群算法的进一步研究趋势。关键字：粒子群优化算法；群体智能；复杂适应系统StatusofresearchandapplicationofparticleswarmReviewHUANGRuo-fan，GUOXiao-qingNanjingAgriculturalUniversity,CollegeofInformationScienceandTechnology,JiangsuNanjing210095Abstract:PSOalgorithmisbasedonswarmintelligencealgorithm.Thealgorithmitselfissimple,versatile,fastconvergence,lessadjustmentparameters,easyprogramming,sothedevelopmentisveryrapid,extensiveresearchhasbeenscholarsandexperts.Particleswarmalgorithmisaverypromisingtoolintherecenttenyears.Ithasbecomeanimportantpartofmodernoptimizationmethod.Thetreatmentwhichinhigh-dimensionalproblemsandlackingofknowledgeinthefieldisespeciallyuseful.Algorithmapplicationspecificperformanceinseveralrespectsinfunctionoptimization,neuralnetworktraining,engineeringpractice,etc.Thispaperdescribestheprinciplesandideasofparticleswarmoptimization,anoverviewandimprovementofthestatusofthealgorithm,summarizestheapplicationofparticleswarmalgorithm,andthefutureresearchtrendsinparticleswarmoptimization.Keywords:PSO；SwarmIntelligence；ComplexAdaptiveSystems引言：优化研究的问题是在许多个方案发展中找到那个最合适的方案。长期以来，优化问题都受到了广泛的关注，也是一个研究的热点。人们关于优化问题的研究工作，随着历史的发展不断深入。但是，任何科学的进步都受到历史条件的限制，直到二十世纪四十年代，由于科学技术的迅猛发展，尤其是高速数字计算机日益广泛的应用，使得优化问题的研究不仅分为一种迫切需要，更沉了求解的有力工具。随着人们生存空间的扩大，常规的优化方法已经无法处理人们所面对的复杂问题，因此，高效的优化算法成为科学工作者的研究目标之一。本文研究的粒子群算法（PSO）是Keenedy和Eberhart在鸟群、鱼群和人类社会的行为规律的启发下提出的一种基于群智能的演化计算技术[1]。该算法模拟鸟群飞行觅食的行为，通过鸟之间的集体协作使群体达到最优，它与遗传算法同属于群体优化技术，但是PSO更加简单，操作更加方便，从诞生起，就引起了国内外学者的高度关注，并掀起了该方法的研究高潮，还在很多领域得到了成功的应用[2]。1基本粒子群算法的思想和原理粒子群算法，也称粒子群进化算法，缩写为PSO，粒子群算法是一种并行算法，是近年来发展起来的一种新的进化算法。PSO算法属于进化算法的一种，和模拟退火算法相似，它是从随机解出发，通过迭代寻找最优解，它是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异”操作，它通过追随当前搜索到的最优解来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。1.1基本粒子群算法的思想PSO算法初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次迭代中，粒子通过两个极值来更新自己：第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值就是整个群众目前为止找到的最优解，这个解就是全局极值。另外也可以不用整个种群只用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值[3]。1.2基本粒子群算法的原理基本粒子群算法中，粒子群由n个粒子组成，每个粒子的位置代表优化问题在D维搜索空间潜在的解。在一个D维的目标搜索空间中，由n个粒子组成一个群落，其中第i个粒子表示为一个D维向量xi=（xi1,xi2,...xij）,i=1,2...n.xi将代入目标函数f(xi)就可以计算出其适应值。根据适应值就可以衡量xi的优劣。第i个粒子飞行速度也是一个D维向量，记为vi=(v1D,v2D,...vID),i=1,2...n.第i个粒子迄今为止搜索到的最优位置为：pi=(p1D,p2D...piD),i=1,2...n,整个粒子群迄今为止搜索到的最优位置为：pg=(pg1,pg2,...piD).Kennedy和Eberhart最早提出的PSO算法用式（1）和式（2）更新粒子状态。vid=vid+c1r1(pid-xid)+c2r1(pgd-xid)(1)Xid=xid+vid(2)式（1）中：c1，c2为正常数，称为学习因子；r1，r2是介于[0，1]间的随机数。迭代终止条件根据具体问题一般选为最大迭代次数或者为粒子迄今为止搜索到的最优位置满足预定最小适应阙值。2粒子群算法的研究现状及改进2.1粒子群算法现状1995年粒子群算法才被提出，是一种新兴的智能优化算法，其研究历史很短。尽管粒子群算法仅有二十余年研究历史，但由于该算法具有适应范围广、原理简单、容易编程实现等很多的优点，大量的相关专业学者和专家都在对这个算法进行研究学习，得到了许多更为优良的粒子群算法。例如混沌粒子群优化算法、结合模拟退火的粒子群优化算法等，还基于粒子群算法研究了一系列的约束优化、不确定优化、调度问题。可以概括为：粒子群算法研究的热点主要集中于以下几个方面[4]：1、位置和速度的更新公式这是研究最热的问题，通过具体问题的设计，改进或者改变位置和速度的更新公式是PSO算法的核心问题。Shi[5]在PSO算法中引入惯性权因子，Clerc[6]提出在PSO中引入收缩因子，He[7]等在PSO中引入被动聚集项，Ratnaweera[8]等引入时变加速因子的时变权惯因子等等，通过增加控制参数，改变更新公式的方法，一定程度上提高了PSO算法的效率，收敛速度。2、多群种Lovbjerg[9]等在PSO中引入种群的概念，通过多种群的协作，将原问题划分成多个片段，该方法类似于分治算法的思想，但是算法同时也增加了计算量，效率不是特别明显。3、混合算法这是一种比较实用的方法，通过引入其他智能算法，利用他们的优点弥补PSO算法自身的问题。Katare提出了基于PSO算法和Levenberg-Marquardt的混合方法，Fan将单纯形法和PSO结合，提高了单纯形法的收敛速度，大大改善了收敛效率等。2.2粒子群算法的改进以下归纳了几种主要的改进PSO[10]：增加惯性因子的改进；基于收敛性分析的改进；导入其他演算法思想的改进；建立非数值问题迷信的改进。（1）增加惯性因子的改进粒子群算法PSO算法是以种群行为而不是适者生存原则来激励粒子的运动。每个潜在的解和粒子运行速度相联系。该速度不停的根据粒子本身的经验以及周围粒子的经验来调整大小、方向，总是希望粒子能朝着更好的方向发展。在搜索过程中，全局搜索能力与局部搜索能力的平衡关系对算法的成功起着至关重要的作用。在求解各种实际应用的问题中，对算法的局部搜索能力和全局搜索能力的比例要求不尽相同，甚至对同一个问题，在其进化的不同阶段，对他们的要求也有可能是不一样的。基于这么一个事实，YuhuiShi等提出了带惯性因子的PSO算法。进化方程为：vι(t+1)=ωvι(t)+clrand()(pi-x(t))+c2rand()(pg-xι(t))(3)xι(t+1)=xι(t)+vι(t+1)(4)以上算式被学者引用作为标准PSO算法。其中惯性因子ω表征粒子惯性大小；对原来速度的保持程度。ω的取值经过试验在[0.8，1.2]之间的收敛速度更快一些。ω大时，具有较强的全局收敛能力，ω小时既有较强的局部收敛能力，因此ω有点类似模拟退火中的温度，随着迭代次数的增加，ω的值应该不断的减小，从而使得在算法开始的初期，要求有较强的全局收敛能力，后期是要求有较强的局部搜索能力，以提高算法的整体的性能。YuhuiShi还提出ω的值在0.9到0.4在间的线性递减策略。但是，因为惯性因子在进化的过程中线性递减策略往往不能反映实际的优化算法搜索过程，为此提出了一种基于模糊系统的惯性因子动态调整策略，取得了良好的成果。（2）基于收敛性分析的改进粒子群算法加速因子决定了粒子本身经验信息和其他粒子的经验信息对粒子运动轨迹的影响，反映了粒子群间的信息交流，由于标准PSO算法有可能出现太早收敛的情况，Clerc提出一种保证收敛的改进粒子算法GCPSO。我们注意到当例子的位置达到最优的时候，粒子只能按照原来的速度进行调整，一直沿着一个方向直线飞行能找到更优解的概率是非常小的。为了保证到达最优解时粒子能够正常的移动，GCPSO提出最佳粒子的位置和速度的更新公式：vι(t+1)=-xι(t)+pg(t)+wvι(t)+ρ(t)(1-2*rand())(6)xι(t+1)=pg(t)+wι(t)+ρ(t)(1-2*rand())(7)其中ι是达到最优解的粒子的下际，ρ(t)是比例因子如果算法连续成功找到最优解达到了指定的次数，这增大ρ(t)的值，如果连续失败到一定的次数，则减小ρ(t)的值，如果连续成功或者连续失败没有达到指定的次数，则保持ρ(t)的值不变。结果表明：GCPSO可以得到比标准PSO更好的结果或者是类似的结果，但是这种算法不能保证全局收敛。（3）导入其他演算思想的改进PSO算法标准的PSO算法中没有明显的选择、交叉以及变异等演算运算。适当的引入演化算子，在一定程度上可以提高算法的性能。在一般粒子群算法中，每个粒子的最优位置的确定相当于隐含的选择机制。有一种具有选择机制的改进的PSO算法，基本思想是：在进化过程中保持种群中所有的粒子适度的排序，然后用较好的适应度的前一半代替适应度教不好的后一般的粒子。测试结果表明，该算法提高了求解性能，但是也增加了陷入拒不足有的可能性。还有一种杂交的粒子群算法，他的基本思路是：在迭代的过程中，按照提前设定的杂交概率选择指定的粒子数量放到杂交池里进行杂交，然后将生成的子代代替上一代。这种算法降低了收敛率，但是提高了收敛速度和精度。（4）建立非数值问题模型的改进PSO算法由于PSO简单的位置和速度算式，对数值化的问题就很容易的表达出来，因此处理数字化的问题的各种PSO改进算法得到了较大的发展，而对于非数值化的问题而言，表现问题不能直接用位置和速度，所