應用于船舶型材套料的遺傳算法關鍵技術

李 政， 方 舟， 吳 權

(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