應(yīng)用改進(jìn)蟻群算法的同心分布噴絲孔檢測(cè)路徑規(guī)劃

郭雋俠， 陶建峰， 劉成良

(上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院， 上海 200240)

應(yīng)用改進(jìn)蟻群算法的同心分布噴絲孔檢測(cè)路徑規(guī)劃

郭雋俠， 陶建峰， 劉成良

(上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院， 上海 200240)

為提高微孔同心分布噴絲板的檢測(cè)效率，提出一種基于改進(jìn)蟻群算法的微孔檢測(cè)路徑規(guī)劃方法。該方法針對(duì)傳統(tǒng)蟻群算法收斂速度慢、易陷入局部最優(yōu)等缺陷進(jìn)行優(yōu)化改進(jìn)：重新定義微孔間的距離以適應(yīng)典型噴絲板檢測(cè)儀運(yùn)動(dòng)特點(diǎn)；采用最近鄰法設(shè)定初始信息素濃度表，使蟻群算法在相同的迭代次數(shù)等參數(shù)下求得更優(yōu)的路徑結(jié)果；通過路徑尖端去除處理對(duì)蟻群算法的結(jié)果進(jìn)一步優(yōu)化，得到了優(yōu)化的微孔檢測(cè)路徑。為驗(yàn)證算法的有效性，以典型的微孔同心分布噴絲板為算例進(jìn)行檢測(cè)路徑的規(guī)劃計(jì)算。結(jié)果表明，所提出的算法具有較快的收斂速度，優(yōu)化所得路徑與傳統(tǒng)逐圈檢測(cè)路徑相比縮短路徑長(zhǎng)度約18%，可顯著提高對(duì)應(yīng)噴絲板的檢測(cè)效率。

噴絲板檢測(cè)； 蟻群算法； 信息素濃度； 最近鄰法； 最優(yōu)化

噴絲板是化纖紡絲工藝中最為重要的部件，其質(zhì)量在很大程度上決定了纖維質(zhì)量的優(yōu)劣以及紡絲能否順利進(jìn)行，因而噴絲板的質(zhì)量檢測(cè)是相關(guān)生產(chǎn)過程中必不可少的流程。噴絲板上的微孔數(shù)量多，孔徑小，傳統(tǒng)的人工檢測(cè)方式普遍存在效率低、精度較差的缺陷[1]。隨著工業(yè)自動(dòng)化技術(shù)的不斷發(fā)展，噴絲板自動(dòng)檢測(cè)技術(shù)越來越受到人們的重視。噴絲板自動(dòng)檢測(cè)儀的原理是由電動(dòng)機(jī)帶動(dòng)鏡頭遍歷每個(gè)微孔的正上方進(jìn)行微孔圖像采集，再傳入計(jì)算機(jī)加以辨識(shí)。在硬件設(shè)施不變的前提下，鏡頭對(duì)每個(gè)微孔的遍歷順序是決定檢測(cè)效率的重要因素，因此，尋找一種優(yōu)化的鏡頭運(yùn)動(dòng)路徑對(duì)于提高噴絲板檢測(cè)速度具有重要的現(xiàn)實(shí)意義。

噴絲孔檢測(cè)路徑的設(shè)計(jì)可抽象為經(jīng)典的旅行商問題(簡(jiǎn)稱TSP)，這是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性問題(NP完全問題)，其龐大的求解計(jì)算量使得精確求解難以實(shí)現(xiàn)。目前較為成熟的近似求解算法包括遺傳算法[2]、模擬退火算法[3]、果蠅算法[4]等。蟻群算法是20世紀(jì)90年代由意大利數(shù)學(xué)家Dorigo等[5]率先提出的針對(duì)旅行商問題的求解算法，該算法受到自然界中螞蟻通過信息素正反饋的方式尋找巢穴到食物最短路徑的啟示，采用加強(qiáng)較短路徑的選擇概率，達(dá)到逼近最優(yōu)路徑的目標(biāo)。這種方法具有魯棒性強(qiáng)、收斂速度易于控制、可靈活改進(jìn)等優(yōu)勢(shì)，因而被廣泛應(yīng)用于飛行器路徑設(shè)計(jì)[6]、軍事目標(biāo)打擊順序配置[7]、優(yōu)化生產(chǎn)線中的緩沖容量配置[8]等諸多領(lǐng)域中。

