粒子群算法ppt课件

1、粒子群算法,2,3,Reynolds,Heppner,Grenader等发现，鸟群在行进过程中会突然同步地改变方向，散开或聚集。一定有种潜在的规则在起作用，据此他们提出了对鸟群行为的模拟。在他们的早期模型中，仅仅依赖个体间距的操作，即群体的同步是个体之间努力保持最优距离的结果,4,1987年Reynolds对鸟群社会系统的仿真研究，一群鸟在空中飞行，每个鸟遵守以下三条规则： 1）避免与相邻的鸟发生碰撞冲突； 2）尽量与自己周围的鸟在速度上保持协调和一致； 3）尽量试图向自己所认为的群体中靠近。 仅通过使用这三条规则，系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕

2、行而过，随后又会重新形成群体。 作为CAS实例,5,Kennedy和Eberhart在CAS中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中,6,鸟群觅食行为,Food,Global Best Solution,Past Best Solution,7,算法介绍,PSO算法是一种进化计算技术（evolutionary computation)，由Eberhart博士和Kennedy博士于1995年提出（Kennedy J, Eberhart R.

3、Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks.1995,19421948).其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解,基本PSO算法,每个粒子在n维空间中，位置表示为矢量 飞行速度表示为矢量,9,基本PSO算法,PSO初始化为一群随机粒子（随机解）。然后通过迭代寻找最优解。每次迭代中，粒子通过跟踪两个极值（pbest：某个粒子到现在为止发现的最好位置。 gbest:整个群体到目前为止发现的最好位置）来更新自己。更新的公式如下： （1）速度

4、更新： (2) 位置更新： 其中c1和c2是学习因子(加速因子)，通常取c1=c2=2, rand( )为0，1之间的随机数； 在每一维，粒子都有一个最大限制速度Vmax。应将Vi限制在-Vmax,Vmax之间,10,基本PSO算法,11,12,标准PSO算法流程,1、初始化一群微粒（规模为m），包括随机位置和速度。 2、评价每个微粒的适应度 3、寻找每个微粒的pbest 4、寻找到目前为止的gbest 5、调整(更新)各微粒的速度和位置 6、未达到结束条件则转到2 迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。 群体规模m一般取2040，对较难或特定类别的问题可取到100200,

5、13,其中，C1,C2为正常数，称为加速因子；rand( )为0，1之间的随机数； w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。 w大则全局寻优能力强，局部寻优能力弱。w小则反之。实验发现，动态改变w效果可能更好,惯性系数,14,目前采用较多的是线性递减权值（linearly decreasing weight,LDW)策略： w(t) = (wini - wend)(Gk-t)/Gk + wend Gk为最大进化代数，wini为初始惯性权值，wend为迭代至最大代数时惯性权值。典型取值为：wini= 0.9,

6、 wend = 0.4. t是当前代数,惯性系数,15,PSO算法的特点,1）PSO算法搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，具有本质的并行性； （2）PSO算法采用实数进行编码，直接在问题域上进行处理，无需转换，因此算法简单，易于实现； （3）PSO算法的各粒子的移动具有随机性，可搜索不确定的复杂区域 （4）PSO算法具备有效的全局/局部搜索的平衡能力，避免早熟； （5）PSO算法在优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习能力； （6）PSO算法得到的解的质量不依赖初始点的选取，保证收敛性； （7）PSO算法可求解带离散变量的优化问题，但是对

7、离散变量的取整可能导致较大的误差,17,标准PSO算法流程,1、初始化一群微粒（规模为m），包括随机位置和速度。 2、评价每个微粒的适应度 3、寻找每个微粒的pbest 4、寻找到目前为止的gbest 5、调整(更新)各微粒的速度和位置 6、未达到结束条件则转到2 迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。 群体规模m一般取2040，对较难或特定类别的问题可取到100200,c1 = 1.49445; c2 = 1.49445; maxgen=300; % 进化次数 sizepop=20; %种群规模 Vmax=0.5; Vmin=-0.5; popmax=2; popmin=

