基于遺傳算法的多規(guī)格管材或型材的優(yōu)化下料

劉在良 翁旭輝 王靜 夏小浩

摘? 要： 在船舶建造中存在大量的管材或型材需求，這些材料的一維優(yōu)化下料（一維套料）問(wèn)題一直在被研究。文章提出了一種基于遺傳算法的求解方法，建立了數(shù)學(xué)模型，給出了編碼解碼方案和交叉變異方法等，并結(jié)合實(shí)際情況提出一種方法利用近似優(yōu)化算法來(lái)修復(fù)無(wú)效基因，同時(shí)還在代代相傳中采用精英保留策略盡可能保留每代最優(yōu)解，有利于加快收斂。實(shí)例結(jié)果表明該算法的有效性，符合預(yù)期目標(biāo)。

關(guān)鍵詞： 一維優(yōu)化下料; 遺傳算法; 優(yōu)化算法; 一維套料

中圖分類號(hào)：U671.2? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：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 引言

在船舶建造過(guò)程中，如何減少浪費(fèi)，不斷的提高材料利用率一直是各大船廠追求的目標(biāo)，如何用數(shù)學(xué)方法來(lái)最大化利用材料也一直被討論。在這些問(wèn)題當(dāng)中有一種以長(zhǎng)度作為唯一維度的下料方式，又稱之為一維排料問(wèn)題。本文討論的問(wèn)題適用于多種長(zhǎng)度原材料下料問(wèn)題。

此類問(wèn)題比較常見(jiàn)的有啟發(fā)式方法或線性規(guī)劃方法（文獻(xiàn)[1-2]），常規(guī)的數(shù)學(xué)方法受零件尺寸跨度和數(shù)量級(jí)影響較大，而遺傳算法理論作為全局搜索進(jìn)化的方式，可以取得到較好的效果，本文將討論遺傳算法在管材或型材下料中的應(yīng)用及效果。

1 數(shù)學(xué)模型

多規(guī)格管材或型材下料問(wèn)題可理解為裝箱問(wèn)題，描述如下：設(shè)有n個(gè)物品，每個(gè)物品的體積分別為：Vi，i=1，2，…，n，有m種箱子容量分別為L(zhǎng)i，i=1，2，…，m，現(xiàn)規(guī)定箱子數(shù)量無(wú)限使用，求把這n個(gè)物品全部放進(jìn)箱子，怎么放才能使箱子利用率最高？當(dāng)物品數(shù)量達(dá)到一定規(guī)模，箱子也不只一種的時(shí)候，這種計(jì)算就變的相對(duì)復(fù)雜，這就是NP（Non-deterministic Polynomial）難題，通常復(fù)雜的NP難題只能得到近似最優(yōu)解。

式⑴中l(wèi)jk為在第j根原材料上第k個(gè)下料零件的長(zhǎng)度，w表示第j根原材料上總共下料w個(gè)零件。式⑵表示為下料零件的總長(zhǎng)與材料總長(zhǎng)比值最大，即利用率最大，為了要達(dá)到的優(yōu)化目標(biāo)。

在實(shí)際生產(chǎn)中，我們?cè)谧非罄寐首畲蟮那疤嵯拢紤]把余料集中在某一根原材料以上便于再次利用。設(shè)定最長(zhǎng)余料長(zhǎng)度為Wmax，將式⑵改進(jìn)：

2 遺傳算法

2.1 遺傳算法概述

遺傳算法是一種模仿生物繁衍，自然選擇的思路建立的算法，模仿了遺傳過(guò)程中交叉變異選擇等現(xiàn)象。他從隨機(jī)的樣本中，經(jīng)過(guò)目標(biāo)函數(shù)的評(píng)估得到部分較好的個(gè)體，將這些個(gè)體按評(píng)估高級(jí)分級(jí)選取概率進(jìn)行交叉變異得到新的個(gè)體，然后在新群體基礎(chǔ)上，繼續(xù)發(fā)展下一代，向更優(yōu)方向發(fā)展為趨勢(shì)，直到得到近似最優(yōu)結(jié)果后停止。遺傳算法具有全局性和自適應(yīng)性，比較適合處理復(fù)雜事物的優(yōu)化計(jì)算。

