基于自适应遗传模拟退火算法的矩形件排样

夏以冲，陈秋莲，宋仁坤

广西大学 计算机与电子信息学院，南宁 530004

1 引言

矩形件排样是指将一定种类和数量的矩形件排放在一个宽度固定、长度不限的矩形板材中，以有效利用板材。矩形件排样优化在现代制造、加工行业中应用非常广泛，比如各类板材的下料、加工等，是制造业自动化从设计到下料过程的关键环节，是二维排样问题中广泛研究的一类排样优化问题。

矩形件排样问题的求解包括两方面：矩形件的定序和定位。其中，定序确定待排样矩形件的排入顺序，定位确定矩形件在板材上的摆放位置。在实际应用中，通常采用遗传算法[1-3]、模拟退火算法[4]等作为定序算法，IBL算法[5]、最低水平线算法[6]等作为定位算法。蒋兴波等[7]提出了一种基于环形交叉和变异算子的自适应遗传算法，通过IBL算法定位，能在较短时间得到满意的解。Liu等[8]提出基于分阶段遗传算子的改进遗传算法，与最低水平线排放策略相结合，有效解决矩形件排样问题。李明等[9]在遗传算法中引入小生境技术，通过排挤与淘汰机制维持种群的多样性，采用高度调整法定位，取得较好的排样效果。

遗传算法具有较强的全局搜索能力，但存在过早收敛，易陷入局部最优，适应性较差等缺点。模拟退火算法具有较强的局部搜索能力，但是每一时刻仅保存一个解，缺乏历史搜索信息，不能很好地把握搜索过程，收敛速度慢。本文将自适应遗传算法和模拟退火算法结合作为定序算法，以启发式最低水平线择优排放策略进行定位，求解矩形件优化排样问题。

2 问题描述及数学模型

矩形件排样问题可以描述为：将n个矩形件{p1,p2,…,pn}排入到一个宽度为W，高度不限的板材中，在满足约束条件的情况下，使得板材利用率最高。需要满足的约束条件包括：（1）pi与 pj互不重叠，i≠j；（2）pi排入时不能超过板材边界；（3）pi的边必须与板材的边平行，可以90°旋转。

矩形件pi(i=1,2,…,n)可以用五元组表示：pi=(xi,yi,wi,hi,θi)。其中，(xi,yi)表示其左下角坐标；(wi,hi)表示宽度和高度；θi表示旋转角度，θi∈{0°,90°}。

板材的利用率F定义为矩形件的面积之和与所用板材面积之比。矩形件优化排样问题的数学模型如下：

其中，H为所用板材的高度。因此，矩形件优化排样问题可以描述为：寻求满足约束条件的最佳排样方案，使得板材的利用率F最大。

3 算法设计

3.1 算法流程

本文以自适应遗传和模拟退火算法相结合作为矩形件的定序算法，以启发式最低水平线择优算法作为定位算法。首先是遗传算法，个体采用整数编码，通过经验选择与随机生成相结合的方式构造初始种群。运用启发式最低水平线择优算法进行解码，计算个体的适应值。然后采用精英选择和轮盘赌相结合的策略进行选择，剩余个体进行自适应交叉和变异。最后对所有个体进行模拟退火，并更新最优个体。重复遗传操作和模拟退火，直到迭代次数等于最大代数。迭代过程中产生的最优个体所对应的排样方案为最终排样方案。算法流程如图1所示。

3.2 算法描述

3.2.1 编码

矩形件优化排样采用整数编码，对n个矩形件{p1,p2,…,pn}分别用整数1,2,…,n进行编号，得到一个染色体编码X={x1,x2,…,xn}。其中表示第i个排入板材的矩形件编号取正数时，矩形件不旋转，即θi=0°；xi取负数时，矩形件旋转，即θi=90°。

图1 基于自适应遗传模拟退火算法流程图

3.2.2 构造初始种群

采用经验选择与随机生成相结合的策略构造初始种群，将矩形件按面积降序排序，面积相等时根据长边长度递减排序，产生一个整数有序序列。对序列中的每个整数随机添加正负号，形成一个个体。重复N次随机添加正负号过程，得到规模为N的初始种群。

3.2.3 计算适应值

整数编码的个体需解码得到对应排样图，计算板材利用率，求出适应值。本文解码算法采用启发式最低水平线择优算法，在文献[10]的最低水平线择优策略基础上引入启发式判断，实现可用空洞区域填充，具体步骤如下：

（1）初始化最高轮廓线集合，其仅包含板材的底部边界。

（2）排入矩形件 pi时，在最高轮廓线集合中选取最低的一段水平线，若该段宽度可排，则 pi靠左排放，并更新最高轮廓线集合，否则，转入步骤（3）。

（3）搜索剩余矩形件序列，选取与最低水平线宽度相同的矩形件（如有数个，选择最高者），插入 pi所在位置再排入，并更新最高轮廓线集合。若当前最低水平线无可排矩形件，则与相邻最低的轮廓线合并，同时更新最高轮廓线集合，转入步骤（2）。

表1 初始参数设置

（4）重复上述过程，直到所有矩形件排放完毕，得到个体的排样图。

3.2.4 遗传算子

（1）选择算子：采用精英保留和轮盘赌相结合的策略，将适应值最高的父代种群个体直接保留至下一代，剩余的N-1个个体以轮盘赌方式进行选择。避免父代最优个体丢失，同时保证适应值高的个体有更多机会保留至下一代，提高全局的收敛性和计算效率。

（2）交叉算子：采用环形交叉，交叉的基因可以环绕整个染色体两端来进行，而不仅仅集中在染色体中间部分，每个基因被选中的概率相等，有利于提高算法的全局搜索能力。

