大規模定制板材排樣的多種群蟻群優化算法

曾 敏，王 乘，劉瓊梅

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

大規模定制板材排樣的多種群蟻群優化算法

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

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

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

優化排料；大規模定制；一刀切；多種群蟻群優化；優化算法

0 引言

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

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

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

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

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

1.1 優化算法和排樣優化的發展

目前優化算法的研究主要集中于指導性搜索方法和系統動態演化方法以及各種混合算法，研究熱點為以遺傳算法為代表的進化計算方法和蟻群算法為代表的群智能計算方法等[3]。

1.2 蟻群算法

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

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

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

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

2 一刀切板材排樣問題的蟻群優化算法

我們可以把背包問題的物品理解為矩形件排樣問題的待切件，把背包問題的背包理解為矩形排樣問題的原料板，這樣矩形件排樣問題就轉化為背包問題，這樣方便構造蟻群算法數學模型。

2.1 數學模型

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

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

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

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

我們可以看出通過求Cj最大來求minN，不滿足上述條件（1）。所以我們要把問題轉換成便于處理的方式。“同樣大小的原料板上布局更多的待切板”和“使原料板利用率更大”等效。

這樣就把求Cj最大轉換為求Sj最大。

2.2 一板兩號的編碼方式

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

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

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

2.3 排料二叉樹

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

2.4 面積，長度，寬度的多種群啟發

2.5 信息素更新

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

2.6 一刀切優化算法

算法步驟：

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

圖1 排料二叉樹和群蚊群算法參數設置

2）設全局最優解數組global-best=面積最大優先生成的第一個可行解，設置啟發信息為面積啟發；

3）計算啟發素，計算初始信息素；

4）對每一螞蟻；

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

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

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

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

ELSE 不取。

所有螞蟻找到了二叉樹？否轉（4），是轉（5）

5）比較適應度函數（容積率），求最優螞蟻。將解存入當前最優解數組current-best；

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

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

7）IF連續全局最優解無更新次數大于或等于規定值，或最大循環次數大于或等于規定值，THEN

圖2 比較試驗結果示意圖

如果啟發信息＝面積啟發，設置啟發信息為長度啟發轉（3）

如果啟發信息＝長度啟發，設置啟發信息為寬度啟發轉（3）

輸出全局最優解；

8）待切板布局完成？否轉（2），進行下一單板優化，是則結束。

3 試驗結果和結論

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

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

1）最大利用率最高；2）多次尋優最大利用率變化區間小。

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

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

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

4 結束語

采用本算法的軟件在多個大批量定制家具企業得到應用，與現有排料軟件的優化結果比較，優勢較為明顯。

[1] 岳琪. 基于遺傳退火算法板式家具大規模矩形件優化下料研究[D]. 東北林業大學, 2005.

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

[3] 孫寧. 人工免疫優化算法及其應用研究[D]. 哈爾濱工業大學, 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] 劉瑞杰. 求解矩形件優化排料蟻群算法[D]. 江南大學,2005.

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

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

[8] 鄒恒明. 算法之道[M]. 北京：機械工業出版社, 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－），女，高級講師，博士研究生，研究方向為計算機輔助設計、計算機應用。