基于遺傳模擬退火算法的布局優化研究

周家智，尹 令，張素敏

?

基于遺傳模擬退火算法的布局優化研究

周家智，尹 令，張素敏

(華南農業大學數學與信息學院，廣東 廣州 510642)

為提高矩形件排樣算法的利用率與時間效率，提出將遺傳算法和模擬退火算法融合優化的矩形排樣算法。采用帶符號的十進制編碼,依據矩形件長寬比和面積而生成基因序列用于建立初始種群，以隨機產生若干排樣順序與排樣尺寸不一的個體，并以利用率為適應度函數，修改后的最低水平線搜索算法作為排樣策略，保證較優個體得以保留，減少閑置區域的產生。采用10組隨機產生的矩形數據將本算法與現有文獻提出的GA算法進行對比實驗，實驗結果顯示：該算法有效地提升了排樣結果的利用率與時間效率。

矩形件排樣；遺傳算法；模擬退火算法；最低水平線改進算法

矩形件排樣問題即給定某單一尺寸的庫存板材和一組毛坯需求，要求從板材中切割出毛坯，并滿足所有毛坯的尺寸及數量需求，使消耗的板材數量或板材價值最小。矩形件排樣問題廣泛存在于布匹裁剪、金屬鍛造、木材切割等加工業領域，具有一定的計算復雜性，屬于NP問題。對矩形件排樣問題的算法優化具有一定的理論價值與現實價值。對矩形件排樣問題的研究通常建立在特定的前提條件下：無限原材料或有限原材料。

矩形件排樣問題作為經典的NP問題，與生產需求存在密切聯系。對于矩形件排樣的研究多數分為兩個方面：排樣策略的研究與排樣順序的研究。排樣策略通過設計矩形件排樣過程所遵循的準則規范，以達到增加板材利用率的目的，如CUI等[1]提出的順序啟發式算法以及SILVA等[2]基于實際工業問題提出的啟發式方法與整數規劃模型均是從排樣策略出發設計或優化提出的；排樣順序地研究證實了矩形件的排放順序對板材利用率的影響，尋找能達到最優解的排樣順序。在實際的應用研究中，矩形排樣問題基于不同的目標有不同的需求，具有一定的個性化，因此至今仍未形成統一的求解方法。近年來，智能優化算法多次用于與原有排樣算法組合優化出新算法以滿足多樣化的現實需求，越來越多研究學者將智能優化算法與改進的排樣算法融合優化成新的排樣算法，如文獻[3]提出控制基因的分組遺傳算法(grouping genetic algorithm with controlled gene transmission，GGA-CGT)解決裝箱問題。

基于此背景，國內涌現了眾多研究成果。如基于三階段排樣方式提出的二維剪切下料算法[4]通過形成規則形狀的剩余原材料，增加可用于二次利用的材料，增加企業效益。以及基于背包算法和線性規劃算法提出的均勻條帶四塊排樣算法[5]?；谧顑炞佣蔚呐艠铀惴ㄡ槍I生產中長矩形原材料排樣問題提供了解決方案[6]。上述提到的幾種優化算法均從實際的生產需求出發，針對性地提出了有效的求解方法。但另一方面，由于生產需求的多樣性，以解決具體生產問題為目標而提出的求解方法存在自身算法不足、可移植性較差地問題。如文獻[4]的算法性能偏低，需要進一步改進；文獻[6]算法僅適用于滿足“一刀切”條件的板材排樣；文獻[5]的兩種算法無法做到時間與利用率同時優化等。

本文在現有的矩形優化排樣算法研究成果上，基于遺傳算法、模擬退火算法兩種智能優化算法，融合設計出針對矩形件排樣問題的遺傳模擬退火算法，該算法可移植性強，原材料利用率相對于參照算法有顯著提高。

1 求解模型構建

1.1 問題描述

矩形件排樣問題在無限原材料條件下指把個已知長寬的矩形件{1,2, ···,p}排放到寬度為MaterialWidth且長度不限的矩形原材料中，在滿足一定約束條件下使原材料利用率最高，從而減少材料的使用以降低成本。其中約束條件包括：

