改进PSO算法在二维下料问题中的研究.pdf

《改进PSO算法在二维下料问题中的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学术探讨算法研究2014年第1-2期改进PSO算法在二维下料问题中的研究张菡（菏泽学院计算机与信息工程系，山东菏泽274000）[摘要]粒子群优化（PSO）算法是一种基于集群智能的进化计算方法，在该方法中粒子通过追随自己找到的最优解和种群最优解完成优化。文章将PSO算法应用到三角形优化下料问题的研究中，给出了具体的实施流程，为了提高PSO算法的收敛精度，避免早熟现象的产生，对PSO进行了改进，提出一种启发式PSO算法。通过对三角形的优化下料进行仿真，仿真结果显示改进后的启发式粒子群优化算法在收敛效果和材料的利用率方面均有显著的提高。[关键词]二维下料；启发式搜索

2、算法；粒子群优化算法在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第1．引言一个就是粒子本身所找到的最优解，这个解叫做个体极值生产中常会遇到通过切割、剪裁、冲压等手段，将原材料pBest[11]，另一个极值是整个种群目前找到的最优解，这个极加工成所需大小的工艺过程，称为原料下料问题。具体来值是全局极值gBest[12]。设粒子i的基本信息可以用d维向量说，二维下料问题[1]就是从平面原料件切割下各式各样的下表示，位置为xi=(xi1，xi2，…xid)，速度为vi=(vi1，vi2，…vid)。在料件，确定下料排样方案，以使用料最省，利润最大，这是典迭代过

3、程中，粒子根据两个极值来调整自己的速度vi和xi位型的优化问题。由于该问题的复杂性，不同领域的专家学者置。个体极值pbest=(pbest1，pbest2，…pbestd)，全局极值从各自领域出发提出了若干个算法，目前比较常用的有遗传gbest=(gbest1，gbest2，…gbestd)，整个求解的过程实际就是不算法、演化算法等。相对于矩形下料问题，对不规则零件下断更新自己速度和位置的过程。料时，其难度要大得多。近几年的研究和实践表明，PSO算在找到这两个最优值时，粒子根据公式（1）（2）来更新自法在空间函数寻优、动态目标寻优等方面有着算法简单、容己的速度和

4、位置：易实现、收敛速度快等优点[2]，但是PSO算法在搜索后期却容v[]=v[]+c1*rand()*(pbest[]-present[])+c2*rand()*(gbest[]-易陷入局部最优值，即所谓的早熟现象，难以很好地解决二present[])(1)维下料问题[3]。本文主要研究三角下料问题，为了能在工程present[]=persent[]+v[](2)中实际应用，采用改进的PSO算法对给定的三角形零件进行v[]是粒子的速度，persent[]表示当前粒子的位置。rand排料计算，在用料最省的情况下切割出所需的三角形零件。()是介于（0，1）之间的随机

5、数。c1，c2表示学习因子，通常2．三角下料的粒子群算法c1=c2=2。在用PSO解决优化问题[9]时，种群数量一般选取20到402．1PSO算法个，对于比较难的问题或特定类别的问题，粒子数可以取到粒子群优化算法（ParticleSwarmOptimization，简称为100到200个；粒子的长度就是问题解的长度；粒子的范围由PSO）又称为微粒群优化算法，是通过模拟鸟群觅食行为而[5，9]优化问题决定，每一维可以设定不同的范围；粒子的最大速发展起来的一种基于群体协作的随机搜索算法。通常认度决定粒子在一循环中最大的移动距离，通常设为粒子的范为它是群集智能(Swa

6、rmintelligence，SI)的一种，由Eberhart和kennedy[6]博士在1995年提出。围宽度；学习因子c1=c2介于（0，4）之间。PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在2．2启发式PSO优化算法这个区域里只有一块食物。所有的鸟都不知道食物在哪里，由于PSO算法容易陷入局部最优问题以及在收敛过程但它们知道自己所处的位置与食物的距离。因此找到食物中易产生早熟现象，本文在原有的PSO算法基础上提出一种的最优策略是搜寻目前与食物最近的鸟的周围区域[7，8]。改进的算法-启发式PSO算法（HeuristicParticleSwarmOpt

7、i-PSO从这种模型中得到启示并用于解决优化问题。PSO中，mization），首先利用图形扫描转换技术把三角形转化为零件将每个优化问题的解看作搜索空间中的一只鸟，称之为“粒的离散化几何表达，然后将基于这种扫描技术的启发式搜索子”。所有的粒子都有一个由被优化的函数决定的适应值，算法（HBLS）[14]作为下料问题的底层算法，PSO算法作为顶每个粒子还有一个速度决定其运动的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。层算法，用底层算法接受顶层算法传递过来的优化参数的方PSO初始化为一群随机粒子，然后通过迭代找到最优解[9]，法来解决三角下料问题。——

8、————————————