粒子群优化算法详细易懂.ppt

《粒子群优化算法详细易懂.ppt》由会员分享，可在线阅读，更多相关《粒子群优化算法详细易懂.ppt（49页珍藏版）》请在第壹文秘上搜索。

1、粒子群优化算法（PS0）Particle Swarm Optimization智能算法q 向大自然学习n 遗传算法遗传算法(GA)(GA)n 物竞天择，设计染色体编码，根据适应物竞天择，设计染色体编码，根据适应值函数进行染色体选择、交叉和变异操值函数进行染色体选择、交叉和变异操作，优化求解作，优化求解n 人工神经网络算法人工神经网络算法(ANN)(ANN)n 模仿生物神经元，透过神经元的信息传模仿生物神经元，透过神经元的信息传递、训练学习、联想，优化求解递、训练学习、联想，优化求解n 模拟退火算法模拟退火算法(SA)(SA)n 模模模仿金属物质退火过程模仿金属物质退火过程解决最优化问题解决最优

2、化问题的方法的方法n 传统搜索方法传统搜索方法n保证能找到最优解保证能找到最优解n Heuristic SearchHeuristic Searchn不能保证找到最优解不能保证找到最优解 由由KennedyKennedy和和EberhartEberhart于于19951995年提出年提出 群体迭代，粒子在解空间追随最优的粒子进行搜索群体迭代，粒子在解空间追随最优的粒子进行搜索.简单易行简单易行 粒子群算法粒子群算法:收敛速度快收敛速度快 设置参数少设置参数少 已成为现代优化方法领域研究的热点已成为现代优化方法领域研究的热点粒子群算法发展历史简介粒子群算法发展历史简介 粒子群粒子群算法的基本思想

3、算法的基本思想q 粒子群算法的思想源于对鸟群捕食行为的研究粒子群算法的思想源于对鸟群捕食行为的研究q 模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于体达到最优目的，是一种基于Swarm IntelligenceSwarm Intelligence的优化的优化方法方法。q 马良教授在他的著作马良教授在他的著作蚁群优化算法蚁群优化算法一书的前言中写到一书的前言中写到：q 大自然对我们的最大恩赐！大自然对我们的最大恩赐！“自然界的蚁群、鸟群、鱼群、自然界的蚁群、鸟群、鱼群、羊群、牛群、蜂群等，其实时时刻刻都在给予羊群、牛

4、群、蜂群等，其实时时刻刻都在给予我们以某种启示，只不过我们常常忽略了我们以某种启示，只不过我们常常忽略了大自然对我们的最大恩赐！大自然对我们的最大恩赐！.”.”粒子群粒子群算法的基本思想算法的基本思想 设想这样一个场景：设想这样一个场景：一群鸟在随机搜索食物一群鸟在随机搜索食物 在这块区域里只有一块食物在这块区域里只有一块食物;所有的鸟都不知道食物在哪里所有的鸟都不知道食物在哪里;但它们能感受到当前的位置离食物还有多远但它们能感受到当前的位置离食物还有多远.已知已知那么那么:找到食物的最优策略是什么呢？找到食物的最优策略是什么呢？搜寻目前离食物最近的鸟的周围区域搜寻目前离食物最近的鸟的周围区域

5、 根据自己飞行的经验判断食物的所在。根据自己飞行的经验判断食物的所在。PSO正是从这种模型中得到了启发正是从这种模型中得到了启发 PSO的基础的基础:信息的社会共享信息的社会共享 n生物学家对鸟生物学家对鸟(鱼鱼)群捕食的行为研究群捕食的行为研究n社会行为社会行为(Social-Only Model)n个体认知个体认知(Cognition-Only Model)算法介绍 q每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行搜索。q所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。q每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。

6、q每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。粒子群优化算法求最优解粒子群优化算法求最优解 D维空间中，有N个粒子；粒子i位置：x xi i=(xi1,xi2,xiD)，将xi代入适应函数f(xi)求适应值；粒子i速度：v vi i=(vi1,vi2,viD)粒子i个体经历过的最好位置：pbestpbesti i=(pi1,pi2,piD)种群所经历过的最好位置：gbestgbest=(g1,g2,gD)通常，在第d（1dD）维的位置变化范围限定在 内，速度变化范围限定在 内（即在迭代中若 超出了边界值，则该维的速度或位置被限制为该

7、维最大速度或边界 位置）min,max,X,ddX,max,-V,max ddVidvid、xq 粒子i的第d维速度更新公式：q 粒子i的第d维位置更新公式：第k次迭代粒子i飞行速度矢量的第d维分量 第k次迭代粒子i位置矢量的第d维分量 c1,c2加速度常数，调节学习最大步长 r1,r2两个随机函数，取值范围0，1，以增加搜索随机性 w 惯性权重，非负数，调节对解空间的搜索范围kk-111idid1 12 2v=wv()()kkididdidc r pbestxc r gbestx11kkkidididxxvkidvkidxq 粒子速度更新公式包含三部分：第一部分为粒子先前的速度 第二部分为“