(1) p不能超出的邊界，= 1, 2, ···,；

(2) p與p不互相重疊，,= 1, 2, ···,；

(3)排放時p只有橫放或豎放兩種排放方式，即長邊或短邊平行于軸。

1.2 數學模型

設原材料的左下角坐標為(0, 0)，定義矩形件排放后的最高點縱坐標為該矩形件的水平線高度。具體參數設置如下：

(1) p為第個待排放矩形件；

(2)(x, y)為矩形件p的左下角坐標；

(3) w為矩形件p的短邊；

(4) l為矩形件p的長邊；

(5) h為矩形件p的水平線高度；

(6) f為矩形件p的排放方式，f= 1為矩形件橫放，即長邊平行于軸；f= –1為矩形件豎放，即短邊平行于軸。

圖1為4個矩形件排放示例圖，其中陰影部分為無法利用的閑置區域。在實際工業生產中，更希望余料盡可能地聚集在原材料的頂部，有利于余料的二次利用，因此追求矩形件排樣高度盡可能低。

圖1 矩形件排放示例圖

基于上述需求，設=(1,2, ···,h)以最高水平線MaxLevel為目標函數，即

且應滿足約束條件

式(3)表示p不超出的邊界；式(4)表示p與p不互相重疊；式(3)、(4)均滿足,= 1, 2,···,，且≠。

2 基于遺傳算法與模擬退火算法的排樣算法

上述矩形件排樣問題中，矩形件的排樣順序與排樣策略對最終排樣結果均有重要影響。為此，本文引入遺傳算法與模擬退火算法最大限度搜尋排樣順序的解空間，并對現有的矩形件排樣算法進行修改，優化排樣策略，最終融合出進一步提升利用率的排樣算法。

2.1 編碼方式設計

為降低算法復雜性，采用十進制編碼方式，設有個待排放矩形件，則矩形件編號為1, 2,···,。在十進制編碼中使用正負符號表示矩形件排放方式，負數表示矩形件豎排，正數表示矩形件橫排。綜上，=(1,2, ···,r)為個體中個矩形件的其中一個排樣序列。對于排樣序列=(1,2, ···,r)，按照1,2, ···,r的順序依次排放，并根據編號的正負決定該編號矩形件的排放方式。

如圖2所示為= (－1, 2, －3, 4, －5)的基因序列，一共5個矩形件按編號升序排樣，其中矩形件1、3、5豎排，2、4橫排。

圖2 矩形排放示意圖

2.2 適應度函數設計

本文算法的目標在于提高原材料的利用率，因此采用式(2)的利用率公式作為適應度函數，即

2.3 選擇操作

為了把父代種群中較優個體得以保留，使用輪盤賭選擇法將較優個體保留到子代種群中。具體操作方法為：

步驟3. 重復步驟2直到達到下一代種群規模。

2.4 交叉變異操作

使用單點交叉操作，從種群中選取兩條互不相同的個體1與2，隨機選取一個交叉位置，將個體1與2在以前的基因序列分別復制到新個體3與4中；再將存在于1且不存在于4的基因復制到4上，對2與4執行同樣的操作。

變異操作所采用的變異方式一共4種：位置變異、插入變異、反轉變異和交換變異。位置變異在選中個體的長度范圍內隨機選取兩個不同的基因位置，并互換基因位置。插入變異在選中個體的長度范圍內隨機選取前后兩個不同的基因位置，將較后處基因插入到較前處基因的后一個位置，兩個基因位之間的基因則往后移動。反轉變異在選中個體的長度范圍內隨機選取兩個不同的基因位置，將兩個基因位置間的基因序列逆序以代替原基因序列。交換變異在選中個體的長度范圍內隨機選取一個基因位置，將選中位置的基因與后一位基因互換，若選中的基因為末位基因，則與首位基因交換。

2.5 模擬退火操作

其中，為溫度衰減參數，參數值手動輸入，用于控制退火的速度，且滿足∈[0.2, 0.95]。

2.6 構造初始種群

