基于遺傳算法的多規格管材或型材的優化下料

劉在良 翁旭輝 王靜 夏小浩

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

關鍵詞： 一維優化下料; 遺傳算法; 優化算法; 一維套料

中圖分類號：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