分布估計算法求解矩形件排樣優化問題

馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮江212003）

分布估計算法求解矩形件排樣優化問題

馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮江212003）

矩形件排樣是一個平面二維優化布局的問題，由于其眾多的約束條件和計算上的復雜性，在短時間內求其最優解相當困難，屬于典型的NP完全問題。針對矩形件排樣問題，本文采取一種改進的最低水平線搜索算法，通過判斷排樣中產生的廢棄空閑區域的位置關系，對鄰接的空閑區域進行有效的合并，并結合分布估計算法求解矩形件排樣優化問題。最后，通過模擬實驗，采用本文算法求解后矩形板材的利用率為93.75%，充分體現了本文算法的有效性。

優化排樣；矩形件；分布估計算法；最低水平線搜索算法

矩形件排樣優化的問題[1]是指將不同數量、大小不一的矩形件按照特定的順序，采取某種排布策略排放到矩形板材上（在本文中，假定矩形板材寬度一定，長度不限），同時滿足特定的約束條件，并且使得板材的利用率能夠最大化[2]。矩形件排樣優化的問題廣泛存在于鈑金下料、造紙工業、玻璃切割、家具生產等現代制造、加工行業中。當前社會的發展對于資源的消耗日益增大，特別對于鋼材等工業原料的需求越來越大。提高原材料的利用率對于保護生態環境，提高企業的生產率進而獲得更大的經濟效益。然而，矩形件排樣優化問題屬于NP完全問題，無法在短時間內求得最優解。難點主要在于如下兩點：第一，矩形件在板材上面進行布局的策略，即排布算法；第二，矩形件的排放順序。目前，通常采用啟發式算法，例如遺傳算法[3]，模擬退火算法[4]，蟻群算法[5]，粒子群算法[6]等，再結合某種排布規則，例如BL算法[7]，最低水平線算法[8]，分層排布算法[9]等。文中將分布估計算法與一種改進的最低水平線搜索算法結合起來求解矩形件排樣優化問題。

1 問題描述

適應度函數和約束條件，問題可描述為：給定大小不一的一組矩形件和一個矩形板材，假定矩形板材的寬度確定，長度無限。將每個矩形件按照一定的順序排入板材中，使得所消耗的矩形材長度最短即板材的利用率最高。同時，根據實際應用的情況，排入矩形件的過程中，必須滿足一定的約束條件。常見的約束條件主要有：1）任何矩形件排入矩形板材時任何一個邊不能超出板材的邊界；2）任意兩個已排入的矩形件之間不能重疊；3）考慮到切割的需要，排入的矩形件各條邊必須與矩形板材的某一邊平行。如圖1所示，一個矩形件排樣樣例，八個矩形件按照順序依次排入矩形板材中，其中陰影的部分是排樣過程中產生的下料即不能利用的部分。矩形件排樣優化旨在找到一個排樣順序，然后按照某種排布規則排入矩形件，使得產生的下料盡可能最少。

圖1 一個矩形件排樣樣例

現假設給定的矩形板材寬度為W，集合P={P1，P2，…，Pn}表示所有需要排放的矩形件，其中，第i個矩形件Pi（1≤i≤n）的寬度為wi，高度為hi。由于本文中矩形板材的寬度一定，假定Hused為排放玩所有的矩形件后所消耗的板材長度，矩形件的最優排樣就意味著排樣完成后消耗的板材長度最短，板材的利用率最高。定義板材的利用率為f，因此，其目標函數如公式（1）所示：

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

2.1 基于最低水平線搜索算法

基于最低水平線搜索算法具體步驟如下[10]：

1）將板材的底邊設為板材的初始最低水平線。

