基于自適應(yīng)遺傳模擬退火算法的矩形件排樣

夏以沖，陳秋蓮，宋仁坤

廣西大學(xué) 計算機與電子信息學(xué)院，南寧 530004

1 引言

矩形件排樣是指將一定種類和數(shù)量的矩形件排放在一個寬度固定、長度不限的矩形板材中，以有效利用板材。矩形件排樣優(yōu)化在現(xiàn)代制造、加工行業(yè)中應(yīng)用非常廣泛，比如各類板材的下料、加工等，是制造業(yè)自動化從設(shè)計到下料過程的關(guān)鍵環(huán)節(jié)，是二維排樣問題中廣泛研究的一類排樣優(yōu)化問題。

矩形件排樣問題的求解包括兩方面：矩形件的定序和定位。其中，定序確定待排樣矩形件的排入順序，定位確定矩形件在板材上的擺放位置。在實際應(yīng)用中，通常采用遺傳算法[1-3]、模擬退火算法[4]等作為定序算法，IBL算法[5]、最低水平線算法[6]等作為定位算法。蔣興波等[7]提出了一種基于環(huán)形交叉和變異算子的自適應(yīng)遺傳算法，通過IBL算法定位，能在較短時間得到滿意的解。Liu等[8]提出基于分階段遺傳算子的改進遺傳算法，與最低水平線排放策略相結(jié)合，有效解決矩形件排樣問題。李明等[9]在遺傳算法中引入小生境技術(shù)，通過排擠與淘汰機制維持種群的多樣性，采用高度調(diào)整法定位，取得較好的排樣效果。

遺傳算法具有較強的全局搜索能力，但存在過早收斂，易陷入局部最優(yōu)，適應(yīng)性較差等缺點。模擬退火算法具有較強的局部搜索能力，但是每一時刻僅保存一個解，缺乏歷史搜索信息，不能很好地把握搜索過程，收斂速度慢。本文將自適應(yīng)遺傳算法和模擬退火算法結(jié)合作為定序算法，以啟發(fā)式最低水平線擇優(yōu)排放策略進行定位，求解矩形件優(yōu)化排樣問題。

2 問題描述及數(shù)學(xué)模型

矩形件排樣問題可以描述為：將n個矩形件{p1,p2,…,pn}排入到一個寬度為W，高度不限的板材中，在滿足約束條件的情況下，使得板材利用率最高。需要滿足的約束條件包括：（1）pi與 pj互不重疊，i≠j；（2）pi排入時不能超過板材邊界；（3）pi的邊必須與板材的邊平行，可以90°旋轉(zhuǎn)。

矩形件pi(i=1,2,…,n)可以用五元組表示：pi=(xi,yi,wi,hi,θi)。其中，(xi,yi)表示其左下角坐標；(wi,hi)表示寬度和高度；θi表示旋轉(zhuǎn)角度，θi∈{0°,90°}。

板材的利用率F定義為矩形件的面積之和與所用板材面積之比。矩形件優(yōu)化排樣問題的數(shù)學(xué)模型如下：

其中，H為所用板材的高度。因此，矩形件優(yōu)化排樣問題可以描述為：尋求滿足約束條件的最佳排樣方案，使得板材的利用率F最大。

3 算法設(shè)計

3.1 算法流程

本文以自適應(yīng)遺傳和模擬退火算法相結(jié)合作為矩形件的定序算法，以啟發(fā)式最低水平線擇優(yōu)算法作為定位算法。首先是遺傳算法，個體采用整數(shù)編碼，通過經(jīng)驗選擇與隨機生成相結(jié)合的方式構(gòu)造初始種群。運用啟發(fā)式最低水平線擇優(yōu)算法進行解碼，計算個體的適應(yīng)值。然后采用精英選擇和輪盤賭相結(jié)合的策略進行選擇，剩余個體進行自適應(yīng)交叉和變異。最后對所有個體進行模擬退火，并更新最優(yōu)個體。重復(fù)遺傳操作和模擬退火，直到迭代次數(shù)等于最大代數(shù)。迭代過程中產(chǎn)生的最優(yōu)個體所對應(yīng)的排樣方案為最終排樣方案。算法流程如圖1所示。

3.2 算法描述

3.2.1 編碼

矩形件優(yōu)化排樣采用整數(shù)編碼，對n個矩形件{p1,p2,…,pn}分別用整數(shù)1,2,…,n進行編號，得到一個染色體編碼X={x1,x2,…,xn}。其中表示第i個排入板材的矩形件編號取正數(shù)時，矩形件不旋轉(zhuǎn)，即θi=0°；xi取負數(shù)時，矩形件旋轉(zhuǎn)，即θi=90°。

