夏以沖，陳秋蓮，宋仁坤

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

1 引言

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

3.1 算法流程

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

3.2 算法描述

3.2.1 編碼

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

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

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

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

3.2.3 計(jì)算適應(yīng)值

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

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

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

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

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

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

3.2.4 遺傳算子

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

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

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

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

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

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

3.2.5 模擬退火

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

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

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

（3）新個(gè)體接受概率：計(jì)算新個(gè)體Xi'的適應(yīng)值F(Xi')，若新個(gè)體更優(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)，若取值過大會(huì)導(dǎo)致收斂過慢，若取值過小會(huì)導(dǎo)致降溫過快而無(wú)法求得最優(yōu)解。因此在設(shè)定α的取值時(shí)，需綜合考慮算法求解效果和收斂速度。

4 實(shí)驗(yàn)分析

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

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

表2 算法的利用率對(duì)比 %

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

圖2 算法進(jìn)化500代時(shí)的最佳排樣圖

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

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

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

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

表4 每組算例的平均相對(duì)距離 %

表5 每組算例的平均計(jì)算時(shí)間 s

5 結(jié)束語(yǔ)

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