初始種群的個體一半通過優先級函數產生，一半通過隨機數作為優先級產生，優先級函數公式為

其中，P為第個矩形基因優先級；l和w分別為第個矩形的長和寬；P為該矩形長寬比值所占權重；P為矩形面積所占權重；函數生成的隨機數R∈(0,1)，其中長寬比值權重與面積權重之和為1，即P+P= 1。

2.7 基于最低水平線算法的修改

最低水平線算法是圍繞水平線而展開的算法，在進行矩形件排樣時，找出當前高度最低，且位于最左的低水平線進行排放，若無法滿足當前矩形件的排放，則將該水平線與相鄰水平線合并，直至能夠滿足當前矩形件的排放條件。

為了進一步優化，最低水平線搜索算法在最低水平線算法上添加了水平線的搜索機制，當最低最左水平線無法滿足當前矩形件排樣條件時，則向后搜索適合排放的矩形件進行排放，若不存在適合的矩形件，再進行水平線合并操作。

最低水平線搜索算法避免了可能因更新水平線而造成浪費的閑置區域出現。然而，在所選取水平線無法排放當前矩形件時，最低水平線搜索算法只往后搜索到一個滿足排放條件的矩形件返回，忽略了存在邊長與水平線長度更接近的矩形件的可能性，沒有充分利用水平線所提供的排放空間。

針對上述不足，本文基于同類文獻的思路進行了修改：

(1) 引入矩形件旋轉機制，若當前矩形件按照原有排放方式無法排放，則變換排放方式進行排放。

(2) 若當前矩形件無法排放，則向后搜索滿足排放條件且邊長與水平線最接近的矩形件進行排放。

修改后算法步驟如下：

步驟1.把矩形原材料寬度放入隊列，作為初始水平線，記為p=(0,0,0,0,,1)；

步驟2.選取高度最低且最左邊的水平線對應的矩形p= (x,y,w,l, h,,f)；

步驟5. 向后尋找滿足排放條件的所有矩形件；

步驟6.如果記錄中存在矩形件數據，則將記錄中邊長最長的矩形件p與待排放矩形件p位置互換，進行排放。進入步驟8，否則進入下一步驟；

步驟7.設h-1所處高度為h′–1= y–1+，h所處高度為h′+1=；若m–1≥h′+1，則令h+1=0且h= h+h+1；否則令h–1=0且h=h+ h–1。跳轉到步驟2；

步驟8. 反復執行步驟2，直到不存在未排放的部件。

從圖3可以看出，引入了旋轉機制的最低水平線搜索算法的排樣高度明顯低于修改前算法，顯著減少板材閑置區域的出現。

顯然，與修改前算法相比，排樣算法修改后減少原材料消耗的同時也增加了可用原材料的面積。

圖3 兩種算法的排樣效果比較圖

2.8 遺傳模擬退火算法的流程圖

綜合上述步驟，遺傳模擬退火算法流程如圖4所示。

圖4 遺傳模擬退火算法流程圖

3 算法評估

為測試遺傳模擬退火算法性能，將本文算法與文獻[8]算法進行橫向比較，以文獻[8]提供的矩形件樣例和其隨機產生的矩形樣例作為測試數據。

實驗平臺：聯想Y510P筆記本，Intel i5 2.50 GHz處理器，8.0 GB RAM，使用Visual Studio C# 2015編程實現該算法。

算法參數：算法初始參數均人為設置。種群大小為100；遺傳迭代次數為20；種群交叉概率p為0.5；種群變異概率p為0.3；矩形長寬比值權重p為0.7；矩形面積權重p為0.3，初始溫度為 3 000；閾值溫度min為1 000；溫度衰減參數為0.9；當溫度低于閾值溫度min，算法終止運行。

本文采用文獻[8]的矩形件數據，見表1。將本文算法運行表1矩形件數據后的結果與文獻[8]進行對比，對比結果見表2。

表1 矩形件數據

表2 排樣結果數據(I)

表2結果顯示，本文所提出算法相對于文獻[8]算法求解利用率有進一步提高，但算法運行時間高于文獻[8]算法。