目前，針對(duì)噴絲板微孔檢測(cè)路徑優(yōu)化算法的研究極少，還沒有關(guān)于以蟻群算法為基礎(chǔ)規(guī)劃噴絲板檢測(cè)路徑的文獻(xiàn)報(bào)道。此外，傳統(tǒng)蟻群算法存在算法時(shí)間長(zhǎng)且易陷入局部最優(yōu)的缺點(diǎn)，為此，近年來紛紛提出相關(guān)的改進(jìn)算法。SONG等[9]改進(jìn)了信息素的取值和更新方式，引入信息素上下限的概念，改善了陷入局部最優(yōu)的情況但無法使收斂速度得到有效提高；GAN等[10]將人工螞蟻的一部分分類為“偵察蟻”，減少了總運(yùn)算量；YANG等[11]引入突變過程和局部搜索等概念，均對(duì)提高算法效率起到了一定的推進(jìn)作用，但得到的優(yōu)化結(jié)果仍有較大的改進(jìn)空間。

本文研究針對(duì)噴絲板微孔檢測(cè)路徑缺乏合理設(shè)計(jì)導(dǎo)致檢測(cè)效率低的現(xiàn)狀，設(shè)計(jì)了一種基于改進(jìn)蟻群算法的同心分布微孔檢測(cè)路徑規(guī)劃方法，即在傳統(tǒng)蟻群算法基礎(chǔ)上重新定義微孔間的距離，采用最近鄰法設(shè)定初始信息素濃度表，并通過路徑尖端去除處理對(duì)蟻群算法的結(jié)果進(jìn)一步優(yōu)化，得到了優(yōu)化的微孔檢測(cè)路徑。首先對(duì)于噴絲板微孔檢測(cè)路徑規(guī)劃問題提出數(shù)學(xué)假設(shè)并建立數(shù)學(xué)模型；接著，介紹了蟻群算法的流程和重要改進(jìn)點(diǎn)；然后，通過MatLab軟件運(yùn)行驗(yàn)證方案的可行性和收斂速度、路徑長(zhǎng)度等重要指標(biāo)，與傳統(tǒng)算法進(jìn)行對(duì)比；最后，給出算法效果的評(píng)價(jià)并進(jìn)行總結(jié)。

1 檢測(cè)路徑規(guī)劃問題建模

1.1假設(shè)

圖1示出典型的XY運(yùn)動(dòng)平臺(tái)驅(qū)動(dòng)的噴絲板自動(dòng)檢測(cè)儀。針對(duì)其檢測(cè)路徑規(guī)劃問題，為建立相應(yīng)的數(shù)學(xué)模型并確定算法適用范圍，給出假設(shè)如下。

1)噴絲板上所有微孔都需被檢測(cè)。

2)每個(gè)微孔只被檢測(cè)1次。

3)帶有檢測(cè)鏡頭相機(jī)的X、Y兩軸電動(dòng)機(jī)最大運(yùn)行速度相同，因而鏡頭從某一位置移動(dòng)至另一位置的耗時(shí)取決于這2個(gè)位置中X和Y坐標(biāo)差較大者。

4)噴絲板上微孔為同心圓或類同心圓形式分布。

5)電動(dòng)機(jī)有足夠的行程，即可裝載鏡頭相機(jī)到達(dá)噴絲板任一微孔的正上方。

6)不考慮鏡頭在Z方向(豎直方向)上的移動(dòng)。

