基于动态最低水平线法和蚁群算法的排样优化

张 娜 赵 罘 龚堰珏 刘玲玲

(北京工商大学材料与机械工程学院 北京 100048)

0 引 言

矩形排样问题属于二维排样，是NP完全问题，计算复杂度高。矩形排样在现代工业的原材料切割中有着大量的应用，如玻璃切割、钢板下料、纸张剪裁等，即使是排样高度的微小降低，也能极大地节约原材料。

鉴于矩形排样问题的复杂性和重要性，研究者们做了长期的研究，但尚无统一有效的求解算法。目前求解矩形排样问题主要由两部分相互配合实现：(1) 利用智能优化算法计算矩形排入顺序，如遗传算法、模拟退火算法、蚁群算法等；(2) 利用启发式算法计算矩形排放位置，如IBL法、BLF法、最低水平线法[1]、剩余矩形法[2]等。Hopper等[3]分别用遗传算法和模拟退火算法配合BLF法，计算出较优解；Liu等[4]采用分阶段遗传算子的遗传算法配合改进的最低水平线法，能快速计算出解；周家智等[5]将遗传算法和模拟退火算法组合并配合修改的最低水平线算法，取得较好的排样结果；蒋兴波等[6]提出的基于环形交叉和变异算子并引入模拟退火算法的自适应模拟退火遗传算法配合IBL法,也能在较短时间得到解。但上述几种算法未能同时平衡求解时间和排样高度，存在排样高度小的，却求解时间长；求解时间短的，却排样高度大的情况。

本文在最低水平线法基础上作改进，提出动态最低水平线法，能弥补最低水平线法易产生材料空余的缺陷，减少空余产生。采用具有较好全局搜索性的蚁群算法[7]计算矩形排入顺序，并作适当改变使其更好适应排样问题。最后，通过多组对比测试，验证动态最低水平线法和蚁群算法相互配合的可行性。

1 问题描述

矩形排样问题是指在满足约束条件的情况下，将已知宽高的n个矩形{R1,R2,…,Rn}按最优方式排入宽度固定为W但高度不限的板材内，使排样高度尽可能小，从而使利用率尽可能大。在排样过程中需同时满足三个约束条件为：

(1)Ri必须完全在板材内部。

(2)Ri的边必须与板材的边平行。

(3) 任意两个矩形Ri和Rj互不重叠。

设任意矩形Ri(i=1,2,…，n)都可用如下6个量描述：

(1)

(2)

minH(或maxF)

(3)

求解矩形排样问题即是求解同时满足约束条件和数学模型且H最小的(或F最大的)排样序列。

2 动态最低水平线法

Step 1初始化水平线集合ξ，其仅包含板材底边ξ0。

Step 4重复Step 2至Step 3，直至矩形Ri被排入板材。

Step 5矩形Ri最终被放入的那条水平线记为ξx(0≤x≤n)，在未排入的矩形中查找是否存在宽度小于等于更新后水平线ξx宽度的矩形。若不存在，则判断更新后水平线ξx与相邻水平线的关系符合图1中的哪种情况，按相应情况进行合并，然后更新水平线集合；若存在，则不进行合并。

(a) hlhr;hc

(a) hlhl;hc

---

hr;hchr

(e) hr不存在;hc>hl (f) hl不存在;hc>hr

(g) hr不存在;hc

(i) hlhl;hc>hr (j) hl>hr;hc>hl;hc>hr图1 合并情况

Step 6取矩形Ri的上边线为水平线ξi，并将ξi加入水平线集合，判断新增的水平线ξi与相邻水平线高度是否相等。若相等，则合并为一条水平线，然后更新水平线集合；若不相等，则不合并。

Step 7重复Step 2至Step 6，直至所有矩形都被排入板材。

图2为本文方法的流程。

图2 动态最低水平线法流程

图3为同一矩形排样序列[1,2,3,4,5,6,7]分别按最低水平线法和动态最低水平线法排放的结果。可以看出，动态最低水平线法解决了最低水平线法忽略的两个问题，最大限度减少了板材空余，缩小了排样高度。

(a) 最低水平线法 (b) 动态最低水平线法图3 排放结果比较

3 蚁群算法

蚁群算法是通过模拟自然界真实蚂蚁行为而形成的算法，模拟了一群蚂蚁寻找从巢穴到食物源最短路径的过程。每只蚂蚁根据启发因素和路径上信息素量选择移动路径，随时间增长和路径上信息素的积累，从而找到最短路径。

