吳長友　戴　寧　劉　浩　程筱勝　李大偉　沈振宏　孫登廣

南京航空航天大學，南京，210016

基于改進蟻群算法的分形刀軌連接技術

吳長友戴寧劉浩程筱勝李大偉沈振宏孫登廣

南京航空航天大學，南京，210016

摘要：為了解決分形刀軌中存在的大量空行程和跳刀問題，使用部分邊界裁剪輪廓對分形路徑段進行了連接。首先采用蟻群算法對同一切片層面上的分形路徑段進行初步連接，確定整體最短連接路徑。然后依據(jù)掃描路徑規(guī)劃原則，對連接路徑進行有效性判斷，消除了不合理連接路徑對成形質量的影響。針對基本蟻群算法存在的收斂慢、易陷入局部最優(yōu)解等缺陷，采用動態(tài)調整選擇策略和信息素揮發(fā)系數(shù)對蟻群算法進行了改進。試驗結果表明，該方法有效減少了同一切片層面上的空行程和跳刀次數(shù)，且改進的蟻群算法具有很好的收斂效果和全局搜索能力。

關鍵詞：分形刀軌；空行程；跳刀；蟻群算法；路徑連接

0引言

隨著三維打印制造技術在航空航天、醫(yī)學工程等領域應用的不斷擴大，人們對成形效率和質量的要求越來越高。目前，在三維打印中，輪廓偏置掃描路徑算法復雜，需要處理環(huán)自交與相交的問題；往復直線掃描路徑在成形過程中的溫度場分布不均勻，容易產生翹曲變形和裂紋[1]。為了提高刀軌路徑規(guī)劃的質量，國內外學者對分形刀軌展開了大量研究。Cox等[2]提出利用分形曲線作為刀具軌跡的想法，并驗證了其可行性。劉征宇等[1]通過有限元模擬仿真分析，證明了與往復直線掃描路徑相比，分形路徑成形過程中的溫度場分布更均勻。Yang等[3]通過判別參數(shù)化表示的任意邊界與原始分形曲線的交點，來實現(xiàn)任意邊界薄層分形曲線的裁剪，為任意形狀輪廓內部采用分形掃描路徑填充提供了可能。李德信等[4]采用倒角和圓弧過渡的方法對分形路徑中的90°拐角進行了優(yōu)化處理，減小了頻繁轉向對設備造成的沖擊。但分形刀軌中存在的大量空行程和跳刀問題，目前還沒有很好的解決方法。因此，為了解決上述問題，提高成形質量和效率，筆者基于改進蟻群算法對分形刀軌進行連接。

針對基本蟻群算法在運行過程中可能出現(xiàn)的收斂慢、易陷入局部最優(yōu)解等問題，許多學者提出的改進策略主要集中在信息素調整、搜索策略改善、搜索速度改進以及與其他搜索方式相結合等方面。Stutzle等[5]提出了一種最大-最小螞蟻系統(tǒng)算法，其基本思想是對路徑上的信息素進行限制及局部更新，以克服算法早熟的問題。Bullnheimer等[6]基于優(yōu)化排序的螞蟻系統(tǒng)，將每次循環(huán)后螞蟻所經過的路徑長度按從小到大排序，并根據(jù)路徑長度賦予不同的權重，提高了搜索速度。朱慶保等[7]提出了基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法，以最近的鄰居節(jié)點選擇和動態(tài)信息更新來加速全局收斂，使收斂速度大幅度提高。柳長安等[8]根據(jù)目標點自適應調整啟發(fā)函數(shù)，借鑒狼群分配原則對信息素進行更新，并采用粒子群算法對蟻群算法的重要參數(shù)進行優(yōu)化選擇，提高了算法的性能。王占鋒等[9]提出一種將遺傳算法和蟻群算法融合的改進蟻群算法，首先將蟻群算法求出的解作為局部最優(yōu)解，然后再采用遺傳算法的交叉變異算子對搜索出的局部最優(yōu)解進一步優(yōu)化，篩選出全局更優(yōu)解，提高了求解的質量。

