李 政， 方 舟， 吴 权

(1. 天海融合防务装备技术股份有限公司， 上海 201612； 2. 嘉兴南洋职业技术学院， 浙江 嘉兴 314031)

应用于船舶型材套料的遗传算法关键技术

李 政1， 方 舟2， 吴 权1

(1. 天海融合防务装备技术股份有限公司， 上海 201612； 2. 嘉兴南洋职业技术学院， 浙江 嘉兴 314031)

为能将遗传算法高效地运用于船舶型材套料，针对船舶型材套料的特点提出一种新颖、简洁、可匹配零件附加信息且易于编程实现的遗传算法基因编码规则，并设计相应的交叉、变异和选择策略，据此开发相应的型材套料软件。数值计算试验表明该编码方式能有效提高型材套料利用率，并验证所提出方法的工程实用性。

型材套料；优化组合；遗传算法；基因编码

0 引 言

型材套料(又称一维下料)问题的优化解决方案在机械、建筑、家具等行业都有较高的实际应用价值。当前造船行业，各个环节都十分注重成本控制，型材在船舶结构中占据重要地位，如何高效地提高型材原材料的利用率越来越受到重视。

型材套料问题，从理论角度分析，可对参与套料的型材零件进行长度的全排列，然后挑选出其中的最优组合方案，但当型材数量超过一定数值之后将大幅增加计算复杂度[1]，计算所需的时间将远远超出所能接受的范围，这个问题则变成了NP难题。目前已有许多学者对此进行了研究。经过对多种智能优化算法的比较，本文选择进一步改进遗传算法的编码方式以获得更适用于船舶型材套料的解决方案。

目前已有的采用遗传算法用于船舶型材套料的解决方案都存在一定局限性：限定原材料为单一长度[2-3]，而船舶型材的原材料通常有多种长度可选用，且长度各异的余料需要被再次利用；加入了下料先后、交货期等时间因素[4]，使问题变得更加复杂，不适合船舶行业目前的生产需求；编码中只包含了型材零件长度，未包含原材料长度，而实际进化策略与原材料长度紧密相关；编码方式过于复杂[5]，增加了编程实现的难度。这些解决方案都只讨论了长度优化组合问题，在编码机制上并未考虑到运算结果最终要以包含零件附加信息(如规格材质、横截面形状、下料后进一步的加工方式及工位等)的图纸呈现出来，如果直接以实数表示各零件长度的一个排列作为一个染色体,在解码过程中由于浮点数精度的问题易导致按照长度匹配的零件附加信息出现错乱。

本文提出一种新颖的用于解决型材套料问题的遗传算法编码规则，其特点有：个体编码中将原材料长度和零件长度同时放置在编码中，使交叉、变异运算进行得更充分，提高算法的全局搜索能力；确保解码后零件附加信息与要求的内容一致。

1 型材套料数学模型

为简化数学模型和约束条件，本文将所有可使用的原材料和参与套料零件进行一一列举，形成两个排列，长度相同的不再进行累加计数，即：设有原材料M根，则形成长度排列为L1,L2,…,LM；需要下料的零件为N件，则形成长度排列为l1,l2,…,lN。

在实际生产过程中，采用任何切割方式(如火焰切割、水刀切割、冷切割)，零件与零件之间有一定的切割间隙，此处l1,l2,…,lN是零件长度加上切割间隙所得的数值。

通过计算，需要实现原材料的利用率最大化，故目标函数为

(1)

约束条件为

(2)

(3)

当存在零件长度超过原材料长度或原材料数量不足时，式(2)取小于符号；当原材料有剩余时，式(3)取小于符号。

第i根原材料Li上排列的零件数量为Ki，应满足：

(4)

(5)

2 遗传算法编码及策略设计

采用Python语言实现遗传算法。

在正式进入遗传算法之前，先对原材料数据和零件数据作简单处理。生成原材料长度列表及其对应的附加信息列表，按原材料长度值由小到大顺序排列；生成零件长度列表及其对应的附加信息列表，按零件长度值由小到大顺序排列：

(6)

经处理后的每一根原材料和每一个零件都有了唯一下标。

2.1 基因编码

2.1.1 基因编码的基本形式及解码

个体基因编码的基本形式由式(6) List Raw Length和List Part Length两个List中的下标值构成：

(7)

式中：i为随机选择的List Raw Length一个下标值；k1,k2,…,kx为随机选择的List Part Length中若干个下标值组成的序列。需特别指出的是该序列中的数值不能重复出现。例如，如果i=0,k1=2,k2=0,kx=N-1，则式(7)可迅速解码得

(8)

这个列表必须满足式(4)。

通过下标值在式(6) List Raw Information和List Part Information两个List中可取得相应原材料和零件的附加信息，确保与零件长度的严格匹配。

