大规模定制板材排样的多种群蚁群优化算法

曾 敏，王 乘，刘琼梅

（1. 华中科技大学 水电与数字化工程仿真中心，武汉 430074；2. 湖南工业大学 计算机与通讯学院，株洲 412000）

大规模定制板材排样的多种群蚁群优化算法

曾 敏1,2，王 乘1，刘琼梅2

（1. 华中科技大学 水电与数字化工程仿真中心，武汉 430074；2. 湖南工业大学 计算机与通讯学院，株洲 412000）

为解决定制家具企业的大规模多品种小批量的矩形件排样问题，针对其一刀切的特殊生产工艺要求，通过对待切板自动生成两个不同的编号：横切编号和纵切编号的方法，采用面积，长度，宽度来启发的多种群蚁群算法，避免了单因素启发的不合理布局，做到了“生成即可行”，经多个企业的实际使用后，发现与单因素蚁群启发相比，多种群算法寻优能力强，主要表现为：最大利用率最高；多次寻优的最大利用率变化区间小。

优化排料；大规模定制；一刀切；多种群蚁群优化；优化算法

0 引言

优化排料，是一个在产品设计、制造和使用中如何节约原料、优化利用资源的问题。其中矩形件排样问题是优化下料问题中最常见，也是最具实际意义的一类优化排样问题。通常以利用率最大或剩余料最少为目标。常见的矩形件排样问题因原料和切割方式的不同可分为以下几种：1）卷料切割(Roll Material Cutting)；2）一刀切(Guillotine Cutting)；3）正交切割(Non-Guillotine Cutting)[1]。

板式家具优化排样是属于“一刀切”方式的矩形件排样问题，大规模多品种小批量的板材排料由于板材尺寸的多样和小批量，一般各板的布局基本不同，对算法的实时性，实用性的要求更高，同时一刀切的生产工艺要求，一般布局算法难做到生成即可行。

1 矩形件排样问题的特点和计算复杂性

按照计算复杂性理论研究问题求解的难易程度，可把问题分为P类、NP类、NP完全类和NP难问题。所以可以正确地求解NP-c完备问题的任何算法，在最坏情况下需要指数级时间，从而除规模很小的实例外，是不实用的[2]。

排样问题已经证明是一个NP-c完备问题。一维排样可以建模为一个o-1背包问题，而0-1背包问题被证明是一个NP-c完备问题，而一维排样问题可视为二维排样问题的特例。所以，排样优化问题的目标减弱为：在能接受的时间和空间约束下，逼近最优解。也就是说为了在保证算法的计算时间和计算空间是可以接受的情况下，只有接受次优解作为问题的结果[2]。

1.1 优化算法和排样优化的发展

目前优化算法的研究主要集中于指导性搜索方法和系统动态演化方法以及各种混合算法，研究热点为以遗传算法为代表的进化计算方法和蚁群算法为代表的群智能计算方法等[3]。

1.2 蚁群算法

蚁群算法是1992年由意大利学者 Dorigo M 等人首先提出的[4]，它是对蚂蚁进行模拟而得出的一种模拟进化算法，该算法不依赖于具体问题的数学描述，有很强的全局优化能力和本质上的并行性，是解决NP-c完全问题的有效方法。2005年江南大学刘瑞杰、须文波给出了优化排料蚁群算法[5]，但是此方法不满足一刀切条件。2007年南昌大学李捷提出了一种新的排样算法—最低水平线旋转搜索法，并将这种算法和遗传算法以及遗传蚁群算法结合应用于矩形件布局问题的求解[6]，但同样不满足一刀切的条件。

1.3 求解0-1背包问题的蚊群算法

我们可以将0-1背包问题解释为一位旅行者在出发前必须决定携带哪些物品。记价值集合C＝{C1，C2，…，Cn}，物品集合X＝{1，2，…，n}，重量集合A＝{A1，A2，…，An}，这里的Ci表示携带第i个物品的“价值”或效益，其重Aj＞0 (kg)。要在携带各种物品的总重量不超过b千克的限制下；使旅途中所携带物品的总“价值”或总效益最大。其数学模型描述为

