曾 敏，王 乘，劉瓊梅

（1. 華中科技大學(xué) 水電與數(shù)字化工程仿真中心，武漢 430074；2. 湖南工業(yè)大學(xué) 計算機與通訊學(xué)院，株洲 412000）

大規(guī)模定制板材排樣的多種群蟻群優(yōu)化算法

曾 敏1,2，王 乘1，劉瓊梅2

（1. 華中科技大學(xué) 水電與數(shù)字化工程仿真中心，武漢 430074；2. 湖南工業(yè)大學(xué) 計算機與通訊學(xué)院，株洲 412000）

為解決定制家具企業(yè)的大規(guī)模多品種小批量的矩形件排樣問題，針對其一刀切的特殊生產(chǎn)工藝要求，通過對待切板自動生成兩個不同的編號：橫切編號和縱切編號的方法，采用面積，長度，寬度來啟發(fā)的多種群蟻群算法，避免了單因素啟發(fā)的不合理布局，做到了“生成即可行”，經(jīng)多個企業(yè)的實際使用后，發(fā)現(xiàn)與單因素蟻群啟發(fā)相比，多種群算法尋優(yōu)能力強，主要表現(xiàn)為：最大利用率最高；多次尋優(yōu)的最大利用率變化區(qū)間小。

優(yōu)化排料；大規(guī)模定制；一刀切；多種群蟻群優(yōu)化；優(yōu)化算法

0 引言

優(yōu)化排料，是一個在產(chǎn)品設(shè)計、制造和使用中如何節(jié)約原料、優(yōu)化利用資源的問題。其中矩形件排樣問題是優(yōu)化下料問題中最常見，也是最具實際意義的一類優(yōu)化排樣問題。通常以利用率最大或剩余料最少為目標(biāo)。常見的矩形件排樣問題因原料和切割方式的不同可分為以下幾種：1）卷料切割(Roll Material Cutting)；2）一刀切(Guillotine Cutting)；3）正交切割(Non-Guillotine Cutting)[1]。

板式家具優(yōu)化排樣是屬于“一刀切”方式的矩形件排樣問題，大規(guī)模多品種小批量的板材排料由于板材尺寸的多樣和小批量，一般各板的布局基本不同，對算法的實時性，實用性的要求更高，同時一刀切的生產(chǎn)工藝要求，一般布局算法難做到生成即可行。

1 矩形件排樣問題的特點和計算復(fù)雜性

按照計算復(fù)雜性理論研究問題求解的難易程度，可把問題分為P類、NP類、NP完全類和NP難問題。所以可以正確地求解NP-c完備問題的任何算法，在最壞情況下需要指數(shù)級時間，從而除規(guī)模很小的實例外，是不實用的[2]。

排樣問題已經(jīng)證明是一個NP-c完備問題。一維排樣可以建模為一個o-1背包問題，而0-1背包問題被證明是一個NP-c完備問題，而一維排樣問題可視為二維排樣問題的特例。所以，排樣優(yōu)化問題的目標(biāo)減弱為：在能接受的時間和空間約束下，逼近最優(yōu)解。也就是說為了在保證算法的計算時間和計算空間是可以接受的情況下，只有接受次優(yōu)解作為問題的結(jié)果[2]。

1.1 優(yōu)化算法和排樣優(yōu)化的發(fā)展

目前優(yōu)化算法的研究主要集中于指導(dǎo)性搜索方法和系統(tǒng)動態(tài)演化方法以及各種混合算法，研究熱點為以遺傳算法為代表的進化計算方法和蟻群算法為代表的群智能計算方法等[3]。

1.2 蟻群算法

蟻群算法是1992年由意大利學(xué)者 Dorigo M 等人首先提出的[4]，它是對螞蟻進行模擬而得出的一種模擬進化算法，該算法不依賴于具體問題的數(shù)學(xué)描述，有很強的全局優(yōu)化能力和本質(zhì)上的并行性，是解決NP-c完全問題的有效方法。2005年江南大學(xué)劉瑞杰、須文波給出了優(yōu)化排料蟻群算法[5]，但是此方法不滿足一刀切條件。2007年南昌大學(xué)李捷提出了一種新的排樣算法—最低水平線旋轉(zhuǎn)搜索法，并將這種算法和遺傳算法以及遺傳蟻群算法結(jié)合應(yīng)用于矩形件布局問題的求解[6]，但同樣不滿足一刀切的條件。

1.3 求解0-1背包問題的蚊群算法

我們可以將0-1背包問題解釋為一位旅行者在出發(fā)前必須決定攜帶哪些物品。記價值集合C＝{C1，C2，…，Cn}，物品集合X＝{1，2，…，n}，重量集合A＝{A1，A2，…，An}，這里的Ci表示攜帶第i個物品的“價值”或效益，其重Aj＞0 (kg)。要在攜帶各種物品的總重量不超過b千克的限制下；使旅途中所攜帶物品的總“價值”或總效益最大。其數(shù)學(xué)模型描述為

