第7章 粒子群优化PPT学习课件.ppt

1 第七章粒子群优化 2 第七章粒子群优化 PSO 一 PSO的产生二 PSO的基本思想三 基本PSO四 标准PSO五 计算举例六 改进与变形七 学习PSO的几点体会 3 ParticleSwarmOptimization简称 PSO粒子群优化 微粒群优化 1995年 Kennedy Eberhart提出 一 PSO的产生 1 4 Particleswarmoptimization IEEEInternationalConferenceonNeuralNetworks 1995Anewoptimizerusingparticleswarmtheory 6thInternationalSymposiumonMicromachineandHumanScience 1995五年后 在国际上逐步被接受 并有大批不同领域的学者投入该算法相关研究 目前已经成为智能优化领域研究的热门 一 PSO的产生 2 5 2003年 控制与决策 第二期刊登国内第一篇PSO论文 综述文章 一 PSO的产生 3 6 1 对社会行为的模拟2 从对 birdflock 的模拟到PSO算法的演化3 PSO算法概述4 名称的由来 Swarm和Particle 二 PSO的基本思想 1 7 1 对社会行为的模拟 1 对鸟群行为的模拟Reynolds和Heppner Grenander在1987年和1990年发表的论文中都关注了鸟群群体行动中的蕴涵的美学 二 PSO的基本思想 2 8 他们发现 由数目庞大的个体组成的鸟群飞行中可以改变方向 散开 或者队形的重组等等 那么一定有某种潜在的能力或者规则保证了这些同步的行为 这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学 在这些早期的模型中他们把重点都放在了个体间距的处理 也就是让鸟群中的个体之间保持最优的距离 二 PSO的基本思想 3 9 1 对社会行为的模拟 2 对鱼群行为的研究1975年 生物社会学家E O Wilson在论文中阐述了对鱼群的研究 二 PSO的基本思想 4 10 他在论文中提出 至少在理论上 鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中发现的和以前的经验 这种受益是明显的 它超过了个体之间的竞争所带来的利益消耗 不管任何时候食物资源不可预知的分散于四处 这说明 同种生物之间信息的社会共享能够带来好处 这是PSO的基础 二 PSO的基本思想 5 11 1 对社会行为的模拟 3 对人类的社会行为的模拟与前者不同 最大区别在于抽象性 鸟类和鱼类是调节他们的物理运动 来避免天敌 寻找食物 优化环境的参数 比如温度等 人类调节的不仅是物理运动 还包括认知和经验变量 我们更多的是调节自己的信仰和态度 来和社会中的上流人物或者专家 或者说在某件事情上获得最优解的人保持一致 二 PSO的基本思想 6 12 1 对社会行为的模拟 这种不同导致了计算机仿真上的差别 至少有一个明显的因素 碰撞 collision 两个个体即使不被绑在一块 也具有相同的态度和信仰 但是两只鸟是绝对不可能不碰撞而在空间中占据相同的位置 这是因为动物只能在三维的物理空间中运动 而人类还在抽象的多维心理空间运动 这里是碰撞自由的 collision free 二 PSO的基本思想 7 13 2 从对 birdflock 的模拟到PSO算法的演化 1 速度匹配和 Craziness 鸟群首先在在二维空间中进行位置的初始化 每个个体具有X和Y两个速度 对邻居间速度的匹配导致鸟群的行动完全一致 方向也不变化 显然小鸟不会这么听话 于是加入了Craziness变量 对坐标增加一些随机的成分 二 PSO的基本思想 8 14 2 从对 birdflock 的模拟到PSO算法的演化 2 麦田向量的引入鸟群最终会飞到麦田中 鸟群开始就知道麦田在哪 用离麦田有多远来评价小鸟飞到的地方好不好 在飞行的过程中 通过与自己找到的最好点和群体找到的最好点进行比较 来调整自己的速度 二 PSO的基本思想 9 15 2 从对 birdflock 的模拟到PSO算法的演化Kennedy和Eberhart对Hepper的模仿鸟群的模型进行了修正 以使粒子能够飞向解空间 并在最好解处降落 从而得到了粒子群优化算法 二 PSO的基本思想 10 16 3 PSO算法概述一个由多个个体 Particle 组成的群体 Swarm 对多维搜索空间进行搜索 每个个体在搜索时 考虑到了自己搜索到的历史最好点和群体内 或邻域内 其他个体的历史最好点 在此基础上进行位置 状态 也就是解 的变化 二 PSO的基本思想 11 17 3 PSO算法概述这里 多维搜索空间是对人类多维的心理空间的模仿 个体在搜索时考虑自己的历史最好点 这是个体经验的积累 同时考虑到群体内其他个体的历史最好点 这是社会信息的共享作用和个体本身具有学习能力的表现 二 PSO的基本思想 12 18 4 名称的由来 Swarm和ParticleSwarm 在美国传统字典中有三个意思 1 一大群尤指正在行进中的一大群昆虫或其它细小生物 2 蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂 3 一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物 二 PSO的基本思想 13 19 4 名称的由来 Swarm和Particle作者引用此词是借用了Millonas在1994年的论文中的人工生命的一个应用模型中的提法 Millonas明确提出Swarm智能 swarmintelligence 的五点原则 在算法的研究中当深思 二 PSO的基本思想 14 20 1 theproximityprinciple群体能够执行简单的时间和空间的计算 2 thequalityprinciple群体能够响应环境的特征要素 3 theprincipleofdiverseresponse群体能够使自己的行动不被限制在一个狭小的范围内 4 theprincipleofstability群体不要每次环境变化都跟着改变自己的行为模式 5 theprincipleofadaptability群体的行为模式要能够在值得计算代价的时候发生改变 二 PSO的基本思想 15 21 4 名称的由来 Swarm和ParticleParticle 算法中有速度和加速度的字眼 这比较适合于粒子 Reeves在1983年的论文中讨论了粒子系统包括基本粒子团和云 火 烟雾等弥漫性物体 作者的想法是让粒子尽量具有一种普遍性的意义用粒子在超空间 Hyperspace 的飞行来模拟人类的社会性行为 二 PSO的基本思想 16 22 算法描述及简要分析基本PSO公式基本PSO步骤 三 基本PSO 1 23 算法描述及简要分析一个由m个粒子 Particle 组成的群体 Swarm 在D维搜索空间中以一定的速度飞行 每个粒子在搜索时 考虑到了自己搜索到的历史最好点和群体内 或邻域内 其他粒子的历史最好点 在此基础上进行位置 状态 也就是解 的变化 三 基本PSO 2 24 描述中与GA相类似的问题 1 种群的规定与初始化 Swarm具有大小 随机初始化 2 点的好坏如何判断 通过适值函数 3 停止准则还要解决的问题 1 个体本身所找到的历史最好点如何进行考虑 也就是让这个点如何影响下一次迭代 2 对群体内或者邻域内成员所找到的历史最好点如何进行考虑 3 粒子的位置如何进行变化 三 基本PSO 3 25 三 基本PSO 4 2 基本PSO公式 26 三 基本PSO 5 2 基本PSO公式 27 2 基本PSO公式c1和c2 学习因子 learningfactor 或加速系数 accelerationcoefficient 一般为正常数 学习因子使粒子具有自我总结和向群体中优秀个体学习的能力 从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近 通常等于2 三 基本PSO 6 28 2 基本PSO公式粒子的速度被限制在一个最大速度Vmax的范围内 引入Vmax的原因 a 防止计算机溢出b 对人类学习和观念转变的模拟c 它还决定了空间搜索的粒子性 三 基本PSO 7 29 2 基本PSO公式当把群体内所有粒子都作为邻域成员时 得到粒子群优化算法的全局版本 当群体内部分成员组成邻域时得到粒子群优化算法的局部版本 局部版本中 一般有两种方式组成邻域 一种是索引号相临的粒子组成邻域 另一种是位置相临的粒子组成邻域 粒子群优化算法的邻域定义策略又可以称为粒子群的邻域拓扑结构 三 基本PSO 8 30 三 基本PSO 9 3 基本PSO步骤 31 三 基本PSO 10 3 基本PSO步骤 32 1 标准PSO公式2 算法构成要素 四 标准PSO 1 33 1 标准PSO公式为改善算法收敛性能 Shi和Eberhart在1998年的论文中引入了惯性权重的概念 将速度更新方程修改为 7 3 所示 四 标准PSO 2 34 这里 称为惯性权重 其大小决定了对粒子当前速度继承的多少 合适的选择可以使粒子具有均衡的探索和开发能力 可见 基本PSO算法是惯性权重的特殊情况 分析和实验表明 设定Vmax的作用可以通过惯性权重的调整来实现 现在的PSO基本上使用Vmax进行初始化 将Vmax设定为每维变量的变化范围 而不必进行细致的选择与调节 四 标准PSO 3 35 目前 对于PSO算法的研究大多以带有惯性权重的PSO为对象进行分析 扩展和修正 因此大多数文献中将带有惯性权重的PSO算法称为PSO算法的标准版本 或者称为标准PSO算法 而将前述PSO算法称为初始PSO算法 基本PSO算法 或者称为PSO算法的初始版本 四 标准PSO 4 36 2 算法构成要素群体大小 mm是个整型参数 当m很小的时候 陷入局优的可能性很大 然而 群体过大将导致计算时间的大幅增加 并且当群体数目增长至一定水平时 再增长将不再有显著的作用 当m 1的时候 PSO算法变为基于个体搜索的技术 一旦陷入局优 将不可能跳出 当m很大时 PSO的优化能力很好 可是收敛的速度将非常慢 四 标准PSO 5 37 2 算法构成要素学习因子 c1和c2学习因子使粒子具有自我总结和向群体中优秀个体学习的能力 从而向群体内或邻域内最优点靠近 c1和c2通常等于2 不过在文献中也有其他的取值 但是一般c1等于c2 并且范围在0和4之间 四 标准PSO 6 38 2 算法构成要素最大速度 Vmax 四 标准PSO 7 39 2 算法构成要素惯性权重智能优化方法的运行是否成功 探索能力和开发能力的平衡是非常关键的 对于粒子群优化算法来说 这两种能力的平衡就是靠惯性权重来实现 四 标准PSO 8 40 2 算法构成要素邻域拓扑结构全局版本粒子群优化算法将整个群体作为粒子的邻域 速度快 不过有时会陷入局部最优 局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒子的邻域 收敛速度慢一点 不过很难陷入局部最优 显然 全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个特例 即将整个群体都作为邻域 四 标准PSO 9 41 2 算法构成要素停止准则一般使用最大迭代次数或可以接受的满意解作为停止准则 四 标准PSO 10 42 2 算法构成要素粒子空间的初始化较好地选择粒子的初始化空间 将大大缩短收敛时间 这是问题依赖的 重要的参数 惯性权重和邻域定义 四 标准PSO 11 43 五 计算举例 1 求解以下的无约束优化问题 Rosenbrock函数 其中 问题的维数n 5 44 五 计算举例 2 简单分析 Rosenbrock是一个著名的测试函数 也叫香蕉函数 其特点是该函数虽然是单峰函数 在 100 100 n上只有一个全局极小点 但它在全局极小点临近的狭长区域内取值变化极为缓慢 常用于评价算法的搜索性能 这种实优化问题非常适合于使用粒子群优化算法来求解 这里使用标准版本的算法来求解 算法的相关设计分析如下 45 五 计算举例 3 编码 因为问题的维数为5 所以每个粒子为5维的实数向量 初始化范围 根据问题要求 设定为 30 30 根据前面的参数分析 我们知道 可以将最大速度设定为Vmax 60 种群大小 为了说明方便 这里采用一个较小的种群规模 m 5 停止准则 设定为最大迭代次数100次 惯性权重 采用固定权重0 5 邻域拓扑结构 使用星形拓扑结构 即全局版本的粒子群优化算法 46 一次迭代后的结果 五 计算举例 4 47 从上面的数据我们可以看到 粒子有的分量跑出了初始化范围 需要说明的是 在这种情况下 我们一般不强行将粒子重新拉回到初始化空间 即使初始化空间也是粒子的约束空间 因为 即使粒子跑出初始化空间 随着迭代的进行 如果在初始化空间内有更好的解存在 那么粒子也可以自行返回到初始化空间 有研究表明 即使将初始化空间不设定为问题的约束空间 即问题的最优解不在初始化空间内 粒子也可能找到最优解 五 计算举例 5 48 五 计算举例 6 49 1 惯性权重2 邻域拓扑结构3 学习因子4 带有收缩因子的PSO 六 改进与变形 1 50 1 惯性权重固定权重即赋予惯性权重以一个常数值 一般来说 该值在0和1之间 固定的惯性权重使粒子在飞行中始终具有相同的探索和开发能力 显然 对于不同的问题 获得最好优化效果的这个常数是不同的 要找到这个值需要大量的实验 通过实验我们发现 种群规模越小 需要的惯性权重越大 因为此时种群需要更好的探索能力来弥补粒子数量的不足 否则粒子极易收敛 种群规模越大 需要的惯性权重越小 因为每个粒子可以更专注于搜索自己附近的区域 六 改进与变形 2 51 时变权重一般来说 希望粒子群在飞行开始的时候具有较好的探索能力 而随着迭代次数的增加 特别是在飞行的后期 希望具有较好的开发能力 所以希望动态调节惯性权重 可以通过时变权重的设置来实现 设惯性权重的取值范围为 最大迭代次数为Iter max 则第i次迭代时的惯性权重可以取为 六 改进与变形 3 52 模糊权重模糊权重是使用模糊系统来动态调节惯性权重 下面的文献给出了一种模糊权重的设置方式ShiY EberhartR Fuzzyadaptiveparticleswarmoptimization IEEEInt CongressonEvolutionaryComputation C Piscataway NJ IEEEServiceCenter 2001 101 106 六 改进与变形 4 53 随机权重随机权重是在一定范围内随机取值 例如可以取值如下 其中 Random为0到1之间的随机数 这样 惯性权重将在0 5到1之间随机变化 均值为0 75 之所以这样设定 是为了应用于动态优化问题 六 改进与变形 5 54 2 邻域拓扑结构基于索引号的拓扑结构 1 环形结构 六 改进与变形 6 55 基于索引号的拓扑结构 2 带有捷径的环形结构 六 改进与变形 7 56 基于索引号的拓扑结构 3 轮形结构 六 改进与变形 8 57 基于索引号的拓扑结构 4 带有捷径的轮形结构 六 改进与变形 9 58 基于索引号的拓扑结构 5 星形结构每个粒子都与种群中的其他所有粒子相连 即将整个种群作为自己的邻域 也就是粒子群算法的全局版本 这种结构下 所有粒子共享的信息是种群中表现最好的粒子的信息 六 改进与变形 10 59 基于索引号的拓扑结构 6 随机结构随机结构是在N个粒子的种群中间 随机地建立N个对称的两两连接 六 改进与变形 11 60 基于距离的拓扑结构基于距离的拓扑结构是在每次迭代时 计算一个粒子与种群中其他粒子之间的距离 然后根据这些距离来确定该粒子的邻域构成 下面是一个具体的实现方法 动态邻域拓扑结构 六 改进与变形 12 61 基于距离的