基于遺傳-貪心混合搜索的人造板下料算法

劉誠，孫遠(yuǎn)升，花軍，姚嘉明

(東北林業(yè)大學(xué)機電工程學(xué)院，哈爾濱 150040)

定制家具發(fā)展快速，數(shù)字化制造成了家具企業(yè)發(fā)展核心競爭力所在，如何利用數(shù)字化信息技術(shù)提供高效率、低成本的定制化產(chǎn)品已成為其面臨的主要問題[1]，因此探討人造板數(shù)字化智能下料具有重要意義。人造板下料問題為可旋轉(zhuǎn)和滿足“一刀切”的二維矩形板排樣(two-dimensional rectangular bin packing of rotate and guillotine，簡稱2RBPRG)，即在工件可90°旋轉(zhuǎn)，且排樣滿足“一刀切”條件下獲得最優(yōu)下料方案，該問題變量較多，包括每個工件的下料順序、尺寸、位置及擺放方向，極具復(fù)雜性，屬于多項式復(fù)雜種樹度的非確定性(non-deterministic polynomial，NP)完全問題，目前僅能通過窮舉法精確求解，當(dāng)問題規(guī)模倍數(shù)擴大時計算機也無法計算。對此大量學(xué)者采取啟發(fā)式算法近似求解，常見算法為二叉樹排樣[2-5]、分塊填充排樣[6-7]和二階段排樣[8-9]等。其中樹形搜索與分塊填充排樣算法時間復(fù)雜度接近O(nlgn)，速度較快，但其采取先“一刀切”劃分后排樣策略可能增大余料碎化程度，降低排樣利用率，對此，通過對排樣空位進行整合[4]，以及通過選擇最佳排樣分解方式[5]，在一定程度上降低余料碎化，提高利用率。二階段排樣算法則簡化排樣問題，采用“條帶排樣”策略，如通過在原料板上逐次剪切下矩形帶后在其上排樣[9]，工件規(guī)格不整齊程度較大時，余料碎化較為嚴(yán)重。

智能算法也大量應(yīng)用在矩形排樣問題求解中，其中遺傳算法應(yīng)用最為廣泛，如Aurelio、趙新芳等[10-11]均在無“一刀切”約束的矩形排樣中使用遺傳算法，獲得較高排樣利用率，但這類算法求解具有隨機性，收斂速度及求解效果較為依賴遺傳策略的選擇。

針對上述算法存在問題，筆者采取對排樣擇優(yōu)后進行“一刀切”檢測的排樣策略，降低余料碎化程度，通過改進遺傳算法進行全局搜索，之后利用貪心算法對其進行二次優(yōu)化，使解的質(zhì)量接近全局最優(yōu)，提高排樣利用率，為人造板優(yōu)選下料提供一種新的解決方案。

1 遺傳-貪心混合算法描述分析

遺傳算法是高度隨機、自適應(yīng)的全局搜索算法，其按評估策略評價每個個體，通過選擇、交叉、變異將種群迭代進化，最終收斂到最適應(yīng)群體求得最優(yōu)解，但易過早陷入局部最優(yōu)而早熟，對此采取貪心策略構(gòu)建適應(yīng)度函數(shù)，對個體解進一步尋優(yōu)，即出現(xiàn)早熟后，仍可通過貪心搜索再次提高解的質(zhì)量，從而提高遺傳算法全局尋優(yōu)能力。筆者基于遺傳算法及貪心算法的原理和方法，研究2RBPRG的求解過程，在種群初始化、編碼和貪心策略3個方面進行改進。

1.1 2RBPRG的求解目標(biāo)

將一組矩形工件{P1，P2，…，Pn}，排樣在給定寬度、高度不限的原料板Y上，其中Pi為第i塊工件，n為工件個數(shù)，求解目標(biāo)為使Y使用高度h最小，即Y利用率最大，并且滿足：

1)Pi不超出Y邊界，1≤i≤n；

2)Pi、Pj互不重疊，1≤i，j≤n；

