不規則區域矩形件排樣的一種改進算法

凌 玲，盧 文，胡于進

(華中科技大學 機械科學與工程學院，湖北 武漢 430074)

矩形件帶排樣問題(RSPP)是在不規則板材上布置多個大小不同的矩形零件，并滿足以下約束條件：(1)零件排放在板材內部；(2)各零件之間互不重疊；(3)滿足一定的工藝要求。其優化目標是尋求一個零件布局方案，使得浪費的板材面積最小，亦材料的利用率最大。排樣問題對造船、服裝、模具等材料加工行業有重要意義，材料利用率的提高可直接降低材料浪費，提高經濟效益，也符合當今創建節約型社會的需求。

[1]中的矩形件帶排樣相比，不規則區域的排樣增加了對板材兩端空洞的利用，實際上增加了兩端空洞排樣時的搜索，所以不規則區域的排樣問題在幾何計算方面的復雜度較高。在滿足約束條件的情況下，矩形排樣的最低最左原則或最低水平線原則在不規則區域排樣的情況下已不能滿足需要，最低最左等傳統放置方法將導致較大的空白區域無法利用。

最大限度地節約材料、提高材料利用率是生產中提高效益的一個重要手段。由于排樣問題的廣泛存在，如板金下料、報刊排版、服裝裁剪等，都需要在可接受的時間里得到最優或近似解。

參考文獻[1-3]中提到的利用遺傳算法求解的矩形件排樣問題，均采用遺傳算法和改進的最低水平算法進行計算，利用此方式對不規則區域排樣，得到的排樣圖出現明顯的空洞。本文提出一種新方法，通過對板材兩端空洞的利用，提高板材的利用率。

1 算法描述

1.1 本文改進遺傳算法流程圖

本文采用十進制的編碼方式對每一個矩形零件進行編碼，將每一個矩形編號，i=1，2，…，n，零件編號構成一個整數串 P={p1，p2，…，pn}，1≤Pi≤n，表示了一種排樣圖(即一個個體)。

初始種群的好壞對遺傳算法的收斂速度和求解質量有較大的影響。本文在初始種群時，分析了矩形零件的數據特點，采用經驗選擇與隨機生成相結合的初始方法，大矩形件排放完后再排小矩形，材料利用率不會太低。

算法開始，首先將零件根據面積降序排列，面積相等時根據長度降序排列，產生一個有序整數串，再隨機產生m個個體，構成初始種群。利用每個個體排列所得排樣圖的高度計算得出該個體的適應度值，進行選擇、交叉和變異之后，再判斷是否達到了計算次數或得到了滿意的結果。如果沒有達到，則返回重新計算每個個體的適應度值；否則，算法就結束。算法流程如圖1所示。

圖1 本文算法流程

1.2 基于最低水平線的算法

由遺傳算法產生一個個體編碼后，只有將此個體對應的零件固定序列快速地求出其對應的排樣圖，得到所需要占據的板材高度，才能計算其適應度值，從而對該個體進行評價。本文在文獻[1]方法的基礎上提出一種基于最低水平線的擇優插入算法，對給定的零件固定序列進行優化排樣，降低排樣高度，使零件排放緊湊，提高材料利用率。

針對不規則區域的排樣時，利用此算法的搜索策略有兩種方案：一種是向后搜索到一個可以放下的零件時馬上停止搜索；另一種是向后搜索所有可以放下的零件，再從中選擇一個寬度最大的，使空間得到較為有效的利用。本文采用第二種方案。

當搜索到最優零件后，參考文獻[2]中采用的是“互換”兩個零件位置的方式。如果最優零件位置比較靠后，且最優零件小于當前排放零件面積，則當前面積較大的零件就會調整到后面的位置。如此多次搜索、互換零件位置可能造成在排樣的前期將較小尺寸的零件全部利用掉，后期剩下的都是大尺寸零件；而較大尺寸的零件對排樣高度的影響較大，這樣可能會出現即使前期得到的排樣圖零件緊湊、空洞較小，但后期總體排樣高度驟增的情況，導致得不到高質量的排樣圖。

此時采用文中的插入策略，將此時搜索到的最優零件直接插入到當前的零件之前。

在零件排放過程中會出現多段最高輪廓線，如圖2所示，最低水平線為當前所有輪廓線中最低的一段。如有數段，選擇最左的一段，其位置和長度在整個排樣的過程中不斷變化，如圖2所示。本文提出了一種基于最低水平線搜索算法，步驟如下：

圖2 基于最低水平線算法排入

(1)設置初始最高輪廓線為板材的最下面的邊(板材在豎直方向無限高)。