設(shè)系統(tǒng)中的螞蟻數(shù)目為m，各個螞蟻從第1個開始到第n個物品依此決定是否選擇該物品。在一次迭代后，每一個螞蟻代表一個解。第i個螞蟻代表的解可表示為{Xi1，Xi2，…，Xin}，其中，Xik標(biāo)志著當(dāng)前一次迭代中第i個螞蟻是否選中物品，選中值為l，否則為0。

2 一刀切板材排樣問題的蟻群優(yōu)化算法

我們可以把背包問題的物品理解為矩形件排樣問題的待切件，把背包問題的背包理解為矩形排樣問題的原料板，這樣矩形件排樣問題就轉(zhuǎn)化為背包問題，這樣方便構(gòu)造蟻群算法數(shù)學(xué)模型。

2.1 數(shù)學(xué)模型

設(shè)原料板材的長為L（一般為2440mm），寬為W（一般為1220mm），需要下K種零件，其中每一種零件需求數(shù)量分別為ni(1＜=i＜=k)，最終求得的優(yōu)化下料方案由N張單板優(yōu)化方案組成。在第j個單板方案上共安置Cj個零件，其中第i種零件有Ai個(1＜=i＜=K)，Ai＜=ni。

貪婪選擇是一種分治策略，即將大問題化為小問題，以最優(yōu)方式解決小問題后獲得大問題的解。貪婪策略每步解決的子問題數(shù)量為1個。所謂貪婪選擇屬性，就是用貪婪策略要想獲得最優(yōu)解，必須滿足下面兩個條件[8]：

1）每一個大問題的最優(yōu)解里面包刮下一級小問題的最優(yōu)解；

2）每一個小問題可由貪婪選擇獲得。

我們可以看出通過求Cj最大來求minN，不滿足上述條件（1）。所以我們要把問題轉(zhuǎn)換成便于處理的方式?！巴瑯哟笮〉脑习迳喜季指嗟拇邪濉焙汀笆乖习謇寐矢蟆钡刃?。

這樣就把求Cj最大轉(zhuǎn)換為求Sj最大。

2.2 一板兩號的編碼方式

因“一刀切(Guillotine Cutting)”方式的矩形件排樣問題，每一次切割的路徑都是貫通整個原料矩形的直線。這就是說，同一塊待切板，我們選擇它，還存在一個怎么下刀的問題，即是橫切還是縱切的問題。橫切和縱切，決定了余料板的尺寸，也就決定了后面能布局的待切板的尺寸。要解決一刀切問題，我們需作一些技術(shù)處理。

我們只要對待切板做兩個不同的編號——橫切編號和縱切編號，螞蟻選擇不同編號的板，就決定了后面的可以選擇的待切板。不同的是無論選擇了橫切編號還是縱切編號，對于對應(yīng)的縱切編號的板或橫切編號的板數(shù)量要同時減一。

例如板A＝577×2265，共兩塊，我們編號為N0H兩塊和N0Z兩塊。這樣即可做到“生成即可行”，不需在優(yōu)化后進行刀路可切性判斷。

2.3 排料二叉樹

用一個根結(jié)點表示布局空間的矩形區(qū)域，按定序規(guī)則從可選布局矩形中選擇一個相對于該矩形區(qū)域來說是最優(yōu)的布局矩形，并將其定位于該矩形區(qū)域的左上角。這樣原布局空間變成了一個J形區(qū)域，將這個J形區(qū)域分成圖1（a）所示2個矩形M和N，分別用根結(jié)點的左、右2個子結(jié)點表示。這樣，剩余的布局空間就變成了2個獨立的布局空間，分別對這兩個獨立的布局空間重復(fù)上述過程，直至沒有可選布局矩形滿足要求時停止分解。如圖1（a）所示，整個排料過程形成了一棵二叉樹，稱為排料二叉樹。該二叉樹的葉子節(jié)點代表的是無法繼續(xù)切分的區(qū)域，節(jié)點與某一確定的排料-切分方式相對應(yīng)。

2.4 面積，長度，寬度的多種群啟發(fā)

2.5 信息素更新

在蟻群算法中，蟻群算法中的信息素更新十分重要。對于大規(guī)模多品種小批量布局，通過我們的仿真實驗，局部信息素采用每次循環(huán)后更新，全局信息素采用只對最優(yōu)解更新的方式效果最好。參數(shù)設(shè)置如圖1(b)所示。

2.6 一刀切優(yōu)化算法

算法步驟：

1）讀入要下料的板材清單，并進行一板兩號編碼，如圖2所示；

圖1 排料二叉樹和群蚊群算法參數(shù)設(shè)置

2）設(shè)全局最優(yōu)解數(shù)組global-best=面積最大優(yōu)先生成的第一個可行解，設(shè)置啟發(fā)信息為面積啟發(fā)；

3）計算啟發(fā)素，計算初始信息素；

4）對每一螞蟻；

生成一個[0,1]之間的隨機數(shù)q=RAND()，

再次生成一個[0,1]之間的隨機數(shù)r=RAND()，