根據(jù)上述研究，筆者首先采用動態(tài)調整選擇策略和信息素揮發(fā)系數(shù)等方式對蟻群算法進行改進，用于分形路徑段的初步連接，確定整體最短連接路徑。然后依據(jù)掃描路徑規(guī)劃原則，對連接路徑進行有效性判斷，消除不合理連接路徑對成形質量的影響。最后通過FDM三維打印驗證本文算法的有效性。

1問題描述及分析

1.1連接路徑的選擇

(a)原始分形曲線　　　　　　　(b)切片輪廓及其偏置輪廓(c)分形刀軌路徑圖1　分形刀軌路徑生成示意圖

(a)無連接路徑

(b)直線連接路徑

(c)本文連接路徑圖2　分形路徑段間連接路徑示意圖

如圖1所示，連續(xù)的原始分形曲線在邊界裁剪輪廓裁剪后，變?yōu)樵S多條分散的分形路徑段，致使同一切片層面上存在大量的空行程和跳刀。大量的空行程嚴重影響成形效率；頻繁的跳刀將導致“拉絲”現(xiàn)象的發(fā)生，直接影響成形質量。對于裁剪之后的分形路徑段，若直接通過直線段將其進行連接，則可能違背掃描路徑規(guī)劃的原則[10]，出現(xiàn)交叉、溢出等現(xiàn)象。圖2b中，虛線表示的直線路徑AB與分形路徑段交叉，將致使成形層面出現(xiàn)凹凸不平。因此，為了避免上述問題的產生，本文采用部分邊界裁剪輪廓對分形路徑段進行連接，如圖2c中虛線表示的路徑AB。由于邊界裁剪輪廓是切片輪廓的一次或二次的偏置輪廓，且分形路徑段的起點和終點都在邊界裁剪輪廓上，故從一條分形路徑段的終點沿著邊界裁剪輪廓到另一條分形路徑段的起點進行連接，不會出現(xiàn)交叉、溢出等情況，同時還能增加分形刀軌路徑上的絲材與外輪廓上絲材的接觸面積，增加成形件的強度。

1.2目標數(shù)學模型

如圖3所示，為了表述方便，本文將問題表述成一個有向圖G(F，L)，其中，F(xiàn)={fi|i=1，2，…，N}為分形路徑段的集合(i為分形路徑段的序號)，f1代表起始分形路徑段；L={lij|i=1，2，…，N-1；j=2，3，…，N}為分形路徑段間連接路徑的集合，對于任意lij定義lij=〈fie,fjs〉，表示從第i條分形路徑段的終點fie沿著邊界裁剪輪廓到第j條分形路徑段的起點fjs所走的路徑。問題具體描述為：設同一切片層面上有N條分形路徑段，從起始分形路徑段的終點f1e出發(fā)，沿著f1e所在的邊界裁剪輪廓，選擇一條起點位于該邊界裁剪輪廓上的分形路徑段。然后將該分形路徑段作為當前分形路徑段，以同樣的方式選擇下一條分形路徑段，直到所有分形路徑段都被選擇，并保證所有分形路徑段間的連接路徑整體最短，其求解目標函數(shù)為

(1)

其中，PL(lij)為連接路徑的長度，即從第i條分形路徑段的終點沿著邊界裁剪輪廓到第j條分形路徑段的起點所走路徑的長度；PF(fi)為第i條分形路徑段的長度。由于本文研究分形路徑段間連接問題，因而可將PF(fi)簡化為常數(shù)，為了簡化起見，令PF(fi)=0。

(a)初始路徑的方向圖(b)最短連接路徑示意圖圖3　分形路徑段連接分析圖

2技術路線

為保證同一切片層面上所有連接路徑整體最短，且連接路徑之間不出現(xiàn)重疊，筆者提出以下技術路線：首先，對同一切片層面上的分形路徑段采用蟻群算法進行初步連接，確定整體最短連接路徑，以提高成形效率。然后，依據(jù)掃描路徑規(guī)劃原則，對每條連接路徑進行有效性判斷，消除不合理連接路徑對成形質量的影響，以提高成形質量。技術路線如圖4所示。

圖4　分形路徑段連接技術路線圖

3基于蟻群算法初步連接