7)假定電動(dòng)機(jī)帶動(dòng)鏡頭從某一孔移動(dòng)至另一孔的過程為勻速運(yùn)動(dòng)，忽略電動(dòng)機(jī)的加速和減速過程。

圖1 典型的噴絲板檢測(cè)儀Fig.1 Typical spinneret detector

1.2數(shù)學(xué)模型

由于平面XY運(yùn)動(dòng)平臺(tái)的特性，本文研究對(duì)于2個(gè)微孔間的距離不采用通常的歐氏距離，而由2個(gè)微孔在X、Y方向的坐標(biāo)差較大值重新定義，即對(duì)于任何2個(gè)微孔Vi(xi,yi)和Vj(xj,yj)，定義

dVi,Vj=max{|xi-xj|,|yi-yj|}

(1)

為微孔間距離，并由此建立目標(biāo)問題的數(shù)學(xué)模型。

已知無向賦權(quán)圖G=(V,E)，求總權(quán)重最小的Hamilton圈。其中：V={V1,V2,…,Vn}為頂點(diǎn)集，表示n個(gè)微孔的集合；E={eij|i,j∈1,2,…,n}為各頂點(diǎn)組成的邊集，表示兩兩微孔間連線的集合。

每條邊都存在與之對(duì)應(yīng)的權(quán)重dVi,Vj，表示微孔間的距離，由式(1)給出。

由于兩兩微孔間的距離具有對(duì)稱性，因此可認(rèn)為對(duì)任意的Vi、Vj，dVi,Vj=dVj,Vi。

設(shè)微孔的搜索順序?yàn)镻={P1,P2,…,Pn}，Pi∈V，并規(guī)定P0與Pn+1均表示原點(diǎn)，則目標(biāo)函數(shù)為

(2)

式(2)中dPi,Pi+1為點(diǎn)Pi與點(diǎn)Pi+1間的距離，其定義方式與式(1)相同。

這個(gè)數(shù)學(xué)模型具有易于描述但難以求解的特點(diǎn)，利用窮舉法精確求出最優(yōu)解要對(duì)所有可行路徑進(jìn)行逐一比較，這需要與(n-1)!/2相當(dāng)?shù)挠?jì)算量級(jí)，如表1所示。這意味著當(dāng)n=50時(shí)，需要約1.5×1064次運(yùn)算，即使在計(jì)算機(jī)技術(shù)發(fā)展到相當(dāng)高程度的當(dāng)下，也是相當(dāng)耗時(shí)的，這顯然無法滿足現(xiàn)實(shí)檢測(cè)需求，因此，采用合理的優(yōu)化算法在保證一定精度和效率的前提下求出該問題的次優(yōu)解，是求解該數(shù)學(xué)模型的必然選擇。

表1 不同微孔數(shù)量下的TSP窮舉法計(jì)算量與耗時(shí)Tab.1 Compute and time-consuming of TSP exhaustive method under different micropore numbers

2 算法及其改進(jìn)

2.1蟻群算法

蟻群算法是一種典型的求解TSP問題的概率型算法，其核心原理是建立若干代路徑方案，通過合理改變后代路徑規(guī)劃時(shí)每個(gè)微孔前往其他微孔的概率逐漸逼近最優(yōu)路徑。這個(gè)概率受2個(gè)因素共同影響,即兩兩微孔間的距離與信息素濃度。

信息素濃度[12]是蟻群算法的重要概念，自然界中蟻群在尋找食物或?qū)ふ一爻猜窂竭^程中，會(huì)在所經(jīng)過的路上釋放一種化學(xué)物質(zhì)，該物質(zhì)濃度越高，其他螞蟻選擇其對(duì)應(yīng)路徑的概率就越大。對(duì)于長(zhǎng)度較短的路徑，在一定時(shí)間內(nèi)通常會(huì)有更多的螞蟻訪問，因而積累的信息素濃度就越高，這種蟻群尋找最優(yōu)路徑中所釋放的重要物質(zhì)稱為信息素。

