【教学课件】第七章粒子群优化算法.ppt

《【教学课件】第七章粒子群优化算法.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第七章粒子群优化算法.ppt（42页珍藏版）》请在三一办公上搜索。

1、1,第七章粒子群优化算法,2,第七章 粒子群优化算法,一.前言二.基本算法三.标准算法四.PSO的改进与变形五.学习PSO的几点体会,3,PSO的产生Particle Swarm Optimization(PSO)，粒子群优化或者微粒群优化PSO算法由美国学者Kennedy（社会心理学家）和Eberhart（电机工程师）于1995年提出，通过模拟鸟群和鱼群的社会交互行为而不仅仅依赖个体认知行为而设计的一种智能优化方法,一.前言,4,PSO的产生2000年以后，PSO算法在国际上逐步被接受，并有大批不同领域的学者投入该算法相关研究，已经成为智能优化领域研究的热门算法 2003年，控制与决策第二期

2、刊登国内第一篇综述性文章,一.前言,5,PSO的基本思想对社会行为的模拟对鸟群行为的模拟：Reynolds和Heppner，Grenander在1987年和1990年发表的论文中都关注了鸟群群体行动中蕴涵的美学。他们发现，由数目庞大的个体组成的鸟群飞行中可以改变方向，散开，或者队形的重组等等，那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了个体间距的处理，也就是让鸟群中的个体之间保持最优的距离。,一.前言,6,PSO的基本思想对社会行为的模拟对鱼群行为的研究：1975年，生物社会学家W

3、ilson在论文中阐述了对鱼群的研究。他在论文中提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中发现的和以前的经验，这种受益是明显的，它超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散于四处。”这说明，同种生物之间信息的社会共享能够带来好处。,一.前言,7,PSO的基本思想对社会行为的模拟对人类的社会行为的模拟：a.与前者不同，最大区别在于抽象性！b.鸟类和鱼类是调节他们的物理运动，来避免天敌，寻找食物，优化环境的参数，比如温度等。人类调节的不仅是物理运动，还包括认知和经验。我们更多的是调节自己的信仰和态度，来和社会中的杰出人物或者专家，或

4、者在某件事情上获得最优解的人保持一致。,一.前言,8,PSO的基本思想对社会行为的模拟对人类的社会行为的模拟：c.这种不同导致了计算机仿真上的差别，至少有一个明显的因素：碰撞（collision）。d.两个个体即使不被绑在一块，也具有相同的态度和信仰，但是两只鸟是绝对不可能不碰撞而在空间中占据相同的位置。这是因为动物只能在三维的物理空间中运动，而人类还在抽象的多维心理空间运动，这里是碰撞自由的（collision-free）。,一.前言,9,PSO的基本思想采纳基于种群(swarm)的机制个体(particle)均是问题的一个潜在解算法寻优依赖于在种群拓扑结构上个体间的社会交互行为,一.前言,

5、10,名称的由来：Swarm和ParticleSwarm：在美国传统字典中有三个意思一大群尤指正在行进中的一大群昆虫或其它细小生物蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物作者引用此词是借用了Millonas在1994年的论文中的人工生命的一个应用模型中的提法,一.前言,11,名称的由来：Swarm和ParticleParticle:算法中有速度和加速度的字眼，这比较适合于粒子。Reeves在1983年的论文中讨论了粒子系统包括基本粒子团和云、火、烟雾等弥漫性物体作者的想法是让粒子尽量具有一种普遍性的意义用粒子在超空间（Hyperspac

6、e）的飞行来模拟个体的社会性行为,一.前言,12,算法描述种群中m个个体分布在一个D维搜索空间中每个个体均具有当前位置、速度以及历史最优位置三个属性种群具有一定的拓扑结构，个体可以基于种群拓扑结构与其邻域内的其他个体进行相互作用算法迭代时，每个个体会根据自身信息（认知行为）和邻域内其他个体的信息（社会行为）进行状态更新,二.基本算法,13,基本PSO的公式,二.基本算法,Index,粒子i,粒子群,14,基本PSO的公式,二.基本算法,(2),(1),15,基本PSO的公式c1和c2：学习因子（learning factor）或加速系数（acceleration coefficient），一般

