王竹婷 鄒樂

(合肥學(xué)院計算機(jī)科學(xué)與技術(shù)系，合肥 230601)

矩形優(yōu)化排樣問題是國內(nèi)外制造業(yè)領(lǐng)域研究的熱點(diǎn)問題之一。在這些行業(yè)的原材料切割工藝中使用優(yōu)化后的排樣方案，可以極大地降低成本，提高企業(yè)的經(jīng)濟(jì)效益。但該問題目前已被證明為一類NP完全問題，即隨問題規(guī)模擴(kuò)大，此類問題的計算復(fù)雜度呈指數(shù)級增長。如何在合理的時間范圍內(nèi)計算出優(yōu)化的排樣方案成為該領(lǐng)域研究的重點(diǎn)。

目前較常用于求解排樣問題的算法主要有遺傳算法［1］(Genetic Algorithm，GA)、模擬退火算法［2］(Simulated Annealing Algorithm，SA)、微粒群算法［3］(Particle Swarm Algorithm，PSA)等通用型的智能優(yōu)化算法，將這些算法與最下最左算法［4］(Bottom－Left，BL)，基于 BL 的填充算法［5］(Bottom － Left Filling，BLF)、最低水平線法［6］(lowest horizontal line，LHL)等作為解碼方法相結(jié)合使用，可以得到較好的排樣結(jié)果。但智能算法迭代次數(shù)多，時間復(fù)雜度較高，在求解大規(guī)模排樣問題時的時間效率偏低。

為降低排樣算法的時間復(fù)雜度，本文將凝聚的層次聚類模型［7］引入排樣問題中，并給出兩矩形件之間結(jié)合度的概念，按層次聚類的思想，將結(jié)合度較高的矩形件合并成矩形簇，最終將所有矩形件合并到一個簇中，排樣結(jié)束。最后設(shè)計算法程序，引用標(biāo)準(zhǔn)數(shù)據(jù)集測試算法性能，測試結(jié)果表明本文所提出算法可有效求解大規(guī)模排樣問題。

1 矩形優(yōu)化排樣問題描述

矩形件優(yōu)化排樣問題，就是在一張或幾張給定長度和寬度的矩形板材上切割指定規(guī)格和數(shù)量的矩形零件，要求所消耗的原材料最少。為方便描述此類問題，本文只討論原材料為單一板材的情況。設(shè)矩形板材的寬度為W，W是排樣前就確定的原材料的最大寬度，高度為H。假設(shè)H的值可無限增大，待切割零件總數(shù)為n，第i個零件為Ri，Ri的長為li，寬為wi。將所有矩形零件排入板材內(nèi)，注意零件和零件之間不允許重疊，排樣過程結(jié)束后板材在高度方向上使用的越少，排樣效果越好，公式(1)為該問題的目標(biāo)函數(shù)。

其中:Hmax為整個排樣過程結(jié)束后所消耗的板材最大高度;f(x)為板材的利用率;f(x)的值越大排樣效果越好。

2 層次聚類模型在矩形排樣中的應(yīng)用

2.1 凝聚的層次聚類算法思想

聚類算法是數(shù)據(jù)挖掘領(lǐng)域中的一項(xiàng)關(guān)鍵技術(shù)，可根據(jù)數(shù)據(jù)的特征屬性，將具有相似特征的數(shù)據(jù)劃分到同一個類別或簇內(nèi)。聚類算法可以分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。根據(jù)矩形排樣問題的特殊性要求，本文重點(diǎn)研究凝聚的層次聚類算法。

凝聚的層次聚類算法是一種自底向上的聚類策略。初始時，每一個對象為一個簇，每一個簇處于最底層;然后再計算每一對簇之間的相似度，選擇相似度最高的兩個簇，兩兩合并，這樣便形成了新的一層;反復(fù)執(zhí)行上述步驟，直到所有的對象合并成一個簇或滿足終止條件，算法結(jié)束。

2.2 矩形件聚類算法相關(guān)概念

在矩形排樣中，需要獲得較高的利用率。排放位置相鄰的兩個零件在長度或?qū)挾壬显浇咏?，那么，將這兩個零件排放在一起造成的板材浪費(fèi)面積越少?；谶@一特征，本文給出了針對矩形排樣問題的結(jié)合度和聚類的相關(guān)定義。

兩矩形件之間的結(jié)合度:兩個待排矩形件合并成一個新矩形后，在這個新矩形內(nèi)部產(chǎn)生的利用率稱之為結(jié)合度。