圖2示出蟻群信息素優(yōu)化過程。如圖2(a)所示為起點(diǎn)至終點(diǎn)的3條可行路徑，初始狀態(tài)下蟻群選擇每條路徑的概率相同，并沿途釋放信息素。隨著時(shí)間的推移，最優(yōu)路徑(路徑2)上的信息素濃度逐漸高于另2條路徑，后續(xù)的螞蟻有更高幾率選擇路徑2，并釋放更多信息素形成正反饋，如圖2(b)所示。最終，蟻群在路徑2上堆積大量信息素，而另2條路徑上的信息素幾乎完全揮發(fā)，蟻群便得到了起點(diǎn)至終點(diǎn)的最優(yōu)路徑，如圖2(c)所示。

人工蟻群算法的尋優(yōu)過程較自然界蟻群的尋優(yōu)方式進(jìn)行了改進(jìn)，其主要優(yōu)勢(shì)在于人工蟻群具有一定的記憶能力，可記憶已被訪問過的節(jié)點(diǎn)，同時(shí)在尋找路徑時(shí)也不像自然蟻群那樣盲目，而是可有意識(shí)地根據(jù)一定算法規(guī)律尋找路徑方案。

圖2 蟻群信息素優(yōu)化過程Fig.2 Optimization process of ant colony by pheromone. (a) Initial state; (b) Positive feedback process; (c) Optimal route result

2.2基于蟻群算法的微孔檢測(cè)路徑優(yōu)化

就噴絲板微孔檢測(cè)路徑而言，設(shè)共規(guī)劃k代路徑方案，第k代路徑規(guī)劃過程中，對(duì)微孔Vi檢測(cè)完畢后前往檢測(cè)微孔Vj的概率pij(k)為

pij(k)=αEij(k)+βDij

(3)

式中，Eij為微孔Vi到微孔Vj中的信息素濃度，在每一代路徑方案規(guī)劃完畢后根據(jù)當(dāng)前全局最優(yōu)路徑方案進(jìn)行更新。迭代至第k代后的Eij(k)由式(4)得到。

(4)

式(4)中ρ稱為揮發(fā)度，反映每次迭代后最優(yōu)路徑上的信息素濃度相對(duì)于其他路徑上信息素濃度的增加程度。

式(3)中，Dij表示微孔Vi(xi,yi)到微孔Vj(xj,yj)距離的倒數(shù)，與迭代次數(shù)k無關(guān)，即

(5)

式(3)中：α為信息素影響因子，反映信息素濃度對(duì)于路徑選擇概率的影響程度；β為距離影響因子，反映微孔間距離對(duì)于路徑選擇概率的影響程度。

最終，取k代路徑方案中的最優(yōu)方案，即最短路徑及對(duì)應(yīng)的微孔檢測(cè)順序作為算法結(jié)果。

2.3算法改進(jìn)研究

傳統(tǒng)蟻群算法有其獨(dú)特的優(yōu)勢(shì)，可利用逐代進(jìn)化的方法不斷逼近最優(yōu)解，但也有一定的局限性。首先，為追求較高精度，往往需要設(shè)置較大的人工螞蟻個(gè)數(shù)和迭代次數(shù)，這無疑增大了計(jì)算機(jī)的運(yùn)算負(fù)擔(dān)，消耗了大量的運(yùn)算時(shí)間；其次，由于蟻群算法信息素采用正反饋方式不斷更新，結(jié)果易陷入局部最優(yōu)。針對(duì)這2個(gè)缺陷，本文研究所采用的算法在傳統(tǒng)蟻群算法中作了如下改進(jìn)。

2.3.1信息素濃度表初始化