2）當下一待排放矩形件Pi排入時，比較矩形板材中當前各層水平線高度，選擇高度最低的那一段水平線，如果有多條水平線段高度相同并且同為最低，則選取位置處于最左邊的那一段水平線作為最低水平線。然后比較最低水平線段和矩形件Pi的寬度：如果該段水平線的寬度大于Pi的寬度，就將Pi排放在此最低水平線段的位置，并更新輪廓線的條數和高度；如果該段水平線的寬度小于Pi的寬度，依次搜索矩形件Pi之后的每一個矩形件，若能夠找到寬度小于最低水平線段的矩形件，將該矩形件和矩形件Pi互換位置并排入當前最低水平線位置；如果有多個矩形件滿足要求，則選取寬度最大的那個矩形件和矩形件Pi互換位置并排入當前最低水平線的位置；如果找不到能夠排入當前水平線位置的矩形件，比較其他各輪廓線的高度，選擇高度最低的輪廓線作為新的最低水平線，并更新輪廓線。重復這個過程直至該矩形件能夠排入。

3）若矩形件沒有排放完成，重復步驟二。如圖 2所示，一個排樣圖示例，該圖是基于最低水平線搜索算法所得到的。

圖2 基于最低水平線搜索算法生成的排樣圖示例

2.2 改進的基于最低水平線搜索算法

1）算法改進策略

基于最低水平線搜索算法缺陷在于：當某一最低水平線段的寬度小于所有帶排放矩形的寬度時，會發生最低水平線高度提升并產生空閑區域，此空閑區域在以后的排布過程中將不再使用，就此廢棄。而且，隨著排放的矩形件增多，產生的空白區域越多，板材的浪費率就越大。

針對上訴不足，本文提出了改進策略：記錄下在排布過程中產生的每一個空閑區域的右上角和左下角坐標，很據這兩個坐標判斷兩個空閑區域的鄰接關系。若存在相鄰接的空閑區域根據鄰接區域合并規則將其合并，然后將合并后的空閑區域存儲到空閑區域鏈表中。在排放矩形件時，首先搜索空閑區域鏈表，如果能夠找到某一空白區域能夠放得下當前的矩形件，則將矩形件排入此空白區域。否則，按照最低水平線搜索算法排放矩形件。

2）相鄰空閑區域合并規則

空閑區域是由于矩形件排放過程中最低水平線提升生成的，最低水平線的提升都是縱向提升，因此空閑區域的相鄰關系都是垂直相鄰關系。排布的過程中，若產生空閑區域，則提取其左下角和右上角坐標，根據兩個空閑區域的坐標關系判斷其是否相鄰。如圖3所示，兩種空閑矩形區域相鄰的情況。

空閑區域相鄰關系判斷方法：對于任意兩個處于同一平面的矩形，其位置關系如圖4所示可分為3種：相交、相離、鄰接。（對于兩矩形重合的情況我們默認為兩矩形是相交的關系）。在對矩形區域位置關系進行判斷的時候，先判斷兩矩形區域是否想交，如果不想交，在判斷兩矩形是否相離。如果兩矩形區域之間既不相交也不相離，那么兩矩形區域鄰接。

圖3 空閑矩形區域相鄰的情況

圖4 同一平面矩形區域之間三種位置關系

空閑區域合并規則：由于最低水平線是縱向提升，空閑區域的鄰接關系也是縱向的，鄰接的空閑區域按照自下而上的順序合并。如果某個未排放的矩形件能夠排入合并后的空閑區域，該矩形件必須轉換排放方式（橫排轉豎排，豎排轉橫排）。因為最低水平線提升是以最低水平線段的寬度小于所有未排放矩形件寬度為前提。如圖5所示，空閑區域合并的不同情況。

圖5 相鄰空白區域合并示意圖

3）算法的具體步驟

設待排放的矩形件集合：P={P1，P2，…，Pn}，改進的最低水平線搜索算法具體步驟如下：

步驟一，初始條件下，最低水平線為矩形板材的底邊，空閑區域鏈表為空

步驟二，按照如下規則排放待排入矩形件Pi：

