基于遗传模拟退火算法的布局优化研究

周家智，尹 令，张素敏



基于遗传模拟退火算法的布局优化研究

周家智，尹 令，张素敏

(华南农业大学数学与信息学院，广东 广州 510642)

为提高矩形件排样算法的利用率与时间效率，提出将遗传算法和模拟退火算法融合优化的矩形排样算法。采用带符号的十进制编码,依据矩形件长宽比和面积而生成基因序列用于建立初始种群，以随机产生若干排样顺序与排样尺寸不一的个体，并以利用率为适应度函数，修改后的最低水平线搜索算法作为排样策略，保证较优个体得以保留，减少闲置区域的产生。采用10组随机产生的矩形数据将本算法与现有文献提出的GA算法进行对比实验，实验结果显示：该算法有效地提升了排样结果的利用率与时间效率。

矩形件排样；遗传算法；模拟退火算法；最低水平线改进算法

矩形件排样问题即给定某单一尺寸的库存板材和一组毛坯需求，要求从板材中切割出毛坯，并满足所有毛坯的尺寸及数量需求，使消耗的板材数量或板材价值最小。矩形件排样问题广泛存在于布匹裁剪、金属锻造、木材切割等加工业领域，具有一定的计算复杂性，属于NP问题。对矩形件排样问题的算法优化具有一定的理论价值与现实价值。对矩形件排样问题的研究通常建立在特定的前提条件下：无限原材料或有限原材料。

矩形件排样问题作为经典的NP问题，与生产需求存在密切联系。对于矩形件排样的研究多数分为两个方面：排样策略的研究与排样顺序的研究。排样策略通过设计矩形件排样过程所遵循的准则规范，以达到增加板材利用率的目的，如CUI等[1]提出的顺序启发式算法以及SILVA等[2]基于实际工业问题提出的启发式方法与整数规划模型均是从排样策略出发设计或优化提出的；排样顺序地研究证实了矩形件的排放顺序对板材利用率的影响，寻找能达到最优解的排样顺序。在实际的应用研究中，矩形排样问题基于不同的目标有不同的需求，具有一定的个性化，因此至今仍未形成统一的求解方法。近年来，智能优化算法多次用于与原有排样算法组合优化出新算法以满足多样化的现实需求，越来越多研究学者将智能优化算法与改进的排样算法融合优化成新的排样算法，如文献[3]提出控制基因的分组遗传算法(grouping genetic algorithm with controlled gene transmission，GGA-CGT)解决装箱问题。

基于此背景，国内涌现了众多研究成果。如基于三阶段排样方式提出的二维剪切下料算法[4]通过形成规则形状的剩余原材料，增加可用于二次利用的材料，增加企业效益。以及基于背包算法和线性规划算法提出的均匀条带四块排样算法[5]。基于最优子段的排样算法针对工业生产中长矩形原材料排样问题提供了解决方案[6]。上述提到的几种优化算法均从实际的生产需求出发，针对性地提出了有效的求解方法。但另一方面，由于生产需求的多样性，以解决具体生产问题为目标而提出的求解方法存在自身算法不足、可移植性较差地问题。如文献[4]的算法性能偏低，需要进一步改进；文献[6]算法仅适用于满足“一刀切”条件的板材排样；文献[5]的两种算法无法做到时间与利用率同时优化等。

本文在现有的矩形优化排样算法研究成果上，基于遗传算法、模拟退火算法两种智能优化算法，融合设计出针对矩形件排样问题的遗传模拟退火算法，该算法可移植性强，原材料利用率相对于参照算法有显著提高。

1 求解模型构建

1.1 问题描述

矩形件排样问题在无限原材料条件下指把个已知长宽的矩形件{1,2, ···,p}排放到宽度为MaterialWidth且长度不限的矩形原材料中，在满足一定约束条件下使原材料利用率最高，从而减少材料的使用以降低成本。其中约束条件包括：

