史偉民,方 俊,楊亮亮

(浙江理工大學機械與自動控制學院,杭州 310018)

基于模擬退火蟻群混合算法的裁床樣片切割路徑優(yōu)化

史偉民,方 俊,楊亮亮

(浙江理工大學機械與自動控制學院,杭州 310018)

樣片切割是影響數(shù)控皮革裁床皮革加工效率的重要因素,為了提高加工效率,應優(yōu)化切割路徑。樣片切割路徑受到樣片遍歷順序和刀具加工起始位置的影響。將樣片切割路徑優(yōu)化歸結(jié)為廣義旅行商問題,用貪婪算法確定刀具加工起始位置,結(jié)合模擬退火和蟻群算法對皮革裁床樣片切割路徑進行優(yōu)化。仿真實驗驗證了算法的有效性。

樣片切割; 路徑優(yōu)化; 貪婪算法; 模擬退火算法; 蟻群算法; 數(shù)控裁床

0 引 言

在數(shù)控皮革裁床的樣片輪廓數(shù)控加工中,一張皮革需要切割成幾十個或上百個樣片。樣片切割路徑主要由各樣片的加工有效行程和樣片間的輔助快速進給空行程構(gòu)成[1]。各樣片切割總的有效切割行程是一定的,而走刀空行程主要由遍歷樣片輪廓的順序和樣片上輪廓加工的起點位置決定。當加工的樣片數(shù)量較大時,走刀空行程將成為影響加工效率的重要因素。因此,需要對走刀空行程進行優(yōu)化。

走刀空行程優(yōu)化問題可以歸結(jié)為廣義旅行商問題。目前,該優(yōu)化問題普遍的解決方法是將廣義旅行商問題轉(zhuǎn)化為標準旅行商問題,然后用求解標準旅行商問題的算法,得到走刀空行程的優(yōu)化結(jié)果。季國順等[2]提出結(jié)合蟻群算法和最鄰近算法對數(shù)控多輪廓加工走刀空行程路徑進行優(yōu)化。張偉等[3]引入蟻群算法優(yōu)化矩形件切割路徑。這些方法在一定程度上減少了樣片加工時間,提高了加工效率,對路徑進行優(yōu)化時都采用了基本蟻群算法。然而,基本蟻群算法存在著初始信息素匱乏,計算時間較長等局限性,因此,本文用貪婪算法計算出樣片上輪廓加工的起點位置,并將模擬退火算法和基于精英螞蟻系統(tǒng)的改進蟻群算法相結(jié)合,對樣片輪廓加工順序進行優(yōu)化。通過在數(shù)控皮革裁床樣片切割路徑優(yōu)化軟件對算法進行驗證。

1 樣片切割的數(shù)學模型

用數(shù)控裁床切割樣片時,對于要切割的樣片,從下刀點開始,沿著刀具總的空行程最短的軌跡,從一個樣片移動到另一個樣片,且不重復,直到所有樣片被加工完畢。對樣片切割路徑的優(yōu)化建立數(shù)學模型如下:

a) 變量設計。設有n個待切割樣片,V={v1,v2,…,vn}為樣片中心點的集合,d(vi,vj)為樣片i、j中心點vi、vj之間的距離。

c) 約束條件。從待切割樣片中隨機選擇一個樣片開始切割,遍歷每一個樣片,且不重復。

d) 優(yōu)化算法。模擬退火算法結(jié)合改進蟻群算法。

2 路徑優(yōu)化算法

針對數(shù)控皮革裁床樣片切割,本文采用貪婪算法確定刀具加工起點位置,采用模擬退火算法與改進蟻群算法相結(jié)合的方法用以優(yōu)化樣片切割路徑。

用貪婪算法構(gòu)建出一條以距離刀具位置最近的樣片為第一個節(jié)點的樣片加工序列,用模擬退火算法和蟻群算法對樣片切割路徑進行優(yōu)化時,不改變樣片庫中第一個樣片在樣片庫中的序列,就能保證刀具加工的起點位置離待加工樣片最近。

蟻群算法初始信息素匱乏。對于基本蟻群算法,信息素初始化時為各條路徑上分配一定量的信息素Q。Q值太小,路徑上信息素積累會很慢,算法搜索時間較長;Q值太大,算法會快速收斂,不利于搜索到全局最優(yōu)解。模擬退火算法具有快速全局搜索能力,但對系統(tǒng)反饋信息利用率較低[4],求精確解效率較低。因此本文采用模擬退火算法和蟻群算法的并行實現(xiàn)來克服這一局限性。先用模擬退火算法生成一條較優(yōu)路徑,在這一路徑上生成初始信息素分布,然后利用蟻群算法求精確解。