兩矩形件之間的結(jié)合度最高為1，最低為0。結(jié)合度為1時，即兩矩形件的在長度或?qū)挾确较蛏贤耆嗤?，合并成一個矩形件后沒有造成浪費(fèi);結(jié)合度為0時，則表示某矩形件與其自身結(jié)合。結(jié)合度越高，兩矩形合并后產(chǎn)生的浪費(fèi)面積越少，結(jié)合度越低，則浪費(fèi)越多。此時，兩矩形件不宜排放在一起。

矩形件聚類:兩個或多個矩形件，在板材中按相鄰位置進(jìn)行無重疊的排放，形成一個面積更大的矩形件，本文將這一排樣過程稱之為聚類。聚類過程中注意，合并后形成的新矩形的長度和寬度不得超過板材的最大寬度W。

矩形簇:兩個或多個矩形件聚類后形成的面積更大的矩形稱為矩形簇。

按矩形件排放位置的不同，結(jié)合度較高的兩個矩形件聚類分為4種方式:矩形件i和矩形件j，其中i不等于j，將矩形件i的長邊與矩形件j的長邊相鄰接;矩形件i的長邊與矩形件j的寬邊相鄰接;矩形件i的寬邊與矩形件j的寬邊相鄰接;矩形件i的寬邊與矩形件j的長邊相鄰接。按照這4種方式排放在一起的兩個矩形件，又可形成一個新的矩形件，分別計算四種方式下形成的矩形簇的面積，選擇面積最小的結(jié)合方式，作為最終聚類的方案。

2.3 層次聚類算法在矩形排樣中的應(yīng)用

在數(shù)據(jù)挖掘領(lǐng)域中執(zhí)行聚類算法，需要根據(jù)數(shù)據(jù)的特征屬性計算不同數(shù)據(jù)之間的相似度，再通過聚類算法將相似度高的數(shù)據(jù)劃分到同一個類別中［8］。本文所處理的問題，也是通過聚類算法將不同規(guī)格的矩形件排放到一個合理的矩形簇中，也需要提取矩形件的相關(guān)特征屬性，計算結(jié)合度，將結(jié)合度較高的矩形件合并到同一個矩形簇中。在聚類算法執(zhí)行前，首先構(gòu)建2種數(shù)據(jù)結(jié)構(gòu):矩形件特征矩陣和結(jié)合度矩陣。

(1)構(gòu)建矩形件特征矩陣。對于有n個待排矩形件的排樣問題，可構(gòu)建一個n行5列的特征矩陣X，其中n行表示n個矩形件的特征向量，5列表示每一個矩形件的5個特征屬性。如公式(2)所示，xi1表示編號為i的矩形件的長度;xi2表示該矩形件的寬度;xi3表示該矩形件或合并后形成的矩形簇的有效面積，如果一個矩形簇是由a、b兩原子簇合并而成的，則xi3的具體數(shù)值為a、b兩矩形件的面積之和;xi4表示形成的矩形簇的實(shí)際面積;xi5表示矩形簇內(nèi)部的實(shí)際利用率，即xi3與xi4的比值。

(2)構(gòu)建結(jié)合度矩陣。該矩陣用來存儲n個矩形件兩兩之間的結(jié)合度，這是一個n行n列的矩陣，矩陣中cij=cji，都表示矩形件i和矩形件j之間的結(jié)合度，其中cii=0，該矩陣也可以寫成上三角或下三角的形式，如公式(3)所示。

(3)層次聚類算法的具體執(zhí)行流程:

步驟一，相關(guān)數(shù)據(jù)初始化:對于有n個矩形件的排樣問題，首先對n個矩形件進(jìn)行1到n的編號，初始化矩形件集合{R1，R2，…，Rn};生成特征矩陣，記錄每個矩形件的長、寬、有效面積、實(shí)際面積、利用率。初始時，每個矩形簇為原子矩形件，因此有效面積與實(shí)際面積相等，利用率為1，即100%;同時，構(gòu)建結(jié)合度矩陣;

步驟二，從結(jié)合度矩陣中選擇相似度高的矩形件兩兩合并。比如，要找與矩形件i結(jié)合度最高的矩形，可以搜索結(jié)合度矩陣的第i行中所有數(shù)值{ci1，ci2，…，cin}，如果 cij最高，則將矩形件 i和矩形件j合并，將矩形件集合中Ri和Rj刪除，并加入合并后的矩形簇，最后將結(jié)合度矩陣中與i和j相關(guān)的所有結(jié)合度修正為0;一輪聚類過程結(jié)束后，n個矩形件合并成n/2個矩形簇，令n=n/2，并對各矩形簇重新編號;

