基于并行遗传算法的矩形件排样优化*

隗平平，刘 斌

(华侨大学机电与自动化学院，福建 厦门 361021)

0 引言

排样优化普遍存在于钣金、钢结构、航空、船舶、服装、皮革和纸制品以及玻璃加工等行业生产过程中，是制造业自动化中从设计到板料切割过程中的一个关键环节。排样优化是指在给定规格的原材料上，互不重叠地尽可能多地排放各种形状的待排零件，使原材料的利用率最高。因此，实现排样优化将最大限度地节约材料，提高工业生产效率，具有重要的现实意义。

在数学计算复杂性理论上，排样优化问题属于NP完全问题。对于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者求解的计算量是爆炸性的。

矩形件排样优化是排样优化问题中较为基础的一类问题，近几十年来，国内外众多学者都是以矩形件排样优化问题为基础，深入研究各种不规则零件的排样问题。到目前已经提出多种切实可行的用于排样优化的近似算法［1-7］。Baker等人在1980年最早提出了最下最左(bottom-left，BL)算法［1-2］，之后的一些学者在 BL 算法的基础上进行了改进，提出了基于BL的填充(bottomleft filling，BLF)算法［3］、下台阶算法［4］及最低水平线法［5］等排样算法。随着智能优化算法的日益成熟及其在TSP问题、空间分配等组合优化问题上的成功应用，遗传算法(GA)［2-5］、模拟退火算法(SA)［6］、粒子群算法(PSO)［7］等优化算法与以上排样算法相结合，广泛应用于矩形件排样问题的求解，并取得了很好的效果。

文献［2］研究了矩形件正交排样的遗传算法求解，其基本思想是将个体的编码视作一个排列，通过BL(Bottom Left)算法将编码转化为相应的排样图。但是，BL算法并不能求解某些问题的最优排样图。如图1所示的排样图显然是一个最优排样图，但用BL算法，即使穷举出所有的个体编码，也不能得到此最优排样图。文献［4］对BL算法做了改进，提出了“下台阶”算法。文献［5］在前二者的基础上做了进一步的改进，提出了“最低水平线”算法。本文对最低水平线算法进行了改进，克服了其存在过多空洞的缺陷。同时，对遗传算法进行了并行性改进，较好地维持了种群多样性，提高了算法的搜索效率。将这两个改进后的编解码算法相结合用于矩形件排样问题的求解，更好的解决了将编码个体转化为较优排样图的解码问题，从而能够快速高效得到最优排样结果。

图1 8个矩形构成的最优排样图［5］

1 前提条件

这里，为了编程方便有效，设置矩形件排样需要满足以下前提条件:

(1)板材宽度W一定，高度理论上无限高，这里设定为一个较高的常量H;

(2)矩形件数量有限，设为n;

(3)排样满足BL原则，即每一个排入矩形件不得超出板材范围(W×H范围内)，也不得与其他已排入矩形相干涉，排入过程中尽量向下向左移动，直至不能再移动为止。

2 遗传编码

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方式不同，遗传算子的运算形式也不同。

本文采用十进制编码方式，染色体长度与待排零件数n相同，染色体中每个基因对应着一个零件编号。把所有零件的编号按排放顺序排列成串，即构成一条染色体(一个个体):P={p1，p2，…，pn}，相对应的表现为一种排样图。其中，pi为整数，有正负之分，且1≤|pi|≤n，表示零件的编号，pi为负值时表示零件作90度旋转后再排放。通过交叉和变异操作改变pi的顺序和正负号，就改变了零件的排放顺序和排放方向，从而产生出不同的排样图。

3 解码排样算法

遗传算法产生一个个体编码P={p1，p2，…，pn}后，能否快速地对其进行解码，转化为对应的排样图，得到所需板材的高度是又一个关键点。因为，只有求得该个体对应的排样图后，才能计算其适应度值，对该个体进行评价，从而实现遗传优化。

基于“最左最下”的BL原则，文献［2］采用了BL算法。文献［4］对文献［2］中的BL算法进行了改进，提出了下台阶算法。文献［5］在此基础上进一步提出了最低水平线算法。