2.2 遺傳算法基本定義

遺傳算法有5個(gè)基本組件：初始群體，用于個(gè)體評(píng)價(jià)的適應(yīng)度函數(shù)，選擇器，交叉函數(shù)，變異函數(shù)。定義公式為：

式中：C為編碼函數(shù)，P0為初始群體，S為種群大小，E為適應(yīng)度函數(shù)，F(xiàn)為選擇器，R為交叉函數(shù)，Y為變異函數(shù)，T為終止條件。

遺傳算法過(guò)程如下（圖1）。

2.3 染色體編碼和解碼

2.3.1 編碼

染色體即群體中的個(gè)體，本文采用零件編號(hào)及所在材料編號(hào)的編號(hào)對(duì)作為編碼，設(shè)零件編碼為，材料編碼為，染色體編碼可記為，，表示零件在材料中下料，其中允許重復(fù)，將所有零件編碼產(chǎn)生的一個(gè)解即為個(gè)體。

2.3.2 解碼

解碼是將數(shù)字編碼轉(zhuǎn)換成下料布局表達(dá)。

遍歷里面所有的編號(hào)對(duì)，將材料編號(hào)相同的對(duì)應(yīng)零件編號(hào)匯總。例如其中剛好有 和中的和為同一編號(hào)，那么建立如下列表：，表示編號(hào)為的材料上分布了編號(hào)為和的兩個(gè)零件，我們稱之為下料表，以次類推，建立所有的下料表，完成解碼。

2.4 適應(yīng)度函數(shù)

根據(jù)本文建立的數(shù)學(xué)模型，要求的目標(biāo)是零件下料的利用率最大，如式⑶：

F（x）介于（0，1）之間，數(shù)值越大表示利用率越高，適應(yīng)度越好，本文以此式作為適應(yīng)度函數(shù)評(píng)估個(gè)體質(zhì)量。

2.5 初始種群

2.5.1 產(chǎn)生種群

初始種群P0按隨機(jī)方式產(chǎn)生，方法如下。

⑴ 零件編碼：初始的零件列表認(rèn)為是無(wú)序隨機(jī)狀態(tài)，根據(jù)編碼方法，將這n個(gè)零件按順序編碼為1，2，3，…，n。

⑵ 材料編碼：假設(shè)有m種材料，且每種材料的數(shù)量為無(wú)限使用，設(shè)定每種材料數(shù)量為w，那么材料編碼如下：，第一個(gè)下標(biāo)表示第i種材料，第二個(gè)下標(biāo)表示第i種材料的第j根。

⑶ 個(gè)體：取第i個(gè)零件，按均等概率得到（1，w×m）的隨機(jī)數(shù)r作為隨機(jī)材料編號(hào)， 按零件編碼順序逐個(gè)取零件，建立如下個(gè)體編碼：，可以簡(jiǎn)化為，rn表示第n個(gè)零件放在編號(hào)為rn的材料中。

⑷ 群體：根據(jù)零件數(shù)量設(shè)定一定的群體規(guī)模q，生成q個(gè)隨機(jī)個(gè)體的集合作為一個(gè)種群。

2.5.2 優(yōu)化種群

⑴ 優(yōu)化基因

種群由于完全是隨機(jī)生成，不可避免會(huì)出現(xiàn)沒(méi)有實(shí)際意義的編碼，我們需要找到并修復(fù)錯(cuò)誤基因。將群體中所有的個(gè)體解碼：，即Lk材料上分布了x個(gè)零件，每一個(gè)Lk分布定義為一個(gè)基因，設(shè)第i個(gè)零件的長(zhǎng)度為li，Lk長(zhǎng)度為L(zhǎng)，計(jì)算該材料中下料零件總長(zhǎng)l'=，如果l'>L，表示Lk這個(gè)材料上的零件總長(zhǎng)大于材料長(zhǎng)度，這種下料方式就沒(méi)有實(shí)際意義，需要修復(fù)。本文使用常規(guī)局部?jī)?yōu)化算子（FFD，BF）等修復(fù)錯(cuò)誤基因。

