基于遗传算法的多规格管材或型材的优化下料

刘在良 翁旭辉 王静 夏小浩

摘  要： 在船舶建造中存在大量的管材或型材需求，这些材料的一维优化下料（一维套料）问题一直在被研究。文章提出了一种基于遗传算法的求解方法，建立了数学模型，给出了编码解码方案和交叉变异方法等，并结合实际情况提出一种方法利用近似优化算法来修复无效基因，同时还在代代相传中采用精英保留策略尽可能保留每代最优解，有利于加快收敛。实例结果表明该算法的有效性，符合预期目标。

关键词： 一维优化下料; 遗传算法; 优化算法; 一维套料

中图分类号：U671.2          文献标志码：A     文章编号：1006-8228（2018）12-67-04

Abstract： There are a large number of pipe or profile requirements in ship construction， one-dimensional optimum cutting （one-dimensional nesting） of multi-size stock materials has been being studied. This paper presents a solution method based on genetic algorithm， establishes a mathematical model， gives the coding and decoding scheme， and cross and mutation methods， according to the actual situation， proposes a method to repair invalid genes by using approximate optimization algorithm. At the same time， elite retention strategies are used to preserve the optimal solution of each generation as far as possible in the process of generation-to-generation transmission， which is helpful to speed up the convergence. The example shows that the algorithm is effective and meets the expected goal.

Key words： optimal one-dimensional cutting; genetic algorithm; optimization algorithm; one-dimensional nesting

0 引言

在船舶建造过程中，如何减少浪费，不断的提高材料利用率一直是各大船厂追求的目标，如何用数学方法来最大化利用材料也一直被讨论。在这些问题当中有一种以长度作为唯一维度的下料方式，又称之为一维排料问题。本文讨论的问题适用于多种长度原材料下料问题。

此类问题比较常见的有启发式方法或线性规划方法（文献[1-2]），常规的数学方法受零件尺寸跨度和数量级影响较大，而遗传算法理论作为全局搜索进化的方式，可以取得到较好的效果，本文将讨论遗传算法在管材或型材下料中的应用及效果。

1 数学模型

多规格管材或型材下料问题可理解为装箱问题，描述如下：设有n个物品，每个物品的体积分别为：Vi，i=1，2，…，n，有m种箱子容量分别为Li，i=1，2，…，m，现规定箱子数量无限使用，求把这n个物品全部放进箱子，怎么放才能使箱子利用率最高？当物品数量达到一定规模，箱子也不只一种的时候，这种计算就变的相对复杂，这就是NP（Non-deterministic Polynomial）难题，通常复杂的NP难题只能得到近似最优解。

式⑴中ljk为在第j根原材料上第k个下料零件的长度，w表示第j根原材料上总共下料w个零件。式⑵表示为下料零件的总长与材料总长比值最大，即利用率最大，为了要达到的优化目标。

在实际生产中，我们在追求利用率最大的前提下，考虑把余料集中在某一根原材料以上便于再次利用。设定最长余料长度为Wmax，将式⑵改进：

2 遗传算法

2.1 遗传算法概述

遗传算法是一种模仿生物繁衍，自然选择的思路建立的算法，模仿了遗传过程中交叉变异选择等现象。他从随机的样本中，经过目标函数的评估得到部分较好的个体，将这些个体按评估高级分级选取概率进行交叉变异得到新的个体，然后在新群体基础上，继续发展下一代，向更优方向发展为趋势，直到得到近似最优结果后停止。遗传算法具有全局性和自适应性，比较适合处理复杂事物的优化计算。

2.2 遗传算法基本定义

遗传算法有5个基本组件：初始群体，用于个体评价的适应度函数，选择器，交叉函数，变异函数。定义公式为：

式中：C为编码函数，P0为初始群体，S为种群大小，E为适应度函数，F为选择器，R为交叉函数，Y为变异函数，T为终止条件。

遗传算法过程如下（图1）。

2.3 染色体编码和解码

2.3.1 编码

染色体即群体中的个体，本文采用零件编号及所在材料编号的编号对作为编码，设零件编码为，材料编码为，染色体编码可记为，，表示零件在材料中下料，其中允许重复，将所有零件编码产生的一个解即为个体。

2.3.2 解码

解碼是将数字编码转换成下料布局表达。

遍历里面所有的编号对，将材料编号相同的对应零件编号汇总。例如其中刚好有 和中的和为同一编号，那么建立如下列表：，表示编号为的材料上分布了编号为和的两个零件，我们称之为下料表，以次类推，建立所有的下料表，完成解码。

2.4 适应度函数

根据本文建立的数学模型，要求的目标是零件下料的利用率最大，如式⑶：

F（x）介于（0，1）之间，数值越大表示利用率越高，适应度越好，本文以此式作为适应度函数评估个体质量。

2.5 初始种群

2.5.1 产生种群

初始种群P0按随机方式产生，方法如下。

⑴ 零件编码：初始的零件列表认为是无序随机状态，根据编码方法，将这n个零件按顺序编码为1，2，3，…，n。

⑵ 材料编码：假设有m种材料，且每种材料的数量为无限使用，设定每种材料数量为w，那么材料编码如下：，第一个下标表示第i种材料，第二个下标表示第i种材料的第j根。

⑶ 个体：取第i个零件，按均等概率得到（1，w×m）的随机数r作为随机材料编号， 按零件编码顺序逐个取零件，建立如下个体编码：，可以简化为，rn表示第n个零件放在编号为rn的材料中。

⑷ 群体：根据零件数量设定一定的群体规模q，生成q个随机个体的集合作为一个种群。