再进一步分析最低水平线算法发现，虽然最低水平线法优于前两种算法，但其仍存在缺陷——该算法思想是只要发现零件的宽度大于最低水平线的宽度，就马上将这段水平线提升，而不管后面是否有零件可以放到该段水平线上，这样就造成了过多的板材空洞，大大降低了算法的效率。针对这一缺陷，对于编码个体 P={p1，p2，…，pi，…，pj，…，pn}，1 ＜ |pi|＜ |pj|＜ n，本文引进脏区标志DF(DF=0表示板材中未排入的区域，DF=1表示板材中已排入区域)，提出如下基于最低水平线的改进算法:

Step1:设置初始板材脏区标志为DF=0，并设置初始零件最高轮廓线和板材最低水平线为板材底边。

Step2:每当要排入一个零件pi时，就对前面已排入的i-1个零件按其在板材中定位后矩形上边界的y值从小到大排序，每个y值对应一条水平线，这些水平线与板材以及其中已排零件相交，得到一个脏区标志DF=0的水平线段组集合HLineSet，其中高度y相等的为一个水平线段组HLine，每组包含若干条水平线段Segment，这些线段按左端点x值从小到大顺序存储在水平线段组中。首先选取最低水平线段组的第一条线段(即最左边的一段)，测试该线段的宽度是否大于或等于要排入零件的宽度:

(1)如果该线段的宽度大于或等于要排入零件pi的宽度，则将该零件在此位置排放，设置该零件排放区域脏区标志DF=1，更新零件最高轮廓线，并清空当前水平线段组集合，准备排入下一个零件。

(2)如果该线段的宽度小于要排入零件pi的宽度，从零件pi所在位置起向后搜索合适排入的零件，即在{pi+1，…，pj，…，pn}中搜索:

①如果有零件pj的宽度恰好等于该段水平线的宽度w，则将零件pj插入到pi之前排入，此时个体编码更新为 P={p1，p2，…，pj，pi，…，pj-1，pj+1，…，pn}，设置该零件排放区域脏区标志DF=1，并更新零件最高轮廓线，清空当前水平线段组集合;

②如果没有宽度相等的零件，则在{pi+1，…，pj，…，pn}中搜索到零件宽度小于w的第一个零件pj，将零件pj插入到pi之前并排入，设置该零件排放区域脏区标志DF=1，更新个体编码和零件最高轮廓线，并清空当前水平线段组集合;

③如果没有找到可以排入的零件，则选择最低水平线段组中下一条线段进行上述判断。若最低水平线段组中所有线段均再找不到能够排入的零件，则将最低水平线段组提升为其在当前水平线段组集合中的下一个线段组，再次进行上述判断。

重复Step2，直至能排入该零件。

重复上述过程，直至所有零件排放完毕。

对于个体编码 P={1，-2，3，4，5，-6，7，-8}，采用该算法的排样过程如图2所示。初始时最低水平线段为板材底边，排入1后，当前水平线段组集合HLine-Set中包含两个高度的水平线段组lowline和Hline1，都只有一条线段(如图a)。零件2的宽度小于lowline组的线段，直接排入到该线段上(如图b)，更新水平线段组集合，同样排入零件3(如图c)。在排入零件4前，检测到其宽度大于lowline线段宽度，所以暂时不排入4，向后搜索到零件6的宽度恰好等于lowline线段宽度，先排入零件6(如图d)。更新水平线集合后准备继续重排零件4(如图e)，此时，当前最低水平线组中有两条线段lowline1和lowline2，分别比较零件4和这两条线段的宽度发现，零件4的宽度大于lowline1的宽度而小于lowline2的宽度，向后搜索得到零件5可以排入lowline1处(如图 f)，同时确定零件4的排放位置在lowline2线段处(如图g)。更新水平线组集合。排入零件7之前再次判断，发现零件7的宽度大于当前最低水平线组中的两条线段lowline1和lowline2的宽度，则暂缓排入零件7，向后搜索发现零件8可以在lowline2处排入，先排入零件8(如图h)。更新水平线组集合，在lowline处排入零件7(如图i)。

图2 改进算法的排样示意图