2.6 選擇算子

根據(jù)自然法則，越強(qiáng)大的個(gè)體獲得的交配機(jī)會(huì)也越多，這將使它強(qiáng)大的基因更多可能的遺傳給下一代。遺傳算法中，我們使用以適應(yīng)度作為概率占比的輪盤賭（文獻(xiàn)[3]）算法來(lái)模仿這種不均等概率選擇。

2.7 交叉方法

交叉算子采用單點(diǎn)交叉方法（文獻(xiàn)[4]）。按一定的概率決定是否發(fā)生交叉，本文設(shè)定交叉概率為55%，即群體中約有55%的個(gè)體發(fā)生交叉。方法如下：

先從P0'中隨機(jī)得到兩個(gè)個(gè)體用做交叉運(yùn)算。

設(shè)初始群體的大小為S，那么P0'的大小也為S，從（1，S）中得到兩個(gè)隨機(jī)位置，取得這兩個(gè)位置的個(gè)體（染色體）記為Ta，Tb。

把Ta，Tb兩個(gè)染色體從某個(gè)隨機(jī)交叉點(diǎn)打斷，將交叉點(diǎn)后的編碼互相交換。

設(shè)染色體編碼長(zhǎng)度即零件數(shù)量為n，取（1，n）之間隨機(jī)數(shù)w作為交叉點(diǎn)，將兩個(gè)染色體切分如下：

交叉互換并修復(fù)后，得到第一代新群體，記為P1。

2.8 變異

遺傳算法采用變異機(jī)制來(lái)擾動(dòng)群體，以減少陷入局部解的困境。

設(shè)發(fā)生變異的概率為1%。設(shè)交叉后的群體P1的大小為n，當(dāng)發(fā)生變異時(shí)，從（1，n）中隨機(jī)抽取x個(gè)個(gè)體，將每個(gè)個(gè)體的染色體編碼進(jìn)行隨機(jī)變異。

設(shè)某染色體編碼為，rn表示第n個(gè)零件所在的材料編碼，設(shè)隨機(jī)變異位置為j，那么，將rj替換為（1，w×m）中的一個(gè)隨機(jī)數(shù)rj'，其中m表示不同長(zhǎng)度材料的種類數(shù)，w表示每種材料的數(shù)量。替換后得到新的編碼。

2.9 精英保留策略

在計(jì)算過(guò)程中，某一代偶爾會(huì)出現(xiàn)適應(yīng)度較好的個(gè)體，由于選擇交叉變異等原因沒(méi)有被保留，為此，把父代適應(yīng)度最高的個(gè)體替換掉子代中適應(yīng)度最差的個(gè)體，即精英保留策略（文獻(xiàn)[5]）。

2.10 終止

目標(biāo)函數(shù)為：去除最大剩余長(zhǎng)度后的利用率F。設(shè)定一個(gè)預(yù)期值（利用率），當(dāng)在整個(gè)進(jìn)化過(guò)程中一旦滿足預(yù)期值則終止進(jìn)化計(jì)算并給出最優(yōu)解。

3 實(shí)例

3.1 應(yīng)用界面

應(yīng)用界面如圖2所示。

3.2 實(shí)例對(duì)比

本文分別挑選三種不同船型進(jìn)行優(yōu)化試驗(yàn)，結(jié)果如下（表2）：

⑴ 散貨船案例。以64000噸散貨船為例，全船約118種管材，共14649根管子零件，零件總長(zhǎng)約20690.28米，包含不銹鋼、卷制鋼管、銅管、無(wú)縫鋼管等。按照傳統(tǒng)經(jīng)驗(yàn)預(yù)估材料（根據(jù)管種不同約加放10%～20%左右余量），管材實(shí)船采購(gòu)清單總長(zhǎng)度24658.8米。設(shè)定適應(yīng)度為0.999。