分形刀軌的連接問題其實是一種基于約束的最短路徑搜索問題，其優(yōu)化目標為搜索出的路徑整體最短。目前對于這類問題的求解方法主要有貪婪算法[11-12]、遺傳算法[13-14]、蟻群算法[15]。貪婪算法逐步構造最優(yōu)解，所作出的選擇只是在某種意義上的局部最優(yōu)，不能保證求得的解是最佳的。遺傳算法盡管具有快速全局搜索能力，但是沒有很好地利用系統(tǒng)的正反饋信息，容易丟失許多較好的解。蟻群算法是模擬自然界中真實蟻群的覓食行為而提出的一種模擬進化算法，它在解決路徑優(yōu)化、任務分配等問題時表現(xiàn)出了許多優(yōu)點，如較好的魯棒性、優(yōu)良的并行計算能力，存在正反饋機制，具有發(fā)現(xiàn)較好解的能力等。分形刀軌連接過程中，通過蟻群算法進行初步排序，確定整體最短連接路徑，以提高成形效率，其主要操作過程如下。

3.1螞蟻數(shù)量的選擇

3.2狀態(tài)轉移策略

為了提高解的搜索質量，加快算法收斂，本文采用確定性轉移和隨機性轉移相結合的策略。

q

(2)

當q≥q0時，螞蟻k根據(jù)轉移概率公式：

p(k)ij(t)=ταij(t)ηβij(t)∑i∈Akταiu(t)ηβiu(t) j∈Ak0 其他ì?í????

(3)

采用輪盤賭法選擇下一條分形路徑段。

由上述狀態(tài)轉移策略可以看出，q0的取值大小決定著確定性轉移和隨機性轉移被選擇的概率。因此，為了使兩種轉移策略合理的搭配，在算法運行過程中動態(tài)調整q0的取值：

