基于自适应遗传算法的矩形排样方法研究*

单宇晗

（哈尔滨工程大学自动化学院 哈尔滨 150001）

1 引言

矩形排样问题是二维排样问题的一种，其目的是将一定数量的不同大小的矩形互不重叠的放置于一个矩形排样空间内，求得一种排样方案，使得排样空间的空间利用率最大［1］。排样问题被广泛应用于板材切割和布匹裁剪等制造业领域，通过计算机自动排样算法，能够较人工排样显著提高材料利用率，从而节约大量的成本［2～4］。

排样问题是非确定型多项式（Nondeterministic Polynomial，NP）问题的一种，理论上不能在多项式时间内得出一种解决方案［5～6］。NP 问题目前在研究领域并没有一种高效的算法可以求得其最优解，在实际中一般利用智能优化算法求出一个近似最优解。排样问题在研究领域一般从新的优化算法和新的排样模型两个方向进行研究。

本文首先建立矩形排样问题模型，应用最低水平线法放置矩形，将排样问题转化为求解矩形最优放置顺序问题。而后应用遗传算法求解矩形排样的最优排样方案，并使用改进自适应策略在基本遗传算法的基础上进行改进，以优化算法的性能。

2 矩形排样问题模型

2.1 问题模型

对于矩形件排样问题，可以设置矩形排样空间为P，长为L，宽度为W，同时存在n 个待排样矩形{Pi，i=1…n}，长度和宽度分别为li和wi，假设矩形的数量足够填满整个排样空间。根据排样问题的定义，不同矩形之间不能重叠。这时求解一种矩形的排列方式，要求放置后矩形在排样空间内所占面积最大，即为空间利用率最高。

定义排样空间的左下角为原点O（0，0），则左上角为(0，L)，右下角为(W，0)。矩形Pi的左上角顶点是，右下角顶点的坐标是(xi1+wi，yi1-li)。则根据定义可以得到矩形排样的模型如下：

约束条件：

目标函数：

2.2 最低水平线算法

对所有的矩形进行编号以后，通过最低水平线法确定待排样矩形的放置规律，能够将任何一种布列的方案都唯一表示为n个矩形{Pi，i=1…n}的一种排列组合［7～9］。

最低水平线法算法放置矩形的过程如下：

Step1：在开始时将最初的最高轮廓线设置为排样空间的下边界。

Step2：在每次放置一个矩形时，在最高轮廓线中选择高度最低的一段水平线，如果有不止一段最低，就选择最左边的水平线。判断这一段最低水平线的宽度是否大于或等于待放置的矩形的宽度，并执行以下操作：

1）如果这一段最低水平线的宽度大于或等于待放置的矩形的宽度，就将待放置的矩形放置在这个水平线的最左侧，并且更新矩形最高轮廓线。

2）如果不是，选择最低水平线两侧的两段水平线，将最低水平线设置为高度较低的一段水平线，并且更新最高轮廓线。

3）转到1），直到找到位置放置待放置的矩形。

Step3：转到Step2，直至所有的矩形放置结束。

算法的前四个矩形的放置过程如图1所示。

图1 最低水平线算法前四个矩形放置示意图

图1 （a）：放置1号矩形，放置在左下角。

图1（b）：放置2 号矩形，此时最低水平线为图中加粗线段A，可以放置2号矩形，则将其放在最低水平的最左侧。

图1（c）：放置3 号矩形，此时最低水平线为图中加粗线段B，3号矩形无法放入，则最低水平线移动至左侧加粗线段C，3号矩形长度比其长，最低水平线继续移动至加粗线段D，可以放入，则放在最低水平的最左侧。

图1（d）：放置4 号矩形，同理最初的最低水平线无法放入则最低水平线移动至其两侧较低的水平线，以此类推。

3 普通遗传算法

3.1 遗传算法

遗传算法（Genetic Algorithm，GA），是由美国密歇根大学的Holland 在1975 年提出的，遗传算法通过模拟自然选择进化过程和自然遗传机制寻找一个最优解，特点是不需要任何先验知识，不易落入局部极值［10～11］。

