顏國霖

(黎明職業(yè)大學 機電及自動化學院, 福建 泉州 362000)

在模具頂針板和面針板加工中孔群加工占有很大比重，但由于孔的位置不同、孔徑大小不一，在孔加工時換刀時間和空走刀時間占總加工時間的30%左右[1]，大大降低了生產(chǎn)效率；因此，尋求一種孔群加工最短路徑的優(yōu)化算法對提高孔群加工效率具有重要意義.目前，提高孔群加工效率普遍采用貪心算法、蟻群算法或蟻群算法與其他算法相結(jié)合的方法[2-5]，這些算法雖然在一定程度上優(yōu)化了加工路徑，但采用貪心算法產(chǎn)生的是全局最優(yōu)解[6]，使刀具空走刀行程增加，實際求得的解并非最優(yōu)，而采用蟻群算法進行優(yōu)化會造成計算量和搜索時間增加，易出現(xiàn)停滯現(xiàn)象.針對孔群中不同孔徑加工問題，本文構造了蟻群算法與2-OPT算法相融合的優(yōu)化算法，并與貪心算法、基本蟻群算法進行了比較，最后在模具頂針板孔群加工實驗中驗證了本文算法的有效性.

1 路徑優(yōu)化算法的數(shù)學模型

使用數(shù)控鉆孔機進行孔加工時，為了將換刀次數(shù)降到最少，通常會使用同一把刀從下刀點開始，沿著最短路徑加工完所有可能加工的孔，然后再換另一把刀加工另一尺寸的孔，如此循環(huán).此過程可視為典型的旅行商問題(travelling salesman problem，TSP)[7]，即刀具充當旅行商角色，孔位置代表城市位置，孔群路徑優(yōu)化目標則是刀具路徑最小值.該問題用圖論可描述為：給定一個帶權有向圖G=(V,E),V表示G的頂點集，V={1,2，…，n}，E表示圖G的邊集，dij表示任意兩孔之間的距離，也就是vi指向vj的邊的權重，i,j=1,2,…,n.圖G的最短路徑問題就是求解從下刀點到V中其他各頂點的最短路徑長度，其中：路徑長度定義為路徑上各條邊的權重之和;約束條件為刀具從換刀點開始，無重復地加工每一個孔，且遍歷所有的孔.其數(shù)學模型為

(1)

其中n表示零件上的孔數(shù).當?shù)毒咴谝?guī)劃加工路線上時，xij=1；否則，xij=0.

2 智能融合算法

假設有m只螞蟻，di表示任意兩孔之間的距離，τij(t)表示t時刻殘留在第i個孔和第j個孔連線上的信息量.初始時刻t=0，各條路徑上有少量的信息τij(0)，根據(jù)各條路徑上信息量的多少，t時刻位于某一個孔的螞蟻k(k=1,2,…,m)一次只能選擇一個目標孔.根據(jù)偽隨機比例規(guī)則，當螞蟻k從孔i移動到孔j時滿足如下關系式：

(2)

(3)

其中N(S)是可行元素的集合，系數(shù)α和β控制著信息τij和啟發(fā)式信息ηij的相對重要性.在孔群加工中，ηij表示孔i和孔j間的期望程度，設為距離的倒數(shù).在每一次迭代中，所有的m只螞蟻都更新它自己所找到的解的路徑上的信息素.信息素τij的更新規(guī)則如下：

(4)

(5)

其中Q是一個常數(shù)，Lk是螞蟻構建的路徑長度.

圖1 2-OPT算法原理圖

在蟻群算法最后階段引入2-OPT算法，即從一條初始可行解開始，通過交換路徑中的2條互不相鄰的邊，做一次2-OPT交換，如圖1所示.該方法可使算法不易陷入局部最優(yōu)解，能夠增大解突變的機率，擴大螞蟻搜索空間，加快搜索速度.兩種算法的融合實現(xiàn)步驟如下：

2) 將m只螞蟻放到節(jié)點n上，每一只螞蟻都從出發(fā)點A1開始，T表示螞蟻選擇孔的集合，循環(huán)次數(shù)N←N+1, 螞蟻數(shù)量k←k+1.

4) 2-OPT優(yōu)化.從蟻群搜索中獲取初始路徑T，設被替代邊集為X, 替代邊集為Y，X和Y為空集；i=1，不斷地增加i后，實施一個局部變換即用新邊替代舊邊，使得xi，yi進入X集和Y集，以此不斷減少路徑長度，直到獲得較短路徑為止，然后轉(zhuǎn)入i=2，….

