基于層次聚類模型的矩形優(yōu)化排樣問(wèn)題研究

王竹婷 鄒樂(lè)

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

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

目前較常用于求解排樣問(wè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ù)多，時(shí)間復(fù)雜度較高，在求解大規(guī)模排樣問(wèn)題時(shí)的時(shí)間效率偏低。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

［3］王珊珊.混沌離散微粒群算法在矩形排樣中的應(yīng)用［J］.計(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］賈志欣，殷國(guó)富，羅陽(yáng)，等.矩形件排樣的模擬退火算法求解［J］.四川大學(xué)學(xué)報(bào):工程科學(xué)版，2005，37(4):134－138.

［7］周兵，王和興，王翠榮.一種基于GiST的層次聚類算法［J］. 計(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.