粒子群优化算法课件.ppt

《粒子群优化算法课件.ppt》由会员分享，可在线阅读，更多相关《粒子群优化算法课件.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于粒子群关于粒子群优化算法化算法现在学习的是第1页，共35页2Contents算法简介算法简介 1 1基本流程基本流程 2 2改进研究改进研究 3 3相关应用相关应用 4 4参数设置参数设置 5 5现在学习的是第2页，共35页36.1 粒子群优化算法简介粒子群优化算法简介粒子群优化算法是什么？粒子群优化算法是什么？粒子群优化算法粒子群优化算法（Particle Swarm Optimization，PSO）是进化计算的一个分支，是进化计算的一个分支，是一种模拟自然界的生物活动的随机搜索算法。是一种模拟自然界的生物活动的随机搜索算法。粒子群优化算法的思想来源是怎样的？粒子群优化算法的思想来源是

2、怎样的？它由谁提出的？它由谁提出的？PSO模拟了自然界鸟群捕食和鱼群捕食的过程。模拟了自然界鸟群捕食和鱼群捕食的过程。通过群体中的协作寻找到问题的全局最优解。通过群体中的协作寻找到问题的全局最优解。它是它是1995年由美国学者年由美国学者Eberhart和和Kennedy提出的，提出的，现在已经广泛应用于各种工程领域的优化问题之中。现在已经广泛应用于各种工程领域的优化问题之中。现在学习的是第3页，共35页46.1.1 思想来源思想来源生物界现象生物界现象群体行为群体行为群体迁徙群体迁徙生物觅食生物觅食社会心理学社会心理学群体智慧群体智慧个体认知个体认知社会影响社会影响粒子群粒子群优化算法优化算

3、法 人工生命人工生命鸟群觅食鸟群觅食鱼群学习鱼群学习群理论群理论现在学习的是第4页，共35页56.1.2 基本基本原理原理鸟群觅食现象鸟群觅食现象鸟群鸟群觅食空间觅食空间飞行速度飞行速度所在位置所在位置个体认知与群体协个体认知与群体协作作找到食物找到食物粒子群优化算法粒子群优化算法搜索空间的一组有效搜索空间的一组有效解解问题的搜索空间问题的搜索空间解的速度向量解的速度向量解的位置向量解的位置向量速度与位置的更新速度与位置的更新找到全局最优解找到全局最优解鸟群觅食现象鸟群觅食现象粒子群优化算法粒子群优化算法类比关系类比关系现在学习的是第5页，共35页66.1.2 基本基本原理原理鸟群觅食现象鸟群

4、觅食现象鸟群觅食现象鸟群觅食现象粒子群优化算法粒子群优化算法粒子群优化算法粒子群优化算法现在学习的是第6页，共35页76.2 粒子群优化算法的基本流程粒子群优化算法的基本流程基本流程基本流程l速度与位置更新公式速度与位置更新公式l速度与位置更新示意图速度与位置更新示意图l算法流程图和伪代码算法流程图和伪代码应用举例应用举例l函数最小化问题函数最小化问题l算法的执行步骤示意图算法的执行步骤示意图现在学习的是第7页，共35页8粒子的个体速度与位置更新公式粒子的个体速度与位置更新公式更新速度更新速度更新速度更新速度 自身速度自身速度自身速度自身速度个体认知个体认知 社会引导社会引导现在学习的是第8页

5、，共35页9速度与位置更新示意图速度与位置更新示意图x1x2P1P2P3gBest现在学习的是第9页，共35页10速度与位置更新示意图速度与位置更新示意图x2x1P3P1P2PB2现在学习的是第10页，共35页11速度与位置更新示意图速度与位置更新示意图经过若干次迭代之后经过若干次迭代之后现在学习的是第11页，共35页12PSO算法流程图和伪代码算法流程图和伪代码现在学习的是第12页，共35页136.2.2 应用举例应用举例例6.1已知函数 ，其中 ，用粒子群优化算法求解y的最小值。现在学习的是第13页，共35页14运行步骤运行步骤现在学习的是第14页，共35页15现在学习的是第15页，共35