(2)當前要排入的零件為Pi，當前最低水平線為Llowest，比較是否大于或等于 Pi。若大于，則將 Pi在 Llowest上排放，更新最高輪廓線；否則，在序列中從 Pi位置開始向后搜索一個可以排放的零件，同時互換這兩個零件的位置；如果沒有搜索到，則將Llowest提升至與其相鄰且高度較低的一段平齊，更新最高輪廓線。

重復(2)，直至所有零件排放完畢。

其中水平線屬性為：

class line{double left； //水平線左端點的橫坐標

double wide； //水平線的寬度

double high；}； //左端點的縱坐標

基于最低水平線，對于不規則區域的矩形件排樣，采用掃描的方式找出不規則區域中最低且能排入此矩形件的水平線。按照最低水平線得到圖2。

如圖2，可以明顯看出，在①中可以插入后面的更小的矩形件，或者將4或5塞入其中，可以減少總排樣圖的高度。在②中可以將2插入其中，這樣也完全可以增加不規則區域的利用，減少總排樣圖的高度。

1.3 本文改進算法

當每排完一個矩形件，依照上述算法就要更新最低水平線，此時只適合針對矩形板材的排樣，不規則區域的排樣會出現上述大規模的空間浪費。

本文提出基于最低水平線的改進算法：在更新水平線的同時，需判斷水平線首尾元素的寬度是否為0，如果不為0，則要在首元素添加頭元素：先取得首元素指針 head， 過 點(head-＞left，head-＞high)與 不 規 則 區 域 相交，取下面的一點 pt。 新增 line 對象，line(pt.x，0，pt.y)，將pt添加到首元素。判斷水平線尾元素與判斷首元素類似。

針對最低水平線搜索算法的改進算法的步驟如下：

(1)判斷底邊是否水平，若水平且能排入當前的矩形件，則排入零件；否則向上掃描直至找到能排入的水平線段，排入零件。

(2)當前要排入的零件 Pi，當前水平線為 Llowest，判斷Llowest-＞wide與 Pi.wide的關系。若 Llowest-＞wide大于或等于 Pi.wide，則轉入(3)，否則轉入(4)。

(3)判斷排入到該水平線上的零件是否超出不規則邊界。如果此時的零件沒有超出不規則區域，則排入此零件，且更新水平線。否則，此時的零件超出了不規則區域，如果超出了右側邊界，則不能排入此零件，同時向后搜索能夠排入的零件，如果搜索不到則直接更新水平線。如果超出了左邊界，則向右移動此零件直至不超出邊界，移動距離為 s，移動之后的零件 Pi仍大于Llowest-s，則排入此零件。如果移動之后的零件Pi小于Llowest-s，則需向后搜索能夠排入且不超出邊界的零件，如果搜索不到則直接更新水平線。搜索到了則將該零件排入到當前水平線上，同時更新水平線。回到(2)。

(4)判斷此時的Llowest是否是最低水平線段的首元素或尾元素。如果不是，則在序列中從Pi位置開始向后搜索一個可以排放的零件，同時將這個零件插入到Pi之前的位置；如果沒有搜索到，則將Llowest提升至與其相鄰且高度較低的一段平齊，更新水平線。如果是，則轉入(5)。

(5)如果Llowest是最低水平線段的首元素，則獲取此段水平線的下一個元素 next，求得點(next-＞left，next-＞high)到不規則區域左側邊的距離為d，此時且有零件序列中寬度最小元素Plowest。如果d小于Plowest.wide，則更新 next，將Llowest-＞left賦給 next-＞left，同時 next的寬度增加 d，同時刪除首元素。如果Pi.wide大于或等于d，則在序列中從Pi位置開始向后搜索一個可以排放的wide最大的零件，同時將此時找到的元素插入到當前Pi的前面；如果沒有搜索到，則同樣更新next，同時刪除首元素。否則Pi.wide小于d，則此時可以將此零件排入首元素，從下往上掃描，直到找到大于或等于Pi.wide的線段為止，之后更新水平線。如果是最低水平線的尾元素，此時與首元素的處理類似。

重復(2)，直至所有零件排放完畢。

由圖3可以看出，經過本文改進算法的排入圖，零件總排樣高度有了明顯降低，整個優化排樣過程都緊湊地排放零件，使不規則區域的“空洞”區域得到了有效利用，提高了材料利用率。有效地將最低水平線算法在不規則區域排樣領域應用。

2 遺傳算法的過程

2.1 遺傳算子

