面向利用率的矩形排样分级进化遗传算法优化

冯建云，刘 祎

（1.山西建筑职业技术学院计算机工程系，山西 太原 030600；2.宿迁学院，江苏 宿迁 223800）

1 引言

生产物流中包括发料、下料和配送等步骤，其中下料的合理性极大地影响生产活动进程。排样是下料部门的核心工作，好的排样方案可以减小余料的浪费、减少无效的搬运、降低生产成本等［1］。然而，目前排样还多处于人工排样阶段，不仅极大地依赖个人经验，而且对大规模排样几乎无法实现。因此，研究矩形件的智能排样问题，可以摆脱排样问题对个人的依赖，同时提高排样质量。

矩形件的排样问题可以分为定序和定位两个步骤，所谓定位是指确定矩形件在板料中的排放位置和姿态，定序是指矩形件的排入顺序。大体来讲，矩形件排样方法可以分为3类，分别为确定性算法、启发式算法和元启发算法。确定性算法包括分支界定［2］、动态规划［3］等。启发式算法又称定位算法，主要解决矩形件的放置位置和放置姿态问题，常用算法包括BL 算法、下台阶算法、最低水平线算法等［4］，这几种启发式算法使用的排序方法一般比较简单，比如基于面积减小的排入顺序、基于宽度减小的排入顺序、基于长宽比减小的排入顺序等。元启发算法是在启发式定位基础上，对矩形件的排入顺序使用智能算法进行优化，比如遗传算法、模拟退火算法等。文献［5］针对二维不规则的排样问题，模拟生物杂交过程提出了并行交叉遗传算法，经过验证此算法可以有效求解二维不规则的排样问题，提高了板材的利用律。文献［6］对矩形件排样时，综合考虑加工成本、加工时间、加工效率等指标，提出了基于粗糙集的综合价值评价方法。将板料划分为多个矩形子段，在每个子段使用动态规划算法求解最大值，得到了最优排样方案。文献［7］为了解决大规模矩形件排样时的耗时指数增长问题，结合最低水平线算法，提出了迁移蚁群强化学习算法，此算法的排样速度是其他智能算法排样速度的（2～6）倍，非常适用于大规模矩形件的排样问题。矩形件排样具有2个发展方向：（1）问题种类的扩展，比如“一刀切”和“零件不可旋转”等工艺约束下的排样问题；（2）排样算法的优化与深入，新算法的提出为排样问题的解决提供了更多可选方法。

这里以矩形排样为研究过程，以提高板材的使用效率为研究目标，将排样分为定位和定序两个过程执行。在定位方法，给出了一种混合定位方法；在定序方面，提出了分级进化遗传算法的定序方法，最终提高了矩形件的排样质量，减少了板材浪费。

2 二维矩形排样问题建模

2.1 问题描述

对于二维矩形件的排样问题，将其描述，如图1所示。给定一个X轴向宽度为W、Y轴向高度不限的长方形板材，将一系列已知尺寸的矩形模板R1，R2，…RN布局在此板材上，要求布局合理，所使用板材的长度最小，也即实现板材利用率最大化。

图1 矩形件排样问题描述Fig.1 Rectangle Packing Problem Description

在矩形模板排样过程中需满足以下约束条件［8］：

（1）所有矩形模板全部放置在板材范围内；

（2）任意两个矩形模板不能有面积重叠，但是允许边缘重合；

（3）应留有一定的下料间隔，这里的处理方法为：在原矩形件尺寸基础上，加上预留尺寸，得到矩形件的新尺寸，使用新尺寸的矩形件用于排样。

2.2 数学建模

为了方便建模过程的描述，首先对一些物理量进行符号说明。将矩形模板Rm的长边记为hm，短边记为wm，其左下角坐标定义为(xm，ym)。矩形存在2种放置方式，即横放和竖放，为了对矩形模板Rm的放置方式进行区分，定义一个标识参数lm。当Rm横放，即短边沿Y轴向时取lm=1；当Rm竖放，即长边沿Y轴向时取lm=-1。

当矩形模板Rm横放时，其右上角坐标为(xm+hm，ym+wm)；当矩形模板Rm竖放时，其右上角坐标为(xm+wm，ym+hm)。综合以上两种放置方式，并将标识参数lm引入到表达式中，得到矩形模板右上角坐标为：

二维矩形件排样的优化目标设置为板材的利用率最高，即板材的有效使用面积最大，为：

式中：G—目标函数；SRm—矩形模板Rm的面积；H—排样后的最高高度。