2.5.2 优化种群

⑴ 优化基因

种群由于完全是随机生成，不可避免会出现没有实际意义的编码，我们需要找到并修复错误基因。将群体中所有的个体解码：，即Lk材料上分布了x个零件，每一个Lk分布定义为一个基因，设第i个零件的长度为li，Lk长度为L，计算该材料中下料零件总长l'=，如果l'>L，表示Lk这个材料上的零件总长大于材料长度，这种下料方式就没有实际意义，需要修复。本文使用常规局部优化算子（FFD，BF）等修复错误基因。

2.6 选择算子

根据自然法则，越强大的个体获得的交配机会也越多，这将使它强大的基因更多可能的遗传给下一代。遗传算法中，我们使用以适应度作为概率占比的轮盘赌（文献[3]）算法来模仿这种不均等概率选择。

2.7 交叉方法

交叉算子采用单点交叉方法（文献[4]）。按一定的概率决定是否发生交叉，本文设定交叉概率为55%，即群体中约有55%的个体发生交叉。方法如下：

先从P0'中随机得到两个个体用做交叉运算。

设初始群体的大小为S，那么P0'的大小也为S，从（1，S）中得到两个随机位置，取得这两个位置的个体（染色体）记为Ta，Tb。

把Ta，Tb两个染色体从某个随机交叉点打断，将交叉点后的编码互相交换。

设染色体编码长度即零件数量为n，取（1，n）之间随机数w作为交叉点，将两个染色体切分如下：

交叉互换并修复后，得到第一代新群体，记为P1。

2.8 变异

遗传算法采用变异机制来扰动群体，以减少陷入局部解的困境。

设发生变异的概率为1%。设交叉后的群体P1的大小为n，当发生变异时，从（1，n）中随机抽取x个个体，将每个个体的染色体编码进行随机变异。

设某染色体编码为，rn表示第n个零件所在的材料编码，设随机变异位置为j，那么，将rj替换为（1，w×m）中的一个随机数rj'，其中m表示不同长度材料的种类数，w表示每种材料的数量。替换后得到新的编码。

2.9 精英保留策略

在计算过程中，某一代偶尔会出现适应度较好的个体，由于选择交叉变异等原因没有被保留，为此，把父代适应度最高的个体替换掉子代中适应度最差的个体，即精英保留策略（文献[5]）。

2.10 终止

目标函数为：去除最大剩余长度后的利用率F。设定一个预期值（利用率），当在整个进化过程中一旦满足预期值则终止进化计算并给出最优解。

3 实例

3.1 应用界面

应用界面如图2所示。

3.2 实例对比

本文分别挑选三种不同船型进行优化试验，结果如下（表2）：

⑴ 散货船案例。以64000吨散货船为例，全船约118种管材，共14649根管子零件，零件总长约20690.28米，包含不锈钢、卷制钢管、铜管、无缝钢管等。按照传统经验预估材料（根据管种不同约加放10%～20%左右余量），管材实船采购清单总长度24658.8米。设定适应度为0.999。

经过优化计算，得到材料总采购长度为21234米，利用率约为97.44%，其中各规格管子9米长的共954根，12米长的共1054根，相比传统材料预估法，可以减少订货3424.8米。部分优化示例见表1。

⑵ 集装箱船案例。以2200箱集装箱船为例，全船约103种管材，共20168根管子零件，管零件总长约25306.85米，管材实船采购清单总长度27351.026米，经过优化算法，得出总采购长度为25803米，其中各管种9米的总共1187根，12米的总共1260根。总长比传统经验法少1548.026米。

⑶ 油船/化学品船案例。以11000吨油船/化学品船为例，全船约111种管材，约14686根管子零件，管零件总长14012.8米，实际采购总长15496.8米，经过优化算法，得出总采购长度为14415米，其中各管种9米的共615根，12米的共740根，总长比传统采购少1081.8米。

4 结论

本文介绍了多规格管材或型材下料问题中的遗传算法解决方案。结合三种船型的实例数据可以看到相较与传统，一条船能节约管材可以达到一千多米甚至更多，遗传算法可以尽可能的减少材料浪费，实现精准下料，这对船舶工业提倡绿色造船、节能减排等具有积极意义。

在应用过程中还发现，当零件数量较少且长度都较接近原材料长度的情况下，由于始终无法达到目标函数从而导致算法陷入无穷的搜索而无法收敛，這时需要通过调节目标函数利用率或最大遗传代数的设定来使得算法终止，所以，还需进一步制定一种自动调节机制来加快收敛，便于实际应用。

参考文献（References）：

[1] 祝胜兰，饶运清.一维下料问题的启发式方法[J].机械制造与自动化，2014：58-61

[2] 崔耀东，周密，杨柳.多线材一维下料问题的求解策略[J].广西师范大学学报（自然科学版），2012.3：169-173

[3] 胡新平，贺玉芝，倪巍伟.基于赌轮选择遗传算法的数据隐藏发布方法[J].计算机研究与发展，2012.11：164-171

[4] 李书全，孙雪，孙德辉.遗传算法中的交叉算子的述评[J].计算机工程与应用，2012.1：40-43

[5] 刘健，李京航，柏小丽.基于精英保留策略遗传算法的配电网无功优化[J].电气技术，2015.4：55-58

[6] 李书全，孙雪，孙德辉.遗传算法中的交叉算子的述评[J].计算机工程与应用，2012.1：40-43

[7] 刘健，李京航，柏小丽.基于精英保留策略遗传算法的配电网无功优化[J].电气技术，2015.4：55-58