粒子群算法.ppt

1、,Particle Swarm Optimization,2011/03,粒子群算法,Introduction Discovery of Particle Swarm Optimization (PSO) PSO概述 PSO算法 PSO算法实例与应用,Outline,Particle Swarm Optimization,03/08 AI course,Swarm Intelligence,Particle Swarm Optimization,向大自然学习 遗传算法(GA) 物竞天择，设计染色体编码，根据适应值函数进行染色体选择、交叉和变异操作，优化求解 人工神经网络算法(ANN) 模仿生物

2、神经元，透过神经元的信息传递、训练学习、联想，优化求解 模拟退火算法(SA) 模模仿金属物质退火过程,03/08 AI course,Swarm Intelligence,Particle Swarm Optimization,Ant Colony Optimization (ACO) Particle Swarm Optimization (PSO) Marriage in Honey Bees Optimization (MBO) Biomimicry (生物模拟),03/08 AI course,AI发展史,Particle Swarm Optimization,Genetic Algo

3、rithm,Tabu Search,1953,Ants System,Particle Swarm Optimization,Swarm Intelligence,Simulated Annealing,1969,Expert System,03/08 AI course,最优化算法,Particle Swarm Optimization,解决最优化问题的方法 传统搜索方法 保证能找到最优解 Heuristic Search 不能保证找到最优解,03/08 AI course,Cooperation example,Particle Swarm Optimization,03/08 AI co

4、urse,Discovery of Particle Swarm Optimization 探索 粒子群优化算法,Inventor (1),Particle Swarm Optimization,Russ Eberhart,Russell Eberhart ,03/08 AI course,Inventor (2),Particle Swarm Optimization,James Kennedy,James Kennedy Kennedy_J,03/08 AI course,PSO概述,Particle Swarm Optimiz

5、ation,起源 生物学家对鸟(鱼)群捕食的行为研究 社会行为 (Social-Only Model) 个体认知 (Cognition-Only Model),03/08 AI course,鸟群(鱼群)行为,Particle Swarm Optimization,03/08 AI course,鸟群(鱼群)行为,Particle Swarm Optimization,粒子群特性,03/08 AI course,PSO概述,Particle Swarm Optimization,每个寻优的问题解都被想象成一只鸟(鱼)，称为 Particle 每个Particle都有记忆能力 所有的Partic

6、le都通过Fitness Function来判断目前的位置之好坏 每个Particle通过Velocity Function来决定移动的距离与方向,03/08 AI course,PSO算法流程,Particle Swarm Optimization,Initialize Evaluation Find the Pbest Find the Gbest Update the Position 回到 Evaluation 继续执行，直到符合终止条件为止,03/08 AI course,PSO算法流程,Particle Swarm Optimization,Initial 将群族初始化，以随机的方

7、式求出每一Particle 之初始位置与速度,03/08 AI course,PSO算法流程,Particle Swarm Optimization,Evaluation 根据 Fitness Function计算出其 Fitness Value 以作为判断每一Particle之好坏,03/08 AI course,PSO演算法流程,Particle Swarm Optimization,Find the Pbest 找出每个Particle 到目前为止的搜寻过程中最优解，这个最优解我们称为Pbest,03/08 AI course,PSO算法流程,Particle Swarm Optimiz

8、ation,Find the Gbest 找出所有Particle 到目前为止所搜寻到的全体最优解，此最优解我们称之为Gbest,03/08 AI course,PSO算法流程,Particle Swarm Optimization,Update the Position 根据 Velocity Function 更新每个Particle的移动方向与速度,回到 Evaluation 继续执行，直到符合终止条件为止,03/08 AI course,PSO 流程图,Particle Swarm Optimization,03/08 AI course,PSO Velocity Function,P

9、article Swarm Optimization,Cognition-Only Model,PSO Velocity Function,Social-Only Model,| |,+,03/08 AI course,PSO Velocity Function,Particle Swarm Optimization,Cognition-Only Model,Vid：第 i 个 particle (有d个维度) 的速度 Pid：每个 particle 到目前为止所出现的最佳位置 Xid：每个 particle 目前的所在位置 C1：学习常数 rand()：01之間的随机数,03/08 AI c

