改进粒子群算法在二维排样中的研究与应用
2016-07-07陈建军
董 辉，陈建军
(浙江工业大学 信息工程学院，浙江 杭州 310023)
改进粒子群算法在二维排样中的研究与应用
董辉，陈建军
(浙江工业大学 信息工程学院，浙江 杭州 310023)
摘要：针对服装行业二维不规则样片优化排样问题，提出了一种改进的粒子群优化排样方法.该算法在传统的粒子群优化算法中先引入小生境的思想，将种群划分成多个子群，各子群运用粒子群算法单独进化，取出各子群进化后的最好粒子，又可形成新群体，新群体运用混合蛙跳算法进化，使子群的最好粒子进一步更新，种群的多样性进一步增强，全局寻优的能力进一步提升.该算法概念简单，易于实现，具有较好的能力去搜索全局最优解和较快的收敛速度.实验结果表明该算法是有效的.
关键词：小生境；粒子群；混合蛙跳；排样
服装行业二维不规则样片的优化排样问题就是在指定大小区域的材料上，寻找一种将很多不规则形状的样片最优的排布方案，所有样片排放位置都互不重叠，样片排放组合紧凑、密集，剩余有效材料越多，材料利用率就越高，排样方案则越优.二维不规则件优化排样问题在服装制造行业中长期存在，也频繁的出现在如机器人、金属、玻璃、木材和船舶等行业中.由于服装总是大批量的生产，特别是服装材料成本价格越来越高，提高一点点材料利用率就可以节省大量材料，产生庞大的经济价值，具有长远的现实意义[1].粒子群算法(Particle swarm optimization，PSO)简单易实现，它所具备得参数个数少、收敛速度快等优点，使得它频繁的应用于模糊系统控制、组合优化、复杂函数求解及机器人路径规划等相关领域.可是，粒子群算法同样也存在不少问题，如对解的搜索精度不高；容易过早收敛和对参数值的影响大.为了解决这些问题，很多学者改进了经典的PSO方法.有些是对粒子群的一些依赖参数做出优化[2-5]，如对惯性权重w和学习因子c1，c2进行调节[6]；还有引入其他算法的思想和粒子群算法相融合[7-9]，比如量子粒子群融合算法[7]、免疫粒子群融合算法[8]及遗传粒子群融合算法[9]等.这些改进的PSO算法虽然具有一定的效果，但使算法概念更加复杂，实现困然，而且仍然克服不了在求解优化排样问题时搜索精度不高和易陷入局部最优解的缺陷.为此提出了一种改进的粒子群优化算法——基于小生境粒子群和混合蛙跳的融合算法(NPSO-SFLA).
新算法中，在传统的粒子群优化算法中先引入小生境[10]的思想，为了解决粒子群算法容易过早收敛、陷入局部最优的问题，将种群划分成多个子群，各子群运用粒子群算法单独进化，使种群多样性增多以避免局部最优.然后，取出各子群进化后的最好粒子，又可形成新群体，新群体运用混合蛙跳算法进化，使子群的最好粒子进一步更新，种群的多样性进一步增强，全局寻优的能力进一步提升.两种算法的结合相得益彰，有效的解决粒子群算法容易陷入局部最优和混合蛙跳算法收敛速度慢也易陷入局部最优的问题.排样实例表明了该方法的有效性.
1排样技术
1.1排样方法
提出了一种改进的粒子群算法来搜索最佳的排样组合，采用文献[11-12]提出的BL(Bottom left)算法进行样片的底层排样.
BL算法基本排样策略：每一个待排样片都先放置在材料的右上角，以材料的右上角为基准点向材料的左下角移动，最初一直向下移动样片，然后一直向左移动样片，直到待排样片向下或向左都不能移动时停止即两个方向都接触到其它已排样片或材料边界，记录下当前的排样高度；重复以上过程，当所有的待排样片都排入时停止，最后所得的最大高度即排样高度记为H.
1.2样片的几何表达
样片的几何形状同排样的利用率密切相关，由于服装行业的样片形状各异而且复杂，若将此样片直接作为排样对象，会使排样问题更加复杂，从而直接影响排样的效果.通常将不规则件排样近似为矩形件来处理，但是未能充分考虑二维不规则样片形状的各异，导致不能充分的利用材料.本方法采用文献[13]提出的一种离散的几何处理方法，能够完全克服二维不规则样片形状高度复杂性的影响，简化排样复杂度从而得到更好的排样效果.二维不规则样片和指定大小的材料区间可以看成由很多坐标形成的直线区域所组成，所以就可以将它们的几何区域转化为一系列坐标区间，从而简化排样的复杂度.
基本思想：每个待排样片所形成的轮廓都是一个不规则的多边形，从该多边形的最低点开始，以某种等距离的水平线去扫描该多边形，水平线与多边形会形成两个或两个以上的交点(顶点时记为两个)，记录下这些交点，一直向上扫描，直到该多边形的最高点结束.这些交点按大小顺序排列，同一水平线上的点两两可组成很多线段区间，所有水平线段区间所形成的区域可看作该样片的区域，扫描距离越小，所形成的离散的几何区间精度越高.此处扫描距离取1 mm，即精度值为1 mm.
1.3个体适应度评价
对于排样问题，本方法取排样图的高度的倒数作为适应度的评价，即适应度函数为F=1/H，其中H是排样图的高度，故H越小，F越大，排样效率越佳.
2粒子群算法和蛙跳算法
2.1经典粒子群算法
PSO算法是1995年由Eberhart和Kennedy[14]提出的一种种群优化算法，该算法可描述如下：D维的搜索空间(即D个待排样片)，种群的大小N(即粒子个数)，种群中第i个粒子的位置xi=
vin(d+1)=w×vin(d)+c1×r1×[pin-xin(d)]+
c2×r2×[gn-xin(d)]
(1)
xin(d+1)=xin(d)+vin(d+1)
(2)
式中：i=(1,2,…,N)；n=(1,2,…,D)；d为迭代次数；c1，c2分别为各项的学习因子；r1，r2都是在0到1之间随机取值；惯性权重w随迭代次数线性递减：w=wmax-wmind/T,wmax，wmin分别为设置的最大值和最小值；xin(d)和vin(d)分别为粒子i当前的位置和速度；xin(d+1)和vin(d+1)分别为粒子i更新后的位置和速度；T为最大迭代次数.
2.2混合蛙跳算法
混合蛙跳算法(SFLA)是2003年由Eusuff和Lanset[15]提出的一种群体进化算法.其基本思想为：青蛙群体被划分为若干个子群，各子群以自己的意识各自单独进化，此时种群进化基于各子群的局部搜索，当子群达到迭代次数以后，各子群再进行混合运算以达到进行全局交流的目的，这个过程一直进行，直至达到退出条件，则停止.各子群先局部搜索，再全局混合信息交流的策略能够有效地跳出局部极值，去寻找到全局最优.
该算法数学模型可描述如下：D维搜索空间中，初始群体P只青蛙，P只青蛙表示有P个解，则第i个解xi=
dj=r×(xb-xw)
(3)
xw,new=xw,old+dj(dmin≤dj≤dmax)
(4)
式中：dj为最差青蛙在第i维移动的距离；r在0到1之间随机取值；xw,new和xw,old分别为族群中最差解的新值和旧值；dmin和dmax分别为移动距离的最小值和最大值.更新过后，比较新解和旧解的适应度值，如果有改进，则用新解代替旧解，并更新族群内xb，xw，xg；如果没有改进，则用xg代替式(3)中的xb，再次执行式(3，4)，如果仍无改进，则随机用一个新解去代替旧解xw,old.重复执行，达到最大迭代次数时结束.当各个族群的都执行完局部搜索，再将所有族群重新混合，并重新划分族群，各个族群重新执行局部搜索，反复迭代，直到满足条件结束.
3改进粒子群算法(NPSO-SFLA)
3.1算法实现
首先在PSO中引入小生境的思想，将粒子初始种群分成Cnum组大小相等的子群(即小生境)，计算种群所有粒子的欧式几何距离[17]，并按从小到大的顺序排列，依序逐一分成Cnum组子群，各子群运用粒子群算法单独进化，取出各子群进化后的最好粒子，形成新群体，新群体运用混合蛙跳算法进化，进一步寻找最好粒子.混合蛙跳模式的进化，使得各子群最好粒子能有机会进一步更新自己，不仅能提高种群多样性，而且能进一步寻优.混合蛙跳算法的引入，增强了全局寻优的能力，把它在子群进化后得到的最好粒子反馈到粒子群的速度更新公式中，从而克服PSO容易过早收敛、陷入局部最优的问题.
新算法的速度和位置更新公式分别为
vin(d+1)=w×vin(d)+c1×r1×[pin-xin(d)]+
c2×r2[gin-xin(d)]+c3×
r3[xb,sfla-xin(d)]
(5)
xin(d+1)=xin(d)+vin(d+1)
(6)
式中：gin为粒子群第i组的全局最优值；r3为0～1之间的随机数；c3为第四项的学习因子；xb,sfla为蛙跳算法得到的最好粒子.相比于式(1)，式(5)中右边第三项改为了子群的最优解，增加了右边第4项，蛙跳算法得到的全局最优粒子的反馈.新公式保留了粒子个体的自身速度、历史最优位置的影响，变化为各子群局部最优粒子的作用，加入了全局最优粒子的反馈，使得局部和全局的信息得到充分的交流，能有力的跳出局部最优解，使全局寻优的能力进一步提升.
3.2算法流程
改进粒子群算法(NPSO-SFLA)具体流程如下：
1) 初始化整个粒子群的初始位置与速度，设置相关参数.
2) 根据粒子的欧式几何距离将粒子分成Cnum组，每组P个粒子.
3) 使用式(5，6)更新每个粒子的速度与位置.
4) 使用BL算法进行排样，计算粒子适应度值F.
5) 根据F更新粒子的个体最优解pin，各组的全局最优解gin.
6) 将各组的全局最优解gin组成蛙群，计算适应度值并进行排序分族，分为M族，每族N个.
7) 蛙群按照式(3，4)更新粒子，找出最优解xb,sfla.
8) 比较子群在连续n代内的最优解是否有更好，若有，则跳到步骤10)；否则执行步骤9).
9) 重置该子群的位置与速度.
10) 迭代次数n=n+1，若n等于最大迭代次数T，则执行结束；否则转到步骤3)继续执行.
4实验结果及分析
实验环境：硬件配置为Intel酷睿i3 370 M，主频2.40 GHz，内存为5 GB；软件配置为Windows7 64位操作系统，VC 2008软件开发平台.本方法选择了一个宽1 200 mm，长度不限的矩形材料作为排样的底板，排放20个任意形状的服装样片.采取与经典PSO算法进行实验结果比较，对NPSO-SFLA算法的性能进行测试，两者采用一样的参数设置.算法参数设置如下：最大迭代次数为500次，惯性因子wmax，wmin分别设为0.9，0.5，学习因子c1，c2，c3都取值为2，种群大小为30个粒子，NPSO-SFLA算法分6个子群，每个子群由5个粒子组成，蛙跳分为2组，每组3个粒子，蛙跳族内迭代10次，样片的旋转角度以90度为基本单位.同样环境下，两种算法各自运行100次，两者的结果对比如表1所示.
表1 PSO与NPSO-SFLA的实验结果对比
表1中，比较两者平均排样高度可得出NPSO-SFLA收敛精度更优；新算法的H标准偏差也较小，说明NPSO-SFLA算法的稳定性好，新算法的平均收敛代数较低，说明NPSO-SFLA算法的收敛速度更快；比较平均收敛代数和标准偏差可得出NPSO-SFLA具有更强的全局搜索能力；从两者的最差和最好排样高度比较可知新提出的NPSO-SFLA都明显要优于PSO；比较两者的排样时间，NPSO-SFLA的耗时比经典的PSO多，这是由于加入蛙跳的进化而增加的运行时间.
图1(a)中，NPSO-SFLA排样高度为947 mm，图1(b)中，PSO排样高度为955 mm，新算法排样效果更好，材料利用率更高.图2中，NPSO-SFLA在380代收敛于排样高度947 mm，PSO在421代收敛于排样高度955 mm，新算法更快的找到最优解，从表1中两中算法的平均收敛代数比较可知：新算法收敛更快，体现出NPSO-SFLA更佳的收敛性能.
图1 两种排样算法最佳效果图Fig.1 The best layout chart by two algorithm
图2 两种排样算法收敛性能比较Fig.2 Convergence performance comparison by two algorithms
5结论
新提出的NPSO-SFLA算法概念简单，易于实现，粒子群算法与蛙跳算法的结合，取长补短，具有较强的搜索最优解的能力.实验结果显示新算法的排样高度明显优于标准的PSO算法，实验数据分析得出NPSO-SFLA具有较好的搜索全局最优解的能力和较快的收敛速度.结果表明：新提出的改进粒子群算法能有效解决服装行业的二维不规则样片排样问题，该算法能够有效地提高材料的利用率，给服装行业的二维不规则件优化排样问题带来新的解决方案.
参考文献：
[1]童科.群智能算法的研究与应用——基于求解矩形优化排样问题[D]. 无锡：江南大学，2011.
[2]ZHANG Y N, TENG H F. Detecting particle swarm optimization[J]. Concurrency and computation practice and experience，2009，21(4)：449-473.
[3]SOUDAN B, SAAD M. An evolutionary dynamic population size PSO implementation[C]//3rd Information and Communication Technologies: From Theory to Applications. Damascus: IEEE，2008:1-5.
[4]韩冬梅，王丽萍，吴秋花.基于模糊偏好的多目标粒子群算法在库存控制中的应用[J].浙江工业大学学报，2012，40(3)：348-351.
[5]黄太安，生佳根，徐红洋，等.一种改进的简化粒子群算法[J].计算机仿真，2013，30(2)：327-330，335.
[6]韩毅，蔡建湖，周根贵，等.线型结构批量计划问题的粒子群算法参数方案设定[J].浙江工业大学学报，2010，38(6)：683-692.
[7]黄建江，须文波，孙俊，等.量子行为粒子群优化算法的布局问题研究[J].计算机应用，2006，26(12)：3015-3018.
[8]段富，苏同芬.免疫粒子群算法的改进及应用[J].计算机应用，2010，30(7)：1883-1884，1888.
[9]SETTLES M, SOULE T. Breeding swarms: a GA /PSO hybrid[C]//GECCO 2005-Genetic and Evolutionary Computation Conference. Washington: Assoc Computing Machinery，2005：161-168.
[10]章军.小生境粒子群优化算法及其在分类器集成中的应用研究[D].合肥：中国科学技术大学，2007.
[11]SHI Yuhui, EBERHART R C. A modified particle swarm optimizer[C]//Proc IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press，1998：69-73.
[12]CHAZELLE B. The bottom-left bin-packing heuristic: an efficient implementation[J]. IEEE transactions on computers，1983，32(8)：697-707.
[13]陈勇，唐敏，童若锋，等.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报，2003，15(5)：598-603.
[14]KENNEDY J, EBERHART R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE，1995：1942-1948.
[15]EUSUFF M M, LANSEY K E. Optimization of water distribution network design using shuffled frog leaping algorithm[J]. Journal of water resources planning and management，2003，129 (3)：210-225.
[16]李俊，孙辉，史小露.多种群粒子群算法与混合蛙跳算法融合的研究[J].小型微型计算机系统，2013，34(9)：2164-2168.
[17]董辉，黄胜.二维排样中小生境粒子群算法的研究与应用[J].浙江工业大学学报，2014，42(3)：257-268.
(责任编辑：陈石平)
Research and application of an improved particle swarm algorithm in two-dimensional layout
DONG Hui, CHEN Jianjun
(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)
Abstract:An improved particle swarm algorithm is proposed to solve the optimization of two-dimensional irregular layout problem in the garment industry. In this algorithm, the niche technology is introduced to the traditional particle swarm optimization algorithm while the population is divided into multiple sub-swarms and each sub-swarm is evolved by particle swarm algorithm independently. Then the best particles in the sub-swarms are reformed into a new group and the new group can be evolved by shuffled frog leaping algorithm. This algorithm can update the best particles of sub-swarms, enhance the diversity of the population and promote the global optimization capability further. The algorithm is simple in concept and is easy to be implemented. It has better ability to search the global optimal solution and faster convergence speed. Experimental results show that the algorithm is effective.
Keywords:niche; particle swarm; shuffled frog leaping algorithm; nesting
收稿日期：2015-12-15
作者简介：董辉(1979—)，男，浙江永康人，副教授，研究方向为嵌入式系统技术及应用，E-mail：hdong@zjut.edu.cn.
中图分类号：TP391
文献标志码：A
文章编号：1006-4303(2016)04-0388-04