3)滿足“一刀切”要求，即每次對Y切割時均可以將其分為兩個獨立矩形板材。

1.2 有序種群初始方式

趙新芳等[11]通過對全部矩形工件編號，隨后根據(jù)面積降序排列，面積相等時根據(jù)最大邊長降序排列，工件編號排列構(gòu)成有序集{P1，P2，…，Pn}，1≤Pi≤n，對每個Pi賦予正負(fù)號，分別表示工件橫放與豎放，以此表示個體，重復(fù)m次隨機賦予正負(fù)號后得到初始種群。上述有序種群初始方式中，每個體工件排樣順序相同，僅擺放方式改變，解的搜索空間較小，不利于得到高質(zhì)量個體，但其根據(jù)面積降序排列方法生成工件初始序列，可顯著提高排樣空位的有效利用，因此對其進行改進優(yōu)化。

首先由面積降序排列方法將工件排序為初始序列，對工件按順序編號，工件編號構(gòu)成有序集{P1，P2，…，Pn}，1≤Pi≤Pi+1≤n，作為初始種群的個體；之后對該有序集中每個編號隨機調(diào)整位置，生成新序列，作為初始種群的個體，重復(fù)m-1次隨機調(diào)序，生成m-1個個體，共m個個體構(gòu)成初始種群。與文獻[11]相比，有序種群初始時不考慮工件擺放順序，在后續(xù)貪心搜索時加以考慮。

初始種群選取對遺傳算法收斂速度和求解效果影響甚大。對于2RBP|R|G初始種群選取存在2個問題：1)工件數(shù)量較多時解空間巨大，n個工件時解有n!種，盲目構(gòu)造初始種群，不易獲得高質(zhì)量個體；2)排樣過程復(fù)雜，僅以面積降序排列初始種群，會忽略形狀差異對排樣的影響，不易獲得滿意求解效果。

為解決上述問題本文隨機調(diào)序為局部調(diào)序。首先將工件初始序列局部分組，每組v個，工件組的排列構(gòu)成有序集{Q1，Q2，…，Qn′}，n′=n/v，Qi= {P(i-1)×v+1，P(i-1)×v +2，…，P(i-1)×v+v}，之后對Qi內(nèi)編號隨機調(diào)序。局部隨機調(diào)序優(yōu)點：在全局序列上保持面積降序排列特性，即優(yōu)先排樣大工件，小工件在后面排樣，大工件排樣時產(chǎn)生的空位較大，隨后小工件排樣可以更好進行空位填補，易獲得滿意的求解效果；同時可以縮小解空間規(guī)模，易獲得高質(zhì)量個體。

1.3 編碼方式

本研究在個體序列與工件初始序列之間建立映射，以工件初始序列作為個體序列中工件位置參考，從個體序列中首個工件開始，記錄其在工件初始序列中位置作為基因首個編碼，然后將其在工件初始序列中刪除，以此往復(fù)編碼，組成有序集{q1，q2，…，q′n}，表示基因，n′=n/v，qi= {p(i-1)×v+1，p(i-1)×v+2，…，p(i-1)×v+v}，p(i-1)×v+j表示基因位置，編碼如下：

1)工件初始序列為{Q′1，Q′2，…，Q′n′}，n′=n/v，Q′i= {(i-1)×v+1，(i-1)×v+2，…，(i-1)×v+v}；

2)個體序列為(Q′i)′= {P(i-1)×v+1，P(i-1)×v +2，…，P(i-1)×v+v}；

3)編碼至p(i-1)×v+ j時，在Q′i中刪除{P(i-1)×v +1，P(i-1)×v+2，…，P(i-1)×v+j -1}的相同元素，之后將P(i-1)×v+j在Q′i中的當(dāng)前序列號作為p(i-1)×v+j，1≤p(i-1)×v+j≤v-j+1，1≤j≤v。如圖1所示，其中首先由P(i-1)×v +1=(i-1)×v+j，得到p(i-1)×v+1=j；之后將(i-1)×v+j在Q′i中刪除，其后序列號全部減1，由P(i-1)×v+2=i×v+k，得到p(i-1)×v+2=k-1，往復(fù)進行編碼。

