第6章粒子群优化算法.ppt

第第6章章 粒子群粒子群优化算法化算法Contents算法算法简介介 1 1基本流程基本流程 2 2改改进研究研究 3 3相关相关应用用 4 4参数参数设置置 5 52.6.1 粒子群粒子群优化算法化算法简介介粒子群粒子群优化算法是什么？化算法是什么？粒子群粒子群优化算法化算法（Particle Swarm Optimization，PSO）是是进化化计算的一个分支，算的一个分支，是一种模是一种模拟自然界的生物活自然界的生物活动的随机搜索算法。的随机搜索算法。粒子群粒子群优化算法的思想来源是怎化算法的思想来源是怎样的？的？它由它由谁提出的？提出的？PSO模模拟了自然界了自然界鸟群捕食和群捕食和鱼群捕食的群捕食的过程。程。通通过群体中的群体中的协作作寻找到找到问题的全局最的全局最优解。解。它是它是1995年由美国学者年由美国学者Eberhart和和Kennedy提出的，提出的，现在已在已经广泛广泛应用于各种工程用于各种工程领域的域的优化化问题之中。之中。3.6.1.1 思想来源思想来源生物界生物界现象象群体行群体行为群体迁徙群体迁徙生物生物觅食食社会心理学社会心理学群体智慧群体智慧个体个体认知知社会影响社会影响粒子群粒子群粒子群粒子群优优化算法化算法化算法化算法 人工生命人工生命鸟群群觅食食鱼群学群学习群理群理论4.6.1.2 基本基本原理原理鸟群群觅食食现象象鸟群群觅食空食空间飞行速度行速度所在位置所在位置个体个体认知与群体知与群体协作作找到食物找到食物粒子群粒子群优化算法化算法搜索空搜索空间的一的一组有效有效解解问题的搜索空的搜索空间解的速度向量解的速度向量解的位置向量解的位置向量速度与位置的更新速度与位置的更新找到全局最找到全局最优解解鸟群群觅食食现象象粒子群粒子群优化算法化算法类比关系比关系5.6.1.2 基本基本原理原理鸟群群觅食食现象象粒子群粒子群优化算法化算法6.6.2 粒子群粒子群优化算法的基本流程化算法的基本流程基本流程基本流程l速度与位置更新公式速度与位置更新公式l速度与位置更新示意速度与位置更新示意图l算法流程算法流程图和和伪代代码应用用举例例l函数最小化函数最小化问题l算法的算法的执行步行步骤示意示意图7.粒子的个体速度与位置更新公式粒子的个体速度与位置更新公式更新速度更新速度更新速度更新速度 自身速度自身速度自身速度自身速度个体个体个体个体认认知知知知 社会引社会引社会引社会引导导8.速度与位置更新示意速度与位置更新示意图x1x2P1P2P3gBest9.速度与位置更新示意速度与位置更新示意图x2x1P3P1P2PB210.速度与位置更新示意速度与位置更新示意图经过若干次迭代之后若干次迭代之后11.PSO算法流程算法流程图和和伪代代码12.6.2.2 应用用举例例例6.1已知函数 ，其中 ，用粒子群优化算法求解y的最小值。13.运行步运行步骤14.15.6.3 粒子群粒子群优化算法的改化算法的改进研究研究PSO 研究研究热点与方向点与方向 算法理算法理算法理算法理论论研究研究研究研究混合算法混合算法混合算法混合算法研究研究研究研究算法参数算法参数算法参数算法参数研究研究研究研究拓扑拓扑拓扑拓扑结结构构构构研究研究研究研究算法算法算法算法应应用用用用研究研究研究研究16.与与PSO相关的重要学相关的重要学术期刊与国期刊与国际会会议重要学重要学术期刊期刊lIEEE Transactions on Evolutionary ComputationlIEEE Transactions on Systems,Man and Cybernetics lIEEE Transactions on lMachine Learning lEvolutionary Computation l17.与与PSO相关的重要学相关的重要学术期刊与国期刊与国际会会议重要国重要国际会会议lIEEE Congress on Evolutionary Computation(CEC)lIEEE International Conference on Systems,Man,and Cybernetics(SMC)lACM Genetic and Evolutionary Computation Conference(GECCO)lInternational Conference on Ant Colony Optimization and Swarm Intelligence(ANTS)lInternational Conference on Simulated Evolution And Learning(SEAL)l18.6.3.1 理理论研究改研究改进2006Kadirkamanathan等人等人2006年在年在动态环境中境中对PSO的行的行为进行研究，由静行研究，由静态分析深入到了分析深入到了动态分析分析 2003Trelea 2003年年指出指出PSO最最终最最终稳定地收定地收敛于空于空间中的中的某一个点，但某一个点，但不能保不能保证是全是全局最局最优点点2002Clerc&Kennedy 2002年年设计了一了一个称个称为压缩因子因子的参数。在使用的参数。在使用了此参数之后，了此参数之后，PSO能能够更快地更快地收收敛2006F.van den Bergh等人等人2006年年对对PSO的的飞飞行行轨轨迹迹进进行了跟踪，深行了跟踪，深入到了入到了动态动态的系的系统统分析和收分析和收敛敛性性研究研究19.6.3.2 拓扑拓扑结构改构改进静静态拓扑拓扑结构构全局版本：全局版本：星型结构局部版本：局部版本：环形结构 齿形结构 金字塔结构 冯诺依曼结构 动态拓扑拓扑结构构逐步增逐步增长法法Suganthan 1999最小距离法最小距离法Hu&Eberhart 2002重新重新组合法合法Liang&Suganthan2005随机随机选择法法Kennedy 等人 2006 其它拓扑其它拓扑结构构社会社会趋同法同法Kennedy 2000Fully InformedMendes 等人 2004广泛学广泛学习策略策略Liang 等人 200620.几种典型的拓扑几种典型的拓扑结构示意构示意图全局版本全局版本PSO和局部版本和局部版本PSO在收在收敛特点：特点：1.GPSO由于其很高的连接度，往往具有比LPSO更快的收敛速度。但是，快速的收敛也让GPSO付出了多样性迅速降低的代价2.LPSO由于具有更好的多样性，因此一般不容易落入局部最优，在处理多峰问题上具有更好的性能在解决具体在解决具体问题的的时候，可以遵循以下一些候，可以遵循以下一些规律：律：(A)邻域较小的拓扑结构在处理复杂的、多峰值的问题上具有优势，例如环型结构的LPSO(B)随着邻域的扩大，算法的收敛速度将会加快，这对简单的、单峰值的问题非常的有利，例如GPSO在这些问题上就表现很好21.6.3.3 混合算法改混合算法改进混合其它技混合其它技术的改的改进单纯形技形技术函数延伸技函数延伸技术混沌技混沌技术量子技量子技术协同技同技术小生境技小生境技术物种形成技物种形成技术混合其它搜索算法混合其它搜索算法的改的改进结合模合模拟退火算法退火算法结合人工免疫算法合人工免疫算法结合差分合差分进化算法化算法结合局部搜索算法合局部搜索算法混合混合进化算子化算子的改的改进选择算子算子交叉算子交叉算子变异算子异算子进化化规划划进化策略化策略蚁群算法群算法22.6.3.4 混合算法改混合算法改进二二进制制编码整数整数编码其它形式其它形式Kennedy和Eberhart 1997 年对PSO进行了离散化，形成了二进制编码的PSO(BPSO)，并且在对De Jong 的五个标准测试函数的测试中取得较好的效果Salman等人2002 年将粒子的位置变量四舍五入为最接近的合法的离散值Yoshida等人 2000 年将连续的值域分区间，每个区间赋予一个相应的离散值Schoofs和Naudts 2002 年重新定义了PSO的“加减乘”法，并且应用到了约束可满足问题（CSP）中Hu等人2003 年将速度定义为位置变量相互交换的概率，从而将PSO离散化并用于解决n皇后问题Clerc 2004 年为PSO定义了合适的“加减乘”法而实现离散化，并且应用于解决旅行商问题（TSP）Chen等人2009年基于集合论的技术，重新定义了PSO速度和位置的更新公式实现了离散化23.6.4 粒子群粒子群优化算法的相关化算法的相关应用用调度与度与规划划优化与化与设计生物与医学生物与医学机器学机器学习与与训练其它其它数据挖掘与分数据挖掘与分类应用用24.6.5 粒子群粒子群优化算法的参数化算法的参数设置置种群种群规模模N 粒子的粒子的长度度D 粒子的范粒子的范围R 最大速度最大速度Vmax 惯性性权重重 压缩因子因子 加速系数加速系数c1和和c2 终止条件止条件 全局和局部全局和局部PSO 同步和异步更新同步和异步更新 25.种群种群规模模N影响着算法的搜索能力和影响着算法的搜索能力和计算量算量lPSO对种群种群规模要求不高，一般取模要求不高，一般取20-40就可以达到很好的求解效果就可以达到很好的求解效果l不不过对于比于比较难的的问题或者特定或者特定类别的的问题，粒子数可以取到，粒子数可以取到100或或200 26.粒子的粒子的长度度D由由优化化问题本身决定，本身决定，就是就是问题解的解的长度度粒子的范粒子的范围R由由优化化问题本身决定，本身决定，每一每一维可以可以设定不同的范定不同的范围27.最大速度最大速度Vmax 决定粒子每一次的最大移决定粒子每一次的最大移动距离，制距离，制约着算法的探索和开着算法的探索和开发能力能力lVmax的每一的每一维 一般可以取相一般可以取相应维搜搜索空索空间的的10%-20%，甚至，甚至100%l也有研究使用将也有研究使用将Vmax按照按照进化代数从大化代数从大到小到小递减的减的设置方案置方案 28.惯性性权重重 控制着前一速度控制着前一速度对当前速度的影响，当前速度的影响，用于平衡算法的探索和开用于平衡算法的探索和开发能力能力l一般一般设置置为从从0.9线性性递减到减到0.4，也有非，也有非线性性递减的减的设置方案置方案 l可以采用模糊控制的方式可以采用模糊控制的方式设定，或者在定，或者在0.5,1.0之之间随机取随机取值l 设为0.729的同的同时将将c1和c2设1.49445，有利于算法的收有利于算法的收敛 29.压缩因子因子 限制粒子的限制粒子的飞行速度的，保行速度的，保证算法的算法的有效收有效收敛lClerc等人通等人通过数学数学计算得到算得到 取取值0.729，同，同时c1和c2设为2.05 30.加速系数加速系数c1和和c2 代表了粒子向自身极代表了粒子向自身极值pBest和全局极和全局极值gBest推推进的加速的加速权值 lc1和和c2通常都等于通常都等于2.0，代表着，代表着对两个引两个引导方向的同等重方向的同等重视 l也存在一些也存在一些c1和和c2不相等的不相等的设置，但其置，但其范范围一般都在一般都在0和和4之之间 l研究研究对c1和和c2的自适的自适应调整方案整方案对算法算法性能的增性能的增强有重要意有重要意义 31.终止条件止条件决定算法运行的决定算法运行的结束，由具体的束，由具体的应用用和和问题本身确定本身确定l将最大循将最大循环环数数设设定定为为500，1000，5000，或者最大的函数或者最大的函数评评估次数，等等估次数，等等l也可以使用算法求解得到一个可接受的也可以使用算法求解得到一个可接受的解作解作为终止条件止条件l或者是当算法在很或者是当算法在很长一段迭代中没有得一段迭代中没有得到任何改善，到任何改善，则可以可以终止算法止算法32.全局和局部全局和局部PSO决定算法如何决定算法如何选择两种版本的粒子群两种版本的粒子群优化算法化算法全局版全局版PSO和局部版和局部版PSOl全局版本全局版本PSO速度快，不速度快，不过有有时会陷入会陷入局部最局部最优l局部版本局部版本PSO收收敛速度慢一点，不速度慢一点，不过不不容易陷入局部最容易陷入局部最优l在在实际应用中，可以根据具体用中，可以根据具体问题选择具体的算法版本具体的算法版本33.同步和异步更新同步和异步更新 两种更新方式的区两种更新方式的区别在于在于对全局的全局的gBest或或者局部的者局部的lBest的更新方式的更新方式l在同步更新方式中，在每一代中，当所有在同步更新方式中，在每一代中，当所有粒子都采用当前的粒子都采用当前的gBest进行速度和位置行速度和位置的更新之后才的更新之后才对粒子粒子进行行评估，更新各自估，更新各自的的pBest，再，再选最好的最好的pBest作作为新的新的gBestl在异步更新方式中，在每一代中，粒子采用当在异步更新方式中，在每一代中，粒子采用当前的前的gBest进行速度和位置的更新，然后行速度和位置的更新，然后马上上评估，更新自己的估，更新自己的pBest，而且如果其，而且如果其pBest要要优于当前的于当前的gBest，则立刻更新立刻更新gBest，迅速将，迅速将更好的更好的gBest用于后面的粒子的更新用于后面的粒子的更新过程中程中l一般而言，异步更新的一般而言，异步更新的PSO具高效的信息具高效的信息传播播能力，具有有更快的收能力，具有有更快的收敛速度速度34.