在遗传算法中解的集合称为“种群”，其中的解称为“个体”。将解通过一定方式进行编码，这种编码称为“染色体”，每个个体对应一个独特的染色体。解中的每一个分量的特征称为基因，这些基因构成染色体。进化过程在算法里体现在在每次迭代过程中，通过个体的适应度函数的值选择个体，并对这些个体的染色体进行“交叉”和“变异”操作，由旧种群产生新种群。种群中每个个体按照“适者生存”规则，在通过多次迭代，最后产生最优的近似解。

1）编码。在前文中将其转化为矩形在排样空间中的组合优化问题。这样以矩形的编号序列作为遗传算法的编码，并采用十进制形式的编码，即每个数字对应一个矩形的十进制编号［12］。例如矩形的放置顺序为{1，5，2，6，3，4}，表示的意义是矩形按照编号1，5，2，6，3，4 的顺序进行放置。

2）适应度函数。优化问题的目标函数代表问题的期望优化结果，排样问题的优化目标是排样空间的剩余空间最小，这里可以使用排样空间剩余面积占总面积的比例，即排样空间未利用率作为适应度函数的数值。

3）选择操作。模拟自然界中的“适者生存”的选择过程，在计算过程中一般以个体的适应度的大小为标准，适应度高的进入一代的几率较高，适应度小的进入下一的几率较小。在本文中使用轮盘赌法进行选择，对于布列问题设一共有n 个矩形，第i 个矩形的适应度大小为fi，则这个矩形被选择的概率Pi：

4）交叉操作。模拟自然界中的染色体基因重组的过程，是生成新个体的主要方式。交叉是将父代的基因进行替换重组的过程，代表着遗传算法的全局搜索能力。在本文中使用顺序交叉法，其实现步骤如下：

图2 选择交叉部分示意图

图3 生成第一个子代个体示意图

图4 生成第二个子代个体示意图

Step1：随机选择第一父染色体上的交叉部分。

(1)旱情监测数据快速处理技术。旱情遥感监测系统每天处理大量的卫星遥感数据，完成数据的自动入库。如何保证高效、稳定、自动的数据接收是系统实现的基础，海量卫星图像的快速、自动化的数据处理是系统实现的关键。实现旱情数据无人值守入库、多源数据快速处理，主要包括多机并行自动化入库、基于数据模型的质检、基于规则的数据目录动态创建、分布式并行全流程运行管理体系的引入、旱情监测数据再处理研发和数据综汇和制图表达等技术。

Step2：将第二个父染色体上和第一个染色体相同的基因去除，并将剩余基因按照原来的顺序排列。

Step3：将第二父染色体的剩余部分同第一个父染色体的交叉部分按照原来的顺便拼接成子染色体。

Step4：使用同样的方式获得第二个子染色体。

5）变异操作。变异操作模仿的是基因突变的过程，目的是增强基因的多样性同时发生变异的个体也有可能因此适应度降低过早被淘汰。在本文中实现具体表现为：随机选取染色体上的两个不同的基因进行交换。

图5 变异操作示意图

6）结束条件。在本文中使用设定最大迭代次数作为算法的终止条件。

3.2 遗传算法实现步骤

普通遗传算法的实现过程如下

Step1：开始算法，初始化遗传算法参数：最大迭代次数、初始种群大小、交叉概率、变异概率。

Step3：计算本代种群中所有的个体的适应度，并求得种群的平均适应度值和最优个体的适应度值。

Step3：判断是否达到最大迭代数，如果达到则转到Step5。

Step4：进行遗传操作：选择、交叉、变异。产生下一代种群，并转到Step3。

Step5：对最后一代种群中的最优个体进行解码，得到矩形排样的最优方案。

4 改进自适应遗传算法