q0=ε1q0 若多數(shù)螞蟻搜索到相同的路徑ε2q0 q0≤qminφ(t) 其他{

(4)

(5)

0<ε1<0.5，1<ε2<1.5

其中，nc為當前的迭代次數(shù)；nmax為允許的最大迭代次數(shù)；φ(t)為時變函數(shù)，其值域為[0.1，0.95]，變化趨勢如圖5所示。

圖5　φ(t)曲線變化圖

在算法迭代初期，q0取較大的值，以較大的概率選擇確定性轉移，加快局部最優(yōu)路徑的搜索；算法中期，q0保持較小的值，以增大隨機性轉移的概率，擴大解的搜索空間；算法的迭代后期，進化方向已基本確定，逐漸增大q0的取值，以加快算法的收斂。在算法運行過程中，若多數(shù)螞蟻搜索到相同的路徑，則減小q0的取值，加大隨機轉移的概率，擴大解的搜索空間；同時為了避免搜索的盲目性，當q0的取值小于設定的最小極限值時，則增大q0的取值。

3.3信息更新策略

隨著時間的推移，為了避免因殘留信息素過多或完全揮發(fā)而導致的算法早熟或收斂過慢，在每只螞蟻完成對所有分形路徑段的遍歷后，對殘留信息素進行更新處理，更新規(guī)則如下：

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(6)

(7)

(8)

由式(6)可知，信息素揮發(fā)系數(shù)ρ的取值對算法的性能具有重要的影響。ρ越大，路徑上的殘留信息素揮發(fā)就越快，算法收斂也就越快，但算法的全局搜索能力將降低；反之，算法的全局搜索能力增強，但收斂將變慢?；鞠伻核惴ㄖ?，ρ為常數(shù)，不利于協(xié)調收斂速度和全局搜索能力相悖的矛盾。因此，為了提高蟻群算法的自適應性，本文將信息素揮發(fā)系數(shù)ρ作自適應動態(tài)的調整：

ρ(t)=ρmin τij(t)≤τminλ(t) τmin<τij(t)<τmaxρmax τij(t)≥τmax{

(9)

(10)

式中，ρmax、ρmin分別為ρ的最大值和最小值；τmax、τmin為防止路徑上的信息素濃度過高或過低設定的信息素極限值，其采用文獻[16]的方法確定；λ(t)為時變函數(shù)，值域為[ρmin，ρmax]，其變化趨勢如圖6所示。

圖6　λ(t)曲線變化圖

當路徑上的信息素濃度小于等于τmin時，使ρ取較小值來減緩路徑上信息素的揮發(fā)，以提高算法的全局搜索能力。當路徑上的信息素濃度大于等于τmax時，為了防止蟻群算法收斂過慢，則使ρ取較大值，加快路徑上信息素的揮發(fā)。當路徑上的信息素濃度在(τmin，τmax)范圍內時，在算法運行初期，使ρ取較大值，以減少信息素對蟻群的影響，加快算法的收斂；而后隨著迭代次數(shù)的增加，使ρ逐漸減小，以保證算法的全局尋優(yōu)。

3.4算法步驟

(1)初始化各項參數(shù)，為每只螞蟻建立禁忌表tk；

(2)把每只螞蟻放到起始分形路徑段上，將起始分形路徑段置入tk中；

(3)If(q

Else{螞蟻k根據(jù)式(3)采用輪盤賭方法選擇下一個分形路徑段j}；

(4)將j置入禁忌表tk，螞蟻轉移到分形路徑段j；

(5)If(所有分形路徑段被每只螞蟻遍歷){轉步驟(6)}

Else{轉步驟(3)}；

(6)根據(jù)式(9)確定信息素揮發(fā)系數(shù)ρ；

(7)根據(jù)式(6)更新所有螞蟻路徑上的信息量；

(8)If(nc大于最大迭代次數(shù)){轉步驟(9)}

Else{清空禁忌表tk，nc←nc+1，轉步驟(2)}；

(9)輸出最優(yōu)路徑，結束算法。

4連接路徑的有效性判斷

根據(jù)蟻群算法求解出分形路徑段的連接順序，依次提取相鄰分形路徑段間的連接路徑，發(fā)現(xiàn)某些連接路徑可能存在不合理的情況。如圖7所示，在掃描路徑f1→LBC→f2→LDE→f3→LFG→f4時，f3到f4的連接路徑LFG與f1到f2的連接路徑LBC出現(xiàn)重疊。相比空行程和跳刀，路徑重疊對成形質量的影響更大，它導致成形過程中路徑被重復掃描，使成形層面呈現(xiàn)凹凸不平，直接影響成形件質量。因此，為了去除不合理連接路徑對成形質量的影響，需要對連接路徑進行有效性判斷，將無效的連接路徑舍棄。

圖7　不合理連接路徑示意圖

通過對不合理連接路徑的分析發(fā)現(xiàn)，它們有一個共同特征：不合理連接路徑除了包含其要連接的兩條分形路徑段的起點與終點外，還包含了其他分形路徑段的起點或終點。圖7中的不合理連接路徑LFG通過了f1的起點A、終點B和f2的起點C。因此，根據(jù)上述分析，連接路徑有效性判斷方法為：對于fi和fj兩條分形路徑段，若存在常數(shù)φ1或φ2，φ1，φ2∈[0，1]，滿足

fns=φ2(vi,j(k)+vi,j(k+1))

(11)

fne=φ1(vi,j(k)+vi,j(k+1))

(12)

k=1，2，…，Kij-1n=1，2，…，Nn≠j

式中，Kij為fi和fj之間連接路徑上所有頂點的個數(shù)；vi,j(k)為fi和fj之間連接路徑上第k個頂點；fns、fne分別為第n條分形路徑段的起點和終點。

則認為fi和fj之間的連接路徑是無效的。

5實驗與分析

上述算法已經在自主開發(fā)的RP(RapidPrototyping)模塊(開發(fā)環(huán)境為VS2008)中得到應用，實驗平臺配備有Corei5-3470 3.20GHz處理器、4.00GB內存的PC。

(a)分形路徑段無連接(b)　　　基本蟻群算法初連接　　　(L=278.652 mm)

(c)　　　改進蟻群算法初連接(d)去除無效連接路徑　　　(L=216.493 mm)圖8　連接路徑生成圖

應用本文算法對圖8所示的分形路徑段進行連接。圖8a所示為原始模型某一切片層面上的分形刀軌，由圖可知，各個分形路徑段互不連接，路徑中存在著大量的空行程和跳刀，嚴重影響著成形的效率和質量。圖8b所示為采用基本蟻群算法對分形路徑段進行的初步連接，總的連接路徑長度L=278.652mm，由圖可知，同一切片層面上的連接路徑間出現(xiàn)大量重疊，算法出現(xiàn)早熟。圖8c所示為采用改進蟻群算法對分形路徑段進行的初步連接，總的連接路徑長度L=216.493mm，對比圖8b可知，總的連接路徑長度有所減小，但存在一些連接路徑與其他連接路徑重疊的情況(圖中虛線方框所示)，將導致成形絲材重復堆積。圖8d為在蟻群算法初步連接的基礎上去除無效連接路徑之后的刀軌路徑圖，對比圖8a、圖8c可知，同一切片層面上的空行程和跳刀有效減少，且生成的連接路徑無交叉、溢出、重疊等情況。圖9為采用本文算法連接的其他實例，表1給出了連接前后的數(shù)據(jù)，其中，L0、J0和L1、J1分別表示連接前后總的空行程距離和跳刀次數(shù)。由圖9和表1可知，采用本文算法連接后，路徑中的空行程和跳刀顯著減少，且無不合理的刀軌路徑。

(a)實例1無連接(L0=194.246 mm，J0=32)

(b)實例1本文算法連接(L1=58.325 mm，J1=8)

(c)實例2無連接(L0=106.685 mm，J0=20)

(d)實例2本文算法連接(L1=22.763 mm，J1=2)

(e)實例3無連接(L0=172.125 mm，J0=28)

(f)實例3本文算法連接(L1=46.729 mm，J1=4)圖9　其他連接實例

測試實例實例1實例2實例3總的空行程(mm)L0194.246106.685172.125L158.32522.76346.729跳刀次數(shù)J0322028J1824空行程減少率(%)(L0-L1)/L070.078.772.9跳刀減少率(%)(J0-J1)/J075.090.085.7

在使用蟻群算法進行初步連接時，算法的主要參數(shù)設置如下：α=1.0，β=3.0，qmin=0.1，ρmax=0.5，ρmin=0.3，nmax=200，Q=200。圖10為圖8所示實例的蟻群算法收斂過程圖，與基本蟻群算法對比可以得出，改進的蟻群算法具有很好的收斂效果和全局搜索能力，在迭代相對較少的情況下，求得的解優(yōu)于基本蟻群算法。

圖10　蟻群算法的收斂過程圖

(a)成形件1-A(t=0.75 h) (b)成形件2-A(t=0.67 h)(c)成形件3-A(t=0.63 h)

(a)成形件1-B(t=0.62 h) (b)成形件2-B(t=0.55 h)(c)成形件3-B(t=0.50 h)

為了進一步說明本文算法的有效性，采用MakerBotReplicator2X打印設備分別對連接前后的分形刀軌進行了打印測試。測試的各項參數(shù)設置如下：分形刀軌的單位步長為2mm，打印耗材為ABS，絲材直徑為1.82mm，噴嘴直徑為0.4mm，分層厚度為0.2mm，噴嘴移動速度為40mm/s，熔融溫度為220 ℃，基板溫度為110 ℃，打印模型高度為8mm。圖11、圖12分別為分形刀軌連接前后的成形件及其局部放大圖，表2給出了打印實驗數(shù)據(jù)。圖11中成形件1-A、成形件2-A、成形件3-A的打印時間分別為0.75h、0.67h、0.63h，其局部放大圖分別為圖11d、圖11e、圖11f，由圖可知，由一條分形路徑段向另一條分形路徑段跳轉時的“拉絲”現(xiàn)象非常嚴重。圖12中，成形件1-B、成形件2-B、成形件3-B為分形刀軌采用本文算法連接之后的成形件，其打印時間分別為0.62h、0.55h、0.50h，與連接前的成形件相比，時間分別節(jié)省了17.3%、17.9%、20.6%，成形效率得到有效提高；圖12d、圖12e、圖12f分別為成形件1-B、成形件2-B、成形件3-B的局部放大圖，與圖11d、圖11e、圖11f對比可知，采用本文算法連接的成形件中“拉絲”現(xiàn)象得到明顯改善，成形質量顯著提高。

(d)成形件1-B的局部放大(e)成形件2-B的局部放大(f)成形件3-B的局部放大圖12　連接后的成形件及其局部放大

打印實例成形件體積(cm3)拉絲現(xiàn)象打印時間(h)ABAB時間節(jié)省率(%)成形件128.8嚴重輕微0.750.6217.3成形件224.6嚴重輕微0.670.5517.9成形件322.5嚴重輕微0.630.5020.6

6結論

(1)針對分形刀軌中存在的大量空行程和跳刀問題，采用蟻群算法對同一切片層面上的分形路徑段進行初步連接，然后依據(jù)掃描路徑規(guī)劃的原則，對連接路徑進行有效性判斷，去除了不合理的連接路徑。試驗結果表明，通過上述操作，分形刀軌中的空行程和跳刀次數(shù)有效減少，提高了成形質量和效率。

(2)針對基本蟻群算法存在的收斂慢、易陷入局部最優(yōu)解等缺陷，在算法運行過程中動態(tài)調整q0的取值和信息素揮發(fā)系數(shù)ρ的大小。試驗結果表明，通過上述改進，算法的收斂速度和全局搜索能力得到明顯提高。

(3)本文方法仍有不足之處，如對于同一切片層面上的分形路徑段，仍不能實現(xiàn)所有分形路徑段間無跳刀的完全連接。因而下一步的研究重點將是對所有分形路徑段進行完全連接。

參考文獻：

[1]劉征宇，賓鴻贊，張小波，等. 生長型制造中分形掃描路徑對溫度場的影響[J]. 華中理工大學學報，1998，26(8):32-34.

LiuZhengyu，BinHongzan，ZhangXiaobo，etal.TheInfluenceoftheFractalScanningPatontheTemperatureFieldoftheLayerinMaterialIncreaseManufacturing[J].JournalofHuazhongUniversityofScienceandTechnology，1998，26(8):32-34.

[2]CoxJJ，TakezakiY，F(xiàn)ergusonHRP，etal.SpaceFillingCurvesinToolPathApplications[J].ComputerAidedDesign，1994，26(3)：215-224.

[3]YangJ，BinH，ZhangX，etal.FractalScanningPathGenerationandControlSystemforSelectiveLaserSintering(SLS)[J].InternationalJournalofMachineToolsandManufacture，2003，43(3)：293-300.

[4]李德信，焦俊鵬.Hilbert填充曲線用于刀具路徑生成的算法及改進研究[J]. 中國機械工程，2011，22(22)：2739-2743.

LiDexin，JiaoJunpeng.ResearchonToolPathGenerationAlgorithmandImprovementBasedonHibertSpace-fillingCurves[J].ChinaMechanicalEngineering，2011，22(22)：2739-2743.

[5]StutzleT，HoosH.Max-minAntSystemandLocalSearchfortheTravelingSalesmanProblem[C]//Proceedingsofthe4thIEEEInternationalConferenceonEvolutionaryComputation.Indianapolis，1997：309-314.

[6]BullnheimerB，HartlRF，StraussC.ANewRank-basedVersionoftheAntSystem:AComputationalStudy[J].CentralEuropeanJouralforOperationsResearchandEconomics，1999，7(1)：25-38.

[7]朱慶保, 楊志軍. 基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J]. 軟件學報，2004，15(2)：185-192.

ZhuQingbao,YangZhijun.AnAntColonyOptimizationAlgorithmBasedonMutationandDynamicPheromoneUpdating[J].JournalofSoftware，2004，15(2)：185-192.

[8]柳長安，鄢小虎，劉春陽，等. 基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J]. 電子學報，2011，39(5)：1220-1224.

LiuChang’an,YanXiaohu,LiuChunyang,etal.DynamicPathPlanningforMobileRobotBasedonImprovedAntColonyOptimizationAlgorithm[J].ActaElectonicaSinica，2011，39(5): 1220-1224.

[9]王占鋒，杜海蓮，安素芳，等. 求解車輛路徑問題的改進蟻群算法[J]. 華僑大學學報，2013，34(1)：36-39.

WangZhanfeng,DuHailian,AnSufang,etal.AnImprovedAntColonyAlgorithmBasedonVehicleRoutingProblem[J].JouralofHuaqiaoUniversity(NaturalScience)，2013，34(1)：36-39.

[10]黃小毛. 熔絲沉積成形若干關鍵技術研究[D]. 武漢：華中科技大學，2009.

[11]YuanY，WangDW.PathSelectionModelandAlgorithmforEmergencyLogisticMangement[J].Computers&IndustrialEngineering，2009，56(3)：1081-1094.

[12]JinYA，HeY，F(xiàn)uJZ.OptimizationofTool-pathGenerationforMaterialExtrusion-basedAdditiveManufacturingTechnology[J].AdditiveManufacturing，2014(1/4)：32-47.

[13]LiuF，ZengGZ.StudyofGeneticAlgorithmwithReinforcementLearningtoSolvetheTS-P[J].ExpertSystemswithAplications，2009，36(3)：6995-7001.

[14]雷偉軍，程筱勝，戴寧，等. 基于改進遺傳算法的多模型加工路徑規(guī)劃[J]. 機械工程學報，2014，50(11)：153-161.

LeiWeijun，ChengXiaosheng，DaiNing，etal.Multi-modelMachiningPathPlanningBasedonImprovedGeneticAlgorithm[J].JournalofMechanicalEngineering，2014，50(11)：153-161.

[15]MarcoD，ThomasS.AntColonyOptimization:OverviewandRecentAdvances[J].HandbookofMetaheuristics，2010，146：227-263.

[16]劉新華，張旭堂，劉文劍. 基于改進最大-最小螞蟻系統(tǒng)的多工藝線路決策方法[J].計算機集成制造系統(tǒng)，2008，14(12)：2414-2420.

LiuXinhua，ZhangXutang，LiuWenjian.Multi-processRoutesDecision-makingMethodologyBasedonImproveMax-minAntSystem[J].ComputerIntegratedManufacturingSystems，2008，14(12)：2414-2420.

(編輯張洋)

FractalToolPathConnectionTechnologyBasedonImprovedAntColonyAlgorithm

WuChangyouDaiNingLiuHaoChenXiaoshengLiDaweiShenZhenhongSunDengguang

NanjingUniversityofAeronauticsandAstronautics,Nanjing,210016

Abstract:To solve the problems of numerous empty trips and tool-retraction in fractal tool path, the fractal path segments were connected by border crop profiles. To determine the shortest overall connection path, an ant colony algorithm was applied to initially connect the scattered fractal path segments on the same layer of slice. Afterwards, according to the principles of the path planning, the validity of the connection path was judged, and the bad forming quality that was affected by the unreasonable connection path was removed. Selection strategy and pheromone evaporation coefficient were dynamically adjusted to improve the basic ant colony algorithm, which converged slowly and was easy to get stuck in a local optimal solution. The experimental results demonstrate that the method can effectively reduce empty trips and tool-retraction on the same layer of slice, and the improved ant colony algorithm shows good convergence and global search capabilities.

Key words:fractal tool path; empty trip; tool-retraction; ant colony algorithm; path connection

收稿日期：2015-04-07

基金項目：國家高技術研究發(fā)展計劃(863計劃)資助項目(SS2013AA040801)；江蘇省三維打印裝備與制造重點實驗室開放課題(BM2013006)；江蘇省科技支撐項目(BE2014009-3)；航空基金資助項目(20151652024)

中圖分類號：TP391

DOI：10.3969/j.issn.1004-132X.2016.01.010

作者簡介：吳長友，男，1989年生。南京航空航天大學機電學院碩士研究生。主要研究方向數(shù)字化設計與制造、三維打印技術。戴寧，男，1978年生。南京航空航天大學機電學院副教授。劉浩，男，1972年生。南京航空航天大學機電學院副教授。程筱勝，男，1964年生。南京航空航天大學機電學院教授、博士研究導師。李大偉，男，1989年生。南京航空航天大學機電學院碩士研究生。沈振宏，男，1990年生。南京航空航天大學機電學院碩士研究生。孫登廣，男，1991年生。南京航空航天大學機電學院碩士研究生。