1）搜索空閑區域鏈表，判斷已產生的空閑區域中是否存在能夠排入矩形件Pi的區域，若存在，則將該矩形件Pi排入，否則轉2）；

2）選取最低水平線段（如果有多段最低水平線，取最左的那一段），比較矩形件Pi和最低水平線段的寬度：如果最低水平線段的寬度大于矩形件Pi的寬度，排入矩形件Pi，更新輪廓線；如果最低水平線段的寬度小于矩形件Pi的寬度，依次搜索矩形件Pi之后的每一個矩形件，若能夠找到寬度小于最低水平線段的矩形件Pj，將矩形件Pj排入當前最低水平線位置，原來的矩形件Pi到Pj-1排放順序相應后移一位；如果有多個矩形件滿足要求，則選取寬度最大的那個矩形件；如果找不到能夠排入當前水平線位置的矩形件，則將最低水平線的高度提升至輪廓線中高度較低的那段水平線位置。記錄產生的空閑區域的坐標信息，搜索空閑矩形鏈表，根據坐標信息判斷是否有已知空閑區域與之鄰接。如果存在已有的空閑區域與之鄰接，則將兩個空閑區域進行合并。更新空閑區域鏈表，更新輪廓線。并返回到2）

3）若矩形件未排放完畢，返回步驟2）

改進的最低水平線搜索算法流程圖如圖6所示。

圖6 改進最低水平線搜索算法流程圖

如圖7所示，對于圖2的矩形件采用改進的最低水平線算法生成的排樣圖。

圖7 基于改進的最低水平線搜索算法生成的排樣圖

3 分布估計算法解決矩形件排樣優化問題

3.1 基本分布估計算法

分 布 估 計 算 法 （Estimation of Distribution Algorithm）的概念最初在1996年被提出[12]，后來迅速發展成為進化計算領域的熱點課題，并得到了國內外學者的廣泛研究。分布估計算法采用了一種全新的進化模式。在傳統的遺傳算法中，種群表示一組候選解集合，通過適應值來描述種群中每個個體的優劣。個體之間反復進行選擇、交叉、變異等操作，實現種群進化并求取最優解。而在分布估計算法中，個體之間不存在交叉和變異等遺傳操作，其采用概率模型描述個體在種群中中的分布，概率模型是通過統計學習的手段從群體的角度宏觀上建立[13]。種群進化時，首先基于概率模型進行隨機采樣生成新的種群，然后選取新種群中的優秀個體更新概率模型，接著基于新的概率模型進行隨機采樣。如此反復進行，實現種群的進化，直到滿足條件終止。

根據采樣方法和概率模型復雜程度的不同，分布估計算法有著很多不同的實現方法，主要可以歸納為下面兩個步驟：

1）構建描述解空間的概率模型。根據種群個體的適應值，選擇優秀的個體集合，運用統計學習的手段更新概率模型，構建描述當前種群的概率模型。

2）根據新的概率模型隨機采樣產生新的種群。

3.2 編碼和解碼

將n個待排放的矩形件按照排放的順序進行編碼，每一種排放順序對應一個編碼序列，其編碼形式為A={a1，a2，…，an}。其中每個十進制數ai表示一個矩形件，由于矩形件在排放的過程中存在橫排和縱排兩種情況，每個整數有正負之分，ai取正數時矩形件直接排入板材中，ai取負數時將矩形件旋轉90度排入板材中。因此，將用來表示矩形件排放順序的十進制數ai用k位（2k-2＜ai＜2k-1）的二進制數Xi=[hik，hi（k-1），…，hi1]∈{0，1}k表示，其中hik取0時，ai取正數，當hik取1時，ai取負數。將n個二進制編碼片段連接在一起就組成了所有待排放矩形件的編碼X=[h1k，h1（k-1），…，h11，…，hnk，hn（k-1），…，hn1]。

已知第i個矩形件的排放順序ai用二進制編碼表示為 Xi=[hik，hi（k-1），…，hi1]∈{0，1}k，則其解碼公式（2）：