傳統(tǒng)蟻群算法的初始信息素濃度矩陣中各元素相等，這會(huì)導(dǎo)致算法在初始迭代中缺乏目的性，使得收斂速度慢，效率低，故采用最近鄰法對(duì)蟻群算法初始信息素濃度表的取值進(jìn)行設(shè)置，由此提高算法效率。最近鄰法是指從原點(diǎn)出發(fā)的微孔路徑規(guī)劃中，選擇滿足后一微孔是未檢孔中距前一孔最近微孔的路徑，例如對(duì)于圖3所示隨機(jī)微孔分布形式(橫、縱坐標(biāo)分別表示各微孔相對(duì)于電動(dòng)機(jī)運(yùn)動(dòng)起點(diǎn)的x方向與y方向距離)，圖4示出其對(duì)應(yīng)的最近鄰路徑。

圖3 隨機(jī)微孔分布Fig.3 Random micropore distribution

圖4 最近鄰路徑及微孔遍歷順序Fig.4 Nearest neighbor method and traversal order

最近鄰算法具有計(jì)算便捷但只能求得唯一次優(yōu)解的特點(diǎn)，其本身作為一種路徑規(guī)劃算法是相對(duì)簡(jiǎn)單的，但非常實(shí)用，其結(jié)果常優(yōu)于絕大多數(shù)可行解。將其結(jié)果作為蟻群算法初始全局最優(yōu)路徑，并相應(yīng)調(diào)整初始信息素濃度，將使蟻群算法在前期若干代路徑規(guī)劃中的路徑優(yōu)化程度得到提升，從而在不增加迭代次數(shù)和人工螞蟻個(gè)數(shù)的情況下提高算法效率。

同時(shí)，雖然可利用設(shè)置距離影響因子β與信息素影響因子α的比值調(diào)整微孔間距離對(duì)于路徑點(diǎn)選擇概率的影響程度，但若β與α比值較大，會(huì)導(dǎo)致在迭代過程的后期路徑規(guī)劃仍受微孔間距離的較大影響，無法發(fā)揮蟻群算法的優(yōu)勢(shì)；若β與α比值較小，在迭代初期又易導(dǎo)致路徑選擇的盲目性，使算法收斂速度過低。引入最近鄰算法得到的結(jié)果作為蟻群算法初始信息素濃度設(shè)置的依據(jù)，不僅將使迭代初期的路徑選擇更具有目的性，也能避免迭代后期微孔間距離對(duì)路徑選擇概率的過大影響，同時(shí)也可分擔(dān)信息素影響因子α和距離影響因子β的調(diào)節(jié)作用，從而為這2個(gè)參數(shù)的設(shè)置提供便利。

2.3.2算法結(jié)果的進(jìn)一步優(yōu)化

由于蟻群算法易陷入局部最優(yōu)的缺點(diǎn)，有時(shí)得到的結(jié)果仍有一定的改進(jìn)空間，故采用去尖端法對(duì)蟻群算法的結(jié)果進(jìn)一步優(yōu)化，其原理如圖5所示。

圖5 去尖端法原理Fig.5 Principle of path peaks removal method

設(shè)蟻群算法求得的最優(yōu)遍歷路徑為O,P1,…,Pi-1,Pi,Pi+1,…，Pj-1,Pj,Pj+1,O，包含連線段Pi-1Pi,PiPi+1,PjPj+1。從圖5中可看到，微孔Pi處的檢測(cè)路徑呈現(xiàn)“向內(nèi)尖端”，可進(jìn)一步優(yōu)化。

如果滿足：

dPi-1,Pi+1+dPj,Pi+dPi,Pj+1

(6)

式中d為式(1)定義的微孔間距離，則去除原檢測(cè)路徑中的連線段Pi-1Pi、PiPi+1、PjPj+1，并替換為連線段Pi-1Pi+1、PjPi、PiPj+1。對(duì)整條路徑上所有滿足式(6)中對(duì)于Pi要求的點(diǎn)均做類似處理，從而實(shí)現(xiàn)總檢測(cè)路徑長(zhǎng)度的降低。

2.4算法流程

本文研究設(shè)計(jì)的算法流程如圖6所示。