设系统中的蚂蚁数目为m，各个蚂蚁从第1个开始到第n个物品依此决定是否选择该物品。在一次迭代后，每一个蚂蚁代表一个解。第i个蚂蚁代表的解可表示为{Xi1，Xi2，…，Xin}，其中，Xik标志着当前一次迭代中第i个蚂蚁是否选中物品，选中值为l，否则为0。

2 一刀切板材排样问题的蚁群优化算法

我们可以把背包问题的物品理解为矩形件排样问题的待切件，把背包问题的背包理解为矩形排样问题的原料板，这样矩形件排样问题就转化为背包问题，这样方便构造蚁群算法数学模型。

2.1 数学模型

设原料板材的长为L（一般为2440mm），宽为W（一般为1220mm），需要下K种零件，其中每一种零件需求数量分别为ni(1＜=i＜=k)，最终求得的优化下料方案由N张单板优化方案组成。在第j个单板方案上共安置Cj个零件，其中第i种零件有Ai个(1＜=i＜=K)，Ai＜=ni。

贪婪选择是一种分治策略，即将大问题化为小问题，以最优方式解决小问题后获得大问题的解。贪婪策略每步解决的子问题数量为1个。所谓贪婪选择属性，就是用贪婪策略要想获得最优解，必须满足下面两个条件[8]：

1）每一个大问题的最优解里面包刮下一级小问题的最优解；

2）每一个小问题可由贪婪选择获得。

我们可以看出通过求Cj最大来求minN，不满足上述条件（1）。所以我们要把问题转换成便于处理的方式。“同样大小的原料板上布局更多的待切板”和“使原料板利用率更大”等效。

这样就把求Cj最大转换为求Sj最大。

2.2 一板两号的编码方式

因“一刀切(Guillotine Cutting)”方式的矩形件排样问题，每一次切割的路径都是贯通整个原料矩形的直线。这就是说，同一块待切板，我们选择它，还存在一个怎么下刀的问题，即是横切还是纵切的问题。横切和纵切，决定了余料板的尺寸，也就决定了后面能布局的待切板的尺寸。要解决一刀切问题，我们需作一些技术处理。

我们只要对待切板做两个不同的编号——横切编号和纵切编号，蚂蚁选择不同编号的板，就决定了后面的可以选择的待切板。不同的是无论选择了横切编号还是纵切编号，对于对应的纵切编号的板或横切编号的板数量要同时减一。

例如板A＝577×2265，共两块，我们编号为N0H两块和N0Z两块。这样即可做到“生成即可行”，不需在优化后进行刀路可切性判断。

2.3 排料二叉树

用一个根结点表示布局空间的矩形区域，按定序规则从可选布局矩形中选择一个相对于该矩形区域来说是最优的布局矩形，并将其定位于该矩形区域的左上角。这样原布局空间变成了一个J形区域，将这个J形区域分成图1（a）所示2个矩形M和N，分别用根结点的左、右2个子结点表示。这样，剩余的布局空间就变成了2个独立的布局空间，分别对这两个独立的布局空间重复上述过程，直至没有可选布局矩形满足要求时停止分解。如图1（a）所示，整个排料过程形成了一棵二叉树，称为排料二叉树。该二叉树的叶子节点代表的是无法继续切分的区域，节点与某一确定的排料-切分方式相对应。

2.4 面积，长度，宽度的多种群启发

2.5 信息素更新

在蚁群算法中，蚁群算法中的信息素更新十分重要。对于大规模多品种小批量布局，通过我们的仿真实验，局部信息素采用每次循环后更新，全局信息素采用只对最优解更新的方式效果最好。参数设置如图1(b)所示。

2.6 一刀切优化算法

算法步骤：

1）读入要下料的板材清单，并进行一板两号编码，如图2所示；

图1 排料二叉树和群蚊群算法参数设置

2）设全局最优解数组global-best=面积最大优先生成的第一个可行解，设置启发信息为面积启发；

