基于改進最低水平線方法與遺傳算法的矩形件排樣優化算法

劉海明， 周 炯， 吳忻生， 羅家祥

(華南理工大學自動化科學與工程學院，廣東 廣州 510641)

基于改進最低水平線方法與遺傳算法的矩形件排樣優化算法

劉海明， 周 炯， 吳忻生， 羅家祥

(華南理工大學自動化科學與工程學院，廣東 廣州 510641)

傳統的最低水平線方法用于矩形件排樣時可能產生較多未被利用的空白區域，造成不必要的材料浪費。針對此缺陷，在搜索過程中引入啟發式判斷，實現空白區域的填充處理，提高板材利用率。在應用遺傳算法優化矩形件排樣順序時，在進化過程中采用分階段設置遺傳算子的方法，改善算法的搜索性能與效果。通過改進最低水平線方法與基于分階段遺傳算子的遺傳算法相結合，共同求解矩形件排樣問題。排樣測試數據表明，所提出的矩形件排樣優化算法能夠有效改善排樣效果，提高材料利用率。

矩形件排樣；優化算法；最低水平線；遺傳算法

矩形件排樣問題屬于二維排樣問題中的一類特殊優化問題，是指將一組給定尺寸的矩形零件在矩形板材上按一定方式進行排放，要求零件的排放不得超出板材邊界，零件之間互不重疊，同時使板材利用率最大化。矩形件排樣優化問題普遍存在于鈑金、紙品、玻璃、家具等現代制造、加工行業中。從數學計算復雜性來看，該問題屬于NP-Complete組合優化問題，很難在一個合理時間內獲得問題最優解。因此，研究和設計有效的矩形件排樣優化算法，具有重要的理論研究意義和應用價值。

自20世紀90年代以來，國內外許多學者針對矩形件排樣問題作了研究，提出了不同的求解方法。多數文獻將矩形件排樣問題分為：矩形件的排放策略問題與矩形件的排放順序問題考慮。前者指矩形件被排入板材時的靠排方式；后者指各個矩形件的排放順序。對于矩形件排放策略，目前多采用基于啟發式規則的方法。Jakobs[1]提出基于BL規則的排放策略，以優先向下、向左靠排的方式排放零件。劉德全和藤弘飛[2]在 BL策略基礎上提出一種下臺階方法，在向左靠排的過程中也同時考慮向下靠排。Hopper和Turton[3]也提出了一種BL改進策略，考慮了排放過程中產生的孔洞的填充利用。Yeung和Tang[4]與Wei等[5]提出了一種基于最低水平線的排放策略，優先在具有最低高度的水平輪廓線上排放零件。Christoforos和Fleszar[6]提出一種剩余矩形匹配算法，將板材可用區域不斷劃分為矩形塊并逐個排入矩形零件，以盡可能減少板材浪費。對于矩形件排放順序問題，其本質為序列的組合優化問題。早期主要采用經驗性做法處理，例如按矩形件高度、面積排序等標準確定矩形件的排放順序。但這種相對硬性的處理方法，在用于不同排樣實例時結果往往時好時差，適用性不強。此外，該方法僅能產生少量特定的解序列，對于排樣問題往往難以得到最優解甚至次優解。目前，多采用一些基于進化思想的大規模搜索算法對矩形件排樣順序進行尋優，如遺傳算法(genetic algorithm，GA)[7]、模擬退火算法[8]等。

本文對原有的最低水平線排放策略作了改進，考慮了板材空白區域的有效利用，避免材料浪費；在應用GA實現矩形件排樣順序優化時，針對GA可能出現的過早收斂、搜索效率低等不足，對傳統GA進行算法搜索性能改進。改進的最低水平線方法與GA相結合，共同求解矩形件排樣優化問題。

1 問題描述與數學模型

根據不同的實際應用與工藝要求，矩形件排樣問題可有不同的表述。該問題的一般化描述為：給定已知矩形件的一組尺寸，在一個寬度確定、高度不限的矩形板材上不重疊地排入這些矩形件，并使得板材利用率最高。根據問題描述可知，排樣過程應滿足以下3個條件：①任何一個矩形件不能超出板材邊界；②各矩形件不能出現重疊；③矩形件可以旋轉，但矩形件的邊需與板材邊界平行，即矩形件只能以0°或90°排放。圖1所示為一個包含8個矩形零件的排樣實例，其中，陰影部分為不能利用的板材(常稱為孔洞)。

圖1 矩形件排樣實例

且滿足約束條件：

其中，式(2)保證所有矩形排放時不超出板材邊界，式(3)保證所有矩形之間不出現重疊。

2 基于改進最低水平線方法的排放策略