图3显示了分别进行最低水平线算法和改进算法后所得到的排样图的差异。

图3 最低水平线算法与其改进算法的排样图比较

4 适应度函数

遗传算法对一个解的好坏用适应度函数值大小来评价，适宜度值越大，解的质量越好。本文采用与文献［4］相同的适应度函数:

其中，H(P)=H-h(P)，h(P)为排样高度，H为事先设定的板材高度值，其值应确保使H(P)的值为正。Area为可再利用余料的面积，W是板材的宽度，h(P)×W为排样高度以下矩形板材的面积。

5 基于遗传算法排样的求解过程

步骤1:初始化种群

设定遗传代数的计数器t=0，对n个待排零件的序号进行数学的排列组合随机产生3m个编码个体，构成初始种群。

步骤2:解码评价适应度

遗传算法经过对种群中个体进行选择，交叉，变异操作后，需要对新一代种群进行适应度评价，适应度值的计算就需要对染色体进行解码，即将染色体串还原为零件在板材上的排布图。本文采用基于最低水平线的改进算法进行解码求出当前种群中每个染色体的适应度函数值，并将其按适应度函数值由大到小排序。

步骤3:选择算子

对3m个个体构成的初始种群(此时t=0)，根据个体适应度函数值由大到小排序，选择排在前面的m个个体构成第一代操作种群。同时记忆适应度函数值最大的个体为精英个体并保存。

对于第t代种群的m个个体，按适应度函数值大小，进行“轮盘赌”方式的比例选择［2］。然后进行精英保留:记忆当前代适应度值最大和最小个体，用上一代保存的精英个体替换当前代适应度值最小个体。同时判断当前代适应度最大个体是否优于上一代精英个体，若是则改变精英个体为当前代适应度值最大个体，否则不改变。

步骤4:交叉算子

对进行了选择运算的当前种群中的m个个体以概率Pc随机的两两配对，进行交叉运算，产生m个个体构成的子代种群。

本文采用的交叉方法是单点交叉和双点交叉两种。这里以随机数0或者1来决定采用哪种交叉方法。交叉后所产生的子个体与父个体一起接受适应度评价，选择适应度值大的两个个体替代原父代个体。设两个交叉的个体分别为 P={p1，p2，…，pn}和Q={q1，q2，…，qn}，则单点交叉具体过程为:在1到n范围内随机生成一个交叉位k，将P中前k个元素拷贝到子代个体Poffspring中作为前面的元素，剩余的元素从Q中第k+1位开始遍历Q中所有元素，拷贝与目前Poffspring中没有的元素到Poffspring中，从而产生了子代个体Poffspring。同样的方法可以产生另一个子代个体 Qoffspring。例如，P=(1，2，3，4，5，6)，Q=(6，4，2，5，3，1)，如果 k=3，则 Poffspring=(1，2，3，5，6，4)，Qoffspring=(6，4，2，5，1，3)。而双点交叉具体过程为:在1到n范围内随机生成两个交叉位p和q，从P中将位于p和q之间的元素拷贝到子代个体中作为前面的元素，剩余的元素按在Q中出现的先后顺序拷贝至子代个体中，从而产生了子代个体Poffspring。同样的方法可以产生另一个子代个体Qoffspring。例如，P=(1，2，3，4，5，6)，Q=(6，4，2，5，3，1)，如果 p=2，q=4，则 Poffspring=(2，3，4，6，5，1)，Qoffspring=(4，2，5，1，3，6)。

步骤5::变异算子

对进行了交叉操作后产生的m个子代个体，本文先后进行两种变异。第一种是旋转变异，以概率Pm1随机选取染色体中任意一个位置k，变异该位置零件的旋转标志，使零件旋转90度。第二种是位置变异，其包括位置互换变异和位置倒序变异两种。这里以随机数0或者1来决定采用哪种位置变异方式。以较小的概率Pm2，在1到n范围内随机产生两个整数k1，k2，对当前个体中位于k1，k2的两个零件对调即为位置互换变异，对当前个体中位于k1，k2之间的零件顺序反向即为位置倒序变异。

步骤6:停止准则