8、认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。kk-111idid1 12 2v=wv()()kkididdidc r pbestxc r gbestx區域區域最佳解最佳解全域全域最佳解最佳解運動向量運動向量慣性向量慣性向量12X=X,X,.,Xiiiid12V=V,V,.,Viiiid12(1)()()()()()()()ididididgdidttttvw vc randpxcrandpx(1)()()iiitttxxvpg1111122V=V+C*r*(P

9、best-X)+C*r*(gbest-X)kkkkiiiii11X=X+Vkkkiii12NX=X,X,.,Xiiii12NV=V,V,.,Viiii算法流程1.Initial：初始化粒子群体（群体规模为n），包括随机位置和速度。2.Evaluation：根据fitness function，评价每个粒子的适应度。3.Find the Pbest：对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。4.Find the Gbest：对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较

10、，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。5.Update the Velocity：根据公式更新每个粒子的速度与位置。6.如未满足结束条件，则返回步骤2 通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。maxG粒子群优化算法流程图粒子群优化算法流程图 开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？粒子群粒子群算法的算法的构成要素构成要素 -群体大小群体大小 m m m 是一个整型参数是一个整型参数 m 很小很小:m 很大很大:当群体

11、数目增长至一定水平时，再增长将当群体数目增长至一定水平时，再增长将不再有显不再有显 但收敛速度慢但收敛速度慢著的作用著的作用陷入局优的可能性很大陷入局优的可能性很大 PSO的优化能力很好，的优化能力很好，粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1c2c失去对粒子本身失去对粒子本身的的速度的记忆速度的记忆 1社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 基本粒子群算法基本粒子群算法 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成：惯性因子惯性因子 kv0

12、kk-111idid1 12 2v=wv()()kkididdidc r pbestxc r gbestx11 1()kididc r pbestx12 2()kdidc r gbestx粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1c2c社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成：kvkk-111idid1 12 2v=wv()()kkididdidc r pbestxc r gbestx11 1()ki

13、didc r pbestx12 2()kdidc r gbestx学习因子学习因子 1c10c 无私型粒子群算法无私型粒子群算法“只有社会，没有自我只有社会，没有自我”迅速丧失群体多样性，迅速丧失群体多样性，易陷入局优而无法跳出易陷入局优而无法跳出粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1c2c社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由三部分组成：kvkk-111idid1 12 2v=wv()()kkididd

14、idc r pbestxc r gbestx11 1()kididc r pbestx12 2()kdidc r gbestx自我认知型粒子群算法自我认知型粒子群算法“只有自我，没有社会只有自我，没有社会”完全没有信息的社会共享，完全没有信息的社会共享，导致算法收敛速度缓慢导致算法收敛速度缓慢 学习因子学习因子 2c20c 粒子群粒子群算法的算法的构成要素构成要素-权重因子权重因子 权重因子：惯性因子权重因子：惯性因子 、学习因子、学习因子 1c2c社会经验部分社会经验部分 前次迭代中自身的速度前次迭代中自身的速度 自我认知部分自我认知部分 粒子的速度更新主要由三部分组成：粒子的速度更新主要由

15、三部分组成：kvkk-111idid1 12 2v=wv()()kkididdidc r pbestxc r gbestx11 1()kididc r pbestx12 2()kdidc r gbestxc c1 1,c,c2 2都不为都不为0 0，称为，称为完全型粒子群算法完全型粒子群算法 完全型粒子群算法更容易保持收敛速度和搜索效完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较好的选择果的均衡，是较好的选择 粒子群粒子群算法的算法的构成要素构成要素-最大速度最大速度 但但 在于维护算法的在于维护算法的探索能力探索能力与与开发能力开发能力的平衡的平衡 Vm较大时，探索能力增强，较大时

16、，探索能力增强，mV作用作用:Vm较小时，开发能力增强，较小时，开发能力增强，mVmVVm一般设为每维变量变化范围的一般设为每维变量变化范围的1020.但但 粒子容易飞过最优解粒子容易飞过最优解 容易陷入局部最优容易陷入局部最优 mV粒子群粒子群算法的算法的构成要素构成要素-邻域的拓扑结构邻域的拓扑结构 全局粒子群算法和局部粒子群算法全局粒子群算法和局部粒子群算法 gp粒子群算法的邻域拓扑结构包括两种，粒子群算法的邻域拓扑结构包括两种，一种是将群体内一种是将群体内所有个体所有个体都作为粒子的邻域，都作为粒子的邻域，另一种是只将群体中的另一种是只将群体中的部分个体部分个体作为粒子的邻域作为粒子的邻域 群体历史最优位置群体历史最优位置 邻域拓扑结构邻域拓扑结构决定决定 由此，将粒子群算法分为由此，将粒子群算法分为粒子群粒子群算法的算法的构成要素构成要素-邻域的拓扑结构邻域的拓扑结构 全局粒子群算法全局粒子群算法 1.1.粒子自己历史最优值粒子自己历史最优值 2.2.粒子群体的全局最优值粒子群体的全局最优值局部粒子群算法局部粒子群算法 1.1.粒子自己历史最优值粒子自己历史最优值 2.2.粒