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

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

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

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

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

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

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

矩形件排樣；優(yōu)化算法；最低水平線；遺傳算法

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

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

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

1 問題描述與數(shù)學模型

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

圖1 矩形件排樣實例

且滿足約束條件：

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

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

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

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

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

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

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

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

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

圖2 改進最低水平線方法

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

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

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

3 基于改進遺傳算法的矩形件排樣優(yōu)化算法

3.1 可行解的編碼方式

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

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

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

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

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

3.3 遺傳算法的改進處理

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

(1) 選擇、交叉和變異操作。為保證種群的多樣性，根據(jù)可行解適應(yīng)度的不同采取相應(yīng)的進化處理?；舅悸窞椋和ㄟ^選擇操作保留一部分適應(yīng)度較好的父代解到子代種群中，通過對父代解的交叉、變異操作生成新的解補充到子代種群中；選擇、交叉和變異操作所產(chǎn)生的解共同構(gòu)成子代種群。

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

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

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

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

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

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

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

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

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

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

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

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

4 算法評估

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

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

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

表1 本文算法采用的參數(shù)

表2 排樣結(jié)果數(shù)據(jù)(I)

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

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

表3 排樣結(jié)果數(shù)據(jù)(II)

5 結(jié) 論

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

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

[2] 劉德全, 藤弘飛. 矩形件排樣問題的遺傳算法求解[J].小型微型計算機系統(tǒng), 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] 龔志輝, 黃星梅. 二維矩形件優(yōu)化排樣算法的改進研究[J]. 湖南大學學報, 2003, 30(3): 47-49.

[8] 王金敏, 王保春, 朱艷華. 求解矩形布局問題的自適應(yīng)算法[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

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

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