优化的约束条件为2.1 节给出的2 个约束条件，其数学描述为：

式中：(xn，yn)—异于矩形件Rm的矩形件Rn左下角坐标。

第一式和第二式保证矩形模板Rm在板材范围内，第三式保证任意两个矩形模板没有面积重叠。

3 矩形模板的混合定位算法

为了在矩形模板的定位环节实现板材使用效率的最大化，提出了最低水平线与填充算法相结合的融合算法。

3.1 传统定位方法介绍

后文对最低水平线算法和填充算法进行融合，因此首先对两种算法原理进行介绍。对于N个矩形模板R1，R2，…RN，使用最低水平线的矩形模板排入步骤为［9］：

（1）将最高轮廓初始化为板材最底端；

（2）按照排入顺序将矩形模板依次排入到板材中，从最高轮廓中选择最低的水平线尝试排入，排放过程中会出现以下两种情况：

①如果最低轮廓线的长度≥矩形件的长度，则将其横放，同时更新最低水平线；如果最低轮廓线的长度小于矩形件的长度，但是≥矩形件的宽度，则将其竖放，同时更新最低水平线；

②如果最低轮廓线的长度小于矩形件的宽度，表示该矩形件无法放入最低水平线中；此时选择次高水平线，重复步骤①和步骤②，直至将矩形模板排入；

（3）重复（2），直至将所有的矩形模板均排放完毕。

对于N个矩形模板R1，R2，…RN，使用填充算法的矩形模板排入步骤为［10］：

①按照排入顺序将矩形模板依次排入到板材中；

②初始时刻将余料集合设置为整个板材，而后每排入一个矩形模板则更新一次余料集合；

③计算待排入矩形模板的面积，从大于矩形面积的余料集合中选择面积最小的尝试排入，若能够排入则转至（5），若不能排入则转至（4）；

（4）将矩形模块尝试排入次大面积的余料中，若能排入则返回（5），不能排入则循环执行（4）；

（5）判断所有矩形是否排放完毕，若否则转至（2），若是则结束。

3.2 混合定位算法

以上两种定位算法各有优缺点，以例进行说明，如图2 所示。最低水平线算法能够得到较好的排样结果，但是矩形件排入后出现空腔时则无法再次使用，造成空腔浪费。而填充算法虽然能够有效使用空腔，但是对于矩形件在板材上方区域的排入方法欠佳。

图2 定位方法缺陷分析Fig.2 Defect Analysis of Positioning Method

为了提高板材的利用率，综合最低水平线算法和填充算法的优势，提出了基于混合算法的定位方法，实现步骤为：

（1）按照排入顺序将矩形模板依次排入到板材中；

（2）初始时刻将余料集合设置为整个板材，而后每排入一个矩形模板则更新一次余料集合；

（3）计算待排入矩形模板的面积，从大于矩形面积的余料集合中选择面积最小的尝试排入，若能够排入则转至（5），若不能排入则转至（4）；

（4）将矩形模块尝试排入次大面积的余料中，若能排入则返回（5），不能排入则循环执行（4），当排入区域确定为图2中上方区域时，调用最低水平线排入法；

（5）判断所有矩形是否排放完毕，若否则转至（2），若是则结束。

4 基于分级进化遗传算法的定序方法

在传统遗传算法中，随着算法的迭代，种群中的染色体趋于相似，交叉操作难以产生有效的进化作用，而变异操作由于概率极低也难以推动种群进化，从而使算法陷入早熟［11］。相比于算法的其他缺陷，早熟问题更加迫切的需要解决。针对这一问题这里提出了分级进化遗传算法。

4.1 分级思想与进化方法

分级进化的核心思想是：将整个种群根据适应度划分为3个层级，其中，适应度高的染色体划分为保留层级，适应度差的染色体划分为变异层级，其余适应度适中的个体划分为交叉层级。种群规模记为M，保留概率记为Ps，交叉概率记为Pc，变异概率记为Pm，要求Ps+Pc+Pm=1。则保留层级染色体数量为M×Ps，交叉层级染色体数量为M×Pc，变异层级染色体数量为M×Pm。这里设置Ps=0.2，Pc=0.7，Pm=0.1。

保留层级：本层级染色体的适应度较高，是种群中的精英个体，在变异操作中应注意保留，防止交叉和变异操作使其失去优秀的性质。因此本层级使用精英保留策略，不进行遗传操作。