7、为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。通常等于2。和：0-1之间的随机数,二.基本算法,16,基本PSO的公式 粒子的速度被限制在-Vmax,Vmax的范围内。引入Vmax的原因：防止溢出保证算法稳定,二.基本算法,17,基本PSO的公式粒子群的拓扑结构决定个体间的相互影响程度PSO的全局版本将整个群体看作是一个全连通图，群体内所有个体共享一个邻域最优 gbestPSO的局部版本中每个个体的邻域将是整个群体的一个子集，此时影响个体的gbest取决于具体的拓扑结构，一种简单的方法是群体内粒子根据其编号相邻的原则

8、组成一个环状结构,二.基本算法,18,基本PSO算法流程图,二.基本算法,begin initialize and evaluate a swarm of particles with random positions and velocities on D dimensions in the search space;repeat for each particle i do update gbest of particle i;endfor for each particle i do adapt the velocity of particle i using Equation(1);u

9、pdate the position of particle i using Equation(2);evaluate the fitness of particle i;update pbest of particle i;endfor until a stop condition is metend,19,带有惯性权重的PSO为改善算法收敛性能，Shi和Eberhart在1998年的论文中引入了惯性权重的概念，将速度更新方程修改为：,三.标准PSO,(3),20,带有惯性权重的PSO这里，w称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以使粒子具有均衡的探索和开发能力。可

10、见，基本PSO算法是惯性权重w=1的特殊情况。分析和实验表明，设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用Vmax进行初始化，将Vmax设定为每维变量的变化范围，而不必进行细致的选择与调节。,三.标准PSO,21,带有收缩因子的PSO2002年Clerc和Kennedy在基本PSO算法中引入可收缩因子的概念，指出该因子对于算法的收敛是必要的，将速度更新公式修改为：其中，,四.PSO的改进与变形,(4),22,带有收缩因子的PSOClerc将参数取值为：则 若带有惯性权重的PSO采用如下的参数设置：则两种标准版本的PSO算法等价,四.PSO的改进与变形,23,计算举例求

11、解无约束优化问题：5维的Rosenbrock函数,三.标准PSO,24,计算举例简单分析：Rosenbrock是一个著名的测试函数，也叫香蕉函数，其特点是该函数虽然是单峰函数，在100，100n上只有一个全局极小点，但它在全局极小点临近的狭长区域内取值变化极为缓慢，常用于评价算法的搜索性能。这种实优化问题非常适合于使用粒子群优化算法来求解。,三.标准PSO,25,计算举例算法设计编码：因为问题的维数为5，所以每个粒子为5维的实数向量。初始化范围：根据问题要求，设定为-30，30。根据前面的参数分析，我们知道，可以将最大速度设定为Vmax=60。种群大小：为了说明方便，这里采用一个较小的种群规模

12、，m=5。停止准则：设定为最大迭代次数100次。,三.标准PSO,26,计算举例算法设计惯性权重：采用固定权重0.5。邻域拓扑结构：使用星形拓扑结构，即全局版本的粒子群优化算法。,三.标准PSO,27,计算举例一次迭代后的结果,三.标准PSO,28,计算举例一次迭代后的结果从上面的数据我们可以看到，粒子有的分量跑出了初始化范围。需要说明的是，在这种情况下，我们一般不强行将粒子重新拉回到初始化空间，即使初始化空间也是粒子的约束空间。因为，即使粒子跑出初始化空间，随着迭代的进行，如果在初始化空间内有更好的解存在，那么粒子也可以自行返回到初始化空间。有研究表明，即使将初始化空间不设定为问题的约束空间

