一維下料的改進(jìn)遺傳算法優(yōu)化

壽周翔等

摘 要： 針對一維下料優(yōu)化問題，在對一維下料方案數(shù)學(xué)模型分析的基礎(chǔ)上，提出了基于改進(jìn)遺傳算法的優(yōu)化求解方案。主要思想是把零件的一個順序作為一種下料方案，定義了遺傳算法中的關(guān)鍵問題：編碼、解碼方法、遺傳算子和適應(yīng)度函數(shù)的定義。該算法設(shè)計了一種新穎的遺傳算子，包括順序交叉算子、線性變異算子、擴(kuò)展選擇算子。根據(jù)這一算法開發(fā)出了一維下料方案的優(yōu)化系統(tǒng)。實際應(yīng)用表明，該算法逼近理論最優(yōu)值，而且收斂速度快，較好地解決了一維下料問題。

關(guān)鍵詞： 一維下料； 遺傳算法； 最優(yōu)交叉； 優(yōu)化

中圖分類號：TH122；TP391.7 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2014）01-36-02

0 引言

一維下料優(yōu)化問題是討論從一種規(guī)格的材料中，分切出各種不同長度的坯料，以使材料的利用率最高。這類優(yōu)化問題在機(jī)械、建筑、木材，甚至布料等行業(yè)中具有廣泛而實際的應(yīng)用。一維下料問題屬于NP難問題。國內(nèi)外關(guān)于這方面的研究十分活躍，并且提出了不少優(yōu)化算法，如Dyckhoff H.提出的線性規(guī)劃方法[1]以及Sarker B. R.提出的動態(tài)規(guī)劃方法[2]等。但這些算法過于復(fù)雜，也未能有效地解決巨大數(shù)量切割方式的優(yōu)選問題。本文討論以傳統(tǒng)遺傳算法為基礎(chǔ)，改進(jìn)了傳統(tǒng)的交叉算子、變異算子和選擇算子，實現(xiàn)了不錯的效果，能夠在較短的時間內(nèi)得到利用率較高的排樣方式。

1 一維下料問題的數(shù)學(xué)模型

1.1 問題定義

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

根據(jù)問題描述，首先找到這些零件的組合方式，即哪幾個零件組合使得每一個原材料的余料最小，假設(shè)有m種下料方式。根據(jù)每種零件的需求量，求取每一種下料方式應(yīng)用的次數(shù)：

求出每種下料方式所產(chǎn)生的余料長度：

2 一維下料方案優(yōu)化問題的求解方法

2.1 編碼方法

2.2 解碼方法

由編碼方法產(chǎn)生個體的編碼后，需通過解碼算法得到其所需原材料的數(shù)目，計算其適應(yīng)度值后，才能對該個體進(jìn)行評價，相應(yīng)的解碼算法如下。

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

對于一維下料問題，用適應(yīng)度函數(shù)來評價遺傳算法時，適應(yīng)度越大，解的質(zhì)量越好，自然的想法是取所需原材料總概數(shù)的倒數(shù)，但當(dāng)二種方案需要原材料根數(shù)相同時，則最后一根余料較長者顯然更優(yōu)，所以本算法采用的適應(yīng)度函數(shù)是：，其中Qm為所用的原材料數(shù)量，L'為最后根原材料所用的長度。那么適應(yīng)度最高為1。

3 一維下料方案遺傳算法的求解過程

3.1 初始種群

3.2 遺傳算子

⑴ 交叉算子

基于生物進(jìn)化學(xué)說，兩個優(yōu)秀的父輩得到的子代往往是比較優(yōu)良的，而兩個較差的父輩得到的子代往往不會優(yōu)秀。因此本算法交叉算子的設(shè)計采用順序交叉的方案[4]，即將父輩按適應(yīng)度降序排序后，采用雙點交叉算子按順序相鄰二二交叉，該算子是在父序列P1中隨機(jī)產(chǎn)生兩個交叉位b1與b2，在這兩個隨機(jī)位之內(nèi)的元素將復(fù)制到新的序列Pnew的對應(yīng)位置。剩余的元素按父序列P2的先后順序依次復(fù)制到Pnew，得到新的序列Pnew。以同樣的方法得到另一個新的子序列Qnew。

⑵ 變異算子

傳統(tǒng)遺傳算法的變異算子主要有位置變異與顛倒位序變異。位置變異是在序列中隨機(jī)得到兩個隨機(jī)位，并將這兩個隨機(jī)位的元素加以對換。顛倒位序變異是在序列中隨機(jī)得到一個隨機(jī)位，并在這隨機(jī)位之后的元素加以顛倒。本算法還采用了模擬基因突變的缺失與增添。缺失是父序列中隨機(jī)取出一個變異位，在該變異位之后的位都向前移一位，最后將取出的變異位添加到最末位。增添是在父序列上隨機(jī)得到一個變異位。將在此變異位之后的位都向后移一位，最后將父序列中最后的位添加到變異位得到新的子序列。由這兩種算子加上傳統(tǒng)的位置變異與顛倒序列變異，在變異概率下，有一定概率執(zhí)行前面四種變異算子，這樣一來進(jìn)化的多樣性會大大提高，更有概率能接近最優(yōu)解。