10、ourse,PSO Velocity Function,Particle Swarm Optimization,Social-Only Model,Vid：第 i 个 particle (有d个维度) 的速度 Pgd：所有 particle 到目前为止所出现的最佳位置 Xid：每个 particle 目前的所在位置 C2：学习常数 rand()：01之间的随机数,03/08 AI course,PSO Velocity Function,Particle Swarm Optimization,PSO Velocity Function,Vid：第 i 个 particle (有d个维度) 的速

11、度 Pid：每个particle 到目前为止所出现的最佳位置 Pgd：所有 particle 到目前为止所出现的最佳位置 Xid：每个 particle 目前的所在位置 C1,C2：学习常数 w：惯性权重 rand()：01之间的随机数,03/08 AI course,區域 最佳解,全域 最佳解,運動向量,慣性向量,PSO Velocity Function,Particle Swarm Optimization,动能向量理论,Here I am!,The best position of team,My best position,x,pg,pi,v,PBest,gBest,03/08 AI

12、 course,PSO Pseudo Code,Particle Swarm Optimization,I) For each particle: Initialize particle II) Do: a) For each particle: 1) Calculate fitness value 2) If the fitness value is better than the best fitness value (Pbest) in history 3) Set current value as the new Pbest End b) For each particle: 1) F

13、ind in the particle neighborhood, the particle with the best fitness 2) Calculate particle velocity according to the velocity function 3) Update particle position according to the position function End While maximum iterations or minimum error criteria is not attained,03/08 AI course,粒子群最优化,Particle

14、 Swarm Optimization,x,z,y,1,2,3,1,2,3,1,2,3,f(3,3,1)=14,f(2,1,2)=7,f(1,3,3)=8,解集合坐标系表示法,03/08 AI course,2维例子,粒子群最优化,Particle Swarm Optimization,Note,合理解集合,目前最优解,个体最优解,全域,区域,03/08 AI course,PSO举例,Particle Swarm Optimization,03/08 AI course,PSO举例,Particle Swarm Optimization,Griewank,Rastrigin,Rosenbro

15、ck,03/08 AI course,PSO举例 （见程序演示）,Particle Swarm Optimization,Best result after 40 000 evaluations,Optimum=0, Dimension=30,03/08 AI course,粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,主要改进方面 对基本粒子群算法更新公式的改进 基于遗传思想对粒子群算法的改进 利用小生境思想对粒子群算法的改进,

16、对基本粒子群算法更新公式的改进,Particle Swarm Optimization,03/08 AI course,带有惯性权重的改进 惯性权重设计 当w1时，公式与前面相同，从而表明带惯性权重的粒子群算法是基本粒子群算法的扩展。 建议w的取值范围为0，1.4，但实验结果表明当w取0.8，1.2时，算法收敛速度更快，而当w1.2时，算法则较多地陷入局部极值。 线性惯性权重法(MaxNumber为最大代数)： 较大的w有较好的全局收敛能力，较小的w则有较强的局部收敛能力。因此，随着迭代次数的增加，惯性权重w应不断减少，从而使得粒子群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能

17、力。,对基本粒子群算法更新公式的改进,Particle Swarm Optimization,03/08 AI course,带有惯性权重的改进 基于模糊系统的惯性权重地动态调整 该模糊系统需要两个输入参数：当前惯性权重w和当前最好性能评价值(CBPE)；输出为惯性权重w的改变量。由于不同的问题有不同范围的性能评价值, 因此需要对CBPE 进行如下的规范化： NCBPE 是规范化后的评价值，CBPEmin和CBPEmax依问题而定，且需事先得知或者可估计。,对基本粒子群算法更新公式的改进,Particle Swarm Optimization,03/08 AI course,带有惯性权重的改进

18、 带有收缩因子的改进粒子群算法 Clerc提出了收缩因子的概念,该方法描述了一种选择w， c1 和c2 的值的方法，以确保算法收敛。通过正确选择这些参数，就没有必要将vij 的值限制在-vmax , vmax 之中, 改进了的速度公式为：,基于遗传思想对粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,利用选择的方法 Angeline引入了具有明显选择机制的改进粒子群算法。该算法所使用的选择算子为锦标赛选择算子，将每个个体的适应值，基于当前位置，与其他个体进行比较，并记下最差的一个点。群体再用这个记录排序，最高的得分出现在群体的头部。 算

