馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮(zhèn)江212003）

分布估計算法求解矩形件排樣優(yōu)化問題

馬 康，高 尚

（江蘇科技大學，計算機科學與工程學院，江蘇 鎮(zhèn)江212003）

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

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

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

1 問題描述

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

圖1 一個矩形件排樣樣例

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

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

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

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

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

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

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

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

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

1）算法改進策略

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

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

2）相鄰空閑區(qū)域合并規(guī)則

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

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

圖3 空閑矩形區(qū)域相鄰的情況

圖4 同一平面矩形區(qū)域之間三種位置關(guān)系

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

圖5 相鄰空白區(qū)域合并示意圖

3）算法的具體步驟

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

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

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

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

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

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

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

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

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

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

3 分布估計算法解決矩形件排樣優(yōu)化問題

3.1 基本分布估計算法

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

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

1）構(gòu)建描述解空間的概率模型。根據(jù)種群個體的適應值，選擇優(yōu)秀的個體集合，運用統(tǒng)計學習的手段更新概率模型，構(gòu)建描述當前種群的概率模型。

2）根據(jù)新的概率模型隨機采樣產(chǎn)生新的種群。

3.2 編碼和解碼

將n個待排放的矩形件按照排放的順序進行編碼，每一種排放順序?qū)粋€編碼序列，其編碼形式為A={a1，a2，…，an}。其中每個十進制數(shù)ai表示一個矩形件，由于矩形件在排放的過程中存在橫排和縱排兩種情況，每個整數(shù)有正負之分，ai取正數(shù)時矩形件直接排入板材中，ai取負數(shù)時將矩形件旋轉(zhuǎn)90度排入板材中。因此，將用來表示矩形件排放順序的十進制數(shù)ai用k位（2k-2＜ai＜2k-1）的二進制數(shù)Xi=[hik，hi（k-1），…，hi1]∈{0，1}k表示，其中hik取0時，ai取正數(shù)，當hik取1時，ai取負數(shù)。將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 評價適應度函數(shù)

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

3.4 建立概率模型

假設(shè)在建立概率模型時各個隨機變量之間相互獨立，采用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 算法步驟

步驟一，根據(jù)概率向量Pl（X）=[0.5，0.5，…，0.5]隨機采樣產(chǎn)生M個個體組成初始群體Dl，其中l(wèi)=0。

步驟二，根據(jù)適應度函數(shù)評估種群M中各個體的適應值，找出最優(yōu)解。

步驟三，若最優(yōu)解滿足要求，達到算法終止條件，則算法結(jié)束，否則轉(zhuǎn)步驟四繼續(xù)執(zhí)行。

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

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

4 算法測試與結(jié)果對比

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

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

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

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

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

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

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

表 3 本文結(jié)果和文獻［16］中結(jié)果對比

5 結(jié)束語

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

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

[2]陳仕軍，曹炬.矩形件優(yōu)化排樣的一種啟發(fā)式算法[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].中國制造業(yè)信息化，2006（15）:65-67，70.

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

[6]宋佩華，蔣聯(lián)源，歐啟忠.基于離散粒子群優(yōu)化算法求解矩形件排樣問題 [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]吳忻生，吳超成，劉海明.基于改進遺傳算法的矩形件排樣優(yōu)化算法[J].制造業(yè)自動化，2013（19）: 55-58，115.

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

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

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

[12]Christoforos C，F(xiàn)leszar 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]隗平平，劉斌.基于并行遺傳算法的矩形件排樣優(yōu)化 [J].組合機床與自動化加工技術(shù)，2011（3）: 78-82.

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

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

[18]劉方，姬曉杰，楊秀.基于改進遺傳算法的微網(wǎng)多目標優(yōu)化調(diào)度[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—），男，江蘇淮安人，碩士研究生。研究方向：智能計算。