傳統(tǒng)的變異率是恒定不變的。基于生物進(jìn)化學(xué)說，兩個優(yōu)秀的父代得到的子代往往是比較優(yōu)良的，而兩個較差的父代往往得到的子代不會優(yōu)秀。所以在遺傳算法進(jìn)化的初期，上一代的適應(yīng)度往往不會太高，經(jīng)過交叉之后往往也不盡如人意。因此較高的變異率則是有助于盡快地進(jìn)化得到較好的下一代。而在進(jìn)化的后期，上一代的適應(yīng)度往往趨近于最高，較高的變異率有可能破壞原有的優(yōu)良基因，導(dǎo)致子代的適應(yīng)度降低。基于這樣考慮，該系統(tǒng)采用線性的變異率，變異率隨著遺傳代數(shù)的增加而降低。變異率的線性變化公式為：R=（0.8G-g）/G+0.1，其中R為當(dāng)前代數(shù)的變異率，G表示的是遺傳算法需要進(jìn)化的總代數(shù)，而g表示當(dāng)前的進(jìn)化代數(shù)。可以看出變異率的范圍是從0.1到0.9。這是因為在進(jìn)化的后期也需要一定的變異率用來提高下代種群的適應(yīng)度。

⑶ 選擇算子

傳統(tǒng)的遺傳算法是由上一代經(jīng)過交叉與一定概率的變異得到兩個下一代。而有可能存在的問題就是在上一代經(jīng)過交叉之后就得到了適應(yīng)度較高的個體，再經(jīng)過變異之后適應(yīng)度有所降低。因此本算法采用擴(kuò)展選擇算子，由上一代經(jīng)過交叉后得到兩個子代，與由這兩個子代個體經(jīng)過一定概率的變異得到兩個子代個體并存。最后將得到的子代與父代通過計算適應(yīng)度篩選出nScale個最優(yōu)個體交給下一次進(jìn)化。如此就避免進(jìn)化途中的浪費，錯過適應(yīng)度較高的解。

3.3 結(jié)束條件

重復(fù)執(zhí)行上面的⑴、⑵、⑶步驟，直到最好解的適應(yīng)度值達(dá)到要求或滿足了預(yù)定的進(jìn)化代數(shù)，才能停止計算，并輸出最優(yōu)解。

4 計算實例

為了測試本算法的性能，我們借鑒文獻(xiàn)[5]中的例子。原材料長3m，需切割的零件分別為長2.2m的3件、長1.8m的3件、長1.2m的4件、長0.5m的6件、長0.3m的6件。求最優(yōu)下料方案（不考慮切口損失）。

文獻(xiàn)[5]采用啟發(fā)式多級序列線性優(yōu)化方法計算，能保證高的材料利用率，而且計算速度也高。但隨著零件規(guī)模的擴(kuò)大，計算時間也會爆炸。而基于改進(jìn)遺傳算法的求解方法雖然對同一問題需要多次運行，從多種下料方案中擇優(yōu)，但計算僅用0.6s就取得了最好解，而且是求解組合爆炸問題的最好選擇。表1和表2是文獻(xiàn)[5]與本文算法的對比。

表2若不計編號8的原料，則余下的原料利用率都為100%。而編號8的原料具備最長的余料，還可以進(jìn)一步利用。計算結(jié)果很理想。

5 結(jié)束語

本文針對工程實際中的一維下料問題，提出了求解該類問題的改進(jìn)遺傳算法，該算法設(shè)計簡單，原理易于理解。實例計算結(jié)果證實了本算法的有效性，而且計算時間較短，同時，原材料的利用率也達(dá)到了較高的水平，對同一問題多次運行可以給出多種利用率相近的方案，便于從多個優(yōu)化結(jié)果中擇優(yōu)，可以滿足生產(chǎn)的需要。今后對于排樣問題的研究，還須對多目標(biāo)優(yōu)化給予重視，以滿足各種生產(chǎn)環(huán)境的需求。

參考文獻(xiàn)：

[1] Dyckhoff H. A New Linear Programming Approach to the Cutting

Stock Problem[J].Opns Res，1981.29（6）：1094-1104

[2] Sarker B R. An optimum solution for one dimensional slitting

problems：A Dynamic Programming Approach[J].J opl Res Soc，1988.39（8）：749-755

[3] 賈志新，殷國富，胡曉兵等.一維下料方案的遺傳算法優(yōu)化[J].西安交

通大學(xué)學(xué)報，2002.36（9）：967-970

[4] 吳迪，李長榮等.基于蜂群遺傳算法的一維優(yōu)化下料問題[J].計算機(jī)

技術(shù)與發(fā)展，2010.20（10）：82-85

[5] 王小東，李剛，歐宗瑛.一維下料優(yōu)化的一種新算法[J].大連理工大學(xué)

學(xué)報，2004.44（3）：407-411