圖1 基因編碼映射示意圖

基因編碼方式對交叉、變異有較大影響。本研究編碼的兩個基因在交叉時，相同序列號元素可任意交換生成新基因，變異時基因某個序列號元素可在域內(nèi)任意改變，均不會出現(xiàn)工件重復(fù)。

1.4 基于貪心算法的后檢測排樣

貪心算法總以當(dāng)前情況為基礎(chǔ)，根據(jù)優(yōu)化測度作最優(yōu)選擇，直至求得最優(yōu)解，不考慮整體情況，效率較高。筆者針對每個個體的工件序列，先利用貪心策略對排樣擇優(yōu)，優(yōu)化測度為排樣利用率，之后對其進行“一刀切”檢測，擴大局部解搜索空間，求出對應(yīng)最優(yōu)排樣方案，計算適應(yīng)度對其進行評價。

1.4.1 排樣擇優(yōu)的貪心策略

排樣擇優(yōu)通過操作矩陣實現(xiàn)，遵循“右下角占優(yōu)”原則，通過迭代求解，時間復(fù)雜度為O(n)。

為便于“一刀切”約束檢測，將全部板材尺寸增大2個刀路寬度DL，建立排樣運算矩陣W及矩陣坐標(biāo)系，以W右下角為原點，向上為X正向，向左為Y正向，W中每個元素fw(x，y)=wxy代表一個板材最小單元，以W內(nèi)元素行、列數(shù)表示原料X向尺寸r+ 2DL、Y向尺寸c+ 2DL，如圖2a所示。通過W的局部矩陣U描述工件，以U內(nèi)元素行、列數(shù)表示工件X向尺寸ru+2DL，Y向尺寸cu+2DL，如圖2b所示。通過改變U內(nèi)元素fw(xu+x，yu+y)數(shù)值，記錄工件信息，如圖2c所示。記錄工件尺寸為ru=7，cu=5，DL=1，僅改變其輪廓處元素：1)下邊界元素記錄尺寸ru，得fw(xu+DL，yu+DL+y)=ru，0≤y≤ru- 1；3)右邊界元素分別記錄本身與上邊界元素的X向距離，fw(xu+DL+x，yu+DL)=ru-x，1 ≤x≤ru-1；4)上邊界元素分別記錄本身與左邊界元素的Y向距離，fw(xu+DL+ru，yu+DL+y)=cu-y，1≤y≤cu-1。排樣擇優(yōu)的貪心策略如下：

圖2 初始矩陣及局部矩陣

Step 1：從W原點開始，沿X正向搜索零矩陣U，以其右下角坐標(biāo)(xu，yu)為搜索位置，當(dāng)xu+ru

Step 2：搜索到零矩陣U時，將工件記錄到U內(nèi)，檢測W內(nèi)排樣是否滿足“一刀切”，若不滿足則重新索搜；

Step 3：將工件旋轉(zhuǎn)90°，重新搜索后與旋轉(zhuǎn)前比較，取利用率高者，排樣下個工件，直至排樣完畢，如圖3所示，為10塊工件的簡單排樣。

圖3 在W上搜索U

1.4.2 后檢測策略

在W中以DL行或列零元素表示刀路占位，檢測排樣是否滿足“一刀切”，可通過遞歸檢測，時間復(fù)雜度為O(n)，具體如下：

Step 1：檢測矩陣(首次為W)是否被刀路占位貫穿，如果貫穿則按刀路占位對其分割，對分割后的兩個矩陣分別檢測，直至分割后的矩陣全部為最小矩陣，即矩陣不被刀路占位貫穿，且內(nèi)部存在非零元素；

Step 2：最小矩陣與已排樣工件數(shù)量相等時，排樣滿足“一刀切”約束，分割過程如圖4所示。

圖4 后檢測中的矩陣分割

1.5 適應(yīng)度函數(shù)

以排樣利用率作為適應(yīng)度，函數(shù)為：

f(O)=Sw/Sm