圖1 基于自適應(yīng)遺傳模擬退火算法流程圖

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

采用經(jīng)驗選擇與隨機生成相結(jié)合的策略構(gòu)造初始種群，將矩形件按面積降序排序，面積相等時根據(jù)長邊長度遞減排序，產(chǎn)生一個整數(shù)有序序列。對序列中的每個整數(shù)隨機添加正負號，形成一個個體。重復(fù)N次隨機添加正負號過程，得到規(guī)模為N的初始種群。

3.2.3 計算適應(yīng)值

整數(shù)編碼的個體需解碼得到對應(yīng)排樣圖，計算板材利用率，求出適應(yīng)值。本文解碼算法采用啟發(fā)式最低水平線擇優(yōu)算法，在文獻[10]的最低水平線擇優(yōu)策略基礎(chǔ)上引入啟發(fā)式判斷，實現(xiàn)可用空洞區(qū)域填充，具體步驟如下：

（1）初始化最高輪廓線集合，其僅包含板材的底部邊界。

（2）排入矩形件 pi時，在最高輪廓線集合中選取最低的一段水平線，若該段寬度可排，則 pi靠左排放，并更新最高輪廓線集合，否則，轉(zhuǎn)入步驟（3）。

（3）搜索剩余矩形件序列，選取與最低水平線寬度相同的矩形件（如有數(shù)個，選擇最高者），插入 pi所在位置再排入，并更新最高輪廓線集合。若當前最低水平線無可排矩形件，則與相鄰最低的輪廓線合并，同時更新最高輪廓線集合，轉(zhuǎn)入步驟（2）。

表1 初始參數(shù)設(shè)置

（4）重復(fù)上述過程，直到所有矩形件排放完畢，得到個體的排樣圖。

3.2.4 遺傳算子

（1）選擇算子：采用精英保留和輪盤賭相結(jié)合的策略，將適應(yīng)值最高的父代種群個體直接保留至下一代，剩余的N-1個個體以輪盤賭方式進行選擇。避免父代最優(yōu)個體丟失，同時保證適應(yīng)值高的個體有更多機會保留至下一代，提高全局的收斂性和計算效率。

（2）交叉算子：采用環(huán)形交叉，交叉的基因可以環(huán)繞整個染色體兩端來進行，而不僅僅集中在染色體中間部分，每個基因被選中的概率相等，有利于提高算法的全局搜索能力。

經(jīng)典遺傳算法的交叉概率為0到1之間的某個固定值，無法靈活協(xié)調(diào)收斂速度與搜索能力[11]。本文采用自適應(yīng)交叉概率Pc，若個體適應(yīng)值低于種群平均適應(yīng)值，則選擇較大的交叉概率，增加產(chǎn)生新個體的可能，擴大搜索范圍。若適應(yīng)值高于種群平均適應(yīng)值，則根據(jù)當前個體適應(yīng)值動態(tài)減小交叉概率，有利于優(yōu)秀個體保留至下一代。

式中，F(xiàn)avg為當前種群的平均適應(yīng)值；Fmax為最大適應(yīng)值；Facross為兩個交叉?zhèn)€體的較大適應(yīng)值；Pc1、Pc2為預(yù)先設(shè)定的0到1之間的固定值。交叉階段生成一個0到1之間的隨機數(shù)r，若r＜Pc，則執(zhí)行環(huán)形交叉；否則不執(zhí)行。

（3）變異算子：采用自適應(yīng)變異概率Pm的交換變異和旋轉(zhuǎn)變異相結(jié)合的策略，若個體適應(yīng)值低于種群的平均適應(yīng)值，則選擇較大的變異概率，提高算法的局部隨機搜索能力，有助于維持種群的多樣性。若適應(yīng)值高于種群平均適應(yīng)值，則自適應(yīng)減少變異概率，以免破壞優(yōu)秀個體。

式中，F(xiàn)mutate為變異個體的適應(yīng)值；Pm1、Pm2為預(yù)先設(shè)定的0到1之間的固定值。變異階段生成一個0到1之間的隨機數(shù)r，若r＜Pm，執(zhí)行變異操作；否則不執(zhí)行。執(zhí)行變異操作時，生成一個0到1之間的隨機數(shù)k，若k＜0.5，采用交換變異；否則采用旋轉(zhuǎn)變異。

3.2.5 模擬退火

遺傳算法容易陷入局部最優(yōu)解，本文將遺傳算法與模擬退火算法相結(jié)合，以增強算法的局部搜索能力。對遺傳操作后的所有個體以狀態(tài)產(chǎn)生函數(shù)生成新個體，按預(yù)定的接受概率替換舊個體，最終得到的N個個體構(gòu)成下一代種群。理論上只要初始溫度足夠高，退火過程足夠慢，算法就能收斂到全局最優(yōu)。