5) 全局更新.當螞蟻成功地完成一次迭代最佳路線后，根據(jù)公式(4)和(5)全局更新當前最佳路徑上的信息素τij.

6) 算法結(jié)束.若螞蟻數(shù)k

3 路徑優(yōu)化實驗結(jié)果與分析

以圖2所示為例，該板需要加工的孔有3類，直徑分別為7、8、12 mm，加工孔數(shù)分別對應的是8、8、10個.選取頂針板上頂面中心為編程坐標系原心.根據(jù)數(shù)控加工工序的不同，所用的鉆頭直徑大小不同，但其中有重疊.為了預制孔的精確定位，引導麻花鉆進行孔加工，以減少加工誤差，首先用中心鉆點孔，然后根據(jù)不同孔徑大小，選用不同直徑麻花鉆鉆孔，最后根據(jù)加工精度要求進行鉸孔.具體加工工序為鉆中心孔φ3→鉆孔φ6.8→鉆孔φ7.8→鉆孔φ11.8→鉸孔φ7→鉸孔φ8→鉸孔φ12.

圖2 模具頂針板零件圖

3.1 路徑優(yōu)化實驗

為了驗證優(yōu)化算法的效果，選用貪心算法、蟻群算法與融合算法分別進行4種刀具走刀路徑優(yōu)化比較.參數(shù)設置如下：螞蟻數(shù)量m=20，信息素重要性系數(shù)α=1，啟發(fā)值重要性系數(shù)β=5，信息素揮發(fā)系數(shù)ρ=0.1，信息素增加強度系數(shù)Q=100.以φ3中心鉆走刀路徑為例，不同算法的優(yōu)化結(jié)果如圖3所示，最優(yōu)解迭代搜索過程如圖4所示.由圖3和圖4可知：貪心算法最短路徑為1 198.92 mm；蟻群算法優(yōu)化所得路徑長度平均值為1 466.46 mm，最短路徑為1 147.55 mm；融合算法優(yōu)化所得路徑長度平均值為1 441.17 mm，最短路徑為1 138.96 mm.

圖3 不同算法下φ 3中心鉆路徑實驗結(jié)果圖

(a)基本蟻群算法 (b)融合算法

3.2 實驗數(shù)據(jù)分析

對比表1中3種算法對4種刀具路徑優(yōu)化后的路徑長度可知，融合算法優(yōu)化刀具路徑比貪心算法分別縮短了5.27%、1.72%、1.36%、3.81%，比蟻群算法分別縮短了0.76%、1.52%、1.05%、3.46%，由此可知，融合算法比貪心算法、蟻群算法更能有效地節(jié)省走刀時間，提高加工效率.在模具加工中，孔的數(shù)量越多，效果越明顯.

表1 不同算法、不同刀具所優(yōu)化的路徑長度

4 結(jié)束語

本文針對基本蟻群算法、貪心算法的不足，提出將蟻群算法與2-OPT算法相結(jié)合的融合算法.路徑優(yōu)化實驗結(jié)果表明，本文提出的算法在模具頂針板加工路徑規(guī)劃上，可有效地縮短走刀路徑，降低頂針板數(shù)控加工時間，節(jié)約加工成本.

參考文獻：

[1] 周鯤,邵華.基于Hopfield算法的孔群加工路徑規(guī)劃 [J].模具技術,2003,21(1):48-50.

[2] 潘海鴻,劉曉琳,廖小平,等.鈑金激光切割加工CAD/CAM軟件的孔群加工路徑算法 [J].組合機床與自動化加工技術,2013(11):110-118.

[3] 陳琳,劉曉琳,潘海鴻,等.孔群分類加工的優(yōu)化算法 [J].制造業(yè)自動化,2013,39(9):45-49.

[4] 曲晶,肖世德,熊鷹.基于蟻群算法的PCB孔加工路徑優(yōu)化 [J].機電工程,2007,40(10):48-51.

[5] Dorigo M, Birattari M, Stutzle T. Ant colony optimization:artificial ants as a computational intelligence technique [J]. IEEE Computational Intelligence Magazine, 2006,1(4):28-39.

[6] 張軍,鐘競輝.算法分析與設計 [M].北京：清華大學出版社,2011：177-185.

[7] 孫業(yè)榮,姚斌,張春雨.基于TSP和塑料模具頂針板孔群加工路徑優(yōu)化問題的研究 [J].機械設計與制造,2010,10:241-243.