6、页166.3 粒子群优化算法的改进研究粒子群优化算法的改进研究PSO 研究热点与方向研究热点与方向 算法理论算法理论算法理论算法理论研究研究研究研究混合算法混合算法混合算法混合算法研究研究研究研究算法参数算法参数算法参数算法参数研究研究研究研究拓扑结构拓扑结构拓扑结构拓扑结构研究研究研究研究算法应用算法应用算法应用算法应用研究研究研究研究现在学习的是第16页，共35页17与与PSO相关的重要学术期刊与国际会议相关的重要学术期刊与国际会议重要学术期刊重要学术期刊lIEEE Transactions on Evolutionary ComputationlIEEE Transactions on

7、Systems,Man and Cybernetics lIEEE Transactions on lMachine Learning lEvolutionary Computation l现在学习的是第17页，共35页18与与PSO相关的重要学术期刊与国际会议相关的重要学术期刊与国际会议重要国际会议重要国际会议lIEEE Congress on Evolutionary Computation(CEC)lIEEE International Conference on Systems,Man,and Cybernetics(SMC)lACM Genetic and Evolutionary

8、Computation Conference(GECCO)lInternational Conference on Ant Colony Optimization and Swarm Intelligence(ANTS)lInternational Conference on Simulated Evolution And Learning(SEAL)l现在学习的是第18页，共35页196.3.1 理论研究改进理论研究改进2006Kadirkamanathan等人等人2006年在动态年在动态环境中对环境中对PSO的行的行为进行研究，由静为进行研究，由静态分析深入到了动态分析深入到了动态分析态分

9、析 2003Trelea 2003年年指出指出PSO最终最终最终稳定地收最终稳定地收敛于空间中的敛于空间中的某一个点，但某一个点，但不能保证是全不能保证是全局最优点局最优点2002Clerc&Kennedy 2002年设计了一年设计了一个称为压缩因子个称为压缩因子的参数。在使用的参数。在使用了此参数之后，了此参数之后，PSO能够更快地能够更快地收敛收敛2006F.van den Bergh等人等人2006年年对对PSO的飞行轨迹的飞行轨迹进行了跟踪，深进行了跟踪，深入到了动态的系入到了动态的系统分析和收敛性统分析和收敛性研究研究现在学习的是第19页，共35页206.3.2 拓扑结构改进拓扑结构

10、改进静态拓扑结构静态拓扑结构全局版本：全局版本：星型结构局部版本：局部版本：环形结构 齿形结构 金字塔结构 冯诺依曼结构 动态拓扑结构动态拓扑结构逐步增长法逐步增长法Suganthan 1999最小距离法最小距离法Hu&Eberhart 2002重新组合法重新组合法Liang&Suganthan2005随机选择法随机选择法Kennedy 等人 2006 其它拓扑结构其它拓扑结构社会趋同法社会趋同法Kennedy 2000Fully InformedMendes 等人 2004广泛学习策略广泛学习策略Liang 等人 2006现在学习的是第20页，共35页21几种典型的拓扑结构示意图几种典型的拓

11、扑结构示意图全局版本全局版本PSO和局部版本和局部版本PSO在收敛特点：在收敛特点：1.GPSO由于其很高的连接度，往往具有比LPSO更快的收敛速度。但是，快速的收敛也让GPSO付出了多样性迅速降低的代价2.LPSO由于具有更好的多样性，因此一般不容易落入局部最优，在处理多峰问题上具有更好的性能在解决具体问题的时候，可以遵循以下一些规律：在解决具体问题的时候，可以遵循以下一些规律：(A)邻域较小的拓扑结构在处理复杂的、多峰值的问题上具有优势，例如环型结构的LPSO(B)随着邻域的扩大，算法的收敛速度将会加快，这对简单的、单峰值的问题非常的有利，例如GPSO在这些问题上就表现很好现在学习的是第2

