應(yīng)用于船舶型材套料的遺傳算法關(guān)鍵技術(shù)

李 政， 方 舟， 吳 權(quán)

(1. 天海融合防務(wù)裝備技術(shù)股份有限公司， 上海 201612； 2. 嘉興南洋職業(yè)技術(shù)學(xué)院， 浙江 嘉興 314031)

應(yīng)用于船舶型材套料的遺傳算法關(guān)鍵技術(shù)

李 政1， 方 舟2， 吳 權(quán)1

(1. 天海融合防務(wù)裝備技術(shù)股份有限公司， 上海 201612； 2. 嘉興南洋職業(yè)技術(shù)學(xué)院， 浙江 嘉興 314031)

為能將遺傳算法高效地運(yùn)用于船舶型材套料，針對船舶型材套料的特點(diǎn)提出一種新穎、簡潔、可匹配零件附加信息且易于編程實(shí)現(xiàn)的遺傳算法基因編碼規(guī)則，并設(shè)計(jì)相應(yīng)的交叉、變異和選擇策略，據(jù)此開發(fā)相應(yīng)的型材套料軟件。數(shù)值計(jì)算試驗(yàn)表明該編碼方式能有效提高型材套料利用率，并驗(yàn)證所提出方法的工程實(shí)用性。

型材套料；優(yōu)化組合；遺傳算法；基因編碼

0 引 言

型材套料(又稱一維下料)問題的優(yōu)化解決方案在機(jī)械、建筑、家具等行業(yè)都有較高的實(shí)際應(yīng)用價(jià)值。當(dāng)前造船行業(yè)，各個環(huán)節(jié)都十分注重成本控制，型材在船舶結(jié)構(gòu)中占據(jù)重要地位，如何高效地提高型材原材料的利用率越來越受到重視。

型材套料問題，從理論角度分析，可對參與套料的型材零件進(jìn)行長度的全排列，然后挑選出其中的最優(yōu)組合方案，但當(dāng)型材數(shù)量超過一定數(shù)值之后將大幅增加計(jì)算復(fù)雜度[1]，計(jì)算所需的時間將遠(yuǎn)遠(yuǎn)超出所能接受的范圍，這個問題則變成了NP難題。目前已有許多學(xué)者對此進(jìn)行了研究。經(jīng)過對多種智能優(yōu)化算法的比較，本文選擇進(jìn)一步改進(jìn)遺傳算法的編碼方式以獲得更適用于船舶型材套料的解決方案。

目前已有的采用遺傳算法用于船舶型材套料的解決方案都存在一定局限性：限定原材料為單一長度[2-3]，而船舶型材的原材料通常有多種長度可選用，且長度各異的余料需要被再次利用；加入了下料先后、交貨期等時間因素[4]，使問題變得更加復(fù)雜，不適合船舶行業(yè)目前的生產(chǎn)需求；編碼中只包含了型材零件長度，未包含原材料長度，而實(shí)際進(jìn)化策略與原材料長度緊密相關(guān)；編碼方式過于復(fù)雜[5]，增加了編程實(shí)現(xiàn)的難度。這些解決方案都只討論了長度優(yōu)化組合問題，在編碼機(jī)制上并未考慮到運(yùn)算結(jié)果最終要以包含零件附加信息(如規(guī)格材質(zhì)、橫截面形狀、下料后進(jìn)一步的加工方式及工位等)的圖紙呈現(xiàn)出來，如果直接以實(shí)數(shù)表示各零件長度的一個排列作為一個染色體,在解碼過程中由于浮點(diǎn)數(shù)精度的問題易導(dǎo)致按照長度匹配的零件附加信息出現(xiàn)錯亂。

本文提出一種新穎的用于解決型材套料問題的遺傳算法編碼規(guī)則，其特點(diǎn)有：個體編碼中將原材料長度和零件長度同時放置在編碼中，使交叉、變異運(yùn)算進(jìn)行得更充分，提高算法的全局搜索能力；確保解碼后零件附加信息與要求的內(nèi)容一致。

