第6章粒子群算法基本理论.

第6章粒子群算法基本理论6.1粒子群算法的概述6.1.1粒子群算法的概念6.1.2粒子群算法的发展6.1.3粒子群算法的特点6.1.4粒子群算法的分类6.2粒子群算法的基本原理6.2.1生物学机理6.2.2传统PSO算法原理6.2.3标准PSO算法原理6.2.4PSO算法流程6.2.5全局和局部最优PSO算法6.2.6PSO算法参数分析6.3粒子群算法与其他算法的比较6.3.1与遗传算法的比较6.3.2与蚁群算法的比较6.4粒子群算法的应用6.5粒子群算法的研究方向6.1粒子群算法概述6.1.1粒子群算法的概念粒子群优化算法（ParticleSwarmOptimization，简称PSO）又称为粒子群算法、微粒算法，是通过模拟鸟类群体觅食行为而发展起来的一种基于群体协作的随机搜索算法，属于启发式全局优化算法。粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。6.1粒子群算法概述6.1.2粒子群算法的发展萌芽阶段1986年，人工生命、计算机图形学专家CraigReynolds提出了简单的人工生命系统——boid模型（解释为birdlikeobject），模拟了鸟类在飞行过程中分离、列队和聚集三种聚群飞行行为，并能感知到周围一定范围内其他boid的飞行信息。boid根据该信息，结合当前自身的飞行状态，在三条简单行为规则的指导下，做出下一步的飞行决策。6.1粒子群算法的概述CraigReynolds生于1953年3月15日避免碰撞：飞离最近的个体，以避免碰撞；速度一致：和邻近的个体的平均速度保持一致；向中心聚集：飞向群体的中心，向邻近个体的平均位置移动。1990年，生物学家FrankHeppner建立了鸟类模型。一群小鸟为找到合适的栖息地在空中飞行，当群体中的一只发现较为合适的栖息地时，它会毫不犹豫地飞向这个栖息地，同时也将信息传给周围的小鸟，使周围的小鸟快速来到这里，最终把整个群体吸引到合适的栖息地。6.1粒子群算法的概述发展阶段1995年，美国社会心理学家JamesKennedy博士和电气工程师RussellEberhart博士根据对鸟群捕食行为的研究，提出了粒子群算法。分别在日本和澳大利亚召开的两个国际会议上发表了两篇文章，标志着粒子群算法的诞生。[1]KennedyJ，EberhartR，Particleswarmoptimization，ProceedingoftheIEEEInternationalConferenceonNeuralNetworks，1995，1942~1948[2]EberhartR，KennedyJ，Anewoptimizerusingparticleswarmtheory，Proceedingofthe6thInternationalSymposiumonMicro-MachineandHumanScience，1995，39~436.1粒子群算法的概述社会心理学家JamesKennedy博士电气工程师RussellEberhart博士1998年，YuhuiShi和RussellEberhart在IEEECongressonEvolution-aryComputation（69~73）上发表了题为Amodifiedparticleswarmoptimizer的学术论文，首次对基本粒子群算法引入惯性权重修正了速度更新公式，修正后的公式已经为大多数研究者所使用。从1998年开始，进化计算领域的著名会议IEEECEC（CongressonEvolutionaryComputation，国际进化计算会议）开始设置PSO算法的专题讨论，与计算智能相关的重要国际会议PPSN（ParallelProblemSolvingfromNeture）和GECCO（Gen-eticandEvolutionaryComputationConference）都将PSO算法作为会议主题之一。6.1粒子群算法的概述2001年，由J.Kennedy、R.C.Eberhart、YuhuiShi合著的第一本关于PSO的专著《SwarmIntelligence》在美国旧金山（SanFrancisco）MorganKaufmannPublishers出版。2003年，第一届群智能研讨会IEEESwarmIntelligenceSymposium在美国的Indianapolis（印第安纳波利斯）召开，此后每年召开一次。2004年，IEEETransactionsonEvolutionaryCompu-tation出版了PSO算法专刊。PSO算法作为一种新兴智能仿生算法，目前还没有完备的数学理论基础，但作为新兴优化算法已在诸多领域得到广泛应用。6.1粒子群算法的概述6.1.3粒子群算法的特点粒子群算法的优点①粒子群算法依靠粒子速度完成搜索，在迭代进化中只有最优的粒子将信息传递给其他粒子，搜索速度快。②粒子群算法具有记忆性，粒子群体的历史最好位置可以记忆，并传递给其他粒子。③需调整的参数较少，结构简单，易于工程实现。④采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维数。6.1粒子群算法的概述粒子群算法的缺点①容易陷入局部最优，导致收敛精度低和不易收敛。②不能有效解决离散及组合优化问题。6.1粒子群算法的概述6.1.4粒子群算法的分类按照发展历程分类一般分为传统粒子群算法和标准粒子群算法。前者于1995年提出，后者于1998年改进，两者之差仅为有无惯性权重因子。根据粒子邻域分类一般分为全局最优粒子群算法和局部最优粒子群算法，目前主要有两种分类方法。6.1粒子群算法的概述6.2粒子群算法的基本原理6.2.1生物学机理一群鸟在一个区域里随机搜索食物，所有的鸟都不知道食物在那里。但是他们知道当前位置离食物还有多远，那么找到食物的最优策略就是搜寻目前离食物最近的鸟的周围区域。6.2粒子群算法的基本原理6.2粒子群算法的基本原理6.2粒子群算法的基本原理6.2粒子群算法的基本原理6.2粒子群算法的基本原理6.2粒子群算法的基本原理粒子群算法PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化函数决定的适应度值（fitnessvalue），每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中进行搜索。PSO初始化为一群随机粒子（随机解），然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个是粒子本身所找到的最优解，称为个体极值pbest，另一个是整个种群目前找到的最优解，称为全局极值gbest。另外也可以不用整个种群而只用其中一部分相邻的粒子，则这些所有相邻粒子中的极值就是局部极值。6.2粒子群算法的基本原理6.2.2传统PSO算法原理鸟被抽象为没有质量和体积的微粒，并延伸到N维空间中。粒子i（i=1，2，…，M）在N维空间的一些参数设置为位置表示为：飞行速度表示为：每个粒子都有一个由目标函数决定的适应度值，并且知道自己迄今为止发现的最好位置（pbest）和现在的位置，可以看做是粒子自己的飞行经验。每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置（gbest），可以看做是粒子同伴的经验。粒子通过自己和同伴的经验决定下一步的运动轨迹。iNiniiix,,x,,x,x21XiNiniiiv,,v,,v,v21V6.2粒子群算法的基本原理PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值（pbest、gbest）来更新自己。在找到这两个最优值后，粒子通过下面的公式更新自己的速度和位置式中，分别表示粒子的数量及其维数；为加速因子或学习因子，一般取正数；为之间的随机数。在迭代中，速度和位置均设定最大值，超过边界值时取边界值。11tvtxtxininintxtgbestrandctxtpbestrandctvtvinininininin211N1,2,n21,M,,,i、21cc、rand10,6.2粒子群算法的基本原理txtgbestrandctxtpbestrandctvtvinininininin211在速度更新公式中，第一项称为记忆项，表示上次速度大小和方向的影响；第二项称为自身认知项，是从当前点指向粒子自身最好点的一个项，表示粒子的动作来源于自身的经验；第三项称为群体认知项，是一个从当前点指向种群最好点的项，反映了粒子间的协同合作和知识共享。总之，粒子的速度更新公式由认知和社会两部分组成，粒子就是通过自身的经验和同伴间最好的经验来决定下一步的运动轨迹。6.2粒子群算法的基本原理txtgbestrandctxtpbestrandctvtvinininininin211tvin1c1tvin2c6.2粒子群算法的基本原理6.2.3标准PSO算法原理1998年，Shi对传统PSO算法进行了修正，引入了惯性权重因子（也称为动量因子），得到惯性权重因子的值较大，全局寻优能力强，但局部寻优能力弱；否则则反之。一般认为，惯性权重因子用于平衡全局和局部搜索能力，较大的倾向于全局搜索，较小的适用于局部搜索，因此惯性权重因子的取值应随时间逐渐减小。初始时，Shi将惯性权重因子取为常数，但后来实验发现，动态值能够获得比固定值更好的寻优效果。既可以在搜索过程中线性变化，也可根据某个测度函数动态改变。但目前采用较多的是Shi建议的线性递减权值。txtgbestrandctxtpbestrandctvtvinininininin2116.2粒子群算法的基本原理6.2.4PSO算法流程Step1：初始化一群微粒（一般设种群规模为m），包括随机位置和速度。Step2：评价每个微粒的适应度值。Step3：将每个微粒的适应度值与其经过的最好位置pbest进行比较，如果较好则将其作为当前的最好位置pbest。Step4：将每个微粒的适应度值与种群的最好位置gbest进行比较，如果较好则将其作为种群的最好位置gbest。Step5：根据速度和位置公式调整粒子的飞行速度和所处位置。Step6：判断是否达到结束条件，若未达到转到Step2。6.2粒子群算法的基本原理6.2粒子群算法的基本原理6.2.5全局和局部最优PSO算法目前关于全局和局部最优PSO算法的概念主要有两种。概念一全局最优PSO算法在速度更新公式中，pbest和gbest分别表示粒子群的局部和全局最优位置。当时，粒子没有认知能力，变为只有社会的模型称为全局最优PSO算法。txtgbestrandctxtpbestrandctvtvinininininin211txtgbestrandctvtvinininin2101c6.2粒子群算法的基本原理对于全局最优PSO算法，搜索空间能力强，缺少局部搜索，因此收敛速度较快，但对于复杂问题易陷入局部最优。局部最优PSO算法当时，粒子间没有交流，即没有社会信息，只有自身的认知能力，变为认知模型称为局部最优PSO算法。对于局部最优PSO算法，由于个体之间没有信息交流，整个群体相当于多个粒子进行盲目的随机搜索，因此收敛速度较慢，得到最优解的可能性较小。txtpbestrandctvtvinininin1102c6.2粒子群算法的基本原理概念二全局和局部最优主要考虑其邻域范围。如果每个粒子的邻域是整个种群，其社会网络的拓扑结构为星状（即通信中的网孔型拓扑结构），任意两个粒子间均有联系，使得速度更新公式中的社会成分反映了种群中所有粒子的信息，即gb