第7章-粒子群优化

1第七章粒子群优化2第七章粒子群优化（PSO）一.PSO的产生二.PSO的基本思想三.基本PSO四.标准PSO五.计算举例六.改进与变形七.学习PSO的几点体会3ParticleSwarmOptimization简称：PSO粒子群优化（微粒群优化）1995年，Kennedy&Eberhart提出一.PSO的产生（1）4Particleswarmoptimization——IEEEInternationalConferenceonNeuralNetworks，1995Anewoptimizerusingparticleswarmtheory——6thInternationalSymposiumonMicromachineandHumanScience，1995五年后，在国际上逐步被接受，并有大批不同领域的学者投入该算法相关研究，目前已经成为智能优化领域研究的热门一.PSO的产生（2）52003年，《控制与决策》第二期刊登国内第一篇PSO论文——综述文章一.PSO的产生（3）61.对社会行为的模拟2.从对“birdflock”的模拟到PSO算法的演化3.PSO算法概述4.名称的由来：Swarm和Particle二.PSO的基本思想（1）71.对社会行为的模拟：（1）对鸟群行为的模拟Reynolds和Heppner，Grenander在1987年和1990年发表的论文中都关注了鸟群群体行动中的蕴涵的美学二.PSO的基本思想（2）8他们发现，由数目庞大的个体组成的鸟群飞行中可以改变方向，散开，或者队形的重组等等，那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了个体间距的处理，也就是让鸟群中的个体之间保持最优的距离。二.PSO的基本思想（3）91.对社会行为的模拟：（2）对鱼群行为的研究1975年，生物社会学家E.O.Wilson在论文中阐述了对鱼群的研究二.PSO的基本思想（4）10他在论文中提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中发现的和以前的经验，这种受益是明显的，它超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散于四处。”这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的基础。二.PSO的基本思想（5）111.对社会行为的模拟：（3）对人类的社会行为的模拟与前者不同，最大区别在于抽象性！鸟类和鱼类是调节他们的物理运动，来避免天敌，寻找食物，优化环境的参数，比如温度等。人类调节的不仅是物理运动，还包括认知和经验变量。我们更多的是调节自己的信仰和态度，来和社会中的上流人物或者专家，或者说在某件事情上获得最优解的人保持一致。二.PSO的基本思想（6）121.对社会行为的模拟：这种不同导致了计算机仿真上的差别，至少有一个明显的因素：碰撞（collision）两个个体即使不被绑在一块，也具有相同的态度和信仰，但是两只鸟是绝对不可能不碰撞而在空间中占据相同的位置。这是因为动物只能在三维的物理空间中运动，而人类还在抽象的多维心理空间运动，这里是碰撞自由的（collision-free）。二.PSO的基本思想（7）132.从对“birdflock”的模拟到PSO算法的演化（1）速度匹配和“Craziness”鸟群首先在在二维空间中进行位置的初始化，每个个体具有X和Y两个速度，对邻居间速度的匹配导致鸟群的行动完全一致，方向也不变化，显然小鸟不会这么听话，于是加入了Craziness变量，对坐标增加一些随机的成分。二.PSO的基本思想（8）142.从对“birdflock”的模拟到PSO算法的演化（2）麦田向量的引入鸟群最终会飞到麦田中。鸟群开始就知道麦田在哪。用离麦田有多远来评价小鸟飞到的地方好不好。在飞行的过程中，通过与自己找到的最好点和群体找到的最好点进行比较，来调整自己的速度。二.PSO的基本思想（9）152.从对“birdflock”的模拟到PSO算法的演化Kennedy和Eberhart对Hepper的模仿鸟群的模型进行了修正，以使粒子能够飞向解空间，并在最好解处降落，从而得到了粒子群优化算法。二.PSO的基本思想（10）163.PSO算法概述一个由多个个体（Particle）组成的群体（Swarm）对多维搜索空间进行搜索，每个个体在搜索时，考虑到了自己搜索到的历史最好点和群体内（或邻域内）其他个体的历史最好点，在此基础上进行位置（状态，也就是解）的变化二.PSO的基本思想（11）173.PSO算法概述这里，多维搜索空间是对人类多维的心理空间的模仿，个体在搜索时考虑自己的历史最好点，这是个体经验的积累，同时考虑到群体内其他个体的历史最好点，这是社会信息的共享作用和个体本身具有学习能力的表现。二.PSO的基本思想（12）184.名称的由来：Swarm和ParticleSwarm：在美国传统字典中有三个意思（1）一大群尤指正在行进中的一大群昆虫或其它细小生物。（2）蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂。（3）一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物。二.PSO的基本思想（13）194.名称的由来：Swarm和Particle作者引用此词是借用了Millonas在1994年的论文中的人工生命的一个应用模型中的提法。Millonas明确提出Swarm智能（swarmintelligence）的五点原则——在算法的研究中当深思二.PSO的基本思想（14）20(1)theproximityprinciple群体能够执行简单的时间和空间的计算(2)thequalityprinciple群体能够响应环境的特征要素(3)theprincipleofdiverseresponse群体能够使自己的行动不被限制在一个狭小的范围内(4)theprincipleofstability群体不要每次环境变化都跟着改变自己的行为模式(5)theprincipleofadaptability群体的行为模式要能够在值得计算代价的时候发生改变二.PSO的基本思想（15）214.名称的由来：Swarm和ParticleParticle:算法中有速度和加速度的字眼，这比较适合于粒子。Reeves在1983年的论文中讨论了粒子系统包括基本粒子团和云，火，烟雾等弥漫性物体。作者的想法是让粒子尽量具有一种普遍性的意义用粒子在超空间（Hyperspace）的飞行来模拟人类的社会性行为二.PSO的基本思想（16）221.算法描述及简要分析2.基本PSO公式3.基本PSO步骤三.基本PSO（1）231.算法描述及简要分析一个由m个粒子（Particle）组成的群体（Swarm）在D维搜索空间中以一定的速度飞行，每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内（或邻域内）其他粒子的历史最好点，在此基础上进行位置（状态，也就是解）的变化。三.基本PSO（2）24描述中与GA相类似的问题：（1）种群的规定与初始化：Swarm具有大小，随机初始化（2）点的好坏如何判断：通过适值函数（3）停止准则还要解决的问题：（1）个体本身所找到的历史最好点如何进行考虑，也就是让这个点如何影响下一次迭代？（2）对群体内或者邻域内成员所找到的历史最好点如何进行考虑？（3）粒子的位置如何进行变化？三.基本PSO（3）25三.基本PSO（4）2.基本PSO公式121212121,1(,,,)(,,,)(,,,)(,,,)iiDiiggDggiiDiiiiDiiimdDppppppppxxxxvvvv26三.基本PSO（5）2.基本PSO公式11211()()(7.1)(7.2),[0,1]kkkkkkididididgdidkkkidididvvcpxcpxxxvU272.基本PSO公式c1和c2：学习因子（learningfactor）或加速系数（accelerationcoefficient），一般为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。通常等于2。三.基本PSO（6）282.基本PSO公式粒子的速度被限制在一个最大速度Vmax的范围内。引入Vmax的原因：a、防止计算机溢出b、对人类学习和观念转变的模拟c、它还决定了空间搜索的粒子性三.基本PSO（7）292.基本PSO公式当把群体内所有粒子都作为邻域成员时，得到粒子群优化算法的全局版本；当群体内部分成员组成邻域时得到粒子群优化算法的局部版本。局部版本中，一般有两种方式组成邻域，一种是索引号相临的粒子组成邻域，另一种是位置相临的粒子组成邻域。粒子群优化算法的邻域定义策略又可以称为粒子群的邻域拓扑结构。三.基本PSO（8）30三.基本PSO（9）3.基本PSO步骤步1：在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度。步2：计算每个粒子的适应值。步3：对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置31三.基本PSO（10）3.基本PSO步骤步4：对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最好位置。步5：根据式（7.1）和（7.2）对粒子的速度和位置进行更新。步6：若未达到终止条件，则转步2。321.标准PSO公式2.算法构成要素四.标准PSO（1）331.标准PSO公式为改善算法收敛性能，Shi和Eberhart在1998年的论文中引入了惯性权重的概念，将速度更新方程修改为（7.3）所示：四.标准PSO（2）112()()(7.3)kkkkkkididididgdidvvcpxcpx34这里，称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。可见，基本PSO算法是惯性权重的特殊情况。分析和实验表明，设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用Vmax进行初始化，将Vmax设定为每维变量的变化范围，而不必进行细致的选择与调节。四.标准PSO（3）35目前，对于PSO算法的研究大多以带有惯性权重的PSO为对象进行分析、扩展和修正，因此大多数文献中将带有惯性权重的PSO算法称为PSO算法的标准版本，或者称为标准PSO算法；而将前述PSO算法称为初始PSO算法/基本PSO算法，或者称为PSO算法的初始版本。四.标准PSO（4）362.算法构成要素群体大小：mm是个整型参数。当m很小的时候，陷入局优的可能性很大。然而，群体过大将导致计算时间的大幅增加。并且当群体数目增长至一定水平时，再增长将不再有显著的作用。当m=1的时候，PSO算法变为基于个体搜索的技术，一旦陷入局优，将不可能跳出。当m很大时，PSO的优化能力很好，可是收敛的速度将非常慢。四.标准PSO（5）372.算法构成要素学习因子：c1和c2学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或邻域内最优点靠近。c1和c2通常等于2，不过在文献中也有其他的取值。但是一般c1等于c2，并且范围在0和4之间。四.标准PSO（6）382.算法构成要素最大速度：Vmax四.标准PSO（7）392.算法构成要素惯性权重智能优化方法的运行是否成功，探索能力和开发能力的平衡是非常关键的。对于粒子群优化算法来说，这两种能力的平衡就是靠惯性权重来实现。四.标准PSO（8）402.算法构成要素邻域拓扑结构全局版本粒子群优化算法将整个群体作为粒子的邻域，速度快，不过有时会陷入局部最优；局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒子的邻域，收敛速度慢一点，不过很难陷入局部最优。显然，全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个