1 型材套料數(shù)學(xué)模型

為簡化數(shù)學(xué)模型和約束條件，本文將所有可使用的原材料和參與套料零件進(jìn)行一一列舉，形成兩個排列，長度相同的不再進(jìn)行累加計(jì)數(shù)，即：設(shè)有原材料M根，則形成長度排列為L1,L2,…,LM；需要下料的零件為N件，則形成長度排列為l1,l2,…,lN。

在實(shí)際生產(chǎn)過程中，采用任何切割方式(如火焰切割、水刀切割、冷切割)，零件與零件之間有一定的切割間隙，此處l1,l2,…,lN是零件長度加上切割間隙所得的數(shù)值。

通過計(jì)算，需要實(shí)現(xiàn)原材料的利用率最大化，故目標(biāo)函數(shù)為

(1)

約束條件為

(2)

(3)

當(dāng)存在零件長度超過原材料長度或原材料數(shù)量不足時，式(2)取小于符號；當(dāng)原材料有剩余時，式(3)取小于符號。

第i根原材料Li上排列的零件數(shù)量為Ki，應(yīng)滿足：

(4)

(5)

2 遺傳算法編碼及策略設(shè)計(jì)

采用Python語言實(shí)現(xiàn)遺傳算法。

在正式進(jìn)入遺傳算法之前，先對原材料數(shù)據(jù)和零件數(shù)據(jù)作簡單處理。生成原材料長度列表及其對應(yīng)的附加信息列表，按原材料長度值由小到大順序排列；生成零件長度列表及其對應(yīng)的附加信息列表，按零件長度值由小到大順序排列：

(6)

經(jīng)處理后的每一根原材料和每一個零件都有了唯一下標(biāo)。

2.1 基因編碼

2.1.1 基因編碼的基本形式及解碼

個體基因編碼的基本形式由式(6) List Raw Length和List Part Length兩個List中的下標(biāo)值構(gòu)成：

(7)

式中：i為隨機(jī)選擇的List Raw Length一個下標(biāo)值；k1,k2,…,kx為隨機(jī)選擇的List Part Length中若干個下標(biāo)值組成的序列。需特別指出的是該序列中的數(shù)值不能重復(fù)出現(xiàn)。例如，如果i=0,k1=2,k2=0,kx=N-1，則式(7)可迅速解碼得

(8)

這個列表必須滿足式(4)。

通過下標(biāo)值在式(6) List Raw Information和List Part Information兩個List中可取得相應(yīng)原材料和零件的附加信息，確保與零件長度的嚴(yán)格匹配。

2.1.2 基因編碼長度確定及結(jié)構(gòu)優(yōu)化

為避免種群中因個體基因長度差異對各種進(jìn)化策略的操作帶來不便，需統(tǒng)一基因編碼長度。具體方法為

(1) 個體基因長度n。該數(shù)值由下式確定：

(9)

(2) 統(tǒng)一基因編碼長度。隨機(jī)生成個體基因編碼的基本形式(如式(7))后，如果列表長度(基因編碼長度)不足n，則在列表的第一個元素(原材料長度)之后的任意位置隨機(jī)插入n-1-kx個None(Python語言語法中的空值)占位，確?；蜷L度統(tǒng)一，則式(7)變?yōu)?/p>

(10)

式中：None的位置隨機(jī)出現(xiàn)。

2.2 適應(yīng)度

適應(yīng)度是用于判定個體基因優(yōu)劣的標(biāo)準(zhǔn)，基因越優(yōu)秀則其適應(yīng)度數(shù)值就越大。適應(yīng)度是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。本文采用原材料利用率高低作為套料結(jié)果優(yōu)劣的評判標(biāo)準(zhǔn)，根據(jù)式(1)、式(6)和式(10)可知個體的適應(yīng)度函數(shù)為

(11)

2.3 初始化種群