2.1 貪婪算法

貪婪算法在求解問題時,總是作出當前最好選擇,因此算法求解效率較高[5]。采用貪婪算法確定刀具開始加工樣片輪廓的起始位置,可以簡單有效地優(yōu)化走刀路徑。

假設P={p1,p2,…,pn}為待加工樣片序列,刀具的位置p0,用貪婪算法求出刀具加工樣片起始節(jié)點的步驟如下:

a) 計算刀具的位置p0與待加工樣片序列中第一個樣片p1的距離d(p1,p0);

b) 對于k=2,…,n,計算樣片pk與刀具位置p0的距離d(pk,p0),如果d(pk,p0)小于d(p1,p0),則交換pk和p1在樣片序列P中的位置,構(gòu)成當前以距離刀具位置最近的樣片為起始節(jié)點的新序列P;

c) 最后可以得到一個以所有樣片中距離刀具位置最近的樣片為起始節(jié)點的樣片序列P。

2.2 模擬退火算法

模擬退火(simulated annealing,SA)算法是一種啟發(fā)式的隨機搜索算法,是對局部搜索算法的一種擴展[6]。但SA以一定概率選擇鄰域中目標值較小的狀態(tài),是一種理論上的全局最優(yōu)算法。模擬退火算法模擬了物理退火過程,首先給定一個初溫,然后利用Metropolis策略在解空間中進行隨機搜索,伴隨著溫度的下降,結(jié)合概率突跳特性尋找到問題的全局最優(yōu)解[7]。

SA算法簡單,運行效率高,易于與其他算法相結(jié)合,且對初始條件的依賴性不高,因此本文將它與蟻群算法結(jié)合,生成初始化信息素分布,提高算法的搜索效率。

2.3 蟻群算法

蟻群優(yōu)化算法(ant colony optimization,ACO)是由意大利學者Dorigo等人于1991年提出的一種模仿螞蟻群體行為的智能算法[8]。該算法具有良好的魯棒性,并且引入正反饋并行機制和分布式計算機制。目前已被廣泛應用于解決組合優(yōu)化問題。

螞蟻在覓食過程中會分泌信息素,覓食路徑越短,則信息素濃度越高。后繼的螞蟻在選擇覓食路徑的時候,會參考路徑上的信息素濃度,路徑被選擇的概率與信息素濃度成正比。螞蟻在選擇的路徑上分泌信息素,引導后來的螞蟻,形成正反饋機制。在信息素正反饋機制的影響下,最終蟻群會聚集到最短路徑上。蟻群算法的核心機制有狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則。

a) 狀態(tài)轉(zhuǎn)移規(guī)則

螞蟻k在t時刻由元素i轉(zhuǎn)移到元素j的概率:

(1)

其中:U為螞蟻k下一步允許的選擇;α為信息啟發(fā)式因子;β為期望啟發(fā)因子;τil為殘留信息量;φil為啟發(fā)函數(shù)。

b) 信息素更新規(guī)則

在每一只螞蟻訪問完所有n個節(jié)點后,削弱舊的信息,將最新的螞蟻訪問路徑的信息加入τij。更新規(guī)則可用下式表示。

(2)

(3)

2.4 精英螞蟻系統(tǒng)

精英螞蟻系統(tǒng)(elitist ant system,EAS)在基本蟻群算法的基礎(chǔ)上對信息素更新規(guī)則作了改進,增加了一個對當前最優(yōu)路徑的強化手段[9]。在一次迭代搜索完成更新信息素的時候,為最優(yōu)路徑增加額外的信息素。改進的信息素更新公式如式(4)所示。

(4)

(5)

式(4)中e為權(quán)值(一般設置e值為城市的規(guī)模n),Lb為最優(yōu)路徑,由式(4)可見,EAS在每輪迭代中為最優(yōu)路徑增加了額外的信息素量。

引入這種額外信息素強化手段,可以更好引導螞蟻的搜索偏向,提高算法搜索效率。

2.5 改進蟻群算法

蟻群算法在搜索過程中,螞蟻在經(jīng)過的路徑上釋放信息素為一個常量Q,因此次優(yōu)路徑上的信息量可能會偏大,算法容易陷入局部最優(yōu),限制算法的全局性。所以螞蟻在釋放信息素時應隨著算法搜索狀態(tài)的變化而作相應的調(diào)整。調(diào)整規(guī)則如下:當某條路徑上的信息素濃度越高,經(jīng)過該路徑的螞蟻分泌的信息素越少。設Q(t)為釋放信息素量,則

(6)