12、1页，共35页226.3.3 混合算法改进混合算法改进混合其它技术混合其它技术的改进的改进单纯形技术单纯形技术函数延伸技术函数延伸技术混沌技术混沌技术量子技术量子技术协同技术协同技术小生境技术小生境技术物种形成技术物种形成技术混合其它搜索算法混合其它搜索算法的改进的改进结合模拟退火算法结合模拟退火算法结合人工免疫算法结合人工免疫算法结合差分进化算法结合差分进化算法结合局部搜索算法结合局部搜索算法混合进化算子混合进化算子的改进的改进选择算子选择算子交叉算子交叉算子变异算子变异算子进化规划进化规划进化策略进化策略蚁群算法蚁群算法现在学习的是第22页，共35页236.3.4 混合算法改进混合算法改进

13、二进制编码二进制编码整数编码整数编码其它形式其它形式Kennedy和Eberhart 1997 年对PSO进行了离散化，形成了二进制编码的PSO(BPSO)，并且在对De Jong 的五个标准测试函数的测试中取得较好的效果Salman等人2002 年将粒子的位置变量四舍五入为最接近的合法的离散值Yoshida等人 2000 年将连续的值域分区间，每个区间赋予一个相应的离散值Schoofs和Naudts 2002 年重新定义了PSO的“加减乘”法，并且应用到了约束可满足问题（CSP）中Hu等人2003 年将速度定义为位置变量相互交换的概率，从而将PSO离散化并用于解决n皇后问题Clerc 200

14、4 年为PSO定义了合适的“加减乘”法而实现离散化，并且应用于解决旅行商问题（TSP）Chen等人2009年基于集合论的技术，重新定义了PSO速度和位置的更新公式实现了离散化现在学习的是第23页，共35页246.4 粒子群优化算法的相关应用粒子群优化算法的相关应用调度与规划调度与规划优化与设计优化与设计生物与医学生物与医学机器学习与训练机器学习与训练其它其它数据挖掘与分类数据挖掘与分类应用应用现在学习的是第24页，共35页256.5 粒子群优化算法的参数设置粒子群优化算法的参数设置种群规模种群规模N 粒子的粒子的长长度度D 粒子的范围粒子的范围R 最大速度最大速度Vmax 惯性权重惯性权重 压

15、缩因子压缩因子 加速系数加速系数c1和和c2 终止条件终止条件 全局和局部全局和局部PSO 同步和异步更新同步和异步更新 现在学习的是第25页，共35页26种群规模种群规模N影响着算法的搜索能力和计算量影响着算法的搜索能力和计算量lPSO对种群规模要求不高，一般取对种群规模要求不高，一般取20-40就就可以达到很好的求解效果可以达到很好的求解效果l不过对于比较难的问题或者特定类别的问题，不过对于比较难的问题或者特定类别的问题，粒子数可以取到粒子数可以取到100或或200 现在学习的是第26页，共35页27粒子的长度粒子的长度D由优化问题本身决定，就是由优化问题本身决定，就是问题解的长度问题解的

16、长度粒子的范粒子的范围围R由优化问题本身决定，每一维由优化问题本身决定，每一维可以设定不同的范围可以设定不同的范围现在学习的是第27页，共35页28最大速度最大速度Vmax 决定粒子每一次的最大移动距离，制约着决定粒子每一次的最大移动距离，制约着算法的探索和开发能力算法的探索和开发能力lVmax的每一的每一维维 一般可以取相一般可以取相应维应维搜索空搜索空间间的的10%-20%，甚至，甚至100%l也有研究使用将也有研究使用将Vmax按照进化代数从大到小递按照进化代数从大到小递减的设置方案减的设置方案 现在学习的是第28页，共35页29惯惯性性权权重重 控制着前一速度控制着前一速度对对当前速度