步驟三，根據(jù)新形成的矩形件集合，重新構(gòu)建特征矩陣和結(jié)合度矩陣;

步驟四，重復(fù)執(zhí)行步驟二、三，直至n變?yōu)?，算法結(jié)束。

3 仿真實(shí)驗(yàn)

筆者用C++編寫了求解矩形排樣問題的層次聚類算法，利用文獻(xiàn)［9］提供的標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行測試。文獻(xiàn)［9］按照板材的規(guī)格和矩形件的數(shù)量不同將數(shù)據(jù)集分成7組，每組3個算例，如表1所示，每個算例都有最優(yōu)解。表1中，第2行為每組算例中矩形件的個數(shù)，第3行為每組算例中板材的寬度，第4行則為最優(yōu)解所對應(yīng)的板材高度，即當(dāng)利用率為100%時所消耗的板材高度。

為驗(yàn)證層次聚類算法求解矩形排樣問題的有效性，編寫了遺傳算法(GA)程序，并采用最低水平線搜索算法(LHLS)作為解碼方法，將其跟本文所提出的算法共同進(jìn)行仿真實(shí)驗(yàn)，對比實(shí)驗(yàn)結(jié)果，從排樣效果和時間效率上驗(yàn)證本文所提算法的有效性。測試結(jié)果記錄如表2所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

表2 GA+LHLS和本文算法的測試結(jié)果

表2中，第4列和第5列分別為GA+LHLS算法和本文算法執(zhí)行完成后所使用的板材高度，與第3列中所列出的最優(yōu)解板材高度對比，與最優(yōu)解越接近，排樣效果越好;第6列和第7列分別為GA+LHLS算法和本文算法計算每組算例所消耗的平均時間，消耗的時間越短，說明算法的時間復(fù)雜度越低。因此，表2中的測試結(jié)果證明，本文算法在排樣效果和時間效率上均優(yōu)于GA+LHLS算法，尤其在時間效率表現(xiàn)較為突出。

4 結(jié)語

本文提出了一種全新的矩形排樣算法，引入了凝聚的層次聚類算法思想，定義了矩形件結(jié)合度的概念;自底向上執(zhí)行聚類算法，將結(jié)合度高的矩形件兩兩合并成一個矩形簇，最終將所有矩形件合并到一個簇中;設(shè)計算法程序，運(yùn)用相同的數(shù)據(jù)集測試本文提出的算法與遺傳算法的性能，測試結(jié)果表明本文算法可以得到較好的排樣結(jié)果，并且時間效率尤為突出，適合于求解大規(guī)模排樣問題。

［1］蔣興波，呂肖慶，劉成城.一種用于矩形排樣優(yōu)化的改進(jìn)遺傳算法［J］.計算機(jī)工程與應(yīng)用，2008(22):244－248.

［2］蔣興波，呂肖慶，劉成城.求解矩形件優(yōu)化排樣的自適應(yīng)模擬退火遺傳算法［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2008(11):1425－1431.

［3］王珊珊.混沌離散微粒群算法在矩形排樣中的應(yīng)用［J］.計算機(jī)工程，2010，(23):174－176.

［4］L iu D，Teng H.An Improved BL Algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles［J］.European Journal of Operational Research，1999，112:413 －420.

［5］Andrea Lodi.Two Dimensional Packing problems:A Survey［J］.European Journal of Operational Research，2002，141:241－252.

［6］賈志欣，殷國富，羅陽，等.矩形件排樣的模擬退火算法求解［J］.四川大學(xué)學(xué)報:工程科學(xué)版，2005，37(4):134－138.

［7］周兵，王和興，王翠榮.一種基于GiST的層次聚類算法［J］. 計算機(jī)工程，2008，34(9):58－60.

［8］Fayyad U，Piatesky S G，Smyth P.The KDD Process for Extracting Useful Kowledge form Volumes of Data［J］.Communication of the ACM，1996，39(11):27 －35.

［9］Hopper E，Turton B C H.An Empirical Investigation of Meta－h(huán)euristic and Heuristic Algorithms for a 2D Packing Problem［J］.European Journal of Operational Research，2001，128(1):34 －57.