8、-2; for i=1:sizepop pop(i,:)=2*rands(1,2); %初始种群 V(i,:)=0.5*rands(1,2); %初始化速度 %计算适应度 fitness(i)=fun(pop(i,:); %染色体的适应度 end, 个体极值和群体极值 bestfitness bestindex=max(fitness); zbest=pop(bestindex,:); %全局最佳 gbest=pop; %个体最佳 fitnessgbest=fitness; %个体最佳适应度值 fitnesszbest=bestfitness; %全局最佳适应度值, 迭代寻优 for i=1:

9、maxgen for j=1:sizepop %速度更新 V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:) + c2*rand*(zbest - pop(j,:); V(j,find(V(j,:)Vmax)=Vmax; V(j,find(V(j,:)popmax)=popmax; pop(j,find(pop(j,:)popmin)=popmin; %适应度值 fitness(j)=fun(pop(j,:); end,for j=1:sizepop %个体最优更新 if fitness(j) fitnessgbest(j) gbest(j,:)

10、= pop(j,:); fitnessgbest(j) = fitness(j); end %群体最优更新 if fitness(j) fitnesszbest zbest = pop(j,:); fitnesszbest = fitness(j); end end yy(i)=fitnesszbest,22,目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置,子群,23,Note,合理解,目前最優解,區域最佳解,全域,區域,24,鸟群觅食行为,Food,Global Best Solution,Past

11、Best Solution,25,26,标准PSO算法流程,1、初始化一群微粒（规模为m），包括随机位置和速度。 2、评价每个微粒的适应度 3、寻找每个微粒的pbest 4、寻找到目前为止的gbest 5、调整(更新)各微粒的速度和位置 6、未达到结束条件则转到2 迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。 群体规模m一般取2040，对较难或特定类别的问题可取到100200,27,其中，C1,C2为正常数，称为加速因子；rand( )为0，1之间的随机数； w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitatio

12、n)。 w大则全局寻优能力强，局部寻优能力弱。w小则反之。实验发现，动态改变w效果可能更好,惯性系数,28,目前采用较多的是线性递减权值（linearly decreasing weight,LDW)策略： w(t) = (wini - wend)(Gk-t)/Gk + wend Gk为最大进化代数，wini为初始惯性权值，wend为迭代至最大代数时惯性权值。典型取值为：wini= 0.9, wend = 0.4. t是当前代数,惯性系数,29,车辆路径问题,车辆路径问题(Vehicle Routing Problem，VRP)由Dantzig和Ramser于1959年首次提出的，它是指对一系

13、列发货点(或收货点)，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件的情况下，达到一定的目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于NP完全问题，在运筹、计算机、物流、管理等学科均有重要意义,30,车辆路径问题,如何找到一个合适的表达（部分）解的方法，使粒子与解对应，是实现算法的关键难点之一,31,车辆路径问题,构造一个2L维的空间对应有L个发货点任务的VRP问题，每个发货点任务对应两维：完成该任务车辆的编号k，该任务在k车行驶路径中的次序r 为表达和计算方便，将每个粒子对应的2L维向量X分成两个L维向量：Xv (表示各任务对应的车辆)和Xr(表示各任务在对应的车辆路径

14、中的执行次序,32,例如，设VRP问题中发货点任务数为7，车辆数为3，若某粒子的位置向量X为： 发货点任务号: 1 2 3 4 5 6 7 Xv ： 1 2 2 2 2 3 3 Xr ： 1 4 3 1 2 2 1 则该粒子对应解路径为： 车1：0 1 0 车2：0 4 5 3 2 0 车3：0 7 6 0 粒子速度向量V与之对应表示为Vv和Vr,33,该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过程计算大大减少。虽然该表示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在

15、实验结果中可以看到,34,VRP问题为整数规划问题，因此在算法实现过程中要做相应修改。具体实现步骤如下： Step1：初始化粒子群。 1.1 粒子群划分成若干个两两相互重叠的相邻子群； 1.2 每个粒子位置向量Xv的每一维随机取1K（车辆数）之间的整数，Xr的每一维随机取1L(发货点任务数)之间的实数； 1.3 每个速度向量Vv的每一维随机取-(K-1)(K-1)（车辆数）之间的整数，Vr的每一维随机取-(L-1)(L-1)之间的实数； 1.4 用评价函数Eval评价所有粒子； 1.5 将初始评价值作为个体历史最优解Pi，并寻找各子群内的最优解Pl和总群体内最优解Pg,35,Step2：重复执

16、行以下步骤，直到满足终止条件或达到最大迭代次数。 2.1 对每一个粒子，按式(1)计算v、r；按照式(2)计算Xv、Xr，其中Xv向上取整；当、X超过其范围时按边界取值； 2.2 用评价函数Eval评价所有粒子； 2.3 若某个粒子的当前评价值优于其历史最优评价值，则记当前评价值为该历史最优评价值，同时将当前位置向量记为该粒子历史最优位置Pi; 2.4 寻找当前各相邻子群内最优和总群体内最优解，若优于历史最优解则更新Pl 、Pg。对于子群内有多个体同为最优值的情况，则随机取其中一个为子群内当前最优解,36,其中，评价函数Eval完成以下任务: 1、根据公式计算该粒子所代表路径方案的行驶成本Z，

17、在计算中发货点任务的执行次序要根据对应Xr值的大小顺序，由小到大执行。 2、将Xr按执行顺序进行重新整数序规范。例如，某粒子迭代一次后结果如下： Xv ：1 2 2 2 2 3 3 Xr ：5 3.2 6.2 1.2 2.5 0.5 4.2 评价后重新规范的Xr是：1 3 4 1 2 1 2 说明：对于整数序规范的理解请观察对车辆2的排序和整理结果,37,实验：问题为一个有7个发货点任务的车辆路径问题，各任务点的坐标及货运量见下表,38,GA参数：群体规模n=40；交叉概率Pc=0.6；变异概率Pm=0.2；轮盘赌法选择子代，最大代数200。 PSO参数：粒子数n=40；分为2个子群，子群规模

18、为22，子群间重叠的粒子数为2个（子群规模的1/10）；w=0.729；c1=c2=1.49445；最大代数200。 两种方法各运行50次，结果如下表所示,39,带时间窗车辆路径问题,带时间窗的车辆路径问题(Vehicle Routing Problem With Time Windows, VRPTW)是在VRP问题上加了客户要求访问的时间窗口（时间段）。由于在现实生活中许多问题都可以归结为VRPTW问题来处理(如邮政投递、火车及公共汽车的调度等)，其处理的好坏将直接影响到企业的服务质量,所以对它的研究越来越受到人们的重视。先后出现了一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智

19、能化启发式算法，也取得了一些较好的效果,40,带时间窗车辆路径问题,时间窗车辆路径问题一般描述为：有一个中心仓库，拥有车K辆，容量分别为qk (k=1,.,K)；现有L个发货点运输任务需要完成，以1,L表示。 第i个发货点的货运量为gi (i=1,L)，( max(gi)max(qi) )，完成发货点i 任务需要的时间(装贷或卸货)表示为Ti，且任务i且必须在时间窗口ETi , LTi完成，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始时间。 如果车辆到达发货点i的时间早于ETi，则车辆需在i处等待；如果车辆到达时间晚于LTi，任务i将被延迟进行。 pE为在某地点等待的单位

20、时间成本，pL为在某地点未完成任务的罚金。 求满足货运要求的运行费用最少的车辆行驶线路,41,容量约束,为地点i运货的卡车只能有一辆,如果kj为1，有且仅有1个i去往j,卡车k从i驶向j,如果ki为1，从i出发的弧段有一个为1,cij表示地点i和j之间路径上的行驶代价，xijk表示为卡车k从i驶向j，yki表示表示编号为k的车为地点i发货，si表示第i个地点的开始卸货的时间，pE表示管理者认为由于提前到达某个地点而未完成任务所导致的损失大小，pL表示管理者认为由于晚到某个地点而未完成任务所带来的损失大小，其中(2)号约束表示每辆车k的运货总量gi*yki应该小于该车的容量qk。（3）和（8）决

21、定为地点i运货的卡车只能有一辆 （4）表示：如果卡车k为地点j送货，那么它只能从1.L中的1个且仅1个地点出发驶向j。（5）表示如果卡车k为地点i运货，那么卡车k应该离开地点i,43,实验2，采用VRPTW的例子，该问题有8项货物运输任务，货物点位置及时间窗略。实验结果如下,44,Particle Swarm研究热点,IEEE TRANSACTION ON EVOLUTIONARY COMPUTION于2004年出版了第3卷：SPECIAL ISSUE ON PSO。Russell C.Eberhart, Yuhui Shi在卷首语中指出了当前PSO研究的几个主要方向及热点： 1 算法分析； 2 粒子群拓扑结构； 3 参数选择与优化； 4 与其他演化计算的融合； 5 应用,动态拓扑的粒子群