蚁群算法主要用于旅行问题中计算最短移动路径[8-9]，本文将它用于矩形排样问题中计算排样高度H最小的矩形排入顺序(即排样序列)，并为适应题目对算法做适当改变。

(1) 信息素更新。由于矩形排样问题不需要计算路径长短，因此由更新蚂蚁从矩形Ri转移到矩形Rj的路径ij的信息素变为更新矩形Rj的信息素，有利于缩短计算时间。

每一次迭代的过程中做信息素局部更新，公式为：

τj=(1-ρ)τj+Δτp×tj

(4)

式中：τj表示矩形j的信息素；ρ为信息素挥发系数；Δτp为信息素局部更新量；tj为在排样次序是同一个值时矩形j被蚂蚁经过的次数。

每完成一次迭代后，依据本次迭代中排样高度最小的排样序列的各矩形次序做信息素全局更新，公式为:

τj=τj+(n-qj)×Δτa

(5)

式中：n为矩形总数；qj为矩形Rj在排样序列中的次序；Δτa为信息素全局更新量。

(2) 矩形选择。蚂蚁选择下一个排入的矩形的概率为：

(6)

矩形Rj的启发因素ηj的计算公式为：

ηj=μ×Sj+(1-μ)×Vj

(7)

式中：Sj为矩形Rj面积；Vj为矩形Rj宽与高的比值；μ为比例系数，表示矩形面积或宽高比值在启发因素中的占比，0≤μ≤1。

通过不断的迭代、信息素的更新和动态最低水平线法计算的排样高度的反馈，蚁群算法能计算出排样高度H最小的矩形排入顺序。具体流程如图4所示。

图4 蚁群算法配合动态最低水平线法的算法流程

4 测试与分析

求解和仿真用VB二次开发SolidWorks[10]实现，测试参数取μ=0.3、ρ=0.1、Δτp=1、Δτa=3、α=0.6、β=2、各矩形Ri的初始信息素τi=2(1≤i≤n)。

4.1 动态最低水平线法效果

采用文献[4]的实例，蚁群算法分别配合最低水平线法和动态最低水平线法，取迭代次数分别为20、50、100、150和200，蚂蚁总数为15，进行测试。测试5次取平均，结果如表1所示。

表1 最低水平线法和动态最低水平线法板材利用率比较 %

随着迭代次数的增加，虽然两种方法的板材利用率都逐渐提高，但新提出的动态最低水平线法对所有的迭代次数都得到了比最低水平线法更高的板材利用率，证明动态最低水平线法效果良好且有效地弥补了最低水平线法的缺陷。

4.2 蚁群算法配合动态最低水平线法效果

采用文献[4]的实例，测试50次取平均，将结果与文献[4]、文献[5]的结果作比较，如表2所示。

表2 不同算法求解结果比较

本文算法求解的板材利用率平均值和最优值均高于其他算法，虽然时间比文献[4]略高，但板材利用率也比文献[4]约高了7百分点，能大大节约原材料，是同时平衡了利用率和求解时间的算法。图5为本文算法在50次测试中求解出的最优排样图，左下角数字为矩形编号，其板材利用率为94.93%，高度为337。

图5 本文算法求解文献[4]实例的最优排样图

为进一步验证本文算法的效果，采用文献[3]的7类数据作比较。每类数据包含3个不同实例，矩形总数、板材固定宽度和板材高度如表3所示。

表3 实验数据

对每个实例测试50次取平均，并与其他算法作比较，表4为平均排样高度与板材高度之差，表5为平均求解时间。

表4 每类数据的平均排样高度与板材高度之差

表5 每类数据的平均求解时间 s

本文算法求解的总体平均差值最小，因此总体求解效果最好，且本文算法几乎对每类数据求解的平均差值都为最低值，仅C7类的差值不是最低值，但求解时间相比差值最低的文献[3]算法2大大降低，仅是文献[3]算法2时间的百分之0.5，证明算法效果好。

由表5可知，本文算法的平均求解时间对C1至C3类实验数据是最短的，对C4至C7类实验数据则不是，高于最短的文献[6]。但综合表4可知，本文算法计算的C4至C7类数据的差值一直小于文献[6]。因此，本文算法最好地平衡了排样高度和求解时间，是一种可行的求解算法，有利于节约原材料。

5 结 语

本文提出动态最低水平线法，配合蚁群算法求解矩形排样问题。测试比较证明，本文算法在同等条件下板材利用率一直高于最低水平线法，弥补了最低水平线法的缺陷。而且本文算法求解效果好，相比其他算法的总体平均排样高度差降低约25%至46%，大幅节约原材料，同时平衡了求解时间，能适应各种规模的矩形排样，可行性好。