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

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

0 引 言

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

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

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

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

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

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

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

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

(1)

約束條件為

(2)

(3)

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

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

(4)

(5)

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

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

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

(6)

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

2.1 基因編碼

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

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

(7)

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

(8)

這個(gè)列表必須滿(mǎn)足式(4)。

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

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

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

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

(9)

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

(10)

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

2.2 適應(yīng)度

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

(11)

2.3 初始化種群

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

2.4 選擇運(yùn)算

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

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

(12)

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

(13)

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

2.5 交叉運(yùn)算

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

2.6 變異運(yùn)算

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

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

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

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

零件長(zhǎng)度如表2所示。

表2 零件長(zhǎng)度 mm

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

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

4 結(jié) 語(yǔ)

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

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

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

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

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

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

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

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

[6] 壽周翔，王琦暉，王李冬，等. 一維下料的改進(jìn)遺傳算法優(yōu)化[J]. 計(jì)算機(jī)時(shí)代， 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ā)展專(zhuān)項(xiàng)資金，編號(hào)：201601046

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

1000-3878(2017)04-0024-04

U671

A