13、，即问题的最优解不在初始化空间内，粒子也可能找到最优解。,三.标准PSO,29,计算举例,三.标准PSO,30,惯性权重固定权重即赋予惯性权重以一个常数值，一般来说，该值在0和1之间。固定的惯性权重使粒子在飞行中始终具有相同的探索和开发能力。显然，对于不同的问题，获得最好优化效果的这个常数是不同的，要找到这个值需要大量的实验。通过实验我们发现：种群规模越小，需要的惯性权重越大，因为此时种群需要更好的探索能力来弥补粒子数量的不足，否则粒子极易收敛；种群规模越大，需要的惯性权重越小，因为每个粒子可以更专注于搜索自己附近的区域。,四.PSO的改进与变形,31,惯性权重时变权重一般来说，希望粒子群在飞

14、行开始的时候具有较好的探索能力，而随着迭代次数的增加，特别是在飞行的后期，希望具有较好的开发能力。所以希望动态调节惯性权重。可以通过时变权重的设置来实现。设惯性权重的取值范围为：最大迭代次数为Iter_max，则第i次迭代时的惯性权重可以取为：,四.PSO的改进与变形,32,惯性权重模糊权重模糊权重是使用模糊系统来动态调节惯性权重。下面的文献给出了一种模糊权重的设置方式 Shi Y,Eberhart R.Fuzzy adaptive particle swarm optimization:IEEE Int.Congress on Evolutionary Computation C.Pisca

15、taway,NJ:IEEE Service Center,2001:101-106.,四.PSO的改进与变形,33,惯性权重随机权重随机权重是在一定范围内随机取值。例如可以取值如下：其中，Random为0到1之间的随机数。这样，惯性权重将在0.5到1之间随机变化，均值为0.75。,四.PSO的改进与变形,34,邻域拓扑结构基于索引号的拓扑结构环形结构,四.PSO的改进与变形,35,邻域拓扑结构基于索引号的拓扑结构星形结构：每个粒子都与种群中的其他所有粒子相连，即将整个种群作为自己的邻域。也就是粒子群算法的全局版本。这种结构下，所有粒子共享的信息是种群中表现最好的粒子的信息。,四.PSO的改进与

16、变形,36,邻域拓扑结构基于距离的拓扑结构基于距离的拓扑结构是在每次迭代时，计算一个粒子与种群中其他粒子之间的距离，然后根据这些距离来确定该粒子的邻域构成。一种动态邻域拓扑结构：在搜索开始的时候，粒子的邻域只有其自己，即将个体最优解作为邻域最优解，然后随着迭代次数的增加，逐渐增大邻域，直至最后将群体中所有粒子作为自己的邻域成员。这样使初始迭代时可以有较好的探索性能，而在迭代后期可以有较好的开发性能。,四.PSO的改进与变形,37,四.PSO的改进与变形,38,学习因子c1和c2同步时变,四.PSO的改进与变形,39,学习因子c1和c2异步时变使两个学习因子在优化过程中随时间进行不同的变化，所以

17、我们这里称之为异步时变。这种设置的目的是在优化初期加强全局搜索，而在搜索后期促使粒子收敛于全局最优解。这种想法可以通过随着时间不断减小自我学习因子c1，和不断增大社会学习因子c2来实现。,四.PSO的改进与变形,40,学习因子c1和c2异步时变在优化的初始阶段，粒子具有较大的自我学习能力和较小的社会学习能力，这样粒子可以倾向于在整个搜索空间飞行，而不是很快就飞向群体最优解；在优化的后期，粒子具有较大的社会学习能力和较小的自我学习能力，使粒子倾向于飞向全局最优解。,四.PSO的改进与变形,41,四.PSO的改进与变形,42,收敛很快的算法解决约束优化问题时，如何处理飞出约束域的粒子是个关键较为适用于求解实优化问题,五.学习PSO的几点体会,