(1)交叉算子。將父輩種群中的個體隨機兩兩配對，進行單點交叉操作，產生m個新個體構成種群。設隨機選定的 2個進行交叉的個體分別為 P={p1，p2，…，pn}和Q={q1，q2，…，qn}。 單點交叉是在 1∪n范圍內隨機生成一個交叉位t，從P中將位于t之前的元素拷貝至子代個體I1中作為前面的元素，P中未拷貝元素按Q中出現的先后順序拷貝至I2；同樣的方法可以產生另一新個體I2。

(2)變異算子。對交叉操作產生的子代個體，利用兩種變異算子進行變異：①旋轉變異。在1∪n范圍內隨機產生一個旋轉位，以概率Pm1對子代個體中位于其后的矩形零件進行旋轉；②顛倒變異。在1∪n范圍內隨機產生2個變異位，以概率Pm2對子代個體中兩個變異位之間的所有零件顛倒順序。

當零件個數較少時，顛倒變異可以提高算法的局部搜索能力。而零件個數較多時，解碼過程中動態調整動作相應增多，則在遺傳過程中的順序調整意義不大。所以解決大規模矩形件排樣問題時，只考慮旋轉變異。

(3)選擇算子。對變異后的m個子代個體依次求解其適應度，并分別與其父輩個體的適應度進行比較，若大于其父輩個體的適應度值，則接收此子代個體，替換其父輩個體作為下一代的父輩個體；否則，不接收此子代個體，其父輩個體直接進化，作為下一代的父輩個體。

圖3 基于改進算法的排入

2.2 適應度函數

遺傳算法對一個解的好壞用適應度函數進行評價，適應度越大，解的質量越好。本文采用參考文獻[2]中的適應度函數f(p)=Area/Area0，其中Area是矩形零件的總面積，Area0是排樣圖最大高度以下的面積，適應度值最大為1。

2.3 終止準則

重復執行，直到最好解的適應度達到要求或滿足預定的進化代數，停止計算，輸出最優解。

3 實驗計算

依據表1所給數據，在改進遺傳算法的基礎上做了一組實驗。

表1 本文中矩形件的數據

采用遺傳算法和最低水平線進行計算，設定板材的端 點 順 時 針 為 (300，50)(100，150)(250，350)(500，300)(600，100)，得出如圖4所示的排樣圖。

圖4 初始排樣圖

此時排樣圖的最高輪廓線為(383.5，80，146)，其中高度為146。上述排樣圖的適應度為0.723。

采用遺傳算法進行計算，設定種群規模m=20。迭代100次計算20次，取其平均適應度作為評價參數，得到如圖5所示的排樣圖。

圖5 本文算法進化100代的結果

此時排樣圖的最高輪廓線為(516.25，40，157)，其中高度為157。排樣圖的適應度為：0.784。

經過遺傳算法的迭代求解，排樣圖的整體高度已經有了很大的改進。

對于求解不規則區域的排樣，本文在最低水平線的基礎上提出了改進，并利用遺傳算法，使不規則區域的面積利用率更為有效。

在研究不規則區域排樣的問題中，需要考慮的是整體排樣圖的高度。利用所給的布局函數和目標函數值，確定整體排樣圖的高度。本文提出的搜索算法中的前后端搜索方式還有待改進。不規則區域的布局可以使用本文算法。由于變異算子、交叉算子等數值對遺傳算法的影響，本文在適應度方面還有待改進，可以提高效率。

參考文獻

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

[2]龔志輝，黃星梅.二維矩形件優化排樣算法的改進研究[J].湖南大學學報(自然科學版)，2003，30(3)：47-49.

[3]HOPPER E，Turton B C H.A review of the application of metaheuristic algorithms to 2D strip packing problems[J].Artificial Intelligence Review， 2001，16(4)： 257-300.

[4]賈志欣，殷國富，羅陽.二維不規則零件排放問題的遺傳算法求解 [J].計算機輔助設計與圖形學學報，2002，14(5)：467-470.

[5]龔志輝.基于遺傳算法的矩形件優化排樣系統研究[D].長沙：湖南大學，2003.

[6]黃紅兵.矩形毛坯優化排樣算法的改進[J].機械工程師，2004(11)：12-14.

[7]HOPPER E，Turton B C H.An empirical investigation of metaheuristic and heuristic algorithms for a2D packing problem [J].European JournalofOperationalResearch，2001， 128(1)：34-57.

[8]Zhang D， Kang Y， Deng A.A new heuristic recursive algorithm forthe strip rectangularpacking problem[J].Computers& Operations Research， 2006， 33(8)：2209-2217.

[9]Zhang D， Liu Y， Chen S， etal.A meta-heuristic algorithm for the strip rectangular packing problem [M].Lecture Notes in Computer Science.Heidelberg： Springer，2005，612： 1235-1241.