19、法流程为： Step1 从种群选择一个个体。将该个体的适应值与种群中的其他个体的适应值逐一进行比较，如果当前个体的适应值优于某个个体的适应值，则每次授予该个体一分。对每一个个体 重复这一过程。 Step2 根据前一步所计算的分数对种群中的个体进行由大到小的排列。 Step3 选择种群中顶部的一半个体，并对他们进行复制，取代种群底部的一半个体，在此过程中最佳个体的适应值并未改变。,基于遗传思想对粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,借鉴杂交的方法 在该方法中，粒子群中的粒子被赋予一个杂交概率，这个杂交概率是用户确定的，与粒子的适

20、应值无关。在每次迭代中，依据杂交概率选取指定数量的粒子放入一个池中。池中的粒子随机地两两杂交，产生相同数目的子代，并用子代粒子取代父代粒子，以保持种群的粒子数目不变。 让a和b表示被选择的两个亲代个体的指针，那么杂交算法的计算公式表示如下： 这里r1U(0，1)。经过杂交操作，在由亲代个体形成超立方体中随机产生了两个新的位置。速度的交叉处将两个亲代个体的速度之和的长度规格化，因此只有方向受到影响，数量却没有被影响。 在单峰值函数情况下，该算法比原始PSO低效；但是在拥有多个局部最小值的函数中该算法比原始的PSO算法效率高。,利用小生境思想对粒子群算法的改进,Particle Swarm Opt

21、imization,03/08 AI course,基于动态邻域的改进粒子群算法 基本粒子群的Lbest版本中，粒子的邻域是基于粒子序号划分的。Suganthan提出了基于粒子的空间位置划分的方案。 在迭代中, 计算每一个粒子与群中其他粒子的距离, 记录任何2 个粒子间的最大距离为dmax 。对每一粒子按照Xa - Xb / dmax 计算一个比值, 其中Xa - Xb是当前粒子a 到粒子b 的距离。而选择阈值frac 根据迭代次数而变化。当另一粒子b 满足Xa - Xb / dmax frac时, 则b 成为当前粒子的邻域。所有满足该条件的粒子组成该邻域。 该算法的基本思想是开始阶段，每个个

22、体的邻域为其自身，随着进化代数的增长，其邻域范围也在不断增大直至整个种群。,利用小生境思想对粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,基于动态邻域的改进粒子群算法 该算法的基本框架为： (1) 初始化各粒子的位置及速度。 (2) 计算各粒子的适应值。 (3) 比较并替换全局最优位置Pbest。 (4) 对每个粒子计算其邻域并确定局部最优Lbest。 (5) 利用速度更新公式进行进化： (6) 修改各粒子位置。 (7) 按下式修改参数： wt=w+(w0- w)1-t/K C1t=C1+(C10-C1)1-t/K C2t=C2+(C

23、20-C2)1-t/K (8) 重复步骤(2)步骤(7)，直至满足结束条件。 其中，K为最大进化代数，t为当前进化代数，且和0分别表示参数的起始和最终的值。,利用小生境思想对粒子群算法的改进,Particle Swarm Optimization,03/08 AI course,基于邻域拓扑的方法 为了进一步改善算法性能，Kennedy在1999年提出了几种基本的邻域拓扑结构，即环形结构和轮形结构及它们的推广，如图所示。,Advantages of PSO,Particle Swarm Optimization,优点 参数较少，容易调整 局部与全局结合，收敛速度快,03/08 AI cours

24、e,PSO相关论文,Particle Swarm Optimization,Kennedy, J. and Eberhart, R. C. “Particle swarm optimization,” Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995. Eberhart, R. C.and Kennedy, J. “A new optimizer using particle swarm theory,” Proceedings of the

25、Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43, 1995. Kennedy, J., and Eberhart, R. C. A discrete binary version of the particle swarm algorithm. Proc. 1997 Conf. on Systems, Man, and Cybernetics, Piscataway, pp. 4104-4109, 1997. Kennedy, J., Eberhart, R. C. with Shi Y., “Swarm Intelligence,” Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001. Eberhart