离散粒子群算法在矩形排样问题上的应用研究

陈 钊

(安徽职业技术学院 实训中心，安徽 合肥 230011)

关键字： 离散粒子群算法；矩形排样；组合优化；

矩形件优化排样是在给定的板材上将待排矩形件按照最优方式进行排布, 以便最大限度地利用材料, 其实质就是一个组合优化的二维布局问题, 但至今仍无法找到解决该问题的有效多项式时间算法。对于矩形优化排样问题的研究，主要有启发式算法的研究、基于人工智能算法的研究以及基于运筹学方法的研究，都取得了很多成果。近年来，基于人工智能算法对于排样问题的研究是现在和未来研究的重点。

1 问题描述

粒子群优化算法( Particle Swarm Optimization) 是由Kennedy 和Eberhart[1，2]于1995 年在鸟群、鱼群和人类社会行为规律的启发下提出的一种基于群智能的演化计算技术。他们提出了PSO算法的离散二进制版，但这只是在对经典连续性PSO问题的针对性修改，并没有考虑到离散型问题组合优化的特点。Clerc[3]提出的DPSO算法，说明了解决离散型问题的关键在于对于问题域的定义及其对于PSO算法相关的数学对象和运算规则的定义。钟一文等[4]利用DPSO很好的解决了TSP问题。针对矩形优化排样问题，由于排样序列不是连续的序列而是一串不重复且属于一定范围内的离散型序列，因此属于离散型组合优化问题。本文通过固定的排样规则(剩余矩形排样法)将原本复杂的二维排样问题转换成为可以求解组合优化的问题，对离散粒子群算法进行了改进，根据所求解问题及离散量运算的特点，对粒子的位置、速度等量及其运算规则进行了重新定义，取得了很好的结果。

2 建立解决问题模型

2.1 下料规则(剩余矩形排样法)

本文采用的是剩余矩形排样法，构造了三个矩形链表，分别为剩余矩形链表、待排矩形链表、已排矩形链表。任何没有被排样的空间，都在矩形链表中表示。形成方法如下：

(1)初始剩余矩形链表中仅有一个矩形，即母板(0，Height，Width，0)。

(2)从待排矩形链表中取出一个矩形，同时删除该结点。在剩余矩形集合中找到一个能放下该矩形件的剩余矩形，将该矩形件放置在剩余矩形的左下角(满足BL条件)，将位置记录并加入已排矩形链表，同时剩余矩形链表中每个剩余矩形都减去该矩形所占的位置，形成新的剩余矩形，如下图所示，切割后形成两个剩余矩形R1和R2，它们有共同的重合部分(虚线部分)。

剩余矩形排样法排样示意图

(3)由于新的剩余矩形的产生，会引起原剩余矩形链表的改变，因此对其(虚线部分)进行调整：去掉面积为零的或已无法排下的所剩的任何一个矩形件的剩余矩形；去掉和已排矩形有相交关系的剩余矩形；把具有完全包含关系的剩余矩形中面积小的矩形去除、有相交关系的矩形全部保留。得到新的剩余矩形集合，为下一次排样使用。

(4)当待排链表非空时，转到第2步继续进行排样。如空则结束排样，计算出板材利用率。

2.2 矩形排样问题的数学模型

根据上述排样规则，可以总结本文研究的矩形排样问题的目标函数和约束条件为：

(1)

(2)

3 改进离散粒子群算法

Clerc说明了解决离散型问题的关键在于对问题域的定义及PSO算法相关的数学对象和运算规则的定义，包括：粒子的位置表示；粒子的速度表示；位置与速度的加法运算规则；位置的减法运算规则；速度的加法和乘法运算规则。本文对于离散粒子群算法进行重新定义，如下：

(1)粒子的位置表示。粒子的位置X定义为一个整数序列X =(x1，x2, x3,……,xn)，1≤i≤n,1≤Xi≤n。并且序列中所有成员不能重复并且属于1-n(n为待排矩形件零件的个数),表示为待排矩形零件的排样顺序。Xi的值为待排矩形零件的编号，表示为编号为Xi的零件的排样顺序为i。例如：X = (3，2，1，4，5)就是一个位置，x1= 3表示编号为3的零件的排样顺序为1即第一个排。

(2)粒子的速度表示。粒子的速度定义为一个整数序列V = (v1,v2,v3,……，vn)，1≤i≤n,1≤Vi≤n。同样序列中所有成员不能重复并且属于1-n,表示为一个交换序列。Vi 的值为该位置Xi交换对象的坐标。例如：V = (2，3，1，4，5)就是一个速度，v1= 2表示为x1的交换对象为x2。

(3)位置与速度的加法运算规则。位置与速度相加得到一个新的位置，X’= X + V ，即：

(3)

式(3)说明，如果Vi=i的话Xi不变，否则，Xi 与Xvi 交换。该交换序列从第1位到第n位依次进行交换，循环执行，交换的次数为vi≠i的个数。例如：X =(3，2，1，4，5),V = (2，3，1，4，5)则X + V = (3，1，2，4，5)。

(4)位置的减法运算规则。俩个位置相减得到一个速度，V=X′-X，即:

X′i-Xi=j;X'j=Xi

(4)

式(4)说明，X′-X得到为Xi在X’中的下标。例如：X =(3，2，1，4，5),V = (2，

3，1，4，5)则X - V = (2，1，3，4，5)。

(5)速度的加法和乘法运算规则。两个速度的相加即为两个交换序列的相加，相加的规则和X + V类似。其中，Rand()为一个在0和1范围之内的随机数；V为以一定概率保留。

(5)

速度的乘法运算为

(6)

(6)粒子的运动方程。通过以上的定义，可以将经典的PSO算法的公式改为：

V’ =V+C1*(Xpbest-X) +C2*(Xgbest-X)；

(7)

X’=X+V；

(8)

其中，惯性权值W=1，C1和C2为学习因子设为2。

4 实验及结果分析

(1)实验数据。该算法采用C++编写，经算法仿真数据的经典算例，算例一为25个矩形的排样问题：将15*40的矩形分成25个小矩形进行排样。算例二为50个矩形的排样问题：将15*40的矩形分成50个小矩形进行排样。

(2)参数设置。两个算例的参数设置均为：W=1，C1=C2=2，初始种群的粒子数为100个，迭代终止条件为运行100代。

(3)实验结果。算例一的实验结果为高度15，宽度42，板材利用率为95.24%，对比结果如表1所示；算例二的实验结果为高度15，宽度42，板材利用率为95.24%，对比结果如表2所示。

表1 25矩形排样问题

表2 50矩形排样问题

实验结果对比显示本文提出的算法所求得的最优解要优于宋佩华等人[5]的离散粒子群算法，李满江等人[6]与王竹婷[7]提出的遗传算法所求得的最优解，材料利用率更是达到了95%以上，说明了本文提出的改进离散粒子群算法的有效性和先进性。