1. 引言
随着市场竞争加剧，企业都在进行资源优化配置，以提高资源的利用率。排样问题是通过将一系列形状各异、大小不同的零件进行有效合理地组合优化，各个零件之间不能重叠，使得零件所占原材料面积最大，并应满足当前的加工工艺要求。而排样下料应用于各行各业，比如船舶制造、皮革剪裁、家具切割等各方面。合理有效地排样不仅能提高材料利用率，节约成本，还可以简化后续加工工艺过程，提高企业的经济效益。所以研究优化排样问题有着非常重要的理论意义和工程应用价值。
排样问题属于NP完全问题，以目前的理论和方法不能得到问题的最优解，只能得到其局部最优近似解。对算法的研究是目前提高排样材料利用率的最为广泛考虑的问题，启发式算法在排样问题上比较常用，比如经典的启发式算法有BL算法 [1] 和BLF算法 [2] ；陈洁琼，樊留群 [3] 等针对分管制造的排样问题，采用改进的遗传算法进行求解；杨卫波，王万良 [4] 等利用改进的自适应遗传模拟退火算法来解决矩形排样问题，结果行之有效；马康，高尚 [5] 针对矩形排样问题，采用改进的最低水平线搜索算法解决问题，通过实验证明该算法的有效性。本文主要是采用遗传算法和蚁群算法相结合的遗传蚁群算法来研究二维矩形排样问题。
2. 二维排样(板材、玻璃等下料)问题简述
二维排样问题就是将若干各种形状不一的零件合理有效地放置在板材内部，使得各零件之间不得重叠交叉，并且零件要完全在板材的区域之内，同时使得排样后的零件总面积占原材料面积的达到最大值，即使得材料利用率最大，也就是使得产生的残余废料(通常我们称为“切割损耗”(Trim Loss)最少)。
因在实际生产中，而二维排样应用性比较广泛，主要应用于板材切割(服装布料裁剪，玻璃切割等)、二维图形填充问题(单层货物堆放，汽车的停放、电路版布局等)等应用。所以我们在本课题中主要研究二维排样问题。
二维排样问题的代数法描述
设有一个原材料的面积为S，我们需要切割下K种零件的面积分别为
，以及所需要的K种零件的个数分别为
，可以切割的数量分别为
，已知原材料面积为S，目标就是要使得产生的残余废料最少，可以建立如下数学模型：
目标函数：
(2-1)
约束条件：
(2-2)
(2-3)
3. 遗传蚁群算法
遗传算法和蚁群算法都有其各自的优缺点，本文将其各自的优点结合到一起，融合得到一种新的遗传蚁群算法。结果表明，融合后的遗传蚁群算法比未结合的遗传算法和蚁群算法会得到更好的排样效果。研究表明遗传算法可以较快地得到最优解，但之后其求解效率就会明显下降：而蚁群算法却因缺乏初始信息素，较慢地得到最优解，但随后由于其反馈特点，信息素的不断增加，其求解效率也明显提高。因此本文将此两种算法融合的机理就是在前段时间采用遗传算法(利用遗传算法的随机性、快速全局收敛性)为此后的蚁群算法提供最优初始信息素，然后利用蚁群算法(利用其正反馈并行自催化特性、良好的鲁棒性、求解效率高等特点)。这样就可以得到我们所满意的排样结果。
3.1. 遗传算法设计如下
染色体编码方法；初始种群的生成；选择；交叉；变异；确定适应度函数，得到最佳个体；确定终止条件。
3.2. 蚁群算法
Dorigo提出了蚁群算法(ACO)。蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得到的一种放生算法。蚂蚁在运动过程中，能够在它经过的路径留下一种称之为外激素的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此直到自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现为一种正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率最大。基本的ACO模型可以通过以下公式进行描述：
(3-1)
(3-2)
(第k个蚂蚁经过由i到j的路径) (3-3)
式(3-1)、式(3-2)和式(3-3)中：m为蚂蚁个数；n为迭代次数；i为蚂蚁所在位置；j为蚂蚁到达位置；
为蚂蚁到达的位置集合；
为启发性信息，为由i到j的路径的能见度，即
；
为目标函数，这里为两点间欧氏距离；
为i到j的路径的信息素强度；
为蚂蚁k由i到j的路径上留下的信息素数量；
为路径权；
为启发性信息素的权；
为路径上信息素数量的蒸发系数；Q为信息素质量系数；
为蚂蚁k从位置i移动到位置j的转移概率。
3.2.1. 适应度函数
适应度函数也就是目标函数，适应度函数是用来评价结果的优劣，其定义为：
。其中，
为需排样的矩形零件的总面积，
为所需排样的板材面积。
3.2.2. 信息素的初始化
开始时，可以利用的信息比较少，所以得到初始条件不理想，会影响排样的优劣和排样效率。该方法采用了最大-最小蚁群系统的MMAS算法。
3.2.3. 信息素的更新
信息素的更新包括全局更新和局部更新。局部更新是在每次搜索排样的过程中实时更新每一个矩形件的信息素的浓度，更新模型如下：
(3-4)
-初始参数(
)：
-信息素浓度的初始值，也对
赋的初始值。
全局更新是在考虑矩形件被访问的先后次序的情形下只对最优排样序列里的矩形件更新信息素浓度，模型如下：
(3-5)
(3-6)
—为矩形件i上的信息素浓度；
—信息素挥发系数
；
—信息素强度常数；
—待排矩形件总数；
—第i个矩形件在最优排样中的次序；
—待排样矩形件的总面积；
—全局最优排样序列所对应的排样图的板材面积。
3.3. 基于遗传蚁群算法的矩形排样实现流程如下：
本文将结合遗传算法和蚁群算法各自的优点，融合为一种新的优点更加突出的遗传蚁群算法。融合后的遗传蚁群算法具有遗传算法在前段时间快速全局收敛性的特点和蚁群算法在后段时间的正反馈并行催化特性、良好鲁棒性、求解效率高等特点，从而可以较快的得到最优解，其融合后的遗传蚁群算法的矩形零件排样流程图实现如下图1所示。
4. 实验结果
本此实验是在最低水平线搜索算法的基础上，运用遗传蚁群算法地该排样问题进行求解。设定初始条件：板材尺寸为1200 * 3000，矩形零件的参数如下表1。
进30次测试所得适应度均值，利用遗传算法所得材料利用率的均值为0.8513，利用蚁群算法所得材料利用率为0.8751。根据本文的遗传蚁群算法所得材料利用率均值为0.8871.由此可见采用遗传蚁群算法比单一采用遗传算法和蚁群算法所得的材料利用率更高。
Table 1. The parameters of the rectangulars
表1. 矩形件参数
Figure 1. The flowchart of genetic and ant colony algorithm
图1. 遗传蚁群算法流程图
5. 结论
本文将遗传算法和蚁群算法的优点结合到一起，融合为一种新的算法即遗传蚁群算法对矩形排样优化问题进行求解。算法前段是采用遗传算法来进行快速高效地来获取初始排样序列，然后以此作为蚁群算法的初始信息素来进一步精确进行优化排样。通过实例验证，该方法所得到的结果的材料利用率更好，结果更加行之有效。