圖6 算法流程Fig.6 Algorithm flow

主要包括3部分：采用最近鄰法求初始可行檢測(cè)路徑并初始化信息素濃度表；主體優(yōu)化算法(蟻群算法)；利用去尖端法對(duì)結(jié)果進(jìn)一步優(yōu)化。

3 算法驗(yàn)證

為驗(yàn)證改進(jìn)蟻群算法的優(yōu)化效果，利用MatLab編程實(shí)現(xiàn)該算法。圖7示出典型的微孔同心分布噴絲板，其上共有 74 個(gè)微孔，噴絲板的一端為入料端，邊緣直徑為104 mm，孔徑約 3 mm，另一端為出料端，邊緣直徑為94 mm，孔徑約為 0.4 mm。圖8示出對(duì)應(yīng)的微孔分布圖(以電動(dòng)機(jī)運(yùn)動(dòng)起點(diǎn)為坐標(biāo)原點(diǎn)，固定噴絲板后，微孔坐標(biāo)如表2所示)。

圖7 微孔同心分布噴絲板Fig.7 Concentric spinneret. (a) Feed surface; (b) Discharge surface

圖8 微孔分布形式Fig.8 Distribution of micropores

揮發(fā)度ρ是蟻群算法中的關(guān)鍵參數(shù)。若揮發(fā)度ρ取值較大，雖能使算法收斂速度提高，但極易導(dǎo)致陷入局部最優(yōu)；若取值較小，需犧牲一定的算法時(shí)間，但可有效降低算法過早陷入局部最優(yōu)的風(fēng)險(xiǎn)。為避免算法過早陷入局部最優(yōu)，將ρ的取值范圍初步限定在0.1～0.4之間。進(jìn)一步，在α=2,β=1,人工螞蟻個(gè)數(shù)m=100，總迭代次數(shù)K=500的條件下，利用MatLab計(jì)算不同ρ值對(duì)應(yīng)的路徑長(zhǎng)度，結(jié)果如表3所示。由表可知，在該參數(shù)條件下，ρ值取0.1與0.2時(shí)算法結(jié)果較優(yōu)。同時(shí)，揮發(fā)度ρ取0.2時(shí)，算法具有更高的收斂速度，因此，選擇0.2作為驗(yàn)證算法中揮發(fā)度ρ的取值。信息素影響因子α與距離影響因子β決定了微孔間距離對(duì)于路徑點(diǎn)選擇概率的影響程度。由2.3.1小節(jié)可知，最近鄰法設(shè)置初始信息素濃度使結(jié)果對(duì)于它們的敏感程度大大降低，經(jīng)測(cè)試后在驗(yàn)證算法中取α=2,β=1。

表2 微孔位置坐標(biāo)Tab.2 Micropore coordinates mm

表3 不同ρ值對(duì)應(yīng)的路徑長(zhǎng)度Tab.3 Route lengths under different ρ values mm

對(duì)圖8所示的微孔分布形式分別采用常規(guī)的逐圈向內(nèi)檢測(cè)路徑[13]、最近鄰檢測(cè)路徑、傳統(tǒng)蟻群算法檢測(cè)路徑 (ρ=0.2,α=2,β=1,人工螞蟻個(gè)數(shù)m=200,迭代次數(shù)k=1 000) 以及改進(jìn)蟻群算法規(guī)劃?rùn)z測(cè)路徑 (ρ=0.2,α=2,β=1,人工螞蟻個(gè)數(shù)m=200, 迭代次數(shù)k=1 000)，由式(1)定義的距離分別計(jì)算總路徑長(zhǎng)度，并按電動(dòng)機(jī)30 mm/s的平均移動(dòng)速度計(jì)算平均檢測(cè)時(shí)間。其中，由于傳統(tǒng)蟻群算法和改進(jìn)蟻群算法屬于概率型算法，其結(jié)果具有不確定性，故分別運(yùn)行10次取平均結(jié)果和最優(yōu)結(jié)果。同時(shí)，為切合實(shí)際檢測(cè)需求，檢測(cè)路徑由原點(diǎn)出發(fā)并最終返回原點(diǎn)。圖9分別示出逐圈向內(nèi)、最近鄰、傳統(tǒng)蟻群算法、改進(jìn)蟻群算法所對(duì)應(yīng)的檢測(cè)路徑方案(橫、縱坐標(biāo)分別表示各微孔相對(duì)于電動(dòng)機(jī)運(yùn)動(dòng)起點(diǎn)的x方向與y方向距離)。

