基于遺傳模擬退火算法的布局優(yōu)化研究

周家智，尹 令，張素敏

?

基于遺傳模擬退火算法的布局優(yōu)化研究

周家智，尹 令，張素敏

(華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院，廣東 廣州 510642)

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

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

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

矩形件排樣問題作為經(jīng)典的NP問題，與生產(chǎn)需求存在密切聯(lián)系。對(duì)于矩形件排樣的研究多數(shù)分為兩個(gè)方面：排樣策略的研究與排樣順序的研究。排樣策略通過設(shè)計(jì)矩形件排樣過程所遵循的準(zhǔn)則規(guī)范，以達(dá)到增加板材利用率的目的，如CUI等[1]提出的順序啟發(fā)式算法以及SILVA等[2]基于實(shí)際工業(yè)問題提出的啟發(fā)式方法與整數(shù)規(guī)劃模型均是從排樣策略出發(fā)設(shè)計(jì)或優(yōu)化提出的；排樣順序地研究證實(shí)了矩形件的排放順序?qū)Π宀睦寐实挠绊懀瑢ふ夷苓_(dá)到最優(yōu)解的排樣順序。在實(shí)際的應(yīng)用研究中，矩形排樣問題基于不同的目標(biāo)有不同的需求，具有一定的個(gè)性化，因此至今仍未形成統(tǒng)一的求解方法。近年來，智能優(yōu)化算法多次用于與原有排樣算法組合優(yōu)化出新算法以滿足多樣化的現(xiàn)實(shí)需求，越來越多研究學(xué)者將智能優(yōu)化算法與改進(jìn)的排樣算法融合優(yōu)化成新的排樣算法，如文獻(xiàn)[3]提出控制基因的分組遺傳算法(grouping genetic algorithm with controlled gene transmission，GGA-CGT)解決裝箱問題。

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

本文在現(xiàn)有的矩形優(yōu)化排樣算法研究成果上，基于遺傳算法、模擬退火算法兩種智能優(yōu)化算法，融合設(shè)計(jì)出針對(duì)矩形件排樣問題的遺傳模擬退火算法，該算法可移植性強(qiáng)，原材料利用率相對(duì)于參照算法有顯著提高。

1 求解模型構(gòu)建

1.1 問題描述

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

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

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

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

1.2 數(shù)學(xué)模型

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

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

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

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

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

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

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

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

圖1 矩形件排放示例圖

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

且應(yīng)滿足約束條件

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

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

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

2.1 編碼方式設(shè)計(jì)

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

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

圖2 矩形排放示意圖

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

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

2.3 選擇操作

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

步驟3. 重復(fù)步驟2直到達(dá)到下一代種群規(guī)模。

2.4 交叉變異操作

使用單點(diǎn)交叉操作，從種群中選取兩條互不相同的個(gè)體1與2，隨機(jī)選取一個(gè)交叉位置，將個(gè)體1與2在以前的基因序列分別復(fù)制到新個(gè)體3與4中；再將存在于1且不存在于4的基因復(fù)制到4上，對(duì)2與4執(zhí)行同樣的操作。

變異操作所采用的變異方式一共4種：位置變異、插入變異、反轉(zhuǎn)變異和交換變異。位置變異在選中個(gè)體的長度范圍內(nèi)隨機(jī)選取兩個(gè)不同的基因位置，并互換基因位置。插入變異在選中個(gè)體的長度范圍內(nèi)隨機(jī)選取前后兩個(gè)不同的基因位置，將較后處基因插入到較前處基因的后一個(gè)位置，兩個(gè)基因位之間的基因則往后移動(dòng)。反轉(zhuǎn)變異在選中個(gè)體的長度范圍內(nèi)隨機(jī)選取兩個(gè)不同的基因位置，將兩個(gè)基因位置間的基因序列逆序以代替原基因序列。交換變異在選中個(gè)體的長度范圍內(nèi)隨機(jī)選取一個(gè)基因位置，將選中位置的基因與后一位基因互換，若選中的基因?yàn)槟┪换颍瑒t與首位基因交換。