以矩形件種類與總數作為標準，生成10組長度與寬度隨機的若干矩形件，進一步測試本文算法性能。以產生的矩形件作為測試數據，測試中算法的參數與板材寬度不變，使用本文算法求解并與文獻[8]結果進行對比，結果見表3。

表3 排樣結果數據(II)

根據表3的數據分析得出，在矩形件種類與總數不斷變換的條件下，本文算法的avg以及best仍然高于文獻[8]算法，而且即使矩形件不斷變換，本文算法的利用率仍然保持在一定水平，具有一定的穩定性。在avg比，無論是排樣的利用率還是算法的運行時間，本文算法均優于文獻[8]算法。

4 結束語

本文綜合已有文獻的研究成果對最低水平線搜索算法做出了排樣策略的修改，使用自適應的規則靈活調整矩形件排放順序，減少了排樣過程中閑置區域的產生，提高了板材的利用率。采用優先級函數構造初始種群，并引入模擬退火機制避免了遺傳算法種群早熟現象，提高算法性能，并將修改后的最低水平線算法與遺傳算法和模擬退火算法結合，用于解決矩形件排樣問題。經過實驗數據測試，本文提出的算法能進一步提升板材利用率，能有效應用于實際生產。

[1] CUI Y P, CUI Y D, TANG T B. Sequential heuristic for the two-dimensional bin-packing problem [J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[2] SILVA E, ALVELOS F, DE CARVALHO J M V. Integerating two-dimensional cutting stock and lot-sizing problems [J]. Journal of the Operational Research Society. 2014, 65(1): 108-123.

[3] QUIROZ-CASTELLANOS M, CRUZ-REYES L, TORRES-JIMENEZ J, et al. A grouping genetic algorithm with controlled gene transmission for the bin packing problem [J]. Computers & Operations Research, 2015, 55(C): 52-64.

[4] 陳秋蓮, 宋仁坤, 崔耀東. 考慮余料價值的三階段二維剪切下料算法[J]. 圖學學報, 2017, 38(1): 10-14.

[5] 曾兆敏, 王繼紅, 管衛利. 二維板材切割下料問題的一種確定性算法[J]. 圖學學報, 2016, 37(4): 471-475.

[6] 姜永亮, 周俊. 基于最優子段的矩形優化排樣[J]. 圖學學報, 2016, 37(2): 280-284.

[7] 楊衛波. 基于遺傳模擬退火算法的矩形件優化排樣[J]. 計算機工程與應用, 2016, 52(7): 259-263.

[8] LIU H M, ZHOU J, WU X S, 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. New York: IEEE Press, 2014: 352-357.

On Layout Optimization Based on Genetic Simulated Annealing Algorithm

ZHOU Jiazhi, YIN Ling, ZHANG Sumin

(School of Mathematics and Informatics, South China Agricultural University, Guangdong Guangzhou 510642, China)

Based on the integration of the genetic algorithm (GA) and the simulated annealing algorithm, an improved lowest horizontal line (ILHL) algorithm is presented in order to improve utilization and stability of the rectangular packing algorithm. In this algorithm, a signed decimal encoding is utilized to generate the gene sequence in accordance with the length-width ratio and the area of the rectangle, which is employed to establish the initial population. The improved lowest horizontal line algorithm adopts the best individuals from a number of random sequences with different nesting orders and layout sizes, uses utilization rate as the fitness function and reduces the idle area. In this paper, a contrast experiment is operated to compare ten groups of rectangular data randomly generated by ILHL with those generated by GA proposed in the current literature. The experiment results show that our algorithm (ILHL) can effectively improve the utilization rate and time efficiency of the packing results.

rectangular packing; genetic algorithm; simulated annealing algorithm; improved lowest horizontal line

TP 301.6

10.11996/JG.j.2095-302X.2018030567

A

2095-302X(2018)03-0567-06

2017-08-31；

2017-09-30

周家智(1994-)，男，廣東清遠人，本科生。主要研究方向為布局優化、機器學習。E-mail：524841091@qq.com