交叉层级：交叉操作是算法进行搜索的关键操作，交叉层级的染色体适应度适中，经过基因段的交叉，具有提高适应度的较大潜力，因此交叉层级的进化方式为交叉操作。

变异层级：变异层级的个体适应度较低，交叉操作这种交换基因段的方式，很难使其适应度有较大提高，只能使用变异的方式产生新的基因段。因此，变异层级的进化方式为变异操作。

4.2 分级进化遗传算法原理

分级进化遗传算法的实现包括基因编码、初始化、选择、交叉、变异、基因解码等操作。

（1）基因编码。按照矩形模板面积大小降序为每个矩形件赋一个编号，则得到了（1～N）的编码序列。染色体使用十进制整数编码方式，如{1，2，…N} 表示矩形模块的排入顺序为1，2，…，N。另外矩形件排入有横放和竖放两种方式，为了进行区别对编号赋予正负号，正号表示竖放，负号表示横放。

（2）基因初始化。考虑到矩形件排样问题的特殊性，这里使用随机方法和统计修正相结合的基因初始化方法。

首先使用随机方法得到设定规模的染色体，由于交叉操作只是交换基因段，无法产生新基因，因此必须保证基因的完整性，才能够更大概率的得到最优染色体。所以随机得到的染色体还需要进行统计修正。以3个基因位的染色体为例，随机初始化得到的染色体为：

统计该种群中的基因数量分布，如表1所示。

从表中可以看出，3个基因位的6种基因中，基因-3是缺失的，无法通过交叉操作产生，因此需对初始化染色体进行修正，方法为：随机选择一个染色体的3号基因位，将其由3变化为-3，从而得到具有全基因模式的染色体种群。

（3）选择。选择必须有标准，遗传算法中选择标准即为染色体的适应度值，这里将适应度设置为模板函数的倒数，即：

染色体种群分为了3个层级，每个层级的选择方法不同。每次交叉变异操作后，从父代和子代的混合种群中选择适应度靠前的M×Ps个体作为保留层级。从适应度后续的2M×Pc个体中随机选择M×Pc个体作为交叉层级。从适应度靠后的2M×Pm个体中随机选择M×Pm个体作为变异层级。

（4）交叉。矩形模板排样问题的特殊性在于，同一染色体中不同出现编号一致的基因位，也即同一个矩形模板不能在同一排序中出现2 次。因此若使用普通的交叉算子，在交叉操作后还需要进行编码重复性检验和调整。为了规避这一繁琐过程，这里使用环形交叉算子［12］。对环形交叉算子执行步骤进行介绍，如图3所示。

图3 环形交叉算子Fig.3 Annular Crossover Operator

环形交叉算子的方法为：随机选择一个基因位，以第1基因位为例，父1的第1基因位为1，对应的父2基因为5，返回父1基因为5的位置，对应的父2基因为2，重复以上步骤直至形成闭环，得到闭环1、5、2、4、9、1。将父1和父2的环形基因位保留，其余基因位进行交叉，得到子代染色体1和2。

（5）变异。变异操作是获得新基因片段、实现染色体适应度快速提升的根本方法，这里使用交换变异和旋转变异两种变异方法。交换变异是指从染色体中随机选择2个基因位，并将此2个基因位进行交换，即可得到变异后的染色体，如图4（a）所示。旋转变异是指随机选择1个基因位，将其进行符号变换，即可实现旋转变异，如图4（b）所示。对某一染色体执行变异操作时，随机选择一种变异方式执行。

图4 变异算子Fig.4 Mutation Operator

（6）基因解码。基因解码是基因编码的逆过程，即根据优化后的排入顺序将矩形模板排入到板材中，具体解码方法前文，这里不再赘述。

4.3 基于多级进化遗传算法的排样流程

依据多级进化遗传算法的工作流程和矩形模板的混合排入方法，制定矩形件的排样流程为：

（1）初始化算法参数，包括子群规模、最大进化代数；

（2）使用随机方式和统计修正的方法初始化染色体，

（3）对染色体进行排序和分级；

（4）保留层级、交叉层级、变异层级按照各自的方式进行进化；

（5）判断算法是否达到最大迭代次数，若否则转至（3）；若是则输出最优染色体；

（6）对最优染色体解码，得到最优排样方案。

5 实验验证及分析

为了对混合定位算法和基于分级进化遗传算法的定序方法进行验证，这里设置了2 组实验，实验1 对定位和定序的不同组合方案进行验证，实验2将这里排样方案与其他文献方案对比，并分析其随不同矩形规模的变化趋势。这里分别使用小规模排样和大规模排样两个实验进行验证。实验环境为：英特尔第四代酷睿15-4460@3.20GHz，8G 内存，win7 操作系统，使用Python语言编程。