经典遗传算法的交叉概率为0到1之间的某个固定值，无法灵活协调收敛速度与搜索能力[11]。本文采用自适应交叉概率Pc，若个体适应值低于种群平均适应值，则选择较大的交叉概率，增加产生新个体的可能，扩大搜索范围。若适应值高于种群平均适应值，则根据当前个体适应值动态减小交叉概率，有利于优秀个体保留至下一代。

式中，Favg为当前种群的平均适应值；Fmax为最大适应值；Facross为两个交叉个体的较大适应值；Pc1、Pc2为预先设定的0到1之间的固定值。交叉阶段生成一个0到1之间的随机数r，若r＜Pc，则执行环形交叉；否则不执行。

（3）变异算子：采用自适应变异概率Pm的交换变异和旋转变异相结合的策略，若个体适应值低于种群的平均适应值，则选择较大的变异概率，提高算法的局部随机搜索能力，有助于维持种群的多样性。若适应值高于种群平均适应值，则自适应减少变异概率，以免破坏优秀个体。

式中，Fmutate为变异个体的适应值；Pm1、Pm2为预先设定的0到1之间的固定值。变异阶段生成一个0到1之间的随机数r，若r＜Pm，执行变异操作；否则不执行。执行变异操作时，生成一个0到1之间的随机数k，若k＜0.5，采用交换变异；否则采用旋转变异。

3.2.5 模拟退火

遗传算法容易陷入局部最优解，本文将遗传算法与模拟退火算法相结合，以增强算法的局部搜索能力。对遗传操作后的所有个体以状态产生函数生成新个体，按预定的接受概率替换旧个体，最终得到的N个个体构成下一代种群。理论上只要初始温度足够高，退火过程足够慢，算法就能收敛到全局最优。

（1）设置初始温度：初始温度T0应足够高，以满足新个体接受概率为1的初始要求，即Tk=T0时，有，需，显然无法实现。实际应用中，只需保证设置的T0使得新个体接受概率趋近于1即可。

（2）状态产生函数：在个体Xi中随机选择两个不同的基因位k、m，对k、m之间（包括k、m）的基因进行逆序操作。假设Xi={4,-3,1,5,-2,6},k=2,m=5,则通过状态产生函数生成新个体Xi'={4,-2,5,1,-3,6}。

（3）新个体接受概率：计算新个体Xi'的适应值F(Xi')，若新个体更优，即 F(Xi')≥F(Xi)，则用 Xi'替换Xi；若F(Xi')＜F(Xi),依照如下接受概率用Xi'替换Xi：

（4）降温函数：采用等比降温函数Tk+1=αTk，其中α为降温系数，且α∈(0,1)。α的取值与初始温度T0有关，若取值过大会导致收敛过慢，若取值过小会导致降温过快而无法求得最优解。因此在设定α的取值时，需综合考虑算法求解效果和收敛速度。

4 实验分析

取文献[12]提供的一组实验数据进行对比测试。算例中包含20种不同尺寸的矩形件，共59个，板材宽度为400。本文的自适应遗传模拟退火算法初始参数设置如表1所示。

本文与文献[12]和文献[8]的优化结果对比如表2所示。其中文献[12]和文献[8]分别采用结合最低水平线的经典遗传算法和基于分阶段遗传算子的改进遗传算法进行排样优化。算法运行50次，得到的平均利用率为表中的平均值，最高利用率为最佳值。本文平均值和最佳值均高于文献[12]和文献[8]。

表2 算法的利用率对比 %

图2为本文算法进化500代时的最佳排样图，其适应值为95.21%，高度为336。

图2 算法进化500代时的最佳排样图

为进一步验证本文算法求解问题的有效性，采用文献[13]提供的21个算例，每个算例由一张已知规格（宽为W，高为Hopt）的板材分割为若干矩形件（无废料）生成。依据板材规格将算例分为7组，分别用C1～C7表示，每组由3个不同算例组成，如表3所示。由分割方式可知板材高度Hopt为最优排样高度，算例要求将n个矩形件排入宽度为W高度不限的板材中，计算最小排样高度H*。算例具体数据参阅文献[13]。

表3 算例数据

定义最小排样高度H*到最优排样高度Hopt的相对距离g=(H*-Hopt)/Hopt作为评价标准，若g越小，表明计算得到的H*越接近Hopt，算法的优化效果越好。本文对每个算例计算30次，取最好结果，每组算例的平均相对距离gaverage如表4所示，平均计算时间haverage如表5所示。

由表4可知，本文算法的gaverage比文献[13]算法1降低2.55%,比算法2降低1.98%，比文献[14]降低1.95%，比文献[15]降低1.05%，整体优化效果最好。由表5可知，本文算法的haverage与文献[13]和文献[15]相比大幅降低，与文献[14]相比虽然耗时增加，但相差不大。在求解中小规模矩形件排样问题时，本文算法能快速得到最优解，求解大规模问题时能在合理时间内得到较好的优化结果。

表4 每组算例的平均相对距离 %

表5 每组算例的平均计算时间 s

5 结束语

本文运用自适应遗传模拟退火算法求解矩形件排样问题，通过精英选择与轮盘赌相结合的策略对父代种群进行选择，自适应调整交叉概率和变异概率，将具有较快全局搜索能力的遗传算法和较强局部搜索能力的模拟退火算法相结合，提高算法收敛至全局最优的速度。采用启发式最低水平线择优算法布局矩形件，从而有效利用板材中的空洞。实验结果表明算法求解速度较快，可以有效提高板材利用率。