其中：Sw為工件總面積；Sm=r·max(yu+cu)，Sm為原料用于排樣的最小矩形面積，max(yu+cu)為工件排樣最大高度；適應(yīng)度值范圍為[0，1]。

2 遺傳算法求解過程

2.1 初始種群

給定n個工件，采用前述種群初始方式生成m個個體，將其編碼為基因，用排樣算法計算其最優(yōu)排樣，用適應(yīng)度函數(shù)計算其適應(yīng)度。

2.2 遺傳算子

1)選擇算子：采取比例選擇方式，每個個體被選擇概率與其適應(yīng)度成正相關(guān)，同時采取最優(yōu)保存策略，防止交叉、變異破壞種群中適應(yīng)度最高的個體。將父輩個體按適應(yīng)度進行降序排序{O1，O2，…，Om}，每個個體死亡率函數(shù)為F(Oi)=(i-1)/m，沒有死亡的父輩個體直接進化為下代個體，數(shù)量記為m′。

2)交叉算子：父輩種群中隨機選擇2個個體配對，進行多點交叉，生成1個新個體，重復(fù)次交叉至下代個體為m個。設(shè)隨機選擇的2個個體基因為Oi1={pi1，pi2，…，pin}和Oj1={pj1，pj2，…，pjn}，取基因Oi1序列奇數(shù)位，基因Oj1序列偶數(shù)位，生成新的基因{pi1，pj2，pi3，pj4，…，pi(j)n}。

3)變異算子：對于選擇和交叉生成的子代個體，根據(jù)最優(yōu)保存策略，除適應(yīng)度最高的父代個體外，其余個體均需變異。對個體基因內(nèi)每個pi×v+j進行變異，變異概率為Pvariation，變異后的pi×v+j在區(qū)間[1,v-j+1]內(nèi)隨機選擇。

本研究交叉算子和變異算子均在Qi內(nèi)獨立進行，求解大規(guī)模排樣問題時，解空間維持在(v！)n/v大小，運算效率高；多次迭代后大工件依舊在個體序列靠前位置，利于得到高質(zhì)量解。

2.3 終止準(zhǔn)則

重復(fù)執(zhí)行第2.2節(jié)，直至滿足預(yù)定的迭代次數(shù)或最優(yōu)解的適應(yīng)度達到要求(最優(yōu)適應(yīng)度3次迭代不發(fā)生改變)，終止計算。

3 試驗計算

本研究在CORE i7 2.40 GHz CPU，8GB內(nèi)存的PC機上進行下面的測試。

測試1：采用Hopper等[12]所采用的7類測試算例，每類分為3組矩形工件，排樣在定寬無限高的矩形原料中，計算占用的最小高度，具體數(shù)據(jù)參閱文獻[12]。該測試算例中沒有考慮刀路損耗及“一刀切”約束，本研究算法將不進行刀路檢測及刀路占位操作。

分別采用Hopper等[12]所采用的GA+BLF算法和SA+BLF算法、Zhang等[13]的FH算法、Leung 等[14]的PH算法和趙新芳等[11]的改進遺傳算法以及本研究所采用的算法，計算每組算例。定義算法最優(yōu)解H*到準(zhǔn)確最優(yōu)解H的絕對差值G=(H*-H) /H作為評價準(zhǔn)則，每類算例的平均差值G平均=(G1+G1+G1) / 3。本研究算法選取種群規(guī)模m=20，變異概率Pv=0.05，各算法計算G平均值如表1所示，平均計算時間T平均如表2所示。

表1 每組例題的平均相對距離

表2 每組例題的平均計算時間

從表1可以看出，本研究算法平均差值G平均為0.883%，比GA+BLF降低3.687%，比SA+BLF降低3.117%，比FH降低0.797%，比PH降低2.067%，比文獻[11]算法降低0.267%，說明本研究算法的解最接近H。由表2可以看出，本研究算法計算時間相對其他算法較少，說明本算法時間效率較高。