(1) p不能超出的边界，= 1, 2, ···,；

(2) p与p不互相重叠，,= 1, 2, ···,；

(3)排放时p只有横放或竖放两种排放方式，即长边或短边平行于轴。

1.2 数学模型

设原材料的左下角坐标为(0, 0)，定义矩形件排放后的最高点纵坐标为该矩形件的水平线高度。具体参数设置如下：

(1) p为第个待排放矩形件；

(2)(x, y)为矩形件p的左下角坐标；

(3) w为矩形件p的短边；

(4) l为矩形件p的长边；

(5) h为矩形件p的水平线高度；

(6) f为矩形件p的排放方式，f= 1为矩形件横放，即长边平行于轴；f= –1为矩形件竖放，即短边平行于轴。

图1为4个矩形件排放示例图，其中阴影部分为无法利用的闲置区域。在实际工业生产中，更希望余料尽可能地聚集在原材料的顶部，有利于余料的二次利用，因此追求矩形件排样高度尽可能低。

图1 矩形件排放示例图

基于上述需求，设=(1,2, ···,h)以最高水平线MaxLevel为目标函数，即

且应满足约束条件

式(3)表示p不超出的边界；式(4)表示p与p不互相重叠；式(3)、(4)均满足,= 1, 2,···,，且≠。

2 基于遗传算法与模拟退火算法的排样算法

上述矩形件排样问题中，矩形件的排样顺序与排样策略对最终排样结果均有重要影响。为此，本文引入遗传算法与模拟退火算法最大限度搜寻排样顺序的解空间，并对现有的矩形件排样算法进行修改，优化排样策略，最终融合出进一步提升利用率的排样算法。

2.1 编码方式设计

为降低算法复杂性，采用十进制编码方式，设有个待排放矩形件，则矩形件编号为1, 2,···,。在十进制编码中使用正负符号表示矩形件排放方式，负数表示矩形件竖排，正数表示矩形件横排。综上，=(1,2, ···,r)为个体中个矩形件的其中一个排样序列。对于排样序列=(1,2, ···,r)，按照1,2, ···,r的顺序依次排放，并根据编号的正负决定该编号矩形件的排放方式。

如图2所示为= (－1, 2, －3, 4, －5)的基因序列，一共5个矩形件按编号升序排样，其中矩形件1、3、5竖排，2、4横排。

图2 矩形排放示意图

2.2 适应度函数设计

本文算法的目标在于提高原材料的利用率，因此采用式(2)的利用率公式作为适应度函数，即

2.3 选择操作

为了把父代种群中较优个体得以保留，使用轮盘赌选择法将较优个体保留到子代种群中。具体操作方法为：

步骤3. 重复步骤2直到达到下一代种群规模。

2.4 交叉变异操作

使用单点交叉操作，从种群中选取两条互不相同的个体1与2，随机选取一个交叉位置，将个体1与2在以前的基因序列分别复制到新个体3与4中；再将存在于1且不存在于4的基因复制到4上，对2与4执行同样的操作。

变异操作所采用的变异方式一共4种：位置变异、插入变异、反转变异和交换变异。位置变异在选中个体的长度范围内随机选取两个不同的基因位置，并互换基因位置。插入变异在选中个体的长度范围内随机选取前后两个不同的基因位置，将较后处基因插入到较前处基因的后一个位置，两个基因位之间的基因则往后移动。反转变异在选中个体的长度范围内随机选取两个不同的基因位置，将两个基因位置间的基因序列逆序以代替原基因序列。交换变异在选中个体的长度范围内随机选取一个基因位置，将选中位置的基因与后一位基因互换，若选中的基因为末位基因，则与首位基因交换。

2.5 模拟退火操作

其中，为温度衰减参数，参数值手动输入，用于控制退火的速度，且满足∈[0.2, 0.95]。

2.6 构造初始种群

初始种群的个体一半通过优先级函数产生，一半通过随机数作为优先级产生，优先级函数公式为