2.5 模擬退火操作

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

2.6 構(gòu)造初始種群

初始種群的個(gè)體一半通過優(yōu)先級(jí)函數(shù)產(chǎn)生，一半通過隨機(jī)數(shù)作為優(yōu)先級(jí)產(chǎn)生，優(yōu)先級(jí)函數(shù)公式為

其中，P為第個(gè)矩形基因優(yōu)先級(jí)；l和w分別為第個(gè)矩形的長和寬；P為該矩形長寬比值所占權(quán)重；P為矩形面積所占權(quán)重；函數(shù)生成的隨機(jī)數(shù)R∈(0,1)，其中長寬比值權(quán)重與面積權(quán)重之和為1，即P+P= 1。

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

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

為了進(jìn)一步優(yōu)化，最低水平線搜索算法在最低水平線算法上添加了水平線的搜索機(jī)制，當(dāng)最低最左水平線無法滿足當(dāng)前矩形件排樣條件時(shí)，則向后搜索適合排放的矩形件進(jìn)行排放，若不存在適合的矩形件，再進(jìn)行水平線合并操作。

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

針對(duì)上述不足，本文基于同類文獻(xiàn)的思路進(jìn)行了修改：

(1) 引入矩形件旋轉(zhuǎn)機(jī)制，若當(dāng)前矩形件按照原有排放方式無法排放，則變換排放方式進(jìn)行排放。

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

修改后算法步驟如下：

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

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

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

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

步驟7.設(shè)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。跳轉(zhuǎn)到步驟2；

步驟8. 反復(fù)執(zhí)行步驟2，直到不存在未排放的部件。

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

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

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

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

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

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

3 算法評(píng)估

為測(cè)試遺傳模擬退火算法性能，將本文算法與文獻(xiàn)[8]算法進(jìn)行橫向比較，以文獻(xiàn)[8]提供的矩形件樣例和其隨機(jī)產(chǎn)生的矩形樣例作為測(cè)試數(shù)據(jù)。

實(shí)驗(yàn)平臺(tái)：聯(lián)想Y510P筆記本，Intel i5 2.50 GHz處理器，8.0 GB RAM，使用Visual Studio C# 2015編程實(shí)現(xiàn)該算法。

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

本文采用文獻(xiàn)[8]的矩形件數(shù)據(jù)，見表1。將本文算法運(yùn)行表1矩形件數(shù)據(jù)后的結(jié)果與文獻(xiàn)[8]進(jìn)行對(duì)比，對(duì)比結(jié)果見表2。

表1 矩形件數(shù)據(jù)

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

表2結(jié)果顯示，本文所提出算法相對(duì)于文獻(xiàn)[8]算法求解利用率有進(jìn)一步提高，但算法運(yùn)行時(shí)間高于文獻(xiàn)[8]算法。

以矩形件種類與總數(shù)作為標(biāo)準(zhǔn)，生成10組長度與寬度隨機(jī)的若干矩形件，進(jìn)一步測(cè)試本文算法性能。以產(chǎn)生的矩形件作為測(cè)試數(shù)據(jù)，測(cè)試中算法的參數(shù)與板材寬度不變，使用本文算法求解并與文獻(xiàn)[8]結(jié)果進(jìn)行對(duì)比，結(jié)果見表3。

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

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

4 結(jié)束語

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

[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] 陳秋蓮, 宋仁坤, 崔耀東. 考慮余料價(jià)值的三階段二維剪切下料算法[J]. 圖學(xué)學(xué)報(bào), 2017, 38(1): 10-14.

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

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

[7] 楊衛(wèi)波. 基于遺傳模擬退火算法的矩形件優(yōu)化排樣[J]. 計(jì)算機(jī)工程與應(yīng)用, 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-)，男，廣東清遠(yuǎn)人，本科生。主要研究方向?yàn)椴季謨?yōu)化、機(jī)器學(xué)習(xí)。E-mail：524841091@qq.com