經(jīng)過(guò)優(yōu)化計(jì)算，得到材料總采購(gòu)長(zhǎng)度為21234米，利用率約為97.44%，其中各規(guī)格管子9米長(zhǎng)的共954根，12米長(zhǎng)的共1054根，相比傳統(tǒng)材料預(yù)估法，可以減少訂貨3424.8米。部分優(yōu)化示例見(jiàn)表1。

⑵ 集裝箱船案例。以2200箱集裝箱船為例，全船約103種管材，共20168根管子零件，管零件總長(zhǎng)約25306.85米，管材實(shí)船采購(gòu)清單總長(zhǎng)度27351.026米，經(jīng)過(guò)優(yōu)化算法，得出總采購(gòu)長(zhǎng)度為25803米，其中各管種9米的總共1187根，12米的總共1260根。總長(zhǎng)比傳統(tǒng)經(jīng)驗(yàn)法少1548.026米。

⑶ 油船/化學(xué)品船案例。以11000噸油船/化學(xué)品船為例，全船約111種管材，約14686根管子零件，管零件總長(zhǎng)14012.8米，實(shí)際采購(gòu)總長(zhǎng)15496.8米，經(jīng)過(guò)優(yōu)化算法，得出總采購(gòu)長(zhǎng)度為14415米，其中各管種9米的共615根，12米的共740根，總長(zhǎng)比傳統(tǒng)采購(gòu)少1081.8米。

4 結(jié)論

本文介紹了多規(guī)格管材或型材下料問(wèn)題中的遺傳算法解決方案。結(jié)合三種船型的實(shí)例數(shù)據(jù)可以看到相較與傳統(tǒng)，一條船能節(jié)約管材可以達(dá)到一千多米甚至更多，遺傳算法可以盡可能的減少材料浪費(fèi)，實(shí)現(xiàn)精準(zhǔn)下料，這對(duì)船舶工業(yè)提倡綠色造船、節(jié)能減排等具有積極意義。

在應(yīng)用過(guò)程中還發(fā)現(xiàn)，當(dāng)零件數(shù)量較少且長(zhǎng)度都較接近原材料長(zhǎng)度的情況下，由于始終無(wú)法達(dá)到目標(biāo)函數(shù)從而導(dǎo)致算法陷入無(wú)窮的搜索而無(wú)法收斂，這時(shí)需要通過(guò)調(diào)節(jié)目標(biāo)函數(shù)利用率或最大遺傳代數(shù)的設(shè)定來(lái)使得算法終止，所以，還需進(jìn)一步制定一種自動(dòng)調(diào)節(jié)機(jī)制來(lái)加快收斂，便于實(shí)際應(yīng)用。

參考文獻(xiàn)（References）：

[1] 祝勝蘭，饒運(yùn)清.一維下料問(wèn)題的啟發(fā)式方法[J].機(jī)械制造與自動(dòng)化，2014：58-61

[2] 崔耀東，周密，楊柳.多線材一維下料問(wèn)題的求解策略[J].廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012.3：169-173

[3] 胡新平，賀玉芝，倪巍偉.基于賭輪選擇遺傳算法的數(shù)據(jù)隱藏發(fā)布方法[J].計(jì)算機(jī)研究與發(fā)展，2012.11：164-171

[4] 李書全，孫雪，孫德輝.遺傳算法中的交叉算子的述評(píng)[J].計(jì)算機(jī)工程與應(yīng)用，2012.1：40-43

[5] 劉健，李京航，柏小麗.基于精英保留策略遺傳算法的配電網(wǎng)無(wú)功優(yōu)化[J].電氣技術(shù)，2015.4：55-58

[6] 李書全，孫雪，孫德輝.遺傳算法中的交叉算子的述評(píng)[J].計(jì)算機(jī)工程與應(yīng)用，2012.1：40-43

[7] 劉健，李京航，柏小麗.基于精英保留策略遺傳算法的配電網(wǎng)無(wú)功優(yōu)化[J].電氣技術(shù)，2015.4：55-58