可以设定停止准则为最大繁殖代数MAXGEN，也可以设定为排样利用率达到某一预定阀值U。本文设定两种停止准则来验证算法效果。准则1:最大进化代数MAXGEN=2000时停止;准则2:排样利用率U＞90%时停止。

重复执行上述遗传操作(选择，交叉，变异)，直到最好解的适应度值达到设定的要求或最大进化代数，则终止进化，输出最优个体及其对应的排样图。遗传算法流程如图4所示。

图4 遗传算法流程图

6 算例

为了测试算法的性能，本文对文献［2］中的两个算例进行了求解。

算例1将一个15×40的大矩形分成25个小矩形，如图5所示，显然我们已知了问题的最优解，按本文算法排样可写出其最优排列顺序为Popt={1，-9，11，-15，17，-24，-25，-10，-14，-22，-23，-2，-3，-5，18，7，-8，-12，19，-20，21，6，16，13，4}。现以宽度为40，高度为25的板材为例，求最小排样高度。文献［2］在第2000代终止时得到的高度为17，用本文算法，在群体规模与文献［2］同样为m=20的情况下，取交叉概率Pc=0.8，旋转变异概率Pm1=0.15，位置变异概率Pm2=0.25，当停止准则为准则1时，求得的最好结果为16，用时4分10秒左右。如图6所示。当停止准则为准则2时，求得的最好结果为16，出现在第1代，用时5秒左右。如图7所示。

图5 25个矩形的最优排样图

算例2.将同样的一个15×40的大矩形分成50个小矩形，如图8所示。该最优解的编码序为Popt={-1，2，-14，-16，-23，-24，-27，-28，30，-49，-50，29，-47，-48，22，-25，-26，3，5，-11，-13，15，-31，32，21，45，46，4，12，18，20，-33，34，-38，42，43，44，6，-9，-10，-39，-40，-41，17，-35，36，7，8，19，37}。现以宽度为40，高度为25的板材为例，求最小排样高度。文献［2］在第2000代终止时得到的高度为17，用本文算法，在群体规模与文献［2］同样为m=20的情况下，取交叉概率Pc=0.8，旋转变异概率Pm1=0.15，位置变异概率Pm2=0.25，当停止准则为准则1时，求得的最好结果为16，用时6分8秒左右。如图9所示。当停止准则为准则2时，则在进化到第3代时即得到满足要求的最好结果16，用时19秒左右。如图10所示。

图8 50个矩形的最优排样图

7 结束语

本文讨论了矩形件排样问题的遗传算法求解，首先对解码排样算法进行了研究分析，对已有算法进行了改进，提出了“基于最低水平线的改进算法”。然后在编码优化算法方面，对文献中的遗传算法进行了并行性改进，融合了多种遗传算子的操作结果，实现了多个种群间的协同进化，从而较好地维持了群体的多样性，增强了算法的搜索效率。从两个算例分析结果可以看出，本文算法是快速有效的，但对于一个已知的最优排样图，还是不能将其快速求出。这一点仍有待于今后作进一步的研究和改进。

［1］R.Baker，E.G.Coffman，and R.L.Rivest.Orthogonal packings in two dimensions［J］.SIAM Journal on Computing，1980，9(4):846-855.

［2］Stefan Jakobs.On genetic algorithms for the packing of polygons［J］.European Journal of Operational Research，1996，88:165-181.

［3］Hopper E，Turton B.A Genetic Algorithm for a 2D Industrial Packing Problem［J］.Computers and Industrial Engineering.1999，37(1-2):375-378.

［4］刘德全，滕弘飞.矩形件排样问题的遗传算法求解［J］.小型微型计算机系统，1998，19(12):20-25.

［5］贾志欣，殷国富，罗阳.二维不规则零件排样问题的遗传算法求解［J］.计算机辅助设计与图形学学报，2002，14(5):467-470.

［6］贾志欣，殷国富，罗阳，等.矩形件排样的模拟退火算法求解［J］. 四川大学学报，2001，33(5):35-38.

［7］宋佩华，蒋联源，欧启忠.基于离散粒子群优化算法求解矩形件排样问题［J］.计算机应用与软件，2008，25(1):238-240.