其中:r為經(jīng)過路徑(i,j)的螞蟻數(shù)量,R為經(jīng)過節(jié)點i的螞蟻數(shù)量。

基于精英螞蟻系統(tǒng),改進蟻群算法信息素更新規(guī)則為,當所有螞蟻完成一輪搜索后,信息素更新如下:

(7)

(8)

3 算法實現(xiàn)

將改進的蟻群算法應用到皮革裁床樣片切割路徑優(yōu)化,程序流程圖見圖1。算法實現(xiàn)步驟如下:

a) 參數(shù)初始化;

b) 運用貪婪算法構(gòu)建出一條以距離刀具位置最近的樣片為初始節(jié)點的樣片加工序列;

c) 運用模擬退火算法生成一條初始節(jié)點不變的較優(yōu)路徑,并在這條路徑上分布信息素作為初始的信息素;

d) 循環(huán)次數(shù)Nc=Nc+1;

e) 螞蟻數(shù)k=k+1;

f) 螞蟻k從樣片序列第一個節(jié)點(相當于蟻巢)出發(fā),將初始節(jié)點加入禁忌表;

g) 對第k只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率公式(1)計算的概率選擇下一個樣片j,且j為不包含在禁忌表中的樣片;

h) 修改禁忌表,螞蟻移動到新選擇的樣片,并把剛訪問的樣片移動禁忌表中;

i) 若樣片未遍歷完,則跳轉(zhuǎn)到第e步,否則執(zhí)行第h步;

j)若不是所有螞蟻都構(gòu)建完路徑,則跳轉(zhuǎn)到第d步,否則執(zhí)行第i步;

k) 根據(jù)信息素更新公式(6)、(7)、(8)更新信息素;

l)若循環(huán)次數(shù)Nc≥Ncmax,則蟻群算法結(jié)束并保存最優(yōu)結(jié)果,否則清空禁忌表并跳轉(zhuǎn)到第c步。

圖1 改進蟻群算法流程

4 仿真實驗

在windows 7環(huán)境下的PC機上,在用Visual C++6.0編寫的皮革裁床上位機控制軟件中實現(xiàn)以上改進蟻群算法。

蟻群算法參數(shù)已由研究人員、學者通過大量實驗給出,參考文獻[5]給出的經(jīng)驗值,本文對蟻群算法和模擬退火算法參數(shù)的設置如表1所示。

表1 算法參數(shù)設置

在數(shù)控皮革裁床上位機控制軟件界面上放置88個待切割樣片,如圖2所示,帶有向箭頭的直線即為樣片切割路徑。初始路徑根據(jù)樣片放置的先后順序規(guī)劃的。樣片上的數(shù)字即為為樣片庫中樣片排放序列。初始路徑總長度為10 268 mm。

數(shù)控皮革裁床上位機控制軟件界面中,橫向為x軸,方向向右,縱向為y軸,方向向下。界面樣片排版區(qū)域左上角為坐標原點。假設刀具位于坐標原點,則距離刀具位置最近的樣片即為排版區(qū)域左上角第一個樣片。交換該樣片與樣片庫中第一個樣片的位置,得到新的樣片序列后,在用模擬退火和蟻群算法對樣片序列進行優(yōu)化時,不改變樣片庫中第一個樣片的序列,就能保證刀具加工的位置最近。如圖2所示,離刀具位置最近的樣片在樣片庫中的序列為2,交換樣片庫中的序列為1、2的樣片位置,得到新的樣片序列如圖3所示。

圖4為模擬退火算法計算出來的路徑,在該路徑上分布信息素。

圖5為基本蟻群算法優(yōu)化后所得到的路徑,路徑總長度為7 066 mm,優(yōu)化過程花費時間為97 309 ms。圖6為改進蟻群算法優(yōu)化結(jié)果。最優(yōu)路徑長度為6 864 mm,優(yōu)化過程花費時間為72 856 ms。分析實驗結(jié)果數(shù)據(jù)可以得出,改進蟻群算法優(yōu)化過程所花費時間為基本蟻群算法的74.87%,由此可見,改進蟻群算法的效率得到較大的提高。改進蟻群算法的最優(yōu)路徑長度比基本蟻群算法優(yōu)化后路徑長度減少202 mm,由此可見,改進蟻群算法的全局優(yōu)化性能較基本蟻群算法得到了提高。

