蟻群算法在定制家具矩形零件排樣中的應用

王潔，陶濤*，陳星艷，錢筱楠，歐陽周洲，劉忠會，馮萬福

(1. 中南林業(yè)科技大學，長沙 410004；2. 歐派家居集團股份有限公司，廣州 510000；3. 江蘇凱蒂家居用品有限公司，邳州 221300)

當前，定制家具市場以其高效低成本的優(yōu)勢逐漸成為制造業(yè)發(fā)展的主流模式。但由于定制家具產品結構和外觀的多樣性，給企業(yè)的生產帶來一定難度[1-4]。如何在滿足客戶個性化需求的同時提高企業(yè)的經濟效益，縮短訂單的交貨期，高效且快速響應客戶需求，是定制家具企業(yè)亟須解決的問題[5-7]。

蟻群算法是一種群體智能搜索算法，具有較強魯棒性和全局搜索能力的特點[8]，通過正反饋機制使得搜索結果不斷收斂逐步達到最優(yōu)解。通過模擬自然界蟻群尋找食物的行為，根據真實的蟻群之間的信息傳遞及路徑選擇行為，通過種群行為的變換最終實現某種功能行為[9]。本研究將蟻群算法應用于定制家具矩形零件排樣問題中，結合定制家具生產特點，以最大化原材料利用率為目標，基于蟻群算法搜索得到零件排樣順序，實現定制家具零件排樣問題優(yōu)化，以期提高定制家具企業(yè)的生產效率、降低生產成本，從而提升企業(yè)的綜合競爭力。

1 矩形零件排樣問題概述

1.1 矩形零件排樣問題描述

板件排樣，是指在一定規(guī)格的原料板材上，按照一定規(guī)則排布若干個不同尺寸規(guī)格的零件，在滿足訂單配套和切割要求的前提下，達到一定的優(yōu)化目標[10-11]。本研究的問題具體描述如下：已知原料板材長為L，寬為W，一個批次中待切割的零件有k種，每種零件的寬為wi，長為li，每種零件數量分別為ni個(i=1,2，…，k)。最終求得一個批次訂單的優(yōu)化下料方案由N張原料板組成。在第j張原料板中共排放Cj個零件，零件所在的矩形命名為Rl(1

1.2 家具矩形零件排樣的數學模型

家具矩形零件排樣的約束條件用數學模型表示如下：

目標函數為：

(1)

式(1)為板件排樣問題的目標函數，表示最大化一個批次排樣原材料利用率。

2 矩形零件排樣的蟻群算法設計

2.1 蟻群算法原理

蟻群算法(ant colony algorithm，ACA)是模擬螞蟻尋找食物過程中搜索到最短路徑的群體智能算法[13-14]。螞蟻覓食時在其經過的路徑上會釋放一種被稱為“信息素”的化學物質，螞蟻群體中每只螞蟻在其經過的路徑上釋放信息素，經過一段時間搜索之后，被眾多螞蟻多次選擇的路徑上信息素濃度逐漸增加，最終，所有螞蟻都將選擇信息素濃度最強的那條路徑，這樣整個蟻群就尋找到了從蟻穴到食物源之間的最短路徑[15]。

基于蟻群算法的矩形零件的排樣思路如下：將矩形零件作為螞蟻尋找路徑時經過的節(jié)點，通過螞蟻的搜索，通過節(jié)點間概率選擇，節(jié)點之間信息素的不斷更新，用算法找出矩形零件排放的先后順序和排放方式，最終形成具有最大原材料利用率的矩形零件排布順序。

2.2 算法設計

將批次的板件集合記為X={X1,X2,…，Xi,…,Xt}，Xi是指第i個板件，該批次總共有t個板件，設系統(tǒng)中的螞蟻個數為m個，各個螞蟻根據概率依次選擇板件，每個螞蟻選擇的板件的序號作為一個解，第k只螞蟻形成的解可表示為{Xk5,Xk10，…,Xkj，…,Xk30}，其中Xk5表示的是當前迭代次數中，第k只螞蟻第一次選擇的是編號為5的板件，以此類推。

2.2.1 節(jié)點與路徑選擇概率

本研究將矩形零件作為螞蟻尋找路徑時經過的節(jié)點，節(jié)點信息包含矩形的長度、寬度、材料描述以及數量、紋理要求等。初始時，將m只螞蟻放置在代表不同矩形零件的節(jié)點上，m只螞蟻同時尋找下一個待排零件。螞蟻k根據概率選擇下一個節(jié)點構建路徑，公式如下：

(2)

式中：τi(t)為t時刻零件i的信息素濃度；ηi(t)為零件i的啟發(fā)信息值；α和β分別決定了信息素濃度和啟發(fā)式信息對算法性能的相對重要程度；S為螞蟻k在t時刻可選擇的節(jié)點集合，對應到矩形排樣問題中是指未排零件集合。

2.2.2 信息素與信息素更新機制

螞蟻遍歷節(jié)點完成之后，更新路徑上的節(jié)點之間的信息素。為了減少算法計算時間，本研究只針對每一次迭代中螞蟻的最優(yōu)解即最優(yōu)路徑進行更新。當螞蟻在節(jié)點i處選擇節(jié)點j對應的矩形作為下一個待排樣的零件，更新節(jié)點i與節(jié)點j之間的的信息素值，本研究設置信息素增量為選擇次數。公式如下：

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

式中：τij(t)為t時刻Xi到Xj路徑上殘留的信息素量；ρ為信息素揮發(fā)系數；Δτij(t)為第t次迭代中信息素值的增量,本研究設置為當節(jié)點i選擇節(jié)點j時，則Δτij(t)=1。

2.2.3 啟發(fā)式信息

本研究的啟發(fā)式信息考慮兩個方面：節(jié)點對應的矩形零件面積和該零件的長寬比。根據定制家具的生產實際可知，在對板材進行排樣時要優(yōu)先排布面積較大的零件，如果優(yōu)先排放小零件，后面再排放大零件時容易產生浪費。因此，本研究在對啟發(fā)式信息進行定義時，要優(yōu)先考慮零件的面積因素，對于面積相同的零件，要考慮選擇該零件不同的長寬比可能產生的浪費。

對啟發(fā)式信息的定義為：

(4)

式中：Si表示板件i的面積；ωi、li分別表示板件i的寬度和長度；p、q分別為面積的影響因子和長寬比的影響因子。

2.3 矩形零件排樣問題的蟻群算法求解流程

通過以上對蟻群算法相關參數定義及取值確定，下面將介紹基于蟻群算法求解定制家具矩形零件排樣問題的詳細流程。

第k只螞蟻的路徑搜索步驟如下：

1)給螞蟻k隨機分配第一個零件i，編號為(±i)，表示原料板橫切或縱切得到零件i。螞蟻k訪問節(jié)點i之后，更新節(jié)點對應的矩形零件的數量。

