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

2021-07-27 09:59:46劉誠孫遠升花軍姚嘉明

林業工程學報 2021年4期

劉誠，孫遠升，花軍，姚嘉明

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

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

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

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

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

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

1.1 2RBPRG的求解目標

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

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

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

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

1.2 有序種群初始方式

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

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

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

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

1.3 編碼方式

本研究在個體序列與工件初始序列之間建立映射，以工件初始序列作為個體序列中工件位置參考，從個體序列中首個工件開始，記錄其在工件初始序列中位置作為基因首個編碼，然后將其在工件初始序列中刪除，以此往復編碼，組成有序集{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中的當前序列號作為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，往復進行編碼。

圖1 基因編碼映射示意圖

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

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

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

1.4.1 排樣擇優的貪心策略

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

為便于“一刀切”約束檢測，將全部板材尺寸增大2個刀路寬度DL，建立排樣運算矩陣W及矩陣坐標系，以W右下角為原點，向上為X正向，向左為Y正向，W中每個元素fw(x，y)=wxy代表一個板材最小單元，以W內元素行、列數表示原料X向尺寸r+ 2DL、Y向尺寸c+ 2DL，如圖2a所示。通過W的局部矩陣U描述工件，以U內元素行、列數表示工件X向尺寸ru+2DL，Y向尺寸cu+2DL，如圖2b所示。通過改變U內元素fw(xu+x，yu+y)數值，記錄工件信息，如圖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。排樣擇優的貪心策略如下：

圖2 初始矩陣及局部矩陣

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

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

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

圖3 在W上搜索U

1.4.2 后檢測策略

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

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

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

圖4 后檢測中的矩陣分割

1.5 適應度函數

以排樣利用率作為適應度，函數為：

f(O)=Sw/Sm

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

2 遺傳算法求解過程

2.1 初始種群

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

2.2 遺傳算子

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

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

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

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

2.3 終止準則

重復執行第2.2節，直至滿足預定的迭代次數或最優解的適應度達到要求(最優適應度3次迭代不發生改變)，終止計算。

3 試驗計算

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

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

分別采用Hopper等[12]所采用的GA+BLF算法和SA+BLF算法、Zhang等[13]的FH算法、Leung 等[14]的PH算法和趙新芳等[11]的改進遺傳算法以及本研究所采用的算法，計算每組算例。定義算法最優解H*到準確最優解H的絕對差值G=(H*-H) /H作為評價準則，每類算例的平均差值G平均=(G1+G1+G1) / 3。本研究算法選取種群規模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，高度不限的矩形原料板上排樣，具體數據參閱文獻。該測試算例同樣不考慮刀路損耗及“一刀切”約束。分別采用龔志輝等[15]的算法、趙新芳等[11]的改進遺傳算法、許華杰等[16]的AAGA算法，以及本研究算法計算該組算例。本研究算法選取種群規模m=50，變異概率Pvariation=0.1，各算法在不同迭代次數下排樣利用率情況如表3所示。

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

表3 不同迭代次數下最優利用率對比

圖5 迭代40次的最優排樣圖

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

表4 3種算法的最優利用率對比

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

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