按式(10)的形式，隨機(jī)產(chǎn)生數(shù)量為G的不重復(fù)的個體，同時計(jì)算每一個個體的適應(yīng)度，此為遺傳算法的初始種群。

2.4 選擇運(yùn)算

選擇運(yùn)算是實(shí)現(xiàn)遺傳過程中優(yōu)勝劣汰的操作手段：適應(yīng)度高的個體遺傳到下一代的概率大于適應(yīng)度低的個體。遺傳算法中的選擇運(yùn)算通常采用輪盤賭選擇法：個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。

個體s的適應(yīng)度為fs，則個體s被選中遺傳到下一代的概率為

(12)

為模擬輪盤賭操作，還需要計(jì)算個體s的被選中累積概率：

(13)

生成0～1之間的隨機(jī)數(shù)，個體累積概率與之匹配的則遺傳到下一代群體。

2.5 交叉運(yùn)算

交叉運(yùn)算是產(chǎn)生新個體的主要方法，在遺傳算法中起關(guān)鍵作用。交叉點(diǎn)數(shù)量的選取應(yīng)隨基因長度增加而適當(dāng)增加。經(jīng)過交叉運(yùn)算后得到的新個體其適應(yīng)度如優(yōu)于舊個體，則將新個體復(fù)制到新的群體中。

2.6 變異運(yùn)算

變異運(yùn)算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。本文的變異運(yùn)算方法為隨機(jī)選擇一個新的下標(biāo)值替換個體基因某一位置的數(shù)值。除此之外，可以參見文獻(xiàn)[6]的方法進(jìn)行變異運(yùn)算。

3 計(jì)算實(shí)例

原材料長度和數(shù)量如表1所示。

表1 原材料長度和數(shù)量

零件長度如表2所示。

表2 零件長度 mm

運(yùn)算結(jié)果如表3所示。

表3 運(yùn)算結(jié)果 mm

4 結(jié) 語

本文針對船舶型材的特點(diǎn)，提出由原材料列表和零件長度列表下標(biāo)值構(gòu)成的遺傳算法編碼，可確保解碼后零件附加信息與要求的內(nèi)容嚴(yán)格一致；個體編碼長度一致，便于交叉運(yùn)算；將原材料長度和零件長度同時放置在編碼中，使交叉、變異運(yùn)算進(jìn)行得更充分，提高算法的全局搜索能力，在遺傳策略方面與實(shí)踐過程中應(yīng)能持續(xù)改進(jìn)。

本文給出的實(shí)例運(yùn)算結(jié)果其利用率為99.14%。大量數(shù)值試驗(yàn)得出，在零件足夠多的前提下能使材料利用率達(dá)到97%以上，具有很強(qiáng)的工程實(shí)用性。

在編寫應(yīng)用軟件時應(yīng)注意添加提示用戶注意的信息，如原材料不足、零件超長等。

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

[2] 吳迪，李長榮，宋廣軍. 基于蜂群遺傳算法的一維優(yōu)化下料問題[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2010(10):82-85.

[3] 李斌，賀飛. 求解一維下料問題的改進(jìn)混合遺傳算法[J]. 內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014(3):245-250.

[4] 邱紅喜. 供應(yīng)鏈環(huán)境下基于交貨期的一維優(yōu)化下料問題研究[D]. 合肥：合肥工業(yè)大學(xué)， 2013.

[5] 李元香，張進(jìn)波，徐靜雯，等. 基于變長編碼求解一維下料問題的演化算法[J]. 武漢大學(xué)學(xué)報(bào)(理學(xué)版)，2001，41(3):289-293.

[6] 壽周翔，王琦暉，王李冬，等. 一維下料的改進(jìn)遺傳算法優(yōu)化[J]. 計(jì)算機(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

上海市信息化發(fā)展專項(xiàng)資金，編號：201601046

李 政(1983-)，男，工程師，研究方向?yàn)榇爸悄苤圃?、船舶減振降噪

1000-3878(2017)04-0024-04

U671

A