粒子群优化算法综述

粒子群优化(PSO)算法[摘要]粒子群优化(PSO)算法是一种新兴的优化技术,其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最优解和整个群的最优解来完成优化。该算法简单易实现,可调参数少,已得到广泛研究和应用。详细介绍了PSO的基本原理、其特点、各种改进方式及其应用等,并对其未来的研究进行展望。[关键词]群体智能;优化算法;粒子群优化1、前言从20世纪90年代初,就产生了模拟自然生物群体(swarm)行为的优化技术。Dorigo等从生物进化的机理中受到启发,通过模拟蚂蚁的寻径行为,提出了蚁群优化方法;Eberhart和Kennedy于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能(swarmintelligence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(PSO)最初是处理连续优化问题的,目前其应用已扩展到组合优化问题。由于其简单、有效的特点,PSO已经得到了众多学者的重视和研究。粒子群算法在求解优化函数时，表现出较好的寻优能力。特别是针对复杂的工程问题，通过迭代寻优计算，能够迅速找到近似解，因而粒子群算法在工程计算中被广泛应用。2、PSO基本原理粒子群优化算法是基于群体的演化算法,其思想来源于人工生命和演化计算理论。Reynolds对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居,但最终的整体结果是整个鸟群好像在一个中心的控制之下,即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的,并用于解决优化问题。另外,人们通常是以他们自己及他人的经验来作为决策的依据,这就构成了PSO的一个基本概念。PSO求解优化问题时,问题的解对应于搜索空间中一只鸟的位置,称这些鸟为“粒子”(particle)或“主体”(agent)。每个粒子都有自己的位置和速度(决定飞行的方向和距离),还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子,在解空间中搜索。每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解。令PSO初始化为一群随机粒子(随机解),在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解,叫做个体极值点(用表示其位置),全局版PSO中的另一个极值点是整个种群目前找到的最好解,称为全局极值点(用gbest表示其位置),而局部版PSO不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用表示其位置)。在找到这两个最好解后,粒子根据如下的式(1)和式(2)来更新自己的速度和位置。粒子i的信息可以用D维向量表示,位置表示为,速度为,其他向量类似.在每一次迭代中，评价各微粒的目标函数，确定t时刻每个微粒所经过的最佳位置以及群体所发现的最佳位置，通过跟踪这两个最佳位置式（1）和（2）分别更新各微粒的速度和位置。()()[()]()(1)()()(),j=1,…,d（2）,是加速系数(或称学习因子),分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域。合适的c1,c2可以加快收敛且不易陷入局部最优,通常令;和为0到1之间均匀分布的随机数。通过设置微粒的速度区间和位置范围,则可以对微粒的移动进行适当的限制。基本PSO的流程可以描述为:Step1初始化初始搜索点的位置X0i及其速度V0i通常是在允许的范围内随机产生的,每个粒子的坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将设置为该最好粒子的当前位置。Step2评价每一个粒子计算粒子的适应度值,如果好于该粒子当前的个体极值,则将设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将设置为该粒子的位置,记录该粒子的序Step3粒子的更新，用式(1)和式(2)对每一个粒子的速度和位置进行更新。Step4检验是否符合结束条件，如果当前的迭代次数达到了预先设定的最大次数(或达到最小错误要求),则停止迭代,输出最优解,否则转到。PSO的一些特点:1)基本PSO算法最初是处理连续优化问题的。2)类似于遗传算法(GA)，PSO也是多点搜索。3)式(1)的第一项对应多样化(diversification)的特点,第二项、第三项对应于搜索过程的集中化(intensification)特点,因此这个方法在多样化和集中化之间建立均衡。PSO有全局版和局部版两种,全局版收敛快,但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟,假设每一个粒子在大小l的邻域内定义为一个集合从Ni中选出最好的,将其位置作为代替公式中的,其他与全局版PSO相同。实验表明,局部版比全局版收敛慢,但不容易陷入局部最优。在实际应用中,可以先用全局PSO找到大致的结果,再用局部PSO进行搜索。3、PSO的改进PSO算法的改进研究可归纳为两个方面：一方面的研究是讲各种先进理论引入PSO算法，研究各种改进和PSO算法；另一方面是将PSO无案发和其他智能优化算法相结合，研究各种混合优化算法，达到取长补短、改善算法某方面性能的效果。由于PSO中粒子向自身历史最佳位置和领域或群体历史最佳位置剧集，形成粒子种群的快速趋同效应，容易出现陷入局部极限、早熟收敛或停滞现象。同时，PSO的性能也依赖于算法参数。算法具体参数设置不同，结果怒同。算法具体参数主要依赖于微粒个数、惯性权重、学习因子，以及添加压缩因子等参数。为了克服上述不足，各国研究人员相继提出了各种改进措施。本文将这些改进分为4类：粒子群初始化、邻域拓扑、参数选择和混合策略。3.1、粒子群初始化研究表明，粒子群初始化对算法性能产生一定影响[16]。为了初始种群尽可能均匀覆盖整个搜索空间，提高全局搜索能力，Richard和Ventura[17]提出了基于centroidalvoronoitessellations(CVTs)的种群初始化方法；薛明志等人[18]采用正交设计方法对种群进行初始化；Campana等人[19]将标准PSO迭代公式改写成线性动态系统，并基于此研究粒子群的初始位置，使它们具有正交的运动轨迹；文献[16]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差，并另外比较了3种初始化分布方法。3.2、邻域拓扑根据粒子邻域是否为整个群体，PSO分为全局模型gbest和局部模型gbest[20]。Kennedy[21]指出，gbest模型虽然具有较快的收敛速度，但更容易陷入局部极值。为了克服gbest全局模型的缺点，研究人员采用每个粒子仅在一定的邻域内进行信息交换，提出各种gbest局部模型[21,]。根据现有的研究成果，本文将邻域分为空间邻域(spatialneighborhood)、性能空间(performancespace)邻域和社会关系邻域(sociometricneighborhood)。空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分，如Suganthan[23]引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标(如适应度、目标函数值)划分的邻域，如文献[24]采用适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。社会关系邻域通常按粒子存储阵列的索引编号进行划分[25]，这也是研究最多的一种划分手段，主要有[21]：环形拓扑(ringorcircletopology)、轮形拓扑(wheeltopology)或星形拓扑(startopology)、塔形拓扑(pyramidtopology)、冯－诺以曼拓扑(VonNeumanntopology)以及随机拓扑(randomtopology)等。针对不同的优化问题，这些拓扑的性能表现各异；但总的来说，随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑[22]。M.Clerc[25]对随机拓扑进行了进一步分析，并在2006年版和2007年版的标准PSO[23]中采用了随机拓扑。此外，文献[21]提出动态社会关系拓扑(Dynamicsociometry)，初始阶段粒子采用环形拓扑(ring-typetopology)，随着迭代次数的增加，逐渐增加粒子间连接，最后形成星形拓扑(star-typetopology)。此外，还有其它一些主要对群体进行划分的邻域结构(本文暂称“宏观邻域”；则上述邻域称为“微观邻域”)。文献[19]引入了子种群，子种群间通过繁殖(Breeding)实现信息交流。Kennedy[20]提出了社会趋同(Stereotyping)模型，使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置。X.Li[21]根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置。StefanJanson等人[22]提出等级PSO(hierarchicalparticleswarmoptimizer,HPSO)，采用动态等级树作为邻域结构，历史最佳位置更优的粒子处于上层，每个粒子的速度由自身历史最佳位置和等级树中处于该粒子上一个节点的粒子的历史最佳位置决定。文献[13]采用主－仆模型(master–slavermodel)，其中包含一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索。文献[14]将小生境(niche)技术引入到PSO中，提出了小生境PSO(NichingParticleSwarmOptimizer)。文献[15]采用多群体进行解的搜索。文献[14]则每间隔一定代数将整个群体随机地重新划分，提出动态多群体PSO。在标准的PSO算法中，所有粒子仅仅向自身和邻域的历史最佳位置聚集，而没有向邻域内其他个体(即使这些个体很优秀)学习，造成信息资源的浪费，甚至因此而陷入局部极值；考虑到此因素，Kennedy等人[17]提出了全信息粒子群(fullyinformedparticleswarm,FIPS)，在FIPS中，每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的成功经验。上述粒子间学习是在整个D维空间中构造邻域进行的，这样当搜索空间维数较高时往往容易遭受“维数灾(curseofdimensionality)”的困扰[14]。基于这方面的考虑，VandenBergh等人[18]提出了协作PSO(CooperativePSO)算法，其基本思路就是采用协作行为，利用多个群体分别在目标搜索空间中的不同维度上进行搜索，也就是一个优化解由多个独立群体协作完成，每个群体只负责优化这个解矢量部分维上的分量。Baskar和Suganthan[19]提出一种类似的协作PSO，称为并发PSO(concurrentPSO，CONPSO)，它采用两个群体并发地优化一个解矢量。近来，El-Abd等人[20]结合文献[18,19]的技术，提出了等级协作PSO(hierarchalcooperativePSO)。J.Liang等人[4]提出了一种既可以进行D-维空间搜索、又能在不同维上选择不同学习对象的新的学习策略，称为全面学习PSO(ComprehensiveLearningParticleSwarmOptimizer，CLPSO)。以上的各种邻域结构称之为PSO的被动局部模型。还有一类局部模型就是主动改变粒子邻域空间，避免碰撞和拥挤，本文称之为PSO的主动局部模型。Blackwell等人