第4章(计算智能-粒子群优化)

2020/1/27人工智能ArtificialIntelligence(AI)董红斌[e-mail]计算机科学与技术学院2013年9-10月2020/1/27第4章计算智能4.7粒子群优化算法2020/1/274.7粒群优化4.7.1群智能和粒群优化1群智能2粒群优化4.7.2粒群优化算法1个体最佳算法2全局最佳算法3局部最佳算法2020/1/274.7.1群智能与粒群优化1群智能群：某种相互交互的组织群的个体：蚂蚁、蜜蜂、黄蜂、鱼群、鸟群等2020/1/27群智能的特点：个体结构和行为是非常简单的，通过个体之间的相互作用与协同合作，可以构成非常复杂的群行为。2020/1/27基于群智能的算法：粒群算法：模拟鸟群的智能行为蚁群算法：模拟蚂蚁的觅食行为用途：解决最优化问题2020/1/272粒群优化粒（子）群优化（ParticleSwarmOptimization，PSO)算法是一种模拟鸟群行为的群体搜索算法。2020/1/27粒子群的最初含义：通过图形来模拟鸟群优美和不可预测的空中飞行动作，发现鸟群支配同步飞行和以最佳队形突然改变飞行方向并重新编队的能力。2020/1/27在粒子群优化中，粒子（个体）在搜索空间中是不断地改变位置的，但是位置变化要受到其邻近粒子行为的影响，所以说，粒子群优化算法是一种共生合作算法。2020/1/274.7.2粒子群优化算法群是粒子的集合，每一个粒子代表一个容许解。每一个粒子的位置由原先的位置和邻近粒子的位置来确定。2020/1/27令xi(t)：粒子Pi在时刻t的位置vi(t)：位置变化速度则粒子Pi的当前位置为xi(t)=xi(t-1)+vi(t)vi(t)xi(t-1)xi(t)2020/1/27三种基本的PSO算法个体最佳算法全局最佳算法局部最佳算法2020/1/271个体最佳算法特点：每一个个体只将它的当前位置与自己的最佳位置的性能值作比较，而不使用其他粒子的信息。2020/1/27记号：()bestbestfxpx目标函数、性能函数已经得到的最佳性能值最佳性能值对应的自变量值，即最佳的粒子位置2020/1/27算法步骤：(1)对于粒子群P(t)初始化，使得t=0时每一个粒子Pi的位置xi(t)是随机的。(2)利用每一个粒子的当前位置计算其性能函数值（即目标函数值）。2020/1/27(3)比较每一个粒子的当前性能值与至今得到的最佳性能，如果(())iibestfxtp则(())()iibestipbestipfxtxxt2020/1/27(4)改变每一个粒子的速度()(1)(())iiipbestivtvtxxt位置随机数(改变参数)每一个粒子的新位置()(1)()1iiixtxtvttt(5)转到(2)，重复(2)-(4)，直到收敛为止。2020/1/27说明：粒子离原先发现的最佳位置越远，使粒子回到它最佳位置所需要的速度就越大。随机数的上限是用户选定的算法参数，其值越大，粒子轨迹振荡就越大；反之，轨迹就越平滑。2020/1/272全局最佳算法在全局最佳算法中，粒子群的全局最优方案具有星形的邻域拓扑结构：2020/1/27在该结构中，每一个粒子都能与其他粒子进行通信，形成一个全连接的网络。每一个粒子的移动速度由粒子群中的最佳粒子位置、本粒子的最佳位置来决定。2020/1/27算法步骤：(1)对于粒子群P(t)初始化，使得t=0时每一个粒子Pi的位置xi(t)是随机的。(2)利用每一个粒子的当前位置计算其性能函数值（即目标函数值）。2020/1/27(3)比较每一个粒子的当前性能值与至今得到的最佳性能，如果(())iibestfxtp则(())()iibestipbestipfxtxxt2020/1/27(4)将每一个粒子的性能与全局最佳粒子的性能进行比较，如果(())ibestfxtg则(())()bestigbestigfxtxxt即找出迄今为止的最佳粒子位置及其性能值2020/1/27(4)(续）改变每一个粒子的速度12()(1)(())(())iiipbestigbestivtvtxxtxxt位置随机数第二项：认知分量第三项：社会分量2020/1/27(4)(续)每一个粒子的新位置()(1)()1iiixtxtvttt(5)转到(2)，重复(2)-(4)，直到收敛为止。2020/1/27说明：粒子离开全局最佳位置和自己的最佳位置越远，使其回到本身最佳位置的速度就越大。随机数(1,2)可以确定为i=rici，其中ri～U(0,1)，ci为正加速度常数。2020/1/273局部最佳算法在局部最佳算法中，粒子群的局部最优方案具有环形的邻域拓扑结构：2020/1/27在该结构中，每一个粒子只与其n个邻近粒子进行通信，形成一个部分连接的网络。每一个粒子的移动速度由邻域内的最佳粒子位置、本粒子的最佳位置来决定。n=22020/1/27算法步骤：(1)对于粒子群P(t)初始化，使得t=0时每一个粒子Pi的位置xi(t)是随机的。(2)利用每一个粒子的当前位置计算其性能函数值（即目标函数值）。2020/1/27(3)比较每一个粒子的当前性能值与至今得到的最佳性能，如果(())iibestfxtp则(())()iibestipbestipfxtxxt2020/1/27(4)将每一个粒子的性能与局部最佳粒子的性能进行比较，如果(())iibestfxtl则(())()iibestilbestilfxtxxt即找出迄今为止的局部最佳粒子位置及其性能值2020/1/27(4)(续）改变每一个粒子的速度12()(1)(())(())iiiipbestilbestivtvtxxtxxt位置随机数第二项：认知分量第三项：社会分量2020/1/27(4)(续)每一个粒子的新位置()(1)()1iiixtxtvttt(5)转到(2)，重复(2)-(4)，直到收敛为止。2020/1/27说明：粒子离开局部最佳位置和自己的最佳位置越远，使其回到本身最佳位置的速度就越大。随机数(1,2)可以确定为i=rici，其中ri～U(0,1)，ci为正加速度常数。