表2列出了不同數(shù)量樣片,基本蟻群算法和改進蟻群算法的優(yōu)化結(jié)果及優(yōu)化時間。當樣片數(shù)為16時,兩個算法優(yōu)化后路徑長度一樣,改進蟻群算法優(yōu)化時間為基本蟻群算法的99.5%;當樣片數(shù)為32時,改進蟻群算法優(yōu)化后路徑長度不變,優(yōu)化時間為基本蟻群算法的96.9%;當樣片數(shù)為48時,改進蟻群算法優(yōu)化路徑長度減少79 mm,優(yōu)化時間為基本蟻群算法的94.5%;當樣片數(shù)為64時,改進蟻群算法優(yōu)化路徑長度減少209 mm,優(yōu)化時間為基本蟻群算法的84.6%。由以上數(shù)據(jù)可以看出,隨著樣片數(shù)目的增多,改進蟻群算法的全局優(yōu)化能力和計算效率更加突出。

實驗結(jié)果表明改進的蟻群算法比基本蟻群算法具有更強的全局搜索能力,效率也明顯高于基本蟻群算法。

圖2 樣片切割初始路徑

圖3 貪婪算法計算結(jié)果

圖4 模擬退火算法計算結(jié)果

圖5 基本蟻群算法優(yōu)化路徑

圖6 改進蟻群算法優(yōu)化路徑

表2 不同樣片數(shù)量基本蟻群算法和改進蟻群算法優(yōu)化結(jié)果

5 結(jié) 論

針對基本蟻群算法在優(yōu)化路徑時初始信息素匱乏而影響全局搜索性能以及計算時間較長的局限性,本文提出了基于模擬退火算法和改進蟻群算法的混合算法對空行程走刀路徑進行優(yōu)化。用貪婪算法確定刀具加工的起始位置,結(jié)合模擬退火算法和蟻群算法對樣片輪廓加工路徑進行優(yōu)化。仿真實驗結(jié)果表明,改進算法的計算效率和全局優(yōu)化性能都得到了提高,證明了算法的有效性,節(jié)省了皮革加工時間,提高了加工效率。

[1] 王 凌.智能優(yōu)化算法及其應用[M].北京: 清華大學出版社,2001: 22-30.

[2] 季國順,王 文,陳子辰.數(shù)控多輪廓加工走刀空行程路徑優(yōu)化[J].農(nóng)業(yè)機械學報,2008,39(7): 154-158.

[3] 張 偉,安魯陵,張 臣,等.基于蟻群算法的矩形件切割路徑優(yōu)化[J].機械科學與技術(shù),2011,30(3): 391-393.

[4] Park M H,Kim K S.Chattering reduction in the position control of induction motor using sliding mode[J].IEEE Trans Power Electronics,2011,6(3): 317-325.

[5] Andries P E.Computational intelligence: an introduction[M].2nd.John Wiley & Sons,2007: 273-313.

[6] 李會玲,汪振華,王基維.基于模擬退火的遺傳算法在TSP中的應用[J].熱處理技術(shù)與裝備,2007,12(25): 51-55.

[7] 王忠英,白艷萍,岳利霞.經(jīng)過改進的求解TSP問題的蟻群算法[J].數(shù)學的實踐與認識,2012,42(4): 174-181.

[8] 劉曉東,冒勇軍.蟻群算法在WSN路由協(xié)議中的應用[J].計算機工程,2009,16(2): 243-244,247.

[9] 段海濱,張祥銀,徐春芳.仿生智能計算[M].北京: 科學出版社.2011: 33-64.

(責任編輯：康 鋒)

Sample Cutting Path Optimization Based on Simulated Annealing and Ant-Colony Algorithm

SHIWei-min,FANGJun,YANGLiang-liang

(School of Mechanical Engineering & Automation,Zhejiang Sci-Tech University,Hangzhou 310018,China)

The sample cutting is the key factor influencing leather working efficiency of CNC cutting bed.To boost processing efficiency and optimize the cutting path,sample cutting path is influenced by sample traversal order and the initial position of cutter.Sample cutting path optimization is boiled down to generalized travelling salesman problem.Greedy algorithm is used to confirm the initial position of cutter.Sample cutting path is optimized in combination of simulated annealing and ant-colony algorithm.The simulation experiment verifies the effectiveness of the algorithm.

sample cutting; path optimization; greedy algorithm; simulated annealing algorithm; ant-colony algorithm; CNC cutting bed

1673-3851 (2015) 02-0214-05

2014-06-18

國家科技支撐計劃項目(2013BAF05B01);國家自然科學基金項目(51305404);浙江理工大學重點實驗室優(yōu)秀青年人才培養(yǎng)基金(ZSTUMD2012B004)

方 俊(1989-),男,浙江安吉人,碩士研究生,主要從事智能算法方面的研究。

楊亮亮,E-mail:yangliangliang@zstu.edu.cn

TP249

A