其中，P为第个矩形基因优先级；l和w分别为第个矩形的长和宽；P为该矩形长宽比值所占权重；P为矩形面积所占权重；函数生成的随机数R∈(0,1)，其中长宽比值权重与面积权重之和为1，即P+P= 1。

2.7 基于最低水平线算法的修改

最低水平线算法是围绕水平线而展开的算法，在进行矩形件排样时，找出当前高度最低，且位于最左的低水平线进行排放，若无法满足当前矩形件的排放，则将该水平线与相邻水平线合并，直至能够满足当前矩形件的排放条件。

为了进一步优化，最低水平线搜索算法在最低水平线算法上添加了水平线的搜索机制，当最低最左水平线无法满足当前矩形件排样条件时，则向后搜索适合排放的矩形件进行排放，若不存在适合的矩形件，再进行水平线合并操作。

最低水平线搜索算法避免了可能因更新水平线而造成浪费的闲置区域出现。然而，在所选取水平线无法排放当前矩形件时，最低水平线搜索算法只往后搜索到一个满足排放条件的矩形件返回，忽略了存在边长与水平线长度更接近的矩形件的可能性，没有充分利用水平线所提供的排放空间。

针对上述不足，本文基于同类文献的思路进行了修改：

(1) 引入矩形件旋转机制，若当前矩形件按照原有排放方式无法排放，则变换排放方式进行排放。

(2) 若当前矩形件无法排放，则向后搜索满足排放条件且边长与水平线最接近的矩形件进行排放。

修改后算法步骤如下：

步骤1.把矩形原材料宽度放入队列，作为初始水平线，记为p=(0,0,0,0,,1)；

步骤2.选取高度最低且最左边的水平线对应的矩形p= (x,y,w,l, h,,f)；

步骤5. 向后寻找满足排放条件的所有矩形件；

步骤6.如果记录中存在矩形件数据，则将记录中边长最长的矩形件p与待排放矩形件p位置互换，进行排放。进入步骤8，否则进入下一步骤；

步骤7.设h-1所处高度为h′–1= y–1+，h所处高度为h′+1=；若m–1≥h′+1，则令h+1=0且h= h+h+1；否则令h–1=0且h=h+ h–1。跳转到步骤2；

步骤8. 反复执行步骤2，直到不存在未排放的部件。

从图3可以看出，引入了旋转机制的最低水平线搜索算法的排样高度明显低于修改前算法，显著减少板材闲置区域的出现。

显然，与修改前算法相比，排样算法修改后减少原材料消耗的同时也增加了可用原材料的面积。

图3 两种算法的排样效果比较图

2.8 遗传模拟退火算法的流程图

综合上述步骤，遗传模拟退火算法流程如图4所示。

图4 遗传模拟退火算法流程图

3 算法评估

为测试遗传模拟退火算法性能，将本文算法与文献[8]算法进行横向比较，以文献[8]提供的矩形件样例和其随机产生的矩形样例作为测试数据。

实验平台：联想Y510P笔记本，Intel i5 2.50 GHz处理器，8.0 GB RAM，使用Visual Studio C# 2015编程实现该算法。

算法参数：算法初始参数均人为设置。种群大小为100；遗传迭代次数为20；种群交叉概率p为0.5；种群变异概率p为0.3；矩形长宽比值权重p为0.7；矩形面积权重p为0.3，初始温度为 3 000；阈值温度min为1 000；温度衰减参数为0.9；当温度低于阈值温度min，算法终止运行。

本文采用文献[8]的矩形件数据，见表1。将本文算法运行表1矩形件数据后的结果与文献[8]进行对比，对比结果见表2。

表1 矩形件数据

表2 排样结果数据(I)

表2结果显示，本文所提出算法相对于文献[8]算法求解利用率有进一步提高，但算法运行时间高于文献[8]算法。