3.3 評價適應度函數

文中所討論的問題是在一個寬度一定，長度無限的矩形板材上排放矩形件，要求全部矩形件在滿足特定約束條件的情況下排入板材中，使得消耗的板材長度最短即板材的利用率達到最高。其適應度函數為公式（1），根據下面的概率模型隨機采樣不斷搜索適應值f較大的解。

3.4 建立概率模型

假設在建立概率模型時各個隨機變量之間相互獨立，采用UMDA算法更新概率模型。用一個概率向量P（X）=[p（x1），p（x2），…，p（xq）]表示候選解空間的概率模型，其中q表示基因鏈的長度，p（xi）∈[0，1]表示基因鏈中位置i取1的概率，1-p（xi）表示位置i取0的概率。如果種群進化到了第l代，那么第l+1代的概率向量如公式（3）：

3.5 算法步驟

步驟一，根據概率向量Pl（X）=[0.5，0.5，…，0.5]隨機采樣產生M個個體組成初始群體Dl，其中l=0。

步驟二，根據適應度函數評估種群M中各個體的適應值，找出最優解。

步驟三，若最優解滿足要求，達到算法終止條件，則算法結束，否則轉步驟四繼續執行。

步驟四，在初始種群的M個個體中選擇N個（N＜M）作為優勢群體，根據優勢群體構建新的概率模型Pl+1（X）。

步驟五，根據概率模型Pl+1（X）隨機采樣M次，得到新一代的種群，然后返回步驟二。

4 算法測試與結果對比

文中采用文獻[16]中的數據進行實驗，測試算法的性能。表1中列出了未排放矩形件的尺寸和需求量，以寬度為65（單位：毫米），高度不限的矩形板材為排放矩形。表2為采取本文的算法得出的矩形件排放順序，其中值為負數的整數表示將對應序號的矩形件旋轉90度排入板材中。圖8是本文中的算法得出的排樣圖。圖 9是文獻[16]中算法得出的排樣圖。表3中列出了基于本文算法排樣和基于文獻[16]中的算法排樣所消耗的板材長度，以及板材的利用率的情況。

表 1 待排放矩形件尺寸及需求量

表2 本文算法得出的排樣順序

圖9中是對于同樣的矩形件數據采用文獻[16]中算法得出的排樣圖，文獻中采取的是一種遺傳算法和最低水平線空閑區域可再利用搜索算法相結合的混合算法。在遺傳算法運行時，設置個體的交叉概率為0.5，變異概率為0.6，初始種群的規模為20，代溝為0.3，取進化代數為100的時候，算法的優化結果。

如表3所示，本文算法與文獻[16]中算法采用相同的數據得到的實驗結果。采取本文優化算法求解表1中的矩形件排樣問題，得到的板材的利用率93.75%，而文獻中的混合算法得到的板材利用率為91.84%。不僅在優化結果上面本文算法的性能更好，而且由于文獻[16]中采取的是基于最低水平線空閑區域可再利用的搜索算法和遺傳算法相結合的算法。在遺傳算法中[14-15]，每個個體之間在種群進化時需要進行交叉和變異操作，且上述結果是遺傳算法迭代100代得出的優化結果。這使得文獻中的算法的時間復雜度較高。而分布估計算法采取統計學習的構建概率模型并隨機采樣產生新的種群的進化方式，是對整個群體進行的操作，免去了個體的交叉和變異的操作。從而降低了算法的復雜度。

圖8 基于本文算法得到的排樣圖

圖9 基于文獻[16]中算法得到的排樣圖

表 3 本文結果和文獻［16］中結果對比

5 結束語

文中將分布估計算法和改進的最低水平線搜索算法相結合求解矩形件排樣優化的問題，在性能上有著很好的效果，為矩形件排樣問題提供了新思路。分布估計算法的研究尚屬初期，仍有許多問題需要去研究。但是從本文的應用效果來看。分布估計算法對于實驗中的應用領域有著很大的價值和意義。