IF r＞=P，THEN Ant人工螞蟻選擇i的對應(yīng)板（含切割方向）。

局部信息素更新 t(i)＝(1-r)×t(i)+r×t0；

ELSE 不取。

所有螞蟻找到了二叉樹？否轉(zhuǎn)（4），是轉(zhuǎn)（5）

5）比較適應(yīng)度函數(shù)（容積率），求最優(yōu)螞蟻。將解存入當(dāng)前最優(yōu)解數(shù)組current-best；

6）IF f(current-best)＞f(global-best) 其 中f()為適應(yīng)度函數(shù)（容積率），THEN global-best=current-best 全局最優(yōu)解更新。

其中Dt(i)的值是最優(yōu)螞蟻所生成的二叉樹所對應(yīng)的原材料容積率；

7）IF連續(xù)全局最優(yōu)解無更新次數(shù)大于或等于規(guī)定值，或最大循環(huán)次數(shù)大于或等于規(guī)定值，THEN

圖2 比較試驗結(jié)果示意圖

如果啟發(fā)信息＝面積啟發(fā)，設(shè)置啟發(fā)信息為長度啟發(fā)轉(zhuǎn)（3）

如果啟發(fā)信息＝長度啟發(fā)，設(shè)置啟發(fā)信息為寬度啟發(fā)轉(zhuǎn)（3）

輸出全局最優(yōu)解；

8）待切板布局完成？否轉(zhuǎn)（2），進行下一單板優(yōu)化，是則結(jié)束。

3 試驗結(jié)果和結(jié)論

本算法在VS2008中用C＃實現(xiàn)。下列試驗橫坐標(biāo)為試驗編號，縱坐標(biāo)為最后一塊單板的最大余料面積（平方毫米/100）。試驗數(shù)據(jù)為待切板種類48，待切板總數(shù)90。用板19塊，其中第19塊的最大余料面積反映優(yōu)化的材料利用率。

圖2 (a)說明與單獨因素蟻群啟發(fā)相比，多種群算法尋優(yōu)能力強，主要表現(xiàn)為：

1）最大利用率最高；2）多次尋優(yōu)最大利用率變化區(qū)間小。

圖2 (b)說明多種群算法尋優(yōu)對蟻群數(shù)量m和最大連續(xù)全局最優(yōu)解無更新次數(shù)N這兩個參數(shù)不敏感。圖中N10表示最大連續(xù)全局最優(yōu)解無更新次數(shù)為10。m5表示蟻群數(shù)量為5。

圖2 (C)說明多種群算法尋優(yōu)比加大蟻群數(shù)量和最大連續(xù)全局最優(yōu)解無更新次數(shù)更有效。

圖2 (d)的橫坐標(biāo)為試驗編號，縱坐標(biāo)為程序運行時間（秒）（不是算法尋優(yōu)時間，還包括各中間步驟顯示所花時間等）。說明采用多種群算法的比加大蟻群數(shù)量和最大連續(xù)全局最優(yōu)解無更新次數(shù)這兩個參數(shù)的方法在時間上表現(xiàn)更離散，平均用時較高，說明好的尋優(yōu)還是要一定的時間代價的。但是這個代價是在我們可以容許的范圍內(nèi)。

4 結(jié)束語

采用本算法的軟件在多個大批量定制家具企業(yè)得到應(yīng)用，與現(xiàn)有排料軟件的優(yōu)化結(jié)果比較，優(yōu)勢較為明顯。

[1] 岳琪. 基于遺傳退火算法板式家具大規(guī)模矩形件優(yōu)化下料研究[D]. 東北林業(yè)大學(xué), 2005.

[2] 宋亞男. 二維排樣系統(tǒng)的圖形匹配、入排控制與碰靠算法研究[D]. 華南理工大學(xué), 2004.

[3] 孫寧. 人工免疫優(yōu)化算法及其應(yīng)用研究[D]. 哈爾濱工業(yè)大學(xué), 2006.

[4] Dorigo M,V Maniezzo & A. Colorni. The Ant System：Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, 1996, Part B, 26(1)： 29-41.

[5] 劉瑞杰. 求解矩形件優(yōu)化排料蟻群算法[D]. 江南大學(xué),2005.

[6] 李捷. 基于遺傳算法與螞蟻算法的矩形件布局問題的研究與應(yīng)用[D]. 南昌大學(xué), 2007.

[7] 秦玲, 自云, 章春芳, 陳峻. 解0-1背包問題的蟻群算法[J].計算機工程, 2006, 32(6).

[8] 鄒恒明. 算法之道[M]. 北京：機械工業(yè)出版社, 2010.

Mass customization cutting layout’s multiple colony ant optimization algorithm

ZENG Min1,2, WANG Cheng1, LIU Qiong-mei2

TP391.72;TP301.6

A

1009-0134(2011)5(下)-0059-04

10.3969/j.issn.1009-0134.2011.5(下).18

2011-03-01

曾敏（1964－），女，高級講師，博士研究生，研究方向為計算機輔助設(shè)計、計算機應(yīng)用。