5.1 实验一：不同定位和定序组合方案验证

本次实验的数据来源于文献［13］，待排入矩形模板为20类共59个，要求将其排入到宽为400mm的样本板料中，待排入矩形模板的部分数据，如表2所示。全部数据可参考文献［13］。

表2 实验一矩形模板参数Tab.2 Rectangular Template Parameters of Experiment 1

根据待排入矩形的规模，将染色体数量设置为100，遗传算法最大迭代次数设置为500。为了形成对比，设置以下对比方案：这里设置的混合排入与分级进化遗传算法的组合方案称为方案1；最低水平面排入与分级进化遗传算法的组合方案，称为方案2；二是混合排入法与传统遗传算法的组合方案，称为方案3；文献［13］的排样方案称为方案4。4种方案的排样统计结果，如表3所示。

表3 实验1矩形排样结果统计Tab.3 Rectangular Packing Result Statistics of Experiment 1

由于篇幅有限，在此仅给出这里提出方案的排样结果，如图5所示。

图5 实验1矩形的最优排样结果Fig.5 Optimal Packing Result of Rectangular of Experiment 1

结合表3和图5可知，这里设计的方案1好于方案（2～4），这是因为方案1使用了混合定位算法和分级进化遗传算法的组合方案。方案2使用最低水平线排入法，与方案1的混合定位法相比，方案2无法有效使用“空腔”部分，造成板料空腔区域的浪费。方案3使用传统遗传算法的定序方法，经前文分析可知，传统遗传算法容易出现早熟的问题，也即难以搜索到最优的排入顺序。方案4使用的是传统遗传算法定序和最低水平线定位法，此方案的定序和定位算法均差于其他方案，因此方案4的板材利用率最低。综上所述，在小规模矩形排样中，这里提出的混合定位方法与分级进化遗传算法的定序方法可以得到较好的排样结果。

5.2 实验二：算法性能随规模变化验证

本次实验的数据来源于文献［14］，数据来源为4组国际通用算例，分别命名为Q1～Q4。4组算例中均包含3种矩形件，同一算例中每种矩形件的尺寸相同且固定。算例存在最优解，材料的最佳利用率均为100%。4组算例的设置参数如表4所示，表中板料宽度即为板料的固定宽度，板料最低高度即为完成排样后所需的板料最小高度，其他未给出参数可从文献［14］中查找。

表4 实验二矩形模板参数Tab.4 Rectangular Template Parameters of Experiment 2

将这里设置的排样方法与文献［14］的排样方法进行对比。文献［14］中包含启发式排样和元启发排样两种方法，分别记为方法1和方法2。文献［14］排样方法与这里方法的排样统计结果，如表5所示。为了更加直观地展示排样结果，使用柱状图展示各方案的排样结果与最优结果的差值、排样方案耗时，如图6所示。

表5 实验二排样结果Tab.5 Packing Result of Experiment 2

图6 实验2的排样结果统计Fig.6 Packing Result Statistics of Experiment 2

结合表5和图6可知，文献［14］中的方法1排样结果较差，与最优高度的差值最大，这是因为此方案使用了启发式排样方法，但是对于排入顺序未经优化，只是根据面积大小确定排入顺序，因此排样效果较差；从时间上看，由于没有排序优化过程，算法耗时较小。文献［14］中的方法2排样质量居中，能够得到较好的排样方法，这是因为在此方法中使用了智能算法对矩形排入顺序进行了优化，但是由于算法搜索能力一般，使得顺序优化程度不足；从时间上，智能算法对排序的优化过程耗时较大。这里提出了方案排样质量最好，其规划高度与最优高度差值极小，而且算法耗时较少，这是因为分级进化遗传算法使用了分层级方法，各层级染色体使用各自的进化操作，提高了算法的优化能力，同时减少了算法耗时，而且随着矩形规模的增大，方法2的耗时急剧增大，这里所提方法的耗时略有增大，但是能够保持较低的耗时水平。因此这里提出的排样方案耗时最少且排样结果最佳。

6 结论

这里研究了矩形件的排样优化问题，分为定序和定位两个步骤实现。对于定位，将最低水平线和填充算法融合，给出了混合定位方法。对于定序，提出了分级进化遗传算法的排序方法，经对比验证，这里提供的排样方案可以得到较好的排样结果，且排样过程耗时较少。