基于TSP的孔群加工路徑優(yōu)化算法

顏國(guó)霖

(黎明職業(yè)大學(xué) 機(jī)電及自動(dòng)化學(xué)院, 福建 泉州 362000)

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

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

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

(1)

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

2 智能融合算法

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

(2)

(3)

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

(4)

(5)

其中Q是一個(gè)常數(shù)，Lk是螞蟻構(gòu)建的路徑長(zhǎng)度.

圖1 2-OPT算法原理圖

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

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

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

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

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

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

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

圖2 模具頂針板零件圖

3.1 路徑優(yōu)化實(shí)驗(yàn)

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

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

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

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

[4] 曲晶,肖世德,熊鷹.基于蟻群算法的PCB孔加工路徑優(yōu)化 [J].機(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] 張軍,鐘競(jìng)輝.算法分析與設(shè)計(jì) [M].北京：清華大學(xué)出版社,2011：177-185.

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