圖9 不同檢測(cè)路徑Fig.9 Different inspection routes. (a) Lap by lap inspection route; (b) Nearest neighbor inspection path; (c) Unimproved ant colony algorithm inspection route; (d) Improved ant colony algorithm inspection route

運(yùn)算結(jié)果如表4所示。由表可知，所提出的基于改進(jìn)蟻群算法的同心圓微孔分布噴絲板檢測(cè)路徑優(yōu)化方案相比于傳統(tǒng)方法在算法結(jié)果上有著較大的改進(jìn)效果。算法平均結(jié)果相比于逐圈向內(nèi)和最近鄰路徑方案，路徑長(zhǎng)度縮短約18%，在相同的算法參數(shù)和迭代次數(shù)下提出的改進(jìn)蟻群算法，相比于傳統(tǒng)蟻群算法在結(jié)果上得到了很大的優(yōu)化。

表4 各檢測(cè)路徑方案結(jié)果Tab.4 Results of different route planning method

注：設(shè)v電動(dòng)機(jī)=30 mm/s。

為進(jìn)一步比較改進(jìn)算法與傳統(tǒng)蟻群算法對(duì)于噴絲板微孔檢測(cè)路徑方案規(guī)劃問題的收斂性能，分別改變傳統(tǒng)蟻群算法及改進(jìn)蟻群算法的迭代次數(shù)，所得結(jié)果如圖10所示。由圖可知，改進(jìn)蟻群算法不僅在結(jié)果上顯著優(yōu)于傳統(tǒng)蟻群算法，且在收斂速度方面也有較大優(yōu)勢(shì)。

圖10 算法性能比較Fig.10 Performance comparison of improved and unimproved ant colony algorithms

4 結(jié) 語(yǔ)

針對(duì)提高微孔同心分布噴絲板的檢測(cè)效率問題，提出了一種基于改進(jìn)蟻群算法的微孔檢測(cè)路徑規(guī)劃方法。研究結(jié)果表明：1)最近鄰法設(shè)定初始信息素濃度表可顯著提高蟻群算法的收斂速度；2)路徑尖端去除處理可進(jìn)一步優(yōu)化蟻群算法計(jì)算結(jié)果，縮短路徑長(zhǎng)度；3)改進(jìn)的蟻群算法對(duì)于典型的微孔同心分布噴絲板檢測(cè)路徑規(guī)劃是有效的，所得路徑相比傳統(tǒng)逐圈向內(nèi)檢測(cè)路徑在長(zhǎng)度上可縮短約18%。

FZXB

[1] 譚志銀. 非織造熔紡噴絲板自動(dòng)化檢測(cè)與加工技術(shù)的研究[D]. 上海: 東華大學(xué), 2009: 1-3.

TAN Zhiyin. Research on automated technologies inspecting and machining spinneret for melt-spun nonwoven[D]. Shanghai: Donghua University, 2009: 1-3.

[2] SUN Lijun. Genetic algorithm for TSP problem[C]// Proceedings of 2015 International Industrial Informatics and Computer Engineering Conference. Xi′an: International Informazation and Engineering Associations, 2015.

[3] GAO Ye, XUE Rui. An improved simulated annealing and genetic algorithm for TSP[C]// Proceedings of 2013 5th IEEE International Conference on Broadband Network & Multimedia Technology. Guilin:IEEI Beijing Section, 2013.