傳統的最低水平線方法只考慮在高度最低的水平輪廓線上排放零件，但排放過程中并不考慮零件尺寸對排放布局的影響，在某些情形下會使板材出現較多孔洞而導致不必要的浪費。針對這一不足，本文提出了改進方法：在排放過程中，考慮待排放矩形件的尺寸，通過引入啟發式判斷條件靈活選擇待排放矩形件，以充分利用板材可用區域。改進后的最低水平線方法的算法步驟如下：

步驟 1. 初始化板材的水平輪廓線集合，其僅包含一條水平輪廓線，即板材的底部邊界，且為集合中的最低水平線；同時，設置變量i＝1。

步驟2. 在給定的矩形件序列中，對第i個待排放矩形件pi，在當前水平輪廓線集合中找到當前高度最低的水平線(最低水平線)，判斷該水平線的寬度是否足夠排入矩形件pi。如果可以排入，在該水平線上靠左排放該矩形件，并轉入步驟4；否則，跳轉到下一步。

步驟3. 對矩形件序列中pi后的所有未排放矩形件，判斷其寬度大小是否可以在當前最低水平線上排放。對于能夠排入的矩形件，優先選取寬度與最低水平線寬度相同的矩形件進行排放(若存在多個滿足條件的矩形件，則選取高度最高的矩形件)，然后交換該矩形件與矩形件pi在矩形件序列中的位置(即交換兩者排放順序)，并轉入下一步處理。若未能在當前最低水平線上找到可以排放的矩形件，則將當前最低水平線的高度提升至與其相鄰且高度最接近的水平輪廓線，合并兩段水平線。更新板材的水平輪廓線集合，然后跳轉到步驟2繼續處理。

步驟 4. 根據新排放的矩形件的位置及尺寸，更新板材的水平輪廓線集合。

步驟5. 若序列中尚有矩形件未排放，令i=i+1，轉入步驟2繼續處理；若所有矩形件已完成排放，則結束算法，此時板材的用量由水平輪廓線集合中高度最大的水平線決定。

在改進最低水平線方法中，通過啟發式規則調整矩形件的排放順序，使得板材空閑區域的利用更為靈活。算法中不僅考慮了小尺寸矩形件的填充排放，而且還考慮了寬度相同但高度不同的矩形件的排放順序優化，優先排放高度較大的矩形件。因為高度較大的矩形件對板材用量的影響較大，優先排入高度較大的矩形件，可避免排樣后期這些矩形件排放造成的材料浪費。改進最低水平線方法的算法流程如圖2所示。

圖2 改進最低水平線方法

圖3和圖4分別為針對同一排樣算例(包含7個矩形件)按最低水平線方法和改進最低水平線方法排放的結果，其中矩形件初始排樣序列為(1,2,3,4,5,6,7)。從排放結果可以看出，改進后的最低水平線方法能夠更好地利用板材空間，使得板材利用率得到提高。

圖3 基于最低水平線方法的排放策略

圖4 基于改進最低水平 線方法的排放策略

3 基于改進遺傳算法的矩形件排樣優化算法

3.1 可行解的編碼方式

從矩形件排樣問題的特點可知，矩形件排樣結果與矩形件的排樣順序密切相關。矩形件排樣順序的優化屬于基于序列的組合優化問題，相對于局部搜索算法，具有全局搜索特性的GA能夠獲得更好求解結果。

所謂可行解編碼，是指將排樣問題的可行解從解空間轉換為GA能夠處理的搜索空間的解。常用編碼方式有整數編碼、實數編碼和符號編碼等。此處，基于排樣問題特點，對排樣可行解采用直觀的十進制編碼方式：對矩形件從1開始順序編號，所有矩形件的編號所構成的序列就可以代表一個可行解(各編號所對應的矩形件在序列中的次序代表其排樣順序)。因此，對于包含n個矩形件的排樣問題，其可行解集合為此外，為了在可行解中體現出矩形件是否旋轉后排放這一信息，對上述編碼方式進行擴展：為每個矩形件編號增加一個符號標志，若符號為正，表示矩形件排放時不旋轉(按0°排放)；若符號為負，表示矩形件旋轉90°后再排放。

3.2 適應度函數

在GA中，需要建立一個適應度函數來評估可行解的優劣。對于矩形件排樣問題，為使適應度函數能夠反映解的優劣，選擇如下適應度函數：

其中，Si為某個排樣序列，AT為所有矩形件的面積之和，W為板材寬度，Hused(Si)為排樣序列Si基于特定排樣策略下的排樣結果中矩形件水平輪廓線中最高水平線的高度。這樣，適應度函數f (Si)的值就代表排樣序列Si對應的板材利用率。易知，適應度函數的取值范圍為(0, 1]。適應度函數值越高，表示對應的可行解(排樣序列)越優。

3.3 遺傳算法的改進處理

