壽周翔等

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

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

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

0 引言

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

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

1.1 問(wèn)題定義

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

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

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

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

2.1 編碼方法

2.2 解碼方法

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

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

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

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

3.1 初始種群

3.2 遺傳算子

⑴ 交叉算子

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

⑵ 變異算子

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

傳統(tǒng)的變異率是恒定不變的。基于生物進(jìn)化學(xué)說(shuō)，兩個(gè)優(yōu)秀的父代得到的子代往往是比較優(yōu)良的，而兩個(gè)較差的父代往往得到的子代不會(huì)優(yōu)秀。所以在遺傳算法進(jìn)化的初期，上一代的適應(yīng)度往往不會(huì)太高，經(jīng)過(guò)交叉之后往往也不盡如人意。因此較高的變異率則是有助于盡快地進(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ù)?？梢钥闯鲎儺惵实姆秶菑?.1到0.9。這是因?yàn)樵谶M(jìn)化的后期也需要一定的變異率用來(lái)提高下代種群的適應(yīng)度。

⑶ 選擇算子

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

3.3 結(jié)束條件

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

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

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

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

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

5 結(jié)束語(yǔ)

本文針對(duì)工程實(shí)際中的一維下料問(wèn)題，提出了求解該類問(wèn)題的改進(jìn)遺傳算法，該算法設(shè)計(jì)簡(jiǎn)單，原理易于理解。實(shí)例計(jì)算結(jié)果證實(shí)了本算法的有效性，而且計(jì)算時(shí)間較短，同時(shí)，原材料的利用率也達(dá)到了較高的水平，對(duì)同一問(wèn)題多次運(yùn)行可以給出多種利用率相近的方案，便于從多個(gè)優(yōu)化結(jié)果中擇優(yōu)，可以滿足生產(chǎn)的需要。今后對(duì)于排樣問(wèn)題的研究，還須對(duì)多目標(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] 賈志新，殷國(guó)富，胡曉兵等.一維下料方案的遺傳算法優(yōu)化[J].西安交

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

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

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

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

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