[4] 鄧義成, 任聲策, 殷旅江. 基于改進(jìn)果蠅算法的旅行商問題[J]. 蘭州理工大學(xué)學(xué)報(bào), 2016, 42(4): 109-114.

DENG Yicheng, REN Shengce, YIN Lüjiang. Improved fruit fly optimization algorithm-based traveling salesman problem[J]. Journal of Lanzhou University of Technology, 2016, 42(4): 109-114.

[5] DORIGO Marco, STUTZLE Thomas. Ant Colony Optimization[M]. Cambridge: MIT Press, 2004.

[6] SUN Fanrong, HAN Songchen, QIAN Ge. Departure trajectory design based on pareto ant colony algorithm[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2016, 33(4): 451-460.

[7] WANG Yanxia, QIAN Longjun, GUO Zhi, et al. Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm[J]. Journal of Systems Engineering and Electronic, 2008, 19(5): 939-944.

[8] ZHOU Binghai, YU Jiadi. Buffer allocation method of serial production lines based on improved ant colony optimization algorithm[J]. High Technology Letters, 2016, 22(21): 113-119.

[9] SONG Jinjuan, BAI Yanping. An improved ant colony algorithm and its application in optimal routing problem[J]. Journal of Measurement Science and Instrumentation, 2013, 4(1): 23-29.

[10] GAN Rongwei, GUO Qingshun, CHANG Huiyou, et al. Improved ant colony optimization algorithm for the traveling salesman problem[J]. Journal of Systems Engineering and Electronics, 2010, 21(2): 329-333.

[11] YANG Jinhui, SHI Xiaohu, MAURIZIO Marchese, et al. An ant colony optimization for generalized TSP problem[J]. Progress in Natural Science, 2008(18): 1417-1422.

[12] 吳華鋒, 陳信強(qiáng), 毛奇凰, 等. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學(xué)報(bào), 2013, 34(4): 165-170.

WU Huafeng, CHEN Xinqiang, MAO Qihuang, et al.Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-170.

[13] 馮培, 劉家強(qiáng), 裘大洪,等. 基于機(jī)器視覺系統(tǒng)對(duì)噴絲頭微孔的自動(dòng)檢測(cè)[J]. 合成纖維工業(yè), 2012, 35(1): 64.

FENG Pei, LIU Jiaqiang, QIU Dahong, et al. Automatic detection of spinneret microhole by machine vision system[J]. China Synthetic Fiber Industry, 2012, 35(1): 64.

Routeplanningforconcentricspinneretinspectionbasedonimprovedantcolonyalgorithm

GUO Junxia， TAO Jianfeng， LIU Chengliang

(SchoolofMechanicalEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)

In order to improve the inspection efficiency of concentric-distribution spinneret, an inspection route planning method based on improved ant colony algorithm was proposed. In order to overcome the shortcomings of conventional algorithm including low convergence speed and sinking into local optimum, this method redefined the distance between micropores to meet the characteristic of typical spinneret inspectors, set up the initial pheromone concentration table by the nearest neighbor method to obtain better results with other parameters unchanged, and further optimized the results by path peaks removal process. To verify the effectiveness of the proposed algorithm, calculation of the route planning for a typical concentric-distribution spinneret was carried out. The results show that the proposed algorithm has higher convergence speed, and it can shorten the route length by about 18% compared with the conventional inspection route and improve the inspection efficiency of matching spinneret.

spinneret inspection; ant colony algorithm; pheromone concentration; nearest neighbor; optimization

10.13475/j.fzxb.20170201208

TS 173.8；TP 391

A

2017-02-10

2017-05-30

郭雋俠(1993—)，男，碩士生。主要研究方向?yàn)闄C(jī)器人軌跡規(guī)劃與機(jī)器視覺。陶建峰，通信作者，E-mail：jftao@sjtu.edu.cn。