基于動(dòng)態(tài)最低水平線法和蟻群算法的排樣優(yōu)化

(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重復(fù)Step 2至Step 6，直至所有矩形都被排入板材。

圖2為本文方法的流程。

圖2 動(dòng)態(tài)最低水平線法流程

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

(a) 最低水平線法 (b) 動(dòng)態(tài)最低水平線法圖3 排放結(jié)果比較

3 蟻群算法

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

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

(1) 信息素更新。由于矩形排樣問題不需要計(jì)算路徑長短，因此由更新螞蟻從矩形Ri轉(zhuǎn)移到矩形Rj的路徑ij的信息素變?yōu)楦戮匦蜶j的信息素，有利于縮短計(jì)算時(shí)間。

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

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

(4)

式中：τj表示矩形j的信息素；ρ為信息素?fù)]發(fā)系數(shù)；Δτp為信息素局部更新量；tj為在排樣次序是同一個(gè)值時(shí)矩形j被螞蟻經(jīng)過的次數(shù)。

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

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

(5)

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

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

(6)

矩形Rj的啟發(fā)因素ηj的計(jì)算公式為：

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

(7)

式中：Sj為矩形Rj面積；Vj為矩形Rj寬與高的比值；μ為比例系數(shù)，表示矩形面積或?qū)捀弑戎翟趩l(fā)因素中的占比，0≤μ≤1。

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

圖4 蟻群算法配合動(dòng)態(tài)最低水平線法的算法流程

4 測(cè)試與分析

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

4.1 動(dòng)態(tài)最低水平線法效果

采用文獻(xiàn)[4]的實(shí)例，蟻群算法分別配合最低水平線法和動(dòng)態(tài)最低水平線法，取迭代次數(shù)分別為20、50、100、150和200，螞蟻總數(shù)為15，進(jìn)行測(cè)試。測(cè)試5次取平均，結(jié)果如表1所示。

表1 最低水平線法和動(dòng)態(tài)最低水平線法板材利用率比較 %

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

4.2 蟻群算法配合動(dòng)態(tài)最低水平線法效果

采用文獻(xiàn)[4]的實(shí)例，測(cè)試50次取平均，將結(jié)果與文獻(xiàn)[4]、文獻(xiàn)[5]的結(jié)果作比較，如表2所示。

表2 不同算法求解結(jié)果比較

本文算法求解的板材利用率平均值和最優(yōu)值均高于其他算法，雖然時(shí)間比文獻(xiàn)[4]略高，但板材利用率也比文獻(xiàn)[4]約高了7百分點(diǎn)，能大大節(jié)約原材料，是同時(shí)平衡了利用率和求解時(shí)間的算法。圖5為本文算法在50次測(cè)試中求解出的最優(yōu)排樣圖，左下角數(shù)字為矩形編號(hào)，其板材利用率為94.93%，高度為337。

圖5 本文算法求解文獻(xiàn)[4]實(shí)例的最優(yōu)排樣圖

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

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

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

表4 每類數(shù)據(jù)的平均排樣高度與板材高度之差

表5 每類數(shù)據(jù)的平均求解時(shí)間 s

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

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

5 結(jié) 語

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