引言

矩形优化排料问题是指将一些数目和尺寸确定的矩形尽量紧密、无重叠地排入一个长度固定、宽度不限的矩形板材中，使板材利用率尽可能高。此问题在报刊排版、皮革和布料裁剪、金属下料等工业生产中有广泛的应用，是一个NP完全问题，具有一定的计算难度，且没有统一的求解方法。求解矩形排料问题需要计算两部分内容，即矩形的排入顺序和排入位置。目前多采用遗传算法^[1]、模拟退火算法^[2]、蚁群算法^[3]等智能优化算法计算排入顺序，通过剩余矩形法^[4]、最低水平线法^[5]等排料方法计算排入位置。其中蚁群算法求解质量高、求解结果稳定，但存在收敛速度慢、求解时间长的缺点，因此研究者们针对以上缺陷作了改进研究。隗平平等^[6]提出一种改进信息素挥发因子的自适应蚁群算法，结合最低水平线法，能在较短时间内得到优化结果。陈江义等^[7]将遗传算法和蚁群算法融合，配合最低水平线搜索法，可达到较好的排料效果。Guo等^[8]充分利用蚁群算法中的信息素，采用最低水平线法，取得较好的板材利用率。但上述几种算法均未能达到求解时间与板材利用率的同等优化，其板材利用率还有较大的提高空间。本文提出非等值初始量蚁群算法，结合提出的改进最低水平线法求解矩形优化排料问题，并用典型实例作对比实验来证明其性能。

1 非等值初始量蚁群算法 1.1 初始信息素量计算

传统蚁群算法求解矩形排料问题时，会对所有待排入的矩形赋予相等的初始信息素量，因此在算法初期，各矩形的信息素量差别较小，蚂蚁运动混乱，拖慢算法的收敛速度，从而使得迭代次数增多，求解时间变长。为弥补此缺陷，本文将各矩形的初始信息素量由等值改为非等值，通过在初始信息素量赋值过程中引入矩形面积和长宽比因素，增大各矩形初始信息素的差别，从而加快算法的收敛速度。

通过观察诸多排料结果发现，矩形排料有如下特点：①若先排入面积较大或长宽差距较大的矩形，易产生大块的闲置区域，这些闲置区域通常能被后排入的面积较小的矩形充分利用；②若先排入面积较小的矩形，易产生小块的闲置区域，但通常无法被后排入的面积较大或长宽差距较大的矩形充分利用。另外若矩形长宽数值较大，将不方便计算，因此对计算结果取对数。综合上述原因，矩形的初始信息素量计算公式为

$ \tau_{i}=\ln \left(C_{1} \times S_{i}+C_{2} \times \frac{a_{i}}{b_{i}}\right) $

(1)

式中，τ_i为编号为i的矩形的初始信息素量；C₁为参数，表示面积对矩形初始信息素量的影响；C₂为参数，表示长宽比对矩形初始信息素量的影响；S_i为矩形i的面积；a_i为矩形i的长；b_i为矩形i的宽。

1.2 状态转移概率计算

在矩形i上的蚂蚁k选择转移至矩形j的概率为P_ij^k。

