粒子群算法

粒子群算法23Reynolds,Heppner,Grenader等发现，鸟群在行进过程中会突然同步地改变方向，散开或聚集。一定有种潜在的规则在起作用，据此他们提出了对鸟群行为的模拟。在他们的早期模型中，仅仅依赖个体间距的操作，即群体的同步是个体之间努力保持最优距离的结果。41987年Reynolds对鸟群社会系统的仿真研究，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。作为CAS实例5Kennedy和Eberhart在CAS中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。6鸟群觅食行为FoodGlobalBestSolutionPastBestSolution7算法介绍PSO算法是一种进化计算技术（evolutionarycomputation)，由Eberhart博士和Kennedy博士于1995年提出（KennedyJ,EberhartR.Particleswarmoptimization.ProceedingsofIEEEInternationalConferenceonNeuralNetworks.1995,1942~1948).其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。基本PSO算法每个粒子在n维空间中，位置表示为矢量飞行速度表示为矢量𝑋𝑖=(𝑥1,𝑥2,...𝑥𝑛𝑉𝑖=(𝑣1,𝑣2,...𝑣𝑛9基本PSO算法PSO初始化为一群随机粒子（随机解）。然后通过迭代寻找最优解。每次迭代中，粒子通过跟踪两个极值（pbest：某个粒子到现在为止发现的最好位置。gbest:整个群体到目前为止发现的最好位置）来更新自己。更新的公式如下：（1）速度更新：(2)位置更新：其中c1和c2是学习因子(加速因子)，通常取c1=c2=2,rand()为[0，1]之间的随机数；在每一维，粒子都有一个最大限制速度Vmax。应将Vi限制在[-Vmax,Vmax]之间。𝑋𝑖=𝑋𝑖+𝑉𝑖𝑉𝑖=𝑉𝑖+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖10基本PSO算法𝑋𝑖(𝑡+1=𝑋𝑖(𝑡+𝑉𝑖(t+1)𝑉𝑖(𝑡+1=𝑉𝑖(𝑡+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖(𝑡+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖(𝑡𝑉𝑖=𝑉+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖𝑋𝑖=𝑋+𝑉𝑖111998年shi等人在进化计算的国际会议上发表了一篇论文《amodifiedparticleswarmoptimizer》对前面的公式进行了修正，引入了惯性权重因子：𝜔非负，称惯性因子，𝜔较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。𝑉𝑖=𝜔×𝑉𝑖+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖12标准PSO算法流程：1、初始化一群微粒（规模为m），包括随机位置和速度。2、评价每个微粒的适应度3、寻找每个微粒的pbest4、寻找到目前为止的gbest5、调整(更新)各微粒的速度和位置6、未达到结束条件则转到2迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。群体规模m一般取20~40，对较难或特定类别的问题可取到100~20013其中，C1,C2为正常数，称为加速因子；rand()为[0，1]之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。w大则全局寻优能力强，局部寻优能力弱。w小则反之。实验发现，动态改变w效果可能更好。惯性系数𝑉𝑖=𝜔×𝑉𝑖+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖14目前采用较多的是线性递减权值（linearlydecreasingweight,LDW)策略：w(t)=(wini-wend)(Gk-t)/Gk+wendGk为最大进化代数，wini为初始惯性权值，wend为迭代至最大代数时惯性权值。典型取值为：wini=0.9,wend=0.4.t是当前代数。惯性系数15PSO算法的特点（1）PSO算法搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，具有本质的并行性；（2）PSO算法采用实数进行编码，直接在问题域上进行处理，无需转换，因此算法简单，易于实现；（3）PSO算法的各粒子的移动具有随机性，可搜索不确定的复杂区域（4）PSO算法具备有效的全局/局部搜索的平衡能力，避免早熟；（5）PSO算法在优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习能力；（6）PSO算法得到的解的质量不依赖初始点的选取，保证收敛性；（7）PSO算法可求解带离散变量的优化问题，但是对离散变量的取整可能导致较大的误差17标准PSO算法流程：1、初始化一群微粒（规模为m），包括随机位置和速度。2、评价每个微粒的适应度3、寻找每个微粒的pbest4、寻找到目前为止的gbest5、调整(更新)各微粒的速度和位置6、未达到结束条件则转到2迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。群体规模m一般取20~40，对较难或特定类别的问题可取到100~200c1=1.49445;c2=1.49445;maxgen=300;%进化次数sizepop=20;%种群规模Vmax=0.5;Vmin=-0.5;popmax=2;popmin=-2;fori=1:sizepoppop(i,:)=2*rands(1,2);%初始种群V(i,:)=0.5*rands(1,2);%初始化速度%计算适应度fitness(i)=fun(pop(i,:));%染色体的适应度end%%个体极值和群体极值[bestfitnessbestindex]=max(fitness);zbest=pop(bestindex,:);%全局最佳gbest=pop;%个体最佳fitnessgbest=fitness;%个体最佳适应度值fitnesszbest=bestfitness;%全局最佳适应度值%%迭代寻优fori=1:maxgenforj=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,:)Vmin))=Vmin;%种群更新pop(j,:)=pop(j,:)+V(j,:);pop(j,find(pop(j,:)popmax))=popmax;pop(j,find(pop(j,:)popmin))=popmin;%适应度值fitness(j)=fun(pop(j,:));endforj=1:sizepop%个体最优更新iffitness(j)fitnessgbest(j)gbest(j,:)=pop(j,:);fitnessgbest(j)=fitness(j);end%群体最优更新iffitness(j)fitnesszbestzbest=pop(j,:);fitnesszbest=fitness(j);endendyy(i)=fitnesszbest;22目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置子群23Note合理解目前最優解區域最佳解全域區域24鸟群觅食行为FoodGlobalBestSolutionPastBestSolution251998年shi等人在进化计算的国际会议上发表了一篇论文《amodifiedpartilceswarmoptimizer》对前面的公式进行了修正，引入了惯性权重因子：𝜔非负，称惯性因子，𝜔较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。𝑉𝑖=𝜔×𝑉𝑖+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖26标准PSO算法流程：1、初始化一群微粒（规模为m），包括随机位置和速度。2、评价每个微粒的适应度3、寻找每个微粒的pbest4、寻找到目前为止的gbest5、调整(更新)各微粒的速度和位置6、未达到结束条件则转到2迭代终止条件一般选为最大迭代次数或（和）误差满足预定阈值。群体规模m一般取20~40，对较难或特定类别的问题可取到100~20027其中，C1,C2为正常数，称为加速因子；rand()为[0，1]之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。w大则全局寻优能力强，局部寻优能力弱。w小则反之。实验发现，动态改变w效果可能更好。惯性系数𝑉𝑖=𝜔×𝑉𝑖+𝑐1×𝑟𝑎𝑛𝑑(×(𝑝𝑏𝑒𝑠𝑡𝑖−𝑋𝑖+𝑐2×𝑟𝑎𝑛𝑑(×(𝑔𝑏𝑒𝑠𝑡−𝑋𝑖28目前采用较多的是线性递减权值（linearlydecreasingweight,LDW)策略：w(t)=(wini-wend)(Gk-t)/Gk+wendGk为最大进化代数，wini为初始惯性权值，wend为迭代至最大代数时惯性权值。典型取值为：wini=0.9,wend=0.4.t是当前代数。惯性系数29车辆路径问题车辆路径问题(VehicleRoutingProblem，VRP)由Dantzig和Ramser于1959年首次提出的，它是指对一系列发货点(或收货点)，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件的情况下，达到一定的目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于NP完全问题，在运筹、计算机、物流、管理等学科均有重要意义。30车辆路径问题如何找到一个合适的表达（部分）解的方法，使粒子与解对应，是实现算法的关键难点之一。31车辆路径问题构造一个2L维的空间对应有L个发货点任务的VRP问题，每个发货点任务对应两维：完成该任务车辆的编号k，该任务在k车行驶路径中的次序r为表达和计算方便，将每个粒子对应的2L维向量X分成两个L维向量：Xv(表示各任务对应的车辆)和Xr(表示各任务在对应的车辆路径中的执行次序)。32例如，设VRP问题中发货点任务数为7，车辆数为3，若某粒子的位置向量X为：发货点任务号:1234567Xv：1222233Xr：1431221则该粒子对应解路径为：车1：010车2：045320车3：0760粒子速度向量V与之对应表示为Vv和Vr。33该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过程计算大大减少。虽然该表示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到。34VRP问题为整数规划问题，因此在算法实现过程中要做相应修改。具体实现步骤如下：