測試2：采用龔志輝等[15]的測試算例，其中給出20種矩形工件共59個，在寬度400 mm，高度不限的矩形原料板上排樣，具體數(shù)據(jù)參閱文獻。該測試算例同樣不考慮刀路損耗及“一刀切”約束。分別采用龔志輝等[15]的算法、趙新芳等[11]的改進遺傳算法、許華杰等[16]的AAGA算法，以及本研究算法計算該組算例。本研究算法選取種群規(guī)模m=50，變異概率Pvariation=0.1，各算法在不同迭代次數(shù)下排樣利用率情況如表3所示。

由表3可以看出：本研究算法與文獻[11]和[15]的算法比較，最優(yōu)利用率均提高了10%；與許華杰等[16]的算法相比最優(yōu)利用率十分接近且接近1，說明本研究算法具有較高的求解質(zhì)量。同時，本研究算法相對于以上3種算法收斂速度較快，迭代40次時便獲得最優(yōu)解，僅為文獻算法0.5倍，本研究算法的遺傳策略具有明顯優(yōu)勢。本研究算法迭代40次后排樣如圖5所示。

表3 不同迭代次數(shù)下最優(yōu)利用率對比

圖5 迭代40次的最優(yōu)排樣圖

測試3：采用王華昌等[17]的 “一刀切”排樣測試算例，其中給定26種矩形工件共49個，在1 850 mm×1 240 mm原料板上排樣，具體數(shù)據(jù)參閱文獻。該測試算例不考慮刀路損耗。分別采用王華昌等[17]的模擬退火算法、陳仕軍等[18]的混合算法及本研究算法計算該組算例。本研究算法選取種群規(guī)模m=20，變異概率Pvariation= 0.05。各算法排樣利用率如表4所示。

表4 3種算法的最優(yōu)利用率對比

由表4可以看出，本研究算法與文獻[17]和[18]的算法比較，最優(yōu)利用率均有所提高，說明本研究算法在“一刀切”的約束下具有較高的求解質(zhì)量。

測試4：采用Vassiliadis[2]和彭碧濤等[3]算法分別對7種工件進行“一刀切”下料，其原料上高度為200，寬度不限，刀路寬度為2，并給出最優(yōu)排樣如圖6a、b所示，具體數(shù)據(jù)參閱文獻。本研究算法選取種群規(guī)模m=20，變異概率Pvariation= 0.05，排樣如圖6c所示。表5給出3種算法的使用尺寸、最優(yōu)利用率、余料數(shù)量。

圖6 3種算法的排樣圖

表5 3種算法的排樣結(jié)果對比

由表5可以看出，本研究算法余料數(shù)量相比文獻[2]減少72.7%，相比文獻[4]減少30.8%，說明本算法在降低余料碎化具有一定效果。同時，本研究算法最優(yōu)利用率相比文獻[2]提高4.5%，相比文獻[4]提高1.3%，說明本算法在考慮“一刀切”約束及刀路損耗下具有較高的求解質(zhì)量。

4 結(jié) 論

對于人造板下料問題，筆者提出基于遺傳-貪心混合算法的板材排樣策略，在初始種群選取、基因編碼及貪心策略三方面予以改進，降低了問題解空間范圍，進而提高了算法效率。在貪心排樣時采取先排樣擇優(yōu)、后對其“一刀切”檢測的策略，擴大了局部解搜索空間，進而提高了算法求解質(zhì)量。實驗計算表明：

1)在測試1中，本研究的算法在無“一刀切”約束排樣中，相比文獻算法得到較高的時間效率及求解質(zhì)量；

2)在測試2中，本研究算法在迭代求解時具有較快收斂速度，相比文獻算法通過少量迭代便獲得滿意解；

3)在測試3中，本研究算法在有“一刀切”約束排樣中，相比文獻算法可以獲得較高的最優(yōu)利用率；

4)在測試4中，本研究算法在有“一刀切”約束排樣中明顯降低余料碎化，使原料利用率進一步提升。

由以上結(jié)論可見，本研究中的人造板下料算法在定制板式家具生產(chǎn)中具有一定應(yīng)用價值。