基于動態最低水平線法和蟻群算法的排樣優化

(e) hr不存在;hc>hl (f) hl不存在;hc>hr

(g) hr不存在;hc

(i) hlhl;hc>hr (j) hl>hr;hc>hl;hc>hr圖1 合并情況

Step 6取矩形Ri的上邊線為水平線ξi，并將ξi加入水平線集合，判斷新增的水平線ξi與相鄰水平線高度是否相等。若相等，則合并為一條水平線，然后更新水平線集合；若不相等，則不合并。

Step 7重復Step 2至Step 6，直至所有矩形都被排入板材。

圖2為本文方法的流程。

圖2 動態最低水平線法流程

圖3為同一矩形排樣序列[1,2,3,4,5,6,7]分別按最低水平線法和動態最低水平線法排放的結果。可以看出，動態最低水平線法解決了最低水平線法忽略的兩個問題，最大限度減少了板材空余，縮小了排樣高度。

(a) 最低水平線法 (b) 動態最低水平線法圖3 排放結果比較

3 蟻群算法

蟻群算法是通過模擬自然界真實螞蟻行為而形成的算法，模擬了一群螞蟻尋找從巢穴到食物源最短路徑的過程。每只螞蟻根據啟發因素和路徑上信息素量選擇移動路徑，隨時間增長和路徑上信息素的積累，從而找到最短路徑。

蟻群算法主要用于旅行問題中計算最短移動路徑[8-9]，本文將它用于矩形排樣問題中計算排樣高度H最小的矩形排入順序(即排樣序列)，并為適應題目對算法做適當改變。

(1) 信息素更新。由于矩形排樣問題不需要計算路徑長短，因此由更新螞蟻從矩形Ri轉移到矩形Rj的路徑ij的信息素變為更新矩形Rj的信息素，有利于縮短計算時間。

每一次迭代的過程中做信息素局部更新，公式為：

τj=(1-ρ)τj+Δτp×tj

(4)

式中：τj表示矩形j的信息素；ρ為信息素揮發系數；Δτp為信息素局部更新量；tj為在排樣次序是同一個值時矩形j被螞蟻經過的次數。

每完成一次迭代后，依據本次迭代中排樣高度最小的排樣序列的各矩形次序做信息素全局更新，公式為:

τj=τj+(n-qj)×Δτa

(5)

式中：n為矩形總數；qj為矩形Rj在排樣序列中的次序；Δτa為信息素全局更新量。

(2) 矩形選擇。螞蟻選擇下一個排入的矩形的概率為：

(6)

矩形Rj的啟發因素ηj的計算公式為：

ηj=μ×Sj+(1-μ)×Vj

(7)

式中：Sj為矩形Rj面積；Vj為矩形Rj寬與高的比值；μ為比例系數，表示矩形面積或寬高比值在啟發因素中的占比，0≤μ≤1。

通過不斷的迭代、信息素的更新和動態最低水平線法計算的排樣高度的反饋，蟻群算法能計算出排樣高度H最小的矩形排入順序。具體流程如圖4所示。

圖4 蟻群算法配合動態最低水平線法的算法流程

4 測試與分析

求解和仿真用VB二次開發SolidWorks[10]實現，測試參數取μ=0.3、ρ=0.1、Δτp=1、Δτa=3、α=0.6、β=2、各矩形Ri的初始信息素τi=2(1≤i≤n)。

4.1 動態最低水平線法效果

采用文獻[4]的實例，蟻群算法分別配合最低水平線法和動態最低水平線法，取迭代次數分別為20、50、100、150和200，螞蟻總數為15，進行測試。測試5次取平均，結果如表1所示。

表1 最低水平線法和動態最低水平線法板材利用率比較 %

隨著迭代次數的增加，雖然兩種方法的板材利用率都逐漸提高，但新提出的動態最低水平線法對所有的迭代次數都得到了比最低水平線法更高的板材利用率，證明動態最低水平線法效果良好且有效地彌補了最低水平線法的缺陷。

4.2 蟻群算法配合動態最低水平線法效果

采用文獻[4]的實例，測試50次取平均，將結果與文獻[4]、文獻[5]的結果作比較，如表2所示。

表2 不同算法求解結果比較

本文算法求解的板材利用率平均值和最優值均高于其他算法，雖然時間比文獻[4]略高，但板材利用率也比文獻[4]約高了7百分點，能大大節約原材料，是同時平衡了利用率和求解時間的算法。圖5為本文算法在50次測試中求解出的最優排樣圖，左下角數字為矩形編號，其板材利用率為94.93%，高度為337。

圖5 本文算法求解文獻[4]實例的最優排樣圖

為進一步驗證本文算法的效果，采用文獻[3]的7類數據作比較。每類數據包含3個不同實例，矩形總數、板材固定寬度和板材高度如表3所示。

表3 實驗數據

對每個實例測試50次取平均，并與其他算法作比較，表4為平均排樣高度與板材高度之差，表5為平均求解時間。

表4 每類數據的平均排樣高度與板材高度之差

表5 每類數據的平均求解時間 s

本文算法求解的總體平均差值最小，因此總體求解效果最好，且本文算法幾乎對每類數據求解的平均差值都為最低值，僅C7類的差值不是最低值，但求解時間相比差值最低的文獻[3]算法2大大降低，僅是文獻[3]算法2時間的百分之0.5，證明算法效果好。

由表5可知，本文算法的平均求解時間對C1至C3類實驗數據是最短的，對C4至C7類實驗數據則不是，高于最短的文獻[6]。但綜合表4可知，本文算法計算的C4至C7類數據的差值一直小于文獻[6]。因此，本文算法最好地平衡了排樣高度和求解時間，是一種可行的求解算法，有利于節約原材料。

5 結 語

本文提出動態最低水平線法，配合蟻群算法求解矩形排樣問題。測試比較證明，本文算法在同等條件下板材利用率一直高于最低水平線法，彌補了最低水平線法的缺陷。而且本文算法求解效果好，相比其他算法的總體平均排樣高度差降低約25%至46%，大幅節約原材料，同時平衡了求解時間，能適應各種規模的矩形排樣，可行性好。