3)根據排放規(guī)則，判斷該層中剩余區(qū)域能否滿足未排零件的排布，如能夠滿足，則繼續(xù)下一步。否則返回2)。

4)根據螞蟻k選擇的新節(jié)點信息，通過選擇概率選擇下一個節(jié)點。

5)螞蟻選擇完畢。

基于蟻群算法求解定制家具排樣問題的流程如下：

1)所有待排零件進行橫切和縱切的兩個編號，即一個零件有兩個編號。

2)設最優(yōu)解數組為paiyang_best，計算啟發(fā)式信息，并初始化信息素矩陣。

3)初始化參數：α、β、ρ、m、p、q、r0。

4)對每一螞蟻

②選擇第2個零件：根據已選節(jié)點i的切割方向，求得第一層剩余空間的長度和寬度。求解節(jié)點i的可選鄰域Ni，根據2.2.1定義的選擇概率選取零件。

③對于同一張原料板，判斷節(jié)點的可選領域是否為空集，若為空集，轉向下一張原料板的排樣。

④判斷所有零件都選擇完畢，計算各板件的原材料利用率，求取平均值，作為該只螞蟻求得的解的目標函數。

5)判斷所有螞蟻是否對所有零件都選擇完畢，找出目標函數值最大的螞蟻，將該螞蟻搜索出的數組存入R_best。

6)對信息素進行更新。

7)是否滿足迭代次數要求，若否，返回步驟4)。

8)輸出目標函數值最大的數值對應的排樣序列，即為蟻群算法求得的最優(yōu)排樣方案。

3 算法運用

3.1 某批次家具訂單矩形零件

本研究選取某定制家具生產企業(yè)的3個批次家具為例，根據批次內的零件尺寸、材料信息對零件進行節(jié)點序號編排正負號編碼。某批次內零件的信息如表1所示。

表1 某批次零件信息Table 1 Information of a batch of parts

3.2 算法參數確定

用MATLAB編寫蟻群算法程序，對蟻群算法中的各個參數進行確定取值，根據前文對矩形零件排樣問題的蟻群算法的設計，算法中的參數設置如表2所示。

表2 參數設置Table 2 Parameter setting

3.3 運行實例分析

根據前文所述步驟，本研究選取3個批次A、B、C進行排樣方案示例，批次A總面積為41.86 m2，共98塊板件；批次B總面積為44.52 m2，共135塊板件；批次C總面積為48.37 m2，共201塊板件，將各批次中的零件信息導入MATLAB軟件中，通過蟻群的多次迭代搜索后，最終完成對3個批次訂單的排樣優(yōu)化方案，節(jié)選部分批次A排樣方案如圖1所示。

通過蟻群的多次迭代搜索，可以計算出3個批次最終生成的排樣方案原材料利用率，并與傳統(tǒng)經驗算法的原材料利用率進行比較，如表3所示。

圖1 部分批決A排樣方案示例Fig. 1 Sample layout plan of Batch A

本研究設定的目標函數為批次的最大原材料利用率，只有每一次迭代中原材料利用率最大的零件組合才能實現信息素更新，經過螞蟻的多次選擇零件之間的信息素濃度不斷增加而零件的啟發(fā)式信息固定，同一張原料板上的零件被選擇在一起的概率不斷增大，被多次選擇的零件組合更容易出現在同一張原料板上，最終實現該批次板件利用率最大化。

表3 不同算例的排樣結果Table 3 Layout results of different examples

對不同算例進行排樣時，對比了A企業(yè)不同的訂單數據樣本聚類分批后排樣的傳統(tǒng)經驗算法與本研究優(yōu)化的排樣算法對原材料利用率的影響，結果表明，在不同的訂單樣本量條件下，本研究優(yōu)化的排樣算法較傳統(tǒng)經驗算法原材料利用率分別提高6.1%，11.1%和10.0%。通過多次迭代能夠最大利用原料板剩余尺寸，提高了原材料的利用率和企業(yè)的經濟效益。

4 結 論

蟻群算法是一種結合分布式計算以及正反饋機制的智能算法，具有較強的全局搜索能力。本研究以最大化一個批次排樣原材料利用率為目標對定制家具矩形零件的排樣問題構建模型，將蟻群算法的結構與定制家具排樣問題的實際信息結合，對蟻群算法中的信息素更新機制和啟發(fā)式信息定義進行設計，將其應用于求解批次排樣問題。通過多次實驗分析確定了蟻群算法中各項參數值，最后通過實例驗證證明該算法能夠有效提高批次的原材料利用率，在定制家具生產中排樣問題中求解具有有效性。