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

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

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

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

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

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

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

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

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

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

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

3)滿足“一刀切”要求，即每次對(duì)Y切割時(shí)均可以將其分為兩個(gè)獨(dú)立矩形板材。

1.2 有序種群初始方式

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

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

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

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

1.3 編碼方式

本研究在個(gè)體序列與工件初始序列之間建立映射，以工件初始序列作為個(gè)體序列中工件位置參考，從個(gè)體序列中首個(gè)工件開始，記錄其在工件初始序列中位置作為基因首個(gè)編碼，然后將其在工件初始序列中刪除，以此往復(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)個(gè)體序列為(Q′i)′= {P(i-1)×v+1，P(i-1)×v +2，…，P(i-1)×v+v}；

3)編碼至p(i-1)×v+ j時(shí)，在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)前序列號(hào)作為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中刪除，其后序列號(hào)全部減1，由P(i-1)×v+2=i×v+k，得到p(i-1)×v+2=k-1，往復(fù)進(jìn)行編碼。

圖1 基因編碼映射示意圖

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

1.4 基于貪心算法的后檢測(cè)排樣

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

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

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

為便于“一刀切”約束檢測(cè)，將全部板材尺寸增大2個(gè)刀路寬度DL，建立排樣運(yùn)算矩陣W及矩陣坐標(biāo)系，以W右下角為原點(diǎn)，向上為X正向，向左為Y正向，W中每個(gè)元素fw(x，y)=wxy代表一個(gè)板材最小單元，以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原點(diǎn)開始，沿X正向搜索零矩陣U，以其右下角坐標(biāo)(xu，yu)為搜索位置，當(dāng)xu+ru

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

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

圖3 在W上搜索U

1.4.2 后檢測(cè)策略

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

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

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

圖4 后檢測(cè)中的矩陣分割

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個(gè)工件，采用前述種群初始方式生成m個(gè)個(gè)體，將其編碼為基因，用排樣算法計(jì)算其最優(yōu)排樣，用適應(yīng)度函數(shù)計(jì)算其適應(yīng)度。

2.2 遺傳算子

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

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

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

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

2.3 終止準(zhǔn)則

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

3 試驗(yàn)計(jì)算

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

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

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

表1 每組例題的平均相對(duì)距離

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

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

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

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

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

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

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

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

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

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

圖6 3種算法的排樣圖

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

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

4 結(jié) 論

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

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

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

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

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

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