基于遺傳算法對二維下料問題的研究

摘要：切割問題是生活中常見的一類問題。本文依據(jù)線性規(guī)劃方程和遺傳算法來研究矩形切割問題。對于復(fù)雜的二維下料問題，所需木板樣件的種類樣式增多，可采用遺傳算法，改變木板切割的適應(yīng)度函數(shù)，從而實現(xiàn)木板切割的利用率最大化。

關(guān)鍵詞：線性規(guī)劃方程;遺傳算法;二維下料

矩形切割問題是二維切割一個重要研究方向，怎樣實現(xiàn)木材最優(yōu)化切割，使木板的利用率達到最高，是工業(yè)生產(chǎn)的重要課題。近幾年來，隨著傳統(tǒng)算法的發(fā)展，各種智能算法的不斷完善著矩形切割的方案。而本文是利用遺傳算法探究在一塊木板上的二維下料問題。

一、單一木板切割模型的建立

僅含一種約束條件：假設(shè)對一個長為3000mm、寬為1500mm的矩形木板進行切割，需要得到n個矩形原件P1（長為373mm寬為201mm）。不考慮木板的厚度，怎樣切割才能得到最多的矩形原件P1，實現(xiàn)木板的利用率最大化呢？

木板利用率與切割出的小矩形的數(shù)量成正相關(guān)。依據(jù)運籌學(xué)中的整數(shù)規(guī)劃問題，可將切割問題分為橫向切割和縱向切割兩種方案。由于斜向切割會造成原料的濫用且討論情況更復(fù)雜，所以不采用斜向切割的方式。通過構(gòu)建線性規(guī)劃方程組，以木板的長、寬為限制條件，得出使木板材料剩余面積最小的方案。

根據(jù)木板的排放方式，建立整數(shù)規(guī)劃方程組：

式中：木板的長與寬分別為L、W;P1原件的長與寬分別為l1、w1;m表示將P1原件的寬w1沿著木板的L方向排列的個數(shù);b指P1原件的長l1沿著木板的W方向排列的個數(shù)。運用LINGO軟件對方程組求解得：m=13，n=1，a=0，b=4.即目標(biāo)值z=44888，但并不是最優(yōu)方案。

分析求解結(jié)果得，P1原件的寬沿著木板的長排列最多可排13列;P1原件的長沿著木板的寬排列最多可排4行。此時木板的長邊剩余387mm，寬邊剩余8mm，所以可再放置一個P1原件的長邊。故仍可以排放7個P1原件。綜上所述，在木板上切割P1原件時，當(dāng)切割59個P1板時，木板利用率為98.3%，達到最高利用率。

二、多元木板切割模型的建立

兩種約束條件的切割方案：現(xiàn)多考慮一個矩形原件P3（長度為406mm，寬為229mm）。由于矩形原件P3的切排樣方式不定，加深求解的難度。針對NP類問題可建立有關(guān)遺傳算法的數(shù)學(xué)模型進行求解。

構(gòu)建一個函數(shù)：

k（x）=1x0

0x<0（1）

由于切割原件在排放時受到木板尺寸的影響，且每個原件之間的排放互不重疊，依此建立如下方程：

k（xli-xrj）+k（yti-ybj）+k（xlj-xri）+k（ytj-ybi）1（2）

式中：第i個原件排放在第j個原件后面，且i

（1）遺傳算法的建立：

首先初始化種群，對各個矩形原件采用符號編碼，將兩種原件命名為1、2。原件既可橫排也可豎排，取橫排為正，豎排為負。下面以P1、P3原件在長為635mm，寬為610mm的木板上的排放為例，p={1，1，2，2}表示底層豎排一個原件P1，再橫排一個原件P1，第二層先橫排一個原件P3，再豎排一個一個原件P3。

其次構(gòu)建適應(yīng)度函數(shù)。將木板利用率作為函數(shù)，得到適應(yīng)度函數(shù)方程：

H（p）=h（p）LW=∑niliwiLW（3）

式中：H（p）表示算子，指編碼為p的個體的面積，ni為標(biāo)號為i的原件的出現(xiàn)次數(shù)，li、wi分別表示標(biāo)號為i的原件的長與寬（這里的i與方程（4）約束條件中的i有區(qū)別）。其余參量均取默認值。

（2）初始化種群的構(gòu)建：

由于初始化種群的編碼較多，一般初始種群的大小要在20個以上，可采用逐層排列生成初始化種群。

步驟一：建立一個坐標(biāo)系，確定上限寬度與長度（即木板尺寸）。

步驟二：生成一個隨機序列數(shù)，取值在集合{2，1，1，2}內(nèi)，表示待排樣的原件。

步驟三：根據(jù)隨機數(shù)，將木塊從左往右按層排列。

步驟四：當(dāng)排樣高度達到寬度限度時，跳出循環(huán)，給出排列編碼。

步驟五：重復(fù)上述步驟，直至給出20個以上的初始個體，構(gòu)建成一個初始化種群。

（3）模型的求解：

運用MATLAB實現(xiàn)遺傳算法，可得三種利用率較高的方案：

在實際生產(chǎn)中，所需原材料的種類是多樣的（不僅限于矩形），求解情況更加復(fù)雜。對于多種約束條件，仍然利用遺傳算法，加入新的約束條件，對適應(yīng)度函數(shù)進行改造。

H（p，N）=h（p）NLW=∑niliwiNLW

P=P{p1，p2，…，pn}（4）

式中：ni是已知量，N是待求解量。然后改造初始化種群，對所加的參數(shù)Ci對原件進行計數(shù)，引入?yún)?shù)N對木板計數(shù)。合并每個板的編碼排序，一個板組成一個編碼，原件全部排完時構(gòu)成P。進一步對初始種群改造，再次建立坐標(biāo)系。

三、評價與總結(jié)

本文構(gòu)建的模型中沒有給出具體的解碼算法和篩選算法，另外遺傳算法也的穩(wěn)定性較差，因為算法屬于隨即類算法，對初始種群有很強的依賴性，不同的初始種群得到結(jié)果與速度也不盡相同?？刹捎媚M退火算法和蟻群算法相結(jié)合，當(dāng)面臨實際解決時，可以通過構(gòu)建這兩個算法解決人力解碼的問題。

參考文獻：

[1]馬廣焜，劉嘉敏，黃有群，等.一種有約束矩形排樣問題的求解算法[J].沈陽工業(yè)大學(xué)學(xué)報，2006，28（4）.

[2]趙新芳，崔耀東，楊瑩，等.矩形件帶排樣的一種遺傳算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2008，20（4）：540544.

作者簡介：田康（2000），男，漢族，安徽銅陵人，本科，研究方向：信號處理。

指導(dǎo)老師：楊靜（1980），漢族，安徽濉溪人，博士，副教授，研究方向：DNA計算與組合優(yōu)化。