普通遗传算法的交叉概率和变异概率的选择会影响算法的收敛速度和解的优秀程度。交叉概率较高会增强算法的搜索能力，但是容易使种群产生退化；较低会使算法易陷入局部最优。变异概率的存在能够保证种群的多样性，但是较高的变异概率会导致算法趋近于随机搜索。当算法中个体之间的适应度相差较大时，较低的交叉和变异概率能够保证优秀个体不被破坏；当算法趋于收敛时，种群中个体的适应度相差不明显，较高的交叉和变异概率能够提高算法的搜索能力［13］。所以通过改变算法的交叉和变异概率可以提高遗传算法的搜索能力，提高算法的性能。

自适应遗传算法相对于普通遗传算法，在执行变异和变异操作之前增加了自适应改变交叉和变异概率的过程，参与交叉或变异的个体越为优秀，其交叉和变异概率越低。但是在算法运算前期存在一定数量的优秀个体不会发生交叉或变异，会导致算法的种群多样性降低，影响算法的搜索能力［14～15］。

可以将整个运算过程分为两个部分：在第i 代之前执行固定的交叉概率m1和变异概率m2，这样保证存在足够多的个体发生交叉和变异，从而保证种群的多样性；在第i 代之后执行自适应交叉概率Pc和变异概率Pm，这样能够根据当前种群的实际环境自适应调节概率，从而提高算法的性能。

对于自适应策略，根据当前种群平均适应度favg、最大适应度fmax和每个个体的适应度fi计算自适应交叉和变异概率，其公式如下：

自适应交叉概率Pc：

其中fc为发生交叉的两个个体适应度较高的适应度的大小，k1和k2为0～1的常数，且k1≥k2。

自适应变异概率Pm：

其中fm为当前变异个体的适应度的大小，k3和k4为0～1的常数，且k3≥k4。

5 仿真和结果分析

应用自适应遗传算法求解矩形排样，在Mat⁃lab2012a环境下进行仿真，并进行结果分析。

在仿真中需要根据排样空间面积需要提供足够数量的待排样矩形以布满整个排样空间。这里使用六种型号的矩形参与排样。设置参与排样的不同型号矩形的尺寸如表1所示。

表1 排样用矩形尺寸

5.1 普通遗传算法和改进自适应遗传算法仿真

设置遗传算法的种群大小为100，最大迭代次数为100 代，固定交叉概率m1取值为0.9，固定变异概率m2取值为为0.1；自适应遗传算法的i 取值为40代，k1和k2取值为0.95，k3和k4的取值为0.2。

表2 排样空间尺寸和适应度对比

普通遗传算法和自适应遗传算法的排样方案图和适应度收敛曲线分别如图6～9。

图6 普通遗传算法排样方案

图7 自适应遗传算法排样方案

图8 普通遗传算法收敛曲线

图9 改进自适应遗传算法收敛曲线

从仿真结果可以看到两种算法都能够得到一个较为优秀的排样方案。改进自适应遗传算法的排样空间未利用率为0.0162 较普通遗传算法的0.0201 低，即自适应遗传算法得解较为优秀，可以证明应用改进自适应策略能够提高遗传算法的性能，即其对应的排样方案的空间未利用率更低。

5.2 改进自适应遗传算法的其它算例

表3 两种算例的排样空间尺寸和适应度

图10 算例一排样方案

图11 算例二排样方案

从以上的仿真可以看到本文中求解矩形排样的方案能够有效地求解不同尺寸排样空间情况下的最优排样方案，可以证明本文中方法的可行性和普遍适用性。

6 结语

本文提出了一种将自适应遗传算法应用于求解矩形排样问题的方法，提供了一种可行的高性能的求解方法，能够求得一种排样空间面积利用率最高的排样方案。通过仿真可以证明，将改进自适应遗传算法应用于矩形排样问题的求解，能够较普通遗传算法得到一种更优秀的解，最终的排样方案的空间未利用率能够达到较低的水平。通过对不同的算例进行仿真，可以证明本文中求解矩形排样的方案的可行性和普遍适用性。本文通过将改进自适应策略应用于遗传算法，增强了算法全局搜索能力，使其在优化性能上得到提升，但是并未改变遗传算法计算量较大，计算时间较长的缺点。在今后的研究中，需要在算法计算速度方面进行改进，以改善算法的计算效率。