[1]劉海明，周炯，吳忻生，等.基于改進最低水平線方法與遺傳算法的矩形件排樣優化算法[J].圖學學報，2015（4）:526-531.

[2]陳仕軍，曹炬.矩形件優化排樣的一種啟發式算法[J].計算機工程與應用，2010（12）:230-232，238.

[3]An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem[J].自動化學報，2007（9）:911-916.

[4]王桂賓，周來水，鄧冬梅.基于模擬退火算法的矩形件排樣[J].中國制造業信息化，2006（15）:65-67，70.

[5]馮琳，史俊友.基于蟻群算法的矩形件優化排樣問題[J].青島科技大學學報：自然科學版，2011（1）: 90-94.

[6]宋佩華，蔣聯源，歐啟忠.基于離散粒子群優化算法求解矩形件排樣問題 [J].計算機應用與軟件，2008（1）:238-240.

[7]Jakobs S.On genetic algorithms for the packing of polygons [J].Eu-ropean Journal of Operational Research，1996，88（1）:165-161.

[8]吳忻生，吳超成，劉海明.基于改進遺傳算法的矩形件排樣優化算法[J].制造業自動化，2013（19）: 55-58，115.

[9]王竹婷，劉林，程浩，等.改進的最低水平線搜索算法求解矩形排樣問題[J].工程設計學報，2009（2）:98-102.

[10]王桂蘭，朱志松，朱龍彪，等.矩形件的“一刀切”排樣優化設計[J].制造業自動化，2014（1）:1-3，12.

[11]陳江義，宋雪楓，張明偉.融合蟻群算法和遺傳算法的矩形件排樣問題研究 [J].鄭州大學學報：理學版，2011（2）:79-82.

[12]Christoforos C，Fleszar K.A constructive binoriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers&Operations Research，2011，38（10）: 1443-1451.

[13]周樹德，孫增圻.分布估計算法綜述[J].自動化學報，2007（2）:113-124.

[14]Wei Lijun，Oon W C，Zhu Wenbin，et al.A skyline heuristic for the 2D rectangular packing and strip packing problems [J].European Journalof Operational Research，2011，215（2）:337-346.

[15]隗平平，劉斌.基于并行遺傳算法的矩形件排樣優化 [J].組合機床與自動化加工技術，2011（3）: 78-82.

[16]黃紅兵.矩形件下料優化排樣的遺傳算法[D].桂林:廣西師范大學，2005.

[17]訾鴻，楊俊杰，宋婀娜.基于改進遺傳算法的船舶電力系統無功優化研究[J].工業儀表與自動化裝置，2013（4）：17-20.

[18]劉方，姬曉杰，楊秀.基于改進遺傳算法的微網多目標優化調度[J].陜西電力，2015（3）：21-24，34.

Solution to optimize cutting pattern in rectangular packing problem based on estimation of distribution algorithm

MA Kang，GAO Shang
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212003，China）

Rectangular packing is a planar layout optimization problem and NP-complete problem，It is difficult to find its exact global optimum in a short time because of the numerous constraints and the high complexity of computation.Facing the problem of rectangular packing，This paper took the improved Lowest Horizontal Search Algorithm and the Estimation of Distribution Algorithms（EDAs）to solve the rectangular packing problem，which make full use of the space area by merging adjacent free area based on the position relationship of wasted free area which produced by rectangular packing. Finally，with the simulation experiment，utilization ratio of rectangular plate is 93.75%with the algorithm of this paper，which proved the effectiveness of the algorithm.

optimization layout；rectangular；EDA；lowest horizontal search algorithm

TN05

：A

：1674-6236（2017）02-0049-06

2016-01-04稿件編號：201601012

馬 康（1992—），男，江蘇淮安人，碩士研究生。研究方向：智能計算。