单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,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.4,PSO,算法流程,6.2.5,全局和局部最优,PSO,算法,6.2.6,PSO,算法参数分析,6.3,粒子群算法与其他算法的比较,6.3.1,与遗传算法的比较,6.3.2,与蚁群算法的比较,6.4,粒子群算法的应用,6.5,粒子群算法的研究方向,6.1,粒子群算法概述,6.1.1,粒子群算法的概念,粒子群,优化算法,（,Particle Swarm Optimization,，简称,PSO,）又称为,粒子群,算法、微粒算法，是通过模拟鸟类群体,觅食行为,而发展起来的一种基于群体协作的,随机搜索,算法，属于启发式全局优化算法。,粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。,6.1,粒子群算法概述,6.1.2,粒子群算法的发展,萌芽阶段,1986,年，人工生命、计算机图形学专家,Craig,Reynolds,提出了简单的人工生命系统,boid,模型（解释为,bird like object,），模拟了鸟类在飞行过程中分离、列队和聚集三种聚群飞行行为，并能感知到周围一定范围内其他,boid,的飞行信息。,boid,根据该信息，结合当前自身的飞行状态，在三条简单行为规则的指导下，做出下一步的飞行决策。,6.1,粒子群算法的概述,Craig Reynolds,生于,1953,年,3,月,15,日,避免碰撞：飞离最近的个体，以避免碰撞；,速度一致：和邻近的个体的平均速度保持一致；,向中心聚集：飞向群体的中心，向邻近个体的平均位置移动。,1990,年，生物学家,Frank Heppner,建立了鸟类模型。一群小鸟为找到合适的栖息地在空中飞行,，当群体中的一只发现较为合适的栖,息地时，它会毫不犹豫地飞向这个栖,息地，同时也将信息传给周围的小鸟,，使周围的小鸟快速来到这里，最终,把整个群体吸引到合适的栖息地。,6.1,粒子群算法的概述,发展阶段,1995,年，美国社会心理学家,James Kennedy,博士和电气工程师,Russell,Eberhart,博士根据对鸟群捕食行为的研究，提出了粒子群算法。分别在日本和澳大利亚召开的两个国际会议上发表了两篇文章，标志着粒子群算法的诞生。,1 Kennedy J,，,Eberhart,R,，,Particle swarm optimization,，,Proceeding of the IEEE International Conference on,Neural Networks,，,1995,，,19421948,2,Eberhart,R,，,Kennedy J,，,A new optimizer using particle,swarm theory,，,Proceeding of the 6th International,Symposium on Micro-Machine and Human Science,，,1995,，,3943,6.1,粒子群算法的概述,社会心理学家,James Kennedy,博士,电气工程师,Russell,Eberhart,博士,1998,年，,Yuhui,Shi,和,Russell,Eberhart,在,IEEE Congress on Evolution-,ary,Computation,（,6973,）上发表了题为,A modified particle swarm optimizer,的学术论文，首次对基本粒子群算法引入惯性权重修正了速度更新公式，修正后的公式已经为大多数研究者所使用。,从,1998,年开始，进化计算领域的著名会议,IEEE CEC,（,Congress on Evolutionary Computation,，国际进化计算会议）开始设置,PSO,算法的专题讨论，与计算智能相关的重要国际会议,PPSN,（,Parallel Problem Solving from,Neture,）和,GECCO,（,Gen-,etic,and Evolutionary Computation Conference,）都将,PSO,算法作为会议主题之一。,6.1,粒子群算法的概述,2001,年，由,J.Kennedy,、,R.C.Eberhart,、,Yuhui,Shi,合著的第一本关于,PSO,的专著,Swarm Intelligence,在美国旧金山（,San Francisco,）,Morgan Kaufmann Publishers,出版。,2003,年，第一届群智能研讨会,IEEE Swarm Intelligence Symposium,在美国的,Indianapolis,（印第安纳波利斯）召开，此后每年召开一次。,2004,年，,IEEE Transactions on Evolutionary,Compu-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,中，每个优化问题的解都是搜索空间中的一只鸟，称之为,“粒子”,。所有的粒子都有一个由被优化函数决定的适应度值（,fitness value,），每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中进行搜索。,PSO,初始化为一群随机粒子（随机解），然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个,“极值”来,更新自己。第一个是粒子本身所找到的最优解，称为个体极值,pbest,，另一个是整个种群目前找到的最优解，称为全局极值,gbest,。另外也可以不用整个种群而只用其中一部分相邻的粒子，则这些所有相邻粒子中的极值就是局部极值。,6.2,粒子群算法的基本原理,6.2.2,传统,PSO,算法原理,鸟被抽象为没有质量和体积的微粒，并延伸到,N,维空间中。粒子,i,（,i=1,，,2,，,，,M,）在,N,维空间的一些参数设置为,位置表示为：,飞行速度表示为：,每个粒子都有一个由目标函数决定的适应度值，并且知道自己迄今为止发现的最好位置（,pbest,）和现在的位置，可以看做是粒子自己的飞行经验。,每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置（,gbest,），可以看做是粒子同伴的经验。,粒子通过自己和同伴的经验决定下一步的运动轨迹。,6.2,粒子群算法的基本原理,PSO,初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值（,pbest,、,gbest,）来更新自己。在找到这两个最优值后，粒子通过下面的公式更新自己的速度和位置,式中，分别表示粒子的数量及其维数；为加速因子或学习因子，一般取正数；为,之间的随机数。,在迭代中，速度和位置均设定最大值，超过边界值时取边界值。,6.2,粒子群算法的基本原理,在速度更新公式中，第一项称为记忆项，表示上次速度大小和方向的影响；第二项称为自身认知项，是从当前点指向粒子自身最好点的一个项，表示粒子的动作来源于自身的经验；第三项称为群体认知项，是一个从当前点指向种群最好点的项，反映了粒子间的协同合作和知识共享。,总之，粒子的速度更新公式由认知和社会两部分组成，粒子就是通过自身的经验和同伴间最好的经验来决定下一步的运动轨迹。,6.2,粒子群算法的基本原理,6.2,粒子群算法的基本原理,6.2.3,标准,PSO,算法原理,1998,年，,Shi,对传统,PSO,算法进行了修正，引入了惯性权重因子（也称为动量因子），得到,惯性权重因子的值较大，全局寻优能力强，但局部寻优能力弱；否则则反之。一般认为，惯性权重因子用于平衡全局和局部搜索能力，较大的倾向于全局搜索，较小的适用于局部搜索，因此惯性权重因子的取值应随时间逐渐减小。,初始时，,Shi,将惯性权重因子取为常数，但后来实验发现，动态值能够获得比固定值更好的寻优效果。既可以在搜索过程中线性变化，也可根据某个测度函数动态改变。但目前采用较多的是,Shi,建议的线性递减权值。,6.2,粒子群算法的基本原理,6.2.4 PSO,算法,流程,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,算法。,6.2,粒子群算法的基本原理,对于全局最优,PSO,算法，搜索空间能力强，缺少局部搜索，因此收敛速度较快，但对于复杂问题易陷入局部最优。,局部最优,PSO,算法,当 时，粒子间没有交流，即没有社会信息，只有自身的认知能力，变为认知模型,称为局部最优,PSO,算法。,对于局部最优,PSO,算法，由于个体之间没有信息交流，整个群体相当于多个粒子进行盲目的随机搜索，因此收敛速度较慢，得到最优解的可能性较小。,6.2,粒子群算法的基本原理,概念二,全局和局部最优主要考虑其邻域范围。,如果每个粒子的邻域是整个种群，其社会网络的拓扑结构为星状（即通信中的网孔型拓扑结构），任意两个粒子间均有联系，使得速度更新公式中的社会成分反映了种群中所有粒子的信息，即,gbest,是种群迄今为止发现的最好位置，则称为全局最优,PSO,算法。,如果每个粒子的邻域是其相邻的两个粒子，其社会网络的拓扑结构为环状。使得更新公式中的社会成分仅代表邻居之间