以矩形件种类与总数作为标准，生成10组长度与宽度随机的若干矩形件，进一步测试本文算法性能。以产生的矩形件作为测试数据，测试中算法的参数与板材宽度不变，使用本文算法求解并与文献[8]结果进行对比，结果见表3。

表3 排样结果数据(II)

根据表3的数据分析得出，在矩形件种类与总数不断变换的条件下，本文算法的avg以及best仍然高于文献[8]算法，而且即使矩形件不断变换，本文算法的利用率仍然保持在一定水平，具有一定的稳定性。在avg比，无论是排样的利用率还是算法的运行时间，本文算法均优于文献[8]算法。

4 结束语

本文综合已有文献的研究成果对最低水平线搜索算法做出了排样策略的修改，使用自适应的规则灵活调整矩形件排放顺序，减少了排样过程中闲置区域的产生，提高了板材的利用率。采用优先级函数构造初始种群，并引入模拟退火机制避免了遗传算法种群早熟现象，提高算法性能，并将修改后的最低水平线算法与遗传算法和模拟退火算法结合，用于解决矩形件排样问题。经过实验数据测试，本文提出的算法能进一步提升板材利用率，能有效应用于实际生产。

[1] CUI Y P, CUI Y D, TANG T B. Sequential heuristic for the two-dimensional bin-packing problem [J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[2] SILVA E, ALVELOS F, DE CARVALHO J M V. Integerating two-dimensional cutting stock and lot-sizing problems [J]. Journal of the Operational Research Society. 2014, 65(1): 108-123.

[3] QUIROZ-CASTELLANOS M, CRUZ-REYES L, TORRES-JIMENEZ J, et al. A grouping genetic algorithm with controlled gene transmission for the bin packing problem [J]. Computers & Operations Research, 2015, 55(C): 52-64.

[4] 陈秋莲, 宋仁坤, 崔耀东. 考虑余料价值的三阶段二维剪切下料算法[J]. 图学学报, 2017, 38(1): 10-14.

[5] 曾兆敏, 王继红, 管卫利. 二维板材切割下料问题的一种确定性算法[J]. 图学学报, 2016, 37(4): 471-475.

[6] 姜永亮, 周俊. 基于最优子段的矩形优化排样[J]. 图学学报, 2016, 37(2): 280-284.

[7] 杨卫波. 基于遗传模拟退火算法的矩形件优化排样[J]. 计算机工程与应用, 2016, 52(7): 259-263.

[8] LIU H M, ZHOU J, WU X S, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy [C]// 2014 IEEE Congress on Evolutionary Computation. New York: IEEE Press, 2014: 352-357.

On Layout Optimization Based on Genetic Simulated Annealing Algorithm

ZHOU Jiazhi, YIN Ling, ZHANG Sumin

(School of Mathematics and Informatics, South China Agricultural University, Guangdong Guangzhou 510642, China)

Based on the integration of the genetic algorithm (GA) and the simulated annealing algorithm, an improved lowest horizontal line (ILHL) algorithm is presented in order to improve utilization and stability of the rectangular packing algorithm. In this algorithm, a signed decimal encoding is utilized to generate the gene sequence in accordance with the length-width ratio and the area of the rectangle, which is employed to establish the initial population. The improved lowest horizontal line algorithm adopts the best individuals from a number of random sequences with different nesting orders and layout sizes, uses utilization rate as the fitness function and reduces the idle area. In this paper, a contrast experiment is operated to compare ten groups of rectangular data randomly generated by ILHL with those generated by GA proposed in the current literature. The experiment results show that our algorithm (ILHL) can effectively improve the utilization rate and time efficiency of the packing results.

rectangular packing; genetic algorithm; simulated annealing algorithm; improved lowest horizontal line

TP 301.6

10.11996/JG.j.2095-302X.2018030567

A

2095-302X(2018)03-0567-06

2017-08-31；

2017-09-30

周家智(1994-)，男，广东清远人，本科生。主要研究方向为布局优化、机器学习。E-mail：524841091@qq.com