（1）設(shè)置初始溫度：初始溫度T0應(yīng)足夠高，以滿足新個體接受概率為1的初始要求，即Tk=T0時，有，需，顯然無法實現(xiàn)。實際應(yīng)用中，只需保證設(shè)置的T0使得新個體接受概率趨近于1即可。

（2）狀態(tài)產(chǎn)生函數(shù)：在個體Xi中隨機選擇兩個不同的基因位k、m，對k、m之間（包括k、m）的基因進行逆序操作。假設(shè)Xi={4,-3,1,5,-2,6},k=2,m=5,則通過狀態(tài)產(chǎn)生函數(shù)生成新個體Xi'={4,-2,5,1,-3,6}。

（3）新個體接受概率：計算新個體Xi'的適應(yīng)值F(Xi')，若新個體更優(yōu)，即 F(Xi')≥F(Xi)，則用 Xi'替換Xi；若F(Xi')＜F(Xi),依照如下接受概率用Xi'替換Xi：

（4）降溫函數(shù)：采用等比降溫函數(shù)Tk+1=αTk，其中α為降溫系數(shù)，且α∈(0,1)。α的取值與初始溫度T0有關(guān)，若取值過大會導(dǎo)致收斂過慢，若取值過小會導(dǎo)致降溫過快而無法求得最優(yōu)解。因此在設(shè)定α的取值時，需綜合考慮算法求解效果和收斂速度。

4 實驗分析

取文獻[12]提供的一組實驗數(shù)據(jù)進行對比測試。算例中包含20種不同尺寸的矩形件，共59個，板材寬度為400。本文的自適應(yīng)遺傳模擬退火算法初始參數(shù)設(shè)置如表1所示。

本文與文獻[12]和文獻[8]的優(yōu)化結(jié)果對比如表2所示。其中文獻[12]和文獻[8]分別采用結(jié)合最低水平線的經(jīng)典遺傳算法和基于分階段遺傳算子的改進遺傳算法進行排樣優(yōu)化。算法運行50次，得到的平均利用率為表中的平均值，最高利用率為最佳值。本文平均值和最佳值均高于文獻[12]和文獻[8]。

表2 算法的利用率對比 %

圖2為本文算法進化500代時的最佳排樣圖，其適應(yīng)值為95.21%，高度為336。

圖2 算法進化500代時的最佳排樣圖

為進一步驗證本文算法求解問題的有效性，采用文獻[13]提供的21個算例，每個算例由一張已知規(guī)格（寬為W，高為Hopt）的板材分割為若干矩形件（無廢料）生成。依據(jù)板材規(guī)格將算例分為7組，分別用C1～C7表示，每組由3個不同算例組成，如表3所示。由分割方式可知板材高度Hopt為最優(yōu)排樣高度，算例要求將n個矩形件排入寬度為W高度不限的板材中，計算最小排樣高度H*。算例具體數(shù)據(jù)參閱文獻[13]。

表3 算例數(shù)據(jù)

定義最小排樣高度H*到最優(yōu)排樣高度Hopt的相對距離g=(H*-Hopt)/Hopt作為評價標準，若g越小，表明計算得到的H*越接近Hopt，算法的優(yōu)化效果越好。本文對每個算例計算30次，取最好結(jié)果，每組算例的平均相對距離gaverage如表4所示，平均計算時間haverage如表5所示。

由表4可知，本文算法的gaverage比文獻[13]算法1降低2.55%,比算法2降低1.98%，比文獻[14]降低1.95%，比文獻[15]降低1.05%，整體優(yōu)化效果最好。由表5可知，本文算法的haverage與文獻[13]和文獻[15]相比大幅降低，與文獻[14]相比雖然耗時增加，但相差不大。在求解中小規(guī)模矩形件排樣問題時，本文算法能快速得到最優(yōu)解，求解大規(guī)模問題時能在合理時間內(nèi)得到較好的優(yōu)化結(jié)果。

表4 每組算例的平均相對距離 %

表5 每組算例的平均計算時間 s

5 結(jié)束語

本文運用自適應(yīng)遺傳模擬退火算法求解矩形件排樣問題，通過精英選擇與輪盤賭相結(jié)合的策略對父代種群進行選擇，自適應(yīng)調(diào)整交叉概率和變異概率，將具有較快全局搜索能力的遺傳算法和較強局部搜索能力的模擬退火算法相結(jié)合，提高算法收斂至全局最優(yōu)的速度。采用啟發(fā)式最低水平線擇優(yōu)算法布局矩形件，從而有效利用板材中的空洞。實驗結(jié)果表明算法求解速度較快，可以有效提高板材利用率。