GA是一種具有全局尋優能力的進化算法，適合大規模組合優化問題的求解。但傳統GA也存在一些缺點，例如過早收斂、搜索效率低等。本文從兩方面對傳統GA進行改進：首先，根據適應度的不同對父代解采取不同的進化操作，保證種群多樣性，以避免種群過早收斂；其次，根據解的進化階段動態調整遺傳算子，提高算法自適應能力，使搜索能夠更快逼近問題最優解。

(1) 選擇、交叉和變異操作。為保證種群的多樣性，根據可行解適應度的不同采取相應的進化處理。基本思路為：通過選擇操作保留一部分適應度較好的父代解到子代種群中，通過對父代解的交叉、變異操作生成新的解補充到子代種群中；選擇、交叉和變異操作所產生的解共同構成子代種群。

設種群大小為N，且進化過程中每一代種群大小不變，算法中的選擇、交叉和變異操作如下所述：

①選擇操作：又稱復制操作，目的是把父代種群中具有較優適應度的解直接復制到子代種群中，保證良好基因的存在。方法是：預設一個選擇算子ps(0

②交叉操作：是在進化過程中產生新解的主要方法，可以改善種群的多樣性。本文采用如下交叉方法：在余下的父代解(未被選擇保留的父代解)中隨機選中兩個解，采用兩點交叉方法產生兩個新的可行解進入下一代。關于兩點交叉方法，已有較多文獻介紹，此處不再贅述。每兩個隨機選取的父代解都可以通過兩點交叉方法獲得兩個新解。交叉操作產生的新解數量為pcN，其中N為種群大小，pc為預設的選擇算子(0

③變異操作：是一種產生新解的方式，是交叉操作的有益補充。根據排樣問題的特點，本文采用兩種變異操作：交換變異與旋轉變異。交換變異對隨機選中的某個父代解中的兩個隨機位置上的基因進行位置交換，從而得到一個新的排樣序列(可行解)。旋轉變異用于調整矩形件排放時的排放角度，其操作方法是：對于隨機選中的某個父代解，在區間[1, n]之間產生一個隨機位置(n為排樣序列長度)，將該位置對應的矩形件編號的符號取反(意味著改變矩形件的排放角度)，從而得到一個新解。

每個被隨機選中的父代解都可以通過交換變異或旋轉變異操作得到一個新解。兩種變異操作產生的新解數量分別由預設的交換變異算子 pme(0

需要說明的是，為了保持每代的種群大小不變，各算子的取值應滿足條件：ps+pc+pme+pmr=1。

(2) 分階段遺傳算子的引入。研究發現，GA的收斂速度、尋優結果與選擇、交叉、變異算子的設置有很大關系。其中，選擇算子對算法收斂速度影響較大，交叉、變異算子則對算法尋優結果有重要影響。在算法搜索的不同階段，合理調整遺傳算子，能夠使算法性能得到改善。因此，本文對GA作了如下改進：

在算法的初始階段，設置一個具有較大值的選擇算子ps(0.6≤ps<1)，目的在于使算法能夠在較短的時間內逼近排樣問題的最優解或次優解，從而快速獲得較好解。此時，由于所設置的交叉算子與變異算子值較小，當算法進行到某個階段時，可能會陷入局部最優，在某個子空間內反復搜索最優解。為避免算法過早收斂，需對各遺傳算子進行調整，將搜索范圍延伸至更大的解空間。此時，令算法進入第二階段搜索過程。在這一階段，對遺傳算子作如下調整：將選擇算子 ps設置為一個較小值(0

在算法實際搜索過程中，兩個搜索階段進行切換的判斷依據是當前搜索到的最好解的變化情況。通過最好解的變化情況及預設的條件，動態調整遺傳算子，使算法循環交替地進入兩個搜索階段。這一處理可使算法不會總受到單一遺傳算子左右，搜索過程既能保證快速性也能保證全局性。

3.4 基于改進最低水平線方法與遺傳算法的排樣優化算法

利用改進GA實現矩形件排樣順序的尋優，并采用改進最低水平線方法實現矩形件排樣，可構造完整的矩形件排樣優化算法。算法流程圖如圖5所示。在算法中，改進最低水平線方法被用于對 GA所產生的每代種群中的各個可行解進行矩形件排放，通過計算可行解的適應度來判斷解的優劣。兩個搜索階段的切換條件為當前搜索到的最好解是否連續多代沒有得到改進，若是則將遺傳算子調整為第二階段的算子，否則設置為第一階段的遺傳算子。

圖5 基于改進最低水平線方法與遺傳算法的排樣優化算法

4 算法評估

為評估所提出的排樣優化算法的性能，在Visual C++ 2008環境下編程實現該算法，并與文獻[9]中提出的排樣優化算法進行實驗對比(文獻[9]采用了基于最低水平線方法與改進GA的排樣優化算法)。首先，以文獻[9]給出的算例作為測試數據，該算例包含20種不同尺寸的矩形件(總數為59個)，板材寬度為400。在仿真實驗中，本文算法的相關參數如表1所示，算法中不同搜索階段的切換條件為：當前搜索到的最好解是否連續5代都未得到改進；算法的終止條件為：迭代次數達到預設的最大迭代次數。

兩種算法的優化結果如表2所示，其中，Uavg指算法重復運行50次得到的板材利用率的平均值，

Ubest指在50次運算中得到的最佳利用率，Tavg指平均運算時間。

表1 本文算法采用的參數

表2 排樣結果數據(I)

從表2可看出，相對于文獻[9]算法，本文算法對該算例的優化結果有明顯提高，而算法所需運算時間略有增加。為更好地評估算法性能，通過隨機方式產生 10組包含數量不等、尺寸不同的矩形件的排樣數據進行算法測試。在算法參數不變的情況下，對上述兩種算法進行排樣對比實驗，排樣數據及結果如表3所示。

從表3結果可以看出，本文提出的排樣優化算法無論是在板材的平均利用率還是最佳利用率方面，均比文獻[9]算法有明顯提升。從算法運算時間來看，本文算法與文獻[9]算法相比略有增加。隨著矩形件種類、數量的增加，這種差別相對于實際運算時間而言幾乎可忽略不計。這表明，改進后的優化算法能夠在保證運算效率的前提下，有效改善排樣效果，提高材料利用率。

表3 排樣結果數據(II)

5 結 論

本文對基于最低水平線方法的矩形件排樣策略作了改進，通過引入啟發式規則靈活選擇矩形件進行排樣，有效利用板材空白區域，避免板材浪費。采用分階段設置遺傳算子的方法改進 GA，改善算法搜索性能，并將算法與改進最低水平線方法相結合，共同求解矩形件排樣問題。排樣測試數據表明，文中提出的算法能夠有效求解矩形件排樣問題，不僅在板材利用率方面有明顯提升，且算法執行效率較高，適用于現代制造業、加工業的實際生產。

[1] Jakobs S. On genetic algorithms for the packing of polygons [J]. European Journal of Operational Research, 1996, 88(1): 165-181.

[2] 劉德全, 藤弘飛. 矩形件排樣問題的遺傳算法求解[J].小型微型計算機系統, 1998, 19(12): 20-25.

[3] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem [J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[4] Yeung L H W, Tang W K S. A hybrid genetic approach for garment cutting in the clothing industry [J]. IEEE Transactions on Industrial Electronics, 2003, 50(3): 449-455.

[5] Wei Lijun, Oon W C, Zhu Wenbin, et al. A skyline heuristic for the 2D rectangular packing and strip packing problems [J]. European Journal of Operational Research, 2011, 215(2): 337-346.

[6] Christoforos C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

[7] 龔志輝, 黃星梅. 二維矩形件優化排樣算法的改進研究[J]. 湖南大學學報, 2003, 30(3): 47-49.

[8] 王金敏, 王保春, 朱艷華. 求解矩形布局問題的自適應算法[J]. 圖學學報, 2012, 33(3): 29-33.

[9] Liu Haiming, Zhou Jiong, Wu Xinsheng, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy [C]//2014 IEEE Congress on Evolutionary Computation (CEC). Beijing: IEEE, 2014: 352-357.

Optimization Algorithm for Rectangle Packing Based on Improved Lowest Horizontal Line Method and Genetic Algorithm

Liu Haiming, Zhou Jiong, Wu Xinsheng, Luo Jiaxiang
(School of Automation Science and Engineering, South China University of Technology, Guangzhou Guangdong 510641, China)

For the issue of rectangle packing problem, traditional lowest horizontal line method might generate certain empty blocks that were not used, which would cause unnecessary waste of material. To solve the problem, heuristic estimate is introduced into search process to achieve rectangle filling for the empty blocks and improve utilization. For optimization packing sequence of rectangles using genetic algorithm, a new strategy of setting different genetic factors by stages of evolution process is applied to improve algorithm performance. The two improved methods are combined in union to solve the rectangle packing problem. The test data of packing show that the proposed algorithm can effectively improve packing results and improve utilization of material.

rectangle packing; optimization algorithm; lowest horizontal line; genetic algorithm

TP 391.72

A

2095-302X(2015)04-0526-06

2014-10-18；定稿日期：2015-01-12

廣東省科技計劃資助項目-工業高新技術領域(2014A010104004)；中央高校基本科研業務費專項資金重點資助項目(2014ZZ0033)

劉海明(1978–)，男，廣東陸河人，講師，博士。主要研究方向為系統優化與調度、計算機輔助設計與優化、智能優化算法與智能系統。E-mail：hmliu@scut.edu.cn