$ P_{ij}^k = \left\{ {\begin{array}{*{20}{l}} {\frac{{{{\left( {{\tau _j}} \right)}^\alpha }{{\left( {{\eta _j}} \right)}^\beta }}}{{\sum\limits_{s \in {A_k}} {{{\left( {{\tau _s}} \right)}^\alpha }} {{\left( {{\eta _s}} \right)}^\beta }}}, }&{j \in {A_k}}\\ {0, }&{j \notin {A_k}} \end{array}} \right. $

(2)

式中，η_j为能见度因数，反映蚂蚁k由矩形i转移至矩形j的启发程度；α为参数，反映信息素量对转移概率的影响；β为参数，反映能见度对转移概率的影响；集合A_k由蚂蚁k允许选择的矩形组成，随蚂蚁k的移动而动态改变。

计算集合A_k中所有矩形的转移概率并比较，蚂蚁k将选择转移至其中概率P_ij^k最大的矩形j。

1.3 信息素更新

假设在矩形i上的蚂蚁k选择转移至矩形j，传统蚁群算法将更新蚂蚁k经过的路径i→j的信息素量，本文提出更新矩形j而非路径的信息素量。改进后的算法有利于信息素快速更新，从而节约计算时间。改进后具体更新方法如下。

当所有蚂蚁都选择完同一次序对应的矩形后，按式(3)对各矩形的信息素量进行更新，即局部信息素更新。

$ \tau_{i}=(1-\rho) \tau_{i}+\tau_{\mathrm{p}} N_{\mathrm{t}}(i) $

(3)

式中，ρ为信息素挥发系数；τ_p为局部信息素更新参数；N_t(i)为本次序中矩形i被蚂蚁经过的次数。

当所有蚂蚁都完成了一次对所有矩形的无重复选择后，即完成了一次迭代，其中每一只蚂蚁的转移顺序就是一个矩形排入顺序序列。比较各序列的板材利用率，只保存此次迭代中板材利用率最大的序列。判断此序列的板材利用率是否大于最优序列的板材利用率，若是，则令此序列为最优序列，并按式(4)和最优序列对各矩形的信息素量进行更新，即全局信息素更新；否则不进行更新。

$ \tau_{i}=\tau_{i}+\left(1-\frac{O(i)}{N_{\mathrm{s}}}\right) \times \tau_{\mathrm{a}} $

(4)

式中，O(i)为矩形i在最优序列中的次序，即表示矩形i在序列中是第几个被排入的；N_s为矩形总数；τ_a为全局信息素更新参数。

每个矩形都会被选择到，只是被选择到的次序不同，越早被选择的矩形更新的信息素量越大，而信息素量越大的又越易被先选择，因此，整个过程能逐渐形成正反馈，最终趋于最优解。

1.4 板材利用率计算

依据板材利用率F的大小，判断蚁群算法计算出的排入顺序序列的优劣。板材利用率越大的序列越好。

$ F=\sum S_{i} /\left(L_{\mathrm{a}} \times L_{\mathrm{b}}\right) $

(5)

式中，∑S_i为所有待排入矩形的面积之和(1≤i≤N_s)；L_a为板材的固定长度；L_b为依据排料方法计算出的占用板材最大宽度。

图 1所示为算法流程，其中N_a表示蚂蚁总数，k表示正在移动的第k只蚂蚁，I_c表示当前迭代次数，I_a表示最大迭代次数。

2 改进的最低水平线法

计算出矩形排入顺序序列后，依据排料方法计算各矩形排入板材的位置，求得该排入顺序序列的排料图和占用板材最大宽度L_b。

最低水平线法是较常用的排料方法，当要排入矩形i时，需先选择当前高度最低的轮廓线作为最低水平线，判断矩形i是否能排入该水平线，若能，将矩形i靠左排入，否则将该水平线与相邻轮廓线中高度较低的一条合并；重复以上过程，直至矩形i被排入板材。但此排料方法会因水平线的合并而形成较多被浪费的闲置区域。图 2所示为依据最低水平线法将矩形序列{4，5，6}排入板材的示意图，其中灰色部分为形成的闲置区域。

为弥补上述不足，本文对最低水平线法作出改进，加入旋转和闲置区域二次利用，改进后能减少闲置区域的产生并充分利用已产生的闲置区域，从而减少板材浪费。具体步骤如下：

1) 初始化最高轮廓线集合，使其仅包含板材的底边；

2) 初始化闲置区域集合；

3) 对于需要排入的矩形i，判断是否存在闲置区域能排入矩形i(可旋转90°)，若存在，则尽量靠下排入，并更新闲置区域集合；否则转入步骤4)；

4) 从最高轮廓线集合中选择高度最低的一条作为最低水平线，若同时存在数条，则任选一条；