17、的影响，用当前速度的影响，用于平衡算法的探索和开于平衡算法的探索和开发发能力能力l一般一般设设置置为为从从0.9线性递减到线性递减到0.4，也有非线，也有非线性递减的设置方案性递减的设置方案 l可以采用模糊控制的方式设定，或者在可以采用模糊控制的方式设定，或者在0.5,1.0之间随机取值之间随机取值l 设为设为0.729的同时将的同时将c1和c2设设1.49445，有利，有利于算法的收敛于算法的收敛 现在学习的是第29页，共35页30压缩压缩因子因子 限制粒子的飞行速度的，保证算法的有限制粒子的飞行速度的，保证算法的有效收敛效收敛lClerc等人通等人通过过数学数学计计算得到算得到 取取值值0

18、.729，同时同时c1和c2设为设为2.05 现在学习的是第30页，共35页31加速系数加速系数c1和和c2 代表了粒子向自身极代表了粒子向自身极值值pBest和全局极和全局极值值gBest推推进进的加速的加速权值权值 lc1和和c2通常都等于通常都等于2.0，代表着，代表着对对两个引两个引导导方方向的同等重向的同等重视视 l也存在一些也存在一些c1和和c2不相等的不相等的设设置，但其范置，但其范围围一般都在一般都在0和和4之之间间 l研究研究对对c1和和c2的自适的自适应调应调整方案整方案对对算法性能的算法性能的增增强强有重要意有重要意义义 现在学习的是第31页，共35页32终止条件终止条件

19、决定算法运行的结束，由具体的应用和决定算法运行的结束，由具体的应用和问题本身确定问题本身确定l将最大循环数设定为将最大循环数设定为500，1000，5000，或者，或者最大的函数评估次数，等等最大的函数评估次数，等等l也可以使用算法求解得到一个可接受的解作也可以使用算法求解得到一个可接受的解作为终为终止条件止条件l或者是当算法在很长一段迭代中没有得到任或者是当算法在很长一段迭代中没有得到任何改善，则可以终止算法何改善，则可以终止算法现在学习的是第32页，共35页33全局和局部全局和局部PSO决定算法如何决定算法如何选择选择两种版本的粒子群两种版本的粒子群优优化算法化算法全局版全局版PSO和局部

20、版和局部版PSOl全局版本全局版本PSO速度快，不速度快，不过过有有时时会陷入局部最会陷入局部最优优l局部版本局部版本PSO收收敛敛速度慢一点，不速度慢一点，不过过不容易不容易陷入局部最陷入局部最优优l在在实际应实际应用中，可以根据具体用中，可以根据具体问题选择问题选择具体具体的算法版本的算法版本现在学习的是第33页，共35页34同步和异步更新同步和异步更新 两种更新方式的区两种更新方式的区别别在于在于对对全局的全局的gBest或者或者局部的局部的lBest的更新方式的更新方式l在同步更新方式中，在每一代中，当所有粒子在同步更新方式中，在每一代中，当所有粒子都采用当前的都采用当前的gBest进

21、进行速度和位置的更新之行速度和位置的更新之后才后才对对粒子粒子进进行行评评估，更新各自的估，更新各自的pBest，再，再选选最好的最好的pBest作作为为新的新的gBestl在异步更新方式中，在每一代中，粒子采用当前在异步更新方式中，在每一代中，粒子采用当前的的gBest进进行速度和位置的更新，然后行速度和位置的更新，然后马马上上评评估，更新估，更新自己的自己的pBest，而且如果其，而且如果其pBest要要优优于当前的于当前的gBest，则则立刻更新立刻更新gBest，迅速将更好的，迅速将更好的gBest用于后面用于后面的粒子的更新的粒子的更新过过程中程中l一般而言，异步更新的一般而言，异步更新的PSO具高效的信息具高效的信息传传播能播能力，具有有更快的收力，具有有更快的收敛敛速度速度现在学习的是第34页，共35页感感谢谢大大家家观观看看现在学习的是第35页，共35页