粒子群优化学习.pptx

上传人:莉*** 文档编号:87418978 上传时间:2023-04-16 格式:PPTX 页数:69 大小:492.22KB
返回 下载 相关 举报
粒子群优化学习.pptx_第1页
第1页 / 共69页
粒子群优化学习.pptx_第2页
第2页 / 共69页
点击查看更多>>
资源描述

《粒子群优化学习.pptx》由会员分享,可在线阅读,更多相关《粒子群优化学习.pptx(69页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1第七章第七章 粒子群优化(粒子群优化(PSO)一一.PSO.PSO的产生的产生二二.PSO.PSO的基本思想的基本思想三三.基本基本PSOPSO四四.标准标准PSOPSO五五.计算举例计算举例六六.改进与变形改进与变形七七.学习学习PSOPSO的几点体会的几点体会第1页/共69页2Particle Swarm Optimization简称:PSO粒子群优化(微粒群优化)1995年,Kennedy&Eberhart 提出一一.PSO.PSO的产生(的产生(1 1)第2页/共69页3lParticle swarm optimization IEEE International Conferenc

2、e on Neural Networks,1995 lA new optimizer using particle swarm theory6th International Symposium on Micromachine and Human Science,1995l五年后,在国际上逐步被接受,并有大批不同领域的学者投入该算法相关研究,目前已经成为智能优化领域研究的热门 一一.PSO.PSO的产生(的产生(2 2)第3页/共69页4 2003年,控制与决策第二期刊登国内第一篇PSO论文综述文章一一.PSO.PSO的产生(的产生(3 3)第4页/共69页51.1.对社会行为的模拟2.从对“

3、bird flockbird flock”的模拟到PSOPSO算法的演化3.PSO3.PSO算法概述4.名称的由来:SwarmSwarm和ParticleParticle二二.PSO.PSO的基本思想(的基本思想(1 1)第5页/共69页61.对社会行为的模拟:(1 1)对鸟群行为的模拟 ReynoldsReynolds和HeppnerHeppner,GrenanderGrenander在19871987年和19901990年发表的论文中都关注了鸟群群体行动中的蕴涵的美学二二.PSO.PSO的基本思想(的基本思想(2 2)第6页/共69页7l他们发现,由数目庞大的个体组成的鸟群飞行中可以改变方

4、向,散开,或者队形的重组等等,那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了个体间距的处理,也就是让鸟群中的个体之间保持最优的距离。二二.PSO.PSO的基本思想(的基本思想(3 3)第7页/共69页81.对社会行为的模拟:(2 2)对鱼群行为的研究 19751975年,生物社会学家E.O.WilsonE.O.Wilson在论文中阐述了对鱼群的研究二二.PSO.PSO的基本思想(的基本思想(4 4)第8页/共69页9l他在论文中提出:“至少在理论上,鱼群的个体成员能够受益于群体中其他

5、个体在寻找食物的过程中发现的和以前的经验,这种受益是明显的,它超过了个体之间的竞争所带来的利益消耗,不管任何时候食物资源不可预知的分散于四处。”这说明,同种生物之间信息的社会共享能够带来好处。这是PSOPSO的基础。二二.PSO.PSO的基本思想(的基本思想(5 5)第9页/共69页101.对社会行为的模拟:(3 3)对人类的社会行为的模拟 与前者不同,最大区别在于抽象性!l鸟类和鱼类是调节他们的物理运动,来避免天敌,寻找食物,优化环境的参数,比如温度等。人类调节的不仅是物理运动,还包括认知和经验变量。我们更多的是调节自己的信仰和态度,来和社会中的上流人物或者专家,或者说在某件事情上获得最优解

6、的人保持一致。二二.PSO.PSO的基本思想(的基本思想(6 6)第10页/共69页111.对社会行为的模拟:l这种不同导致了计算机仿真上的差别,至少有一个明显的因素:碰撞(collisioncollision)l两个个体即使不被绑在一块,也具有相同的态度和信仰,但是两只鸟是绝对不可能不碰撞而在空间中占据相同的位置。这是因为动物只能在三维的物理空间中运动,而人类还在抽象的多维心理空间运动,这里是碰撞自由的(collision-collision-freefree)。二二.PSO.PSO的基本思想(的基本思想(7 7)第11页/共69页122.2.从对“bird flockbird flock”

7、的模拟到PSOPSO算法的演化 (1 1)速度匹配和“CrazinessCraziness”l鸟群首先在在二维空间中进行位置的初始化,每个个体具有X X和Y Y两个速度,对邻居间速度的匹配导致鸟群的行动完全一致,方向也不变化,显然小鸟不会这么听话,于是加入了CrazinessCraziness变量,对坐标增加一些随机的成分。二二.PSO.PSO的基本思想(的基本思想(8 8)第12页/共69页132.2.从对“bird flockbird flock”的模拟到PSOPSO算法的演化 (2 2)麦田向量的引入l鸟群最终会飞到麦田中。鸟群开始就知道麦田在哪。用离麦田有多远来评价小鸟飞到的地方好不好

8、。在飞行的过程中,通过与自己找到的最好点和群体找到的最好点进行比较,来调整自己的速度。二二.PSO.PSO的基本思想(的基本思想(9 9)第13页/共69页142.2.从对“bird flockbird flock”的模拟到PSOPSO算法的演化 lKennedy和Eberhart对Hepper的模仿鸟群的模型进行了修正,以使粒子能够飞向解空间,并在最好解处降落,从而得到了粒子群优化算法。二二.PSO.PSO的基本思想(的基本思想(1010)第14页/共69页153.3.PSO算法概述l一个由多个个体(ParticleParticle)组成的群体(SwarmSwarm)对多维搜索空间进行搜索,

9、每个个体在搜索时,考虑到了自己搜索到的历史最好点和群体内(或邻域内)其他个体的历史最好点,在此基础上进行位置(状态,也就是解)的变化二二.PSO.PSO的基本思想(的基本思想(1111)第15页/共69页163.3.PSO算法概述l这里,多维搜索空间是对人类多维的心理空间的模仿,个体在搜索时考虑自己的历史最好点,这是个体经验的积累,同时考虑到群体内其他个体的历史最好点,这是社会信息的共享作用和个体本身具有学习能力的表现。二二.PSO.PSO的基本思想(的基本思想(1212)第16页/共69页174.4.名称的由来:SwarmSwarm和ParticleParticlelSwarmSwarm:在

10、美国传统字典中有三个意思(1 1)一大群尤指正在行进中的一大群昆虫或其它细小生物。(2 2)蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂。(3 3)一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物。二二.PSO.PSO的基本思想(的基本思想(1313)第17页/共69页184.4.名称的由来:SwarmSwarm和ParticleParticlel作者引用此词是借用了MillonasMillonas在19941994年的论文中的人工生命的一个应用模型中的提法。lMillonasMillonas明确提出SwarmSwarm智能(swarm intelligenceswarm intelli

11、gence)的五点原则 在算法的研究中当深思二二.PSO.PSO的基本思想(的基本思想(1414)第18页/共69页19(1)the proximity principle 群体能够执行简单的时间和空间的计算(2)the quality principle 群体能够响应环境的特征要素(3)the principle of diverse response 群体能够使自己的行动不被限制在一个狭小的范围内 (4)the principle of stability 群体不要每次环境变化都跟着改变自己的行为模式(5)the principle of adaptability 群体的行为模式要能够在值

12、得计算代价的时候发生改变二二.PSO.PSO的基本思想(的基本思想(1515)第19页/共69页204.4.名称的由来:SwarmSwarm和ParticleParticleParticle:Particle:l算法中有速度和加速度的字眼,这比较适合于粒子。ReevesReeves在19831983年的论文中讨论了粒子系统包括基本粒子团和云,火,烟雾等弥漫性物体。l作者的想法是让粒子尽量具有一种普遍性的意义l用粒子在超空间(HyperspaceHyperspace)的飞行来模拟人类的社会性行为二二.PSO.PSO的基本思想(的基本思想(1616)第20页/共69页211.算法描述及简要分析2.

13、基本PSO公式3.基本PSO步骤三三.基本基本PSOPSO(1 1)第21页/共69页221.算法描述及简要分析l一个由m个粒子(Particle)组成的群体(Swarm)在D维搜索空间中以一定的速度飞行,每个粒子在搜索时,考虑到了自己搜索到的历史最好点和群体内(或邻域内)其他粒子的历史最好点,在此基础上进行位置(状态,也就是解)的变化。三三.基本基本PSOPSO(2 2)第22页/共69页23l描述中与GAGA相类似的问题:(1 1)种群的规定与初始化:SwarmSwarm具有大小,随机初始化 (2 2)点的好坏如何判断:通过适值函数 (3 3)停止准则l还要解决的问题:(1 1)个体本身所

14、找到的历史最好点如何进行考虑,也就是让这个点如何影响下一次迭代?(2 2)对群体内或者邻域内成员所找到的历史最好点如何进行考虑?(3 3)粒子的位置如何进行变化?三三.基本基本PSOPSO(3 3)第23页/共69页24三三.基本基本PSOPSO(4 4)2.基本PSO公式第24页/共69页25三三.基本基本PSOPSO(5 5)2.基本PSO公式第25页/共69页262.基本PSO公式l c1和c2:学习因子(learning factor)或加速系数(acceleration coefficient),一般为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最

15、优点以及群体内或邻域内的历史最优点靠近。通常等于2。三三.基本基本PSOPSO(6 6)第26页/共69页272.基本PSO公式l 粒子的速度被限制在一个最大速度Vmax的范围内。引入Vmax的原因:a、防止计算机溢出b、对人类学习和观念转变的模拟c、它还决定了空间搜索的粒子性三三.基本基本PSOPSO(7 7)第27页/共69页282.基本PSO公式l当把群体内所有粒子都作为邻域成员时,得到粒子群优化算法的全局版本;当群体内部分成员组成邻域时得到粒子群优化算法的局部版本。l局部版本中,一般有两种方式组成邻域,一种是索引号相临的粒子组成邻域,另一种是位置相临的粒子组成邻域。粒子群优化算法的邻域

16、定义策略又可以称为粒子群的邻域拓扑结构。三三.基本基本PSOPSO(8 8)第28页/共69页29三三.基本基本PSOPSO(9 9)3.基本PSO步骤第29页/共69页30三三.基本基本PSOPSO(1010)3.基本PSO步骤第30页/共69页311.标准PSO公式2.算法构成要素四四.标准标准PSOPSO(1 1)第31页/共69页321.标准PSO公式 为改善算法收敛性能,Shi和Eberhart在1998年的论文中引入了惯性权重的概念,将速度更新方程修改为(7.3)所示:四四.标准标准PSOPSO(2 2)第32页/共69页33l这里,称为惯性权重,其大小决定了对粒子当前速度继承的多

17、少,合适的选择可以使粒子具有均衡的探索和开发能力。可见,基本PSO算法是惯性权重的特殊情况。l分析和实验表明,设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用Vmax进行初始化,将Vmax设定为每维变量的变化范围,而不必进行细致的选择与调节。四四.标准标准PSOPSO(3 3)第33页/共69页34l目前,对于PSO算法的研究大多以带有惯性权重的PSO为对象进行分析、扩展和修正,因此大多数文献中将带有惯性权重的PSO算法称为PSO算法的标准版本,或者称为标准PSO算法;而将前述PSO算法称为初始PSO算法/基本PSO算法,或者称为PSO算法的初始版本。四四.标准标准PSO

18、PSO(4 4)第34页/共69页352.算法构成要素l群体大小:m m是个整型参数。当m很小的时候,陷入局优的可能性很大。然而,群体过大将导致计算时间的大幅增加。并且当群体数目增长至一定水平时,再增长将不再有显著的作用。当m=1的时候,PSO算法变为基于个体搜索的技术,一旦陷入局优,将不可能跳出。当m很大时,PSO的优化能力很好,可是收敛的速度将非常慢。四四.标准标准PSOPSO(5 5)第35页/共69页362.算法构成要素l学习因子:c1和c2 学习因子使粒子具有自我总结和向群体中优秀个体学习的能力,从而向群体内或邻域内最优点靠近。c1和c2通常等于2,不过在文献中也有其他的取值。但是一

19、般c1等于c2,并且范围在0和4之间。四四.标准标准PSOPSO(6 6)第36页/共69页372.算法构成要素l最大速度:Vmax 四四.标准标准PSOPSO(7 7)第37页/共69页382.算法构成要素l惯性权重 智能优化方法的运行是否成功,探索能力和开发能力的平衡是非常关键的。对于粒子群优化算法来说,这两种能力的平衡就是靠惯性权重来实现。四四.标准标准PSOPSO(8 8)第38页/共69页392.算法构成要素l邻域拓扑结构 全局版本粒子群优化算法将整个群体作为粒子的邻域,速度快,不过有时会陷入局部最优;局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒子的邻域,收敛速度慢一点

20、,不过很难陷入局部最优。显然,全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个特例,即将整个群体都作为邻域。四四.标准标准PSOPSO(9 9)第39页/共69页402.算法构成要素l停止准则 一般使用最大迭代次数或可以接受的满意解作为停止准则 四四.标准标准PSOPSO(1010)第40页/共69页412.算法构成要素l粒子空间的初始化 较好地选择粒子的初始化空间,将大大缩短收敛时间。这是问题依赖的。重要的参数:惯性权重和邻域定义四四.标准标准PSOPSO(1111)第41页/共69页42五五.计算举例(计算举例(1 1)求解以下的无约束优化问题(Rosenbrock函数)其中,

21、问题的维数n=5。第42页/共69页43五五.计算举例(计算举例(2 2)简单分析:Rosenbrock是一个著名的测试函数,也叫香蕉函数,其特点是该函数虽然是单峰函数,在100,100n上只有一个全局极小点,但它在全局极小点临近的狭长区域内取值变化极为缓慢,常用于评价算法的搜索性能。这种实优化问题非常适合于使用粒子群优化算法来求解。这里使用标准版本的算法来求解,算法的相关设计分析如下:第43页/共69页44五五.计算举例(计算举例(3 3)编码:因为问题的维数为5,所以每个粒子为5维的实数向量。初始化范围:根据问题要求,设定为-30,30。根据前面的参数分析,我们知道,可以将最大速度设定为V

22、max=60。种群大小:为了说明方便,这里采用一个较小的种群规模,m=5。停止准则:设定为最大迭代次数100次。惯性权重:采用固定权重0.5。邻域拓扑结构:使用星形拓扑结构,即全局版本的粒子群优化算法。第44页/共69页45一次迭代后的结果:五五.计算举例(计算举例(4 4)第45页/共69页46l从上面的数据我们可以看到,粒子有的分量跑出了初始化范围。需要说明的是,在这种情况下,我们一般不强行将粒子重新拉回到初始化空间,即使初始化空间也是粒子的约束空间。因为,即使粒子跑出初始化空间,随着迭代的进行,如果在初始化空间内有更好的解存在,那么粒子也可以自行返回到初始化空间。l有研究表明,即使将初始

23、化空间不设定为问题的约束空间,即问题的最优解不在初始化空间内,粒子也可能找到最优解。五五.计算举例(计算举例(5 5)第46页/共69页47五五.计算举例(计算举例(6 6)第47页/共69页481.惯性权重2.邻域拓扑结构3.学习因子4.带有收缩因子的PSO六六.改进与变形(改进与变形(1 1)第48页/共69页491.惯性权重l固定权重 即赋予惯性权重以一个常数值,一般来说,该值在0和1之间。固定的惯性权重使粒子在飞行中始终具有相同的探索和开发能力。显然,对于不同的问题,获得最好优化效果的这个常数是不同的,要找到这个值需要大量的实验。通过实验我们发现:种群规模越小,需要的惯性权重越大,因为

24、此时种群需要更好的探索能力来弥补粒子数量的不足,否则粒子极易收敛;种群规模越大,需要的惯性权重越小,因为每个粒子可以更专注于搜索自己附近的区域。六六.改进与变形(改进与变形(2 2)第49页/共69页50l时变权重 一般来说,希望粒子群在飞行开始的时候具有较好的探索能力,而随着迭代次数的增加,特别是在飞行的后期,希望具有较好的开发能力。所以希望动态调节惯性权重。可以通过时变权重的设置来实现。设惯性权重的取值范围为:最大迭代次数为Iter_max,则第i次迭代时的惯性权重可以取为:六六.改进与变形(改进与变形(3 3)第50页/共69页51l模糊权重 模糊权重是使用模糊系统来动态调节惯性权重。下

25、面的文献给出了一种模糊权重的设置方式 Shi Y,Eberhart R.Fuzzy adaptive particle swarm optimization:IEEE Int.Congress on Evolutionary Computation C.Piscataway,NJ:IEEE Service Center,2001:101-106.六六.改进与变形(改进与变形(4 4)第51页/共69页52l随机权重 随机权重是在一定范围内随机取值。例如可以取值如下:其中,Random为0到1之间的随机数。这样,惯性权重将在0.5到1之间随机变化,均值为0.75。之所以这样设定,是为了应用于动态

26、优化问题。六六.改进与变形(改进与变形(5 5)第52页/共69页532.邻域拓扑结构l基于索引号的拓扑结构(1)环形结构六六.改进与变形(改进与变形(6 6)第53页/共69页54l基于索引号的拓扑结构(2)带有捷径的环形结构六六.改进与变形(改进与变形(7 7)第54页/共69页55l基于索引号的拓扑结构(3)轮形结构六六.改进与变形(改进与变形(8 8)第55页/共69页56l基于索引号的拓扑结构(4)带有捷径的轮形结构六六.改进与变形(改进与变形(9 9)第56页/共69页57l基于索引号的拓扑结构(5)星形结构 每个粒子都与种群中的其他所有粒子相连,即将整个种群作为自己的邻域。也就是

27、粒子群算法的全局版本。这种结构下,所有粒子共享的信息是种群中表现最好的粒子的信息。六六.改进与变形(改进与变形(1010)第57页/共69页58l基于索引号的拓扑结构(6)随机结构 随机结构是在N个粒子的种群中间,随机地建立N个对称的两两连接。六六.改进与变形(改进与变形(1111)第58页/共69页59l基于距离的拓扑结构 基于距离的拓扑结构是在每次迭代时,计算一个粒子与种群中其他粒子之间的距离,然后根据这些距离来确定该粒子的邻域构成。下面是一个具体的实现方法:动态邻域拓扑结构。六六.改进与变形(改进与变形(1212)第59页/共69页60l基于距离的拓扑结构 在搜索开始的时候,粒子的邻域只

28、有其自己,即将个体最优解作为邻域最优解,然后随着迭代次数的增加,逐渐增大邻域,直至最后将群体中所有粒子作为自己的邻域成员。这样使初始迭代时可以有较好的探索性能,而在迭代后期可以有较好的开发性能。六六.改进与变形(改进与变形(1313)第60页/共69页61六六.改进与变形(改进与变形(1414)第61页/共69页62六六.改进与变形(改进与变形(1515)3.学习因子lc1和c2同步时变第62页/共69页633.学习因子lc1和c2异步时变使两个学习因子在优化过程中随时间进行不同的变化,所以我们这里称之为异步时变。这种设置的目的是在优化初期加强全局搜索,而在搜索后期促使粒子收敛于全局最优解。这

29、种想法可以通过随着时间不断减小自我学习因子c1,和不断增大社会学习因子c2来实现。即:(1)在优化的初始阶段,粒子具有较大的自我学习能力和较小的社会学习能力,这样粒子可以倾向于在整个搜索空间飞行,而不是很快就飞向群体最优解;(2)在优化的后期,粒子具有较大的社会学习能力和较小的自我学习能力,使粒子倾向于飞向全局最优解。六六.改进与变形(改进与变形(1616)第63页/共69页64六六.改进与变形(改进与变形(1717)第64页/共69页654.带有收缩因子的PSOl基本粒子群优化算法有两种重要的改进版本:加入惯性权重和加入收缩因子(constriction factor)。惯性权重的版本已成为标准版本,所以放在算法的基本原理中介绍,收缩因子版本放在本节介绍。lClerc在原始粒子群优化算法中引入可收缩因子的概念,并指出该因子对于算法的收敛是必要的 六六.改进与变形(改进与变形(1818)第65页/共69页664.带有收缩因子的PSO六六.改进与变形(改进与变形(1919)第66页/共69页67六六.改进与变形(改进与变形(2020)第67页/共69页681.收敛很快的算法2.解决约束优化问题时,如何处理飞出约束域的粒子是个关键3.目前还没有较好的解决离散问题的方案七七.学习学习PSOPSO的几点体会的几点体会第68页/共69页69感谢您的观看!第69页/共69页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > PPT文档

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