3）计算启发素，计算初始信息素；

4）对每一蚂蚁；

生成一个[0,1]之间的随机数q=RAND()，

再次生成一个[0,1]之间的随机数r=RAND()，

IF r＞=P，THEN Ant人工蚂蚁选择i的对应板（含切割方向）。

局部信息素更新 t(i)＝(1-r)×t(i)+r×t0；

ELSE 不取。

所有蚂蚁找到了二叉树？否转（4），是转（5）

5）比较适应度函数（容积率），求最优蚂蚁。将解存入当前最优解数组current-best；

6）IF f(current-best)＞f(global-best) 其 中f()为适应度函数（容积率），THEN global-best=current-best 全局最优解更新。

其中Dt(i)的值是最优蚂蚁所生成的二叉树所对应的原材料容积率；

7）IF连续全局最优解无更新次数大于或等于规定值，或最大循环次数大于或等于规定值，THEN

图2 比较试验结果示意图

如果启发信息＝面积启发，设置启发信息为长度启发转（3）

如果启发信息＝长度启发，设置启发信息为宽度启发转（3）

输出全局最优解；

8）待切板布局完成？否转（2），进行下一单板优化，是则结束。

3 试验结果和结论

本算法在VS2008中用C＃实现。下列试验横坐标为试验编号，纵坐标为最后一块单板的最大余料面积（平方毫米/100）。试验数据为待切板种类48，待切板总数90。用板19块，其中第19块的最大余料面积反映优化的材料利用率。

图2 (a)说明与单独因素蚁群启发相比，多种群算法寻优能力强，主要表现为：

1）最大利用率最高；2）多次寻优最大利用率变化区间小。

图2 (b)说明多种群算法寻优对蚁群数量m和最大连续全局最优解无更新次数N这两个参数不敏感。图中N10表示最大连续全局最优解无更新次数为10。m5表示蚁群数量为5。

图2 (C)说明多种群算法寻优比加大蚁群数量和最大连续全局最优解无更新次数更有效。

图2 (d)的横坐标为试验编号，纵坐标为程序运行时间（秒）（不是算法寻优时间，还包括各中间步骤显示所花时间等）。说明采用多种群算法的比加大蚁群数量和最大连续全局最优解无更新次数这两个参数的方法在时间上表现更离散，平均用时较高，说明好的寻优还是要一定的时间代价的。但是这个代价是在我们可以容许的范围内。

4 结束语

采用本算法的软件在多个大批量定制家具企业得到应用，与现有排料软件的优化结果比较，优势较为明显。

[1] 岳琪. 基于遗传退火算法板式家具大规模矩形件优化下料研究[D]. 东北林业大学, 2005.

[2] 宋亚男. 二维排样系统的图形匹配、入排控制与碰靠算法研究[D]. 华南理工大学, 2004.

[3] 孙宁. 人工免疫优化算法及其应用研究[D]. 哈尔滨工业大学, 2006.

[4] Dorigo M,V Maniezzo & A. Colorni. The Ant System：Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, 1996, Part B, 26(1)： 29-41.

[5] 刘瑞杰. 求解矩形件优化排料蚁群算法[D]. 江南大学,2005.

[6] 李捷. 基于遗传算法与蚂蚁算法的矩形件布局问题的研究与应用[D]. 南昌大学, 2007.

[7] 秦玲, 自云, 章春芳, 陈峻. 解0-1背包问题的蚁群算法[J].计算机工程, 2006, 32(6).

[8] 邹恒明. 算法之道[M]. 北京：机械工业出版社, 2010.

Mass customization cutting layout’s multiple colony ant optimization algorithm

ZENG Min1,2, WANG Cheng1, LIU Qiong-mei2

TP391.72;TP301.6

A

1009-0134(2011)5(下)-0059-04

10.3969/j.issn.1009-0134.2011.5(下).18

2011-03-01

曾敏（1964－），女，高级讲师，博士研究生，研究方向为计算机辅助设计、计算机应用。