2.1.2 基因编码长度确定及结构优化

为避免种群中因个体基因长度差异对各种进化策略的操作带来不便，需统一基因编码长度。具体方法为

(1) 个体基因长度n。该数值由下式确定：

(9)

(2) 统一基因编码长度。随机生成个体基因编码的基本形式(如式(7))后，如果列表长度(基因编码长度)不足n，则在列表的第一个元素(原材料长度)之后的任意位置随机插入n-1-kx个None(Python语言语法中的空值)占位，确保基因长度统一，则式(7)变为

(10)

式中：None的位置随机出现。

2.2 适应度

适应度是用于判定个体基因优劣的标准，基因越优秀则其适应度数值就越大。适应度是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。本文采用原材料利用率高低作为套料结果优劣的评判标准，根据式(1)、式(6)和式(10)可知个体的适应度函数为

(11)

2.3 初始化种群

按式(10)的形式，随机产生数量为G的不重复的个体，同时计算每一个个体的适应度，此为遗传算法的初始种群。

2.4 选择运算

选择运算是实现遗传过程中优胜劣汰的操作手段：适应度高的个体遗传到下一代的概率大于适应度低的个体。遗传算法中的选择运算通常采用轮盘赌选择法：个体被选中的概率与其适应度函数值大小成正比。

个体s的适应度为fs，则个体s被选中遗传到下一代的概率为

(12)

为模拟轮盘赌操作，还需要计算个体s的被选中累积概率：

(13)

生成0～1之间的随机数，个体累积概率与之匹配的则遗传到下一代群体。

2.5 交叉运算

交叉运算是产生新个体的主要方法，在遗传算法中起关键作用。交叉点数量的选取应随基因长度增加而适当增加。经过交叉运算后得到的新个体其适应度如优于旧个体，则将新个体复制到新的群体中。

2.6 变异运算

变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。本文的变异运算方法为随机选择一个新的下标值替换个体基因某一位置的数值。除此之外，可以参见文献[6]的方法进行变异运算。

3 计算实例

原材料长度和数量如表1所示。

表1 原材料长度和数量

零件长度如表2所示。

表2 零件长度 mm

运算结果如表3所示。

表3 运算结果 mm

4 结 语

本文针对船舶型材的特点，提出由原材料列表和零件长度列表下标值构成的遗传算法编码，可确保解码后零件附加信息与要求的内容严格一致；个体编码长度一致，便于交叉运算；将原材料长度和零件长度同时放置在编码中，使交叉、变异运算进行得更充分，提高算法的全局搜索能力，在遗传策略方面与实践过程中应能持续改进。

本文给出的实例运算结果其利用率为99.14%。大量数值试验得出，在零件足够多的前提下能使材料利用率达到97%以上，具有很强的工程实用性。

在编写应用软件时应注意添加提示用户注意的信息，如原材料不足、零件超长等。

[1] MAGNUS L H. Python Algorithms:Mastering Basic Algorithms in the Python Language[M]. California Berkeley：Apress，2010.

[2] 吴迪，李长荣，宋广军. 基于蜂群遗传算法的一维优化下料问题[J]. 计算机技术与发展，2010(10):82-85.

[3] 李斌，贺飞. 求解一维下料问题的改进混合遗传算法[J]. 内蒙古大学学报(自然科学版)，2014(3):245-250.

[4] 邱红喜. 供应链环境下基于交货期的一维优化下料问题研究[D]. 合肥：合肥工业大学， 2013.

[5] 李元香，张进波，徐静雯，等. 基于变长编码求解一维下料问题的演化算法[J]. 武汉大学学报(理学版)，2001，41(3):289-293.

[6] 寿周翔，王琦晖，王李冬，等. 一维下料的改进遗传算法优化[J]. 计算机时代， 2014(1):36,37,41.

Key Technology of Genetic Algorithm Applied to Hull Profile Nesting

LI Zheng1, FANG Zhou2, WU Quan1

(1. Bestway Marine & Energy Technology Co., Ltd., Shanghai 201612, China；2. Jiaxing Nanyang Polytechnic Institute, Jiaxing 314031, Zhejiang, China)

For the purpose of applying genetic algorithm to hull profile nesting efficiently, a gene encoding rule for genetic algorithm is presented according to the characteristics of the hull profile, which is novel, concise, matching additional information of hull profile perfectly, and easy to code, and the rules for crossover, mutation and selection are designed. The profile nesting software is developed accordingly. Numerical tests show that the proposed method can improve the utilization ratio effectively, which proves validity in engineering application.

profile nesting; optimization; genetic algorithm; genetic encoding

上海市信息化发展专项资金，编号：201601046

李 政(1983-)，男，工程师，研究方向为船舶智能制造、船舶减振降噪

1000-3878(2017)04-0024-04

U671

A