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

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

關鍵詞：線性規劃方程;遺傳算法;二維下料

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

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

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

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

根據木板的排放方式，建立整數規劃方程組：

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

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

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

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

構建一個函數：

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。

其次構建適應度函數。將木板利用率作為函數，得到適應度函數方程：

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

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

（2）初始化種群的構建：

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

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

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

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

步驟四：當排樣高度達到寬度限度時，跳出循環，給出排列編碼。

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

（3）模型的求解：

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

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

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

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

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

三、評價與總結

本文構建的模型中沒有給出具體的解碼算法和篩選算法，另外遺傳算法也的穩定性較差，因為算法屬于隨即類算法，對初始種群有很強的依賴性，不同的初始種群得到結果與速度也不盡相同。可采用模擬退火算法和蟻群算法相結合，當面臨實際解決時，可以通過構建這兩個算法解決人力解碼的問題。

參考文獻：

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

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

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

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