(a) 若最低水平线的长度大于等于矩形i的长度, 则将矩形i靠左排入, 同时更新最高轮廓线集合，否则转入步骤(b)；

(b) 将矩形i旋转90°，若最低水平线的长度大于等于矩形i的长度, 则将矩形i靠左排入, 同时更新最高轮廓线集合，否则转入步骤(c)；

(c) 在最高轮廓线集合中查找与最低水平线左右相邻的轮廓线, 比较两条轮廓线的高度, 将最低水平线与其中高度较低的一条进行合并, 同时更新最高轮廓线集合和闲置区域集合；

5) 重复步骤4), 直到矩形i被排入板材；

6) 重复步骤3)~5)，直到所有矩形都被排入板材。

图 3为依据改进的最低水平线法将矩形序列{4，5，6}排入板材的示意图。从图中可发现，占用板材的最大宽度L_{b，改进后}明显低于改进前方法求得的宽度L_{b，改进前}，且闲置区域少，证明了改进的最低水平线法的有效性。

3 实验分析

为测试非等值初始量蚁群算法性能，对两个典型实例进行求解，并与其他算法作对比。

本文算法参数设定：C₁=0.3，C₂=0.7，α=1，β=2，ρ=0.1，τ_p=0.2，τ_a=3，η_i=S_i(1≤i≤N_s)，N_a=10。

实验一   求解文献[8]中的一个实例，该实例含24种不同尺寸矩形共66个，板材固定长度为500。将求解结果与传统蚁群算法求解的结果进行比较。传统蚁群算法的初始信息素量τ_i(1≤i≤N_s)和信息素强度分别设定为2和100，其余参数的值与本文对应参数的值相同。两种算法都取10只蚂蚁，以改进的最低水平线法为排料方法，设定迭代次数500为算法终止条件，分别运行5次后取平均值。图 4为依据平均值绘制的两种算法的迭代过程曲线，图 5为本文算法求解出的最优排料图，板材利用率为94.04%，宽度为305。

从图 4中可以看到，传统蚁群算法的曲线在400代时逐渐趋于平缓，而非等值初始量蚁群算法在100代时就趋于平缓，且之后仍略有上升趋势。二者比较可知，改进后的蚁群算法收敛更快。此外，图 4中非等值初始量蚁群算法的曲线一直呈上升趋势，且始终在传统蚁群算法的曲线之上，这说明改进后的蚁群算法收敛性良好，未陷入停滞状态，且优化效果更佳。

实验二   为进一步验证本文算法的性能，求解文献[7]中的实例，该实例含20种不同尺寸矩形共59个，板材固定长度为400。对本文算法运行20次取平均，将求解结果与其他算法求解的结果进行比较，如表 1所示。表 2为采用算法的主要内容。图 6为20次运行中的最优排料图，板材利用率为94.09%，宽度为340。

从表 1可以看出，本文算法的板材利用率最高，且耗时最短，与文献[7]、文献[9]、文献[10]相比，板材利用率分别提升约1%~6%不等，同时求解时间仅是文献[9]算法的57%，文献[10]算法的51%，大幅节约了求解时间，并进一步提高了板材利用率。此外，通过板材利用率最优值与平均值之差可比较算法的稳定性。由表 1数据可知，文献[7]、文献[9]、文献[10]和本文的最优值与平均值之差分别为2.33%、1.49%、0.92%和0.86%，本文算法的差值最小，由此可知本文算法的稳定性更好。

4 结束语

本文提出非等值初始量蚁群算法求解矩形优化排料问题，根据矩形面积和长宽比确定初始信息素量，并简化信息素更新规则，从而提高了算法收敛速度，节约了求解时间。提出改进的最低水平线法用于计算矩形位置能充分利用板材中的闲置区域，减少板材浪费。对比实验结果表明，本文算法能进一步提高板材利用率(至少1%)，且求解时间短。