應用改進蟻群算法的同心分布噴絲孔檢測路徑規劃

郭雋俠， 陶建峰， 劉成良

(上海交通大學 機械與動力工程學院， 上海 200240)

應用改進蟻群算法的同心分布噴絲孔檢測路徑規劃

郭雋俠， 陶建峰， 劉成良

(上海交通大學 機械與動力工程學院， 上海 200240)

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

噴絲板檢測； 蟻群算法； 信息素濃度； 最近鄰法； 最優化

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

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

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

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

1 檢測路徑規劃問題建模

1.1假設

圖1示出典型的XY運動平臺驅動的噴絲板自動檢測儀。針對其檢測路徑規劃問題，為建立相應的數學模型并確定算法適用范圍，給出假設如下。

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

2)每個微孔只被檢測1次。

3)帶有檢測鏡頭相機的X、Y兩軸電動機最大運行速度相同，因而鏡頭從某一位置移動至另一位置的耗時取決于這2個位置中X和Y坐標差較大者。

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

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

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

7)假定電動機帶動鏡頭從某一孔移動至另一孔的過程為勻速運動，忽略電動機的加速和減速過程。

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

1.2數學模型

由于平面XY運動平臺的特性，本文研究對于2個微孔間的距離不采用通常的歐氏距離，而由2個微孔在X、Y方向的坐標差較大值重新定義，即對于任何2個微孔Vi(xi,yi)和Vj(xj,yj)，定義

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

(1)

為微孔間距離，并由此建立目標問題的數學模型。

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

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

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

設微孔的搜索順序為P={P1,P2,…,Pn}，Pi∈V，并規定P0與Pn+1均表示原點，則目標函數為

(2)

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

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

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

2 算法及其改進

2.1蟻群算法

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

信息素濃度[12]是蟻群算法的重要概念，自然界中蟻群在尋找食物或尋找回巢路徑過程中，會在所經過的路上釋放一種化學物質，該物質濃度越高，其他螞蟻選擇其對應路徑的概率就越大。對于長度較短的路徑，在一定時間內通常會有更多的螞蟻訪問，因而積累的信息素濃度就越高，這種蟻群尋找最優路徑中所釋放的重要物質稱為信息素。

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

人工蟻群算法的尋優過程較自然界蟻群的尋優方式進行了改進，其主要優勢在于人工蟻群具有一定的記憶能力，可記憶已被訪問過的節點，同時在尋找路徑時也不像自然蟻群那樣盲目，而是可有意識地根據一定算法規律尋找路徑方案。

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

2.2基于蟻群算法的微孔檢測路徑優化

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

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

(3)

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

(4)

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

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

(5)

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

最終，取k代路徑方案中的最優方案，即最短路徑及對應的微孔檢測順序作為算法結果。

2.3算法改進研究

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

2.3.1信息素濃度表初始化

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

圖3 隨機微孔分布Fig.3 Random micropore distribution

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

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

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

2.3.2算法結果的進一步優化

由于蟻群算法易陷入局部最優的缺點，有時得到的結果仍有一定的改進空間，故采用去尖端法對蟻群算法的結果進一步優化，其原理如圖5所示。

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

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

如果滿足：

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

(6)

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

2.4算法流程

本文研究設計的算法流程如圖6所示。

圖6 算法流程Fig.6 Algorithm flow

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

3 算法驗證

為驗證改進蟻群算法的優化效果，利用MatLab編程實現該算法。圖7示出典型的微孔同心分布噴絲板，其上共有 74 個微孔，噴絲板的一端為入料端，邊緣直徑為104 mm，孔徑約 3 mm，另一端為出料端，邊緣直徑為94 mm，孔徑約為 0.4 mm。圖8示出對應的微孔分布圖(以電動機運動起點為坐標原點，固定噴絲板后，微孔坐標如表2所示)。

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

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

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

表2 微孔位置坐標Tab.2 Micropore coordinates mm

表3 不同ρ值對應的路徑長度Tab.3 Route lengths under different ρ values mm

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

圖9 不同檢測路徑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

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

表4 各檢測路徑方案結果Tab.4 Results of different route planning method

注：設v電動機=30 mm/s。

為進一步比較改進算法與傳統蟻群算法對于噴絲板微孔檢測路徑方案規劃問題的收斂性能，分別改變傳統蟻群算法及改進蟻群算法的迭代次數，所得結果如圖10所示。由圖可知，改進蟻群算法不僅在結果上顯著優于傳統蟻群算法，且在收斂速度方面也有較大優勢。

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

4 結 語

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

FZXB

[1] 譚志銀. 非織造熔紡噴絲板自動化檢測與加工技術的研究[D]. 上海: 東華大學, 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]. 蘭州理工大學學報, 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] 吳華鋒, 陳信強, 毛奇凰, 等. 基于自然選擇策略的蟻群算法求解TSP問題[J]. 通信學報, 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] 馮培, 劉家強, 裘大洪,等. 基于機器視覺系統對噴絲頭微孔的自動檢測[J]. 合成纖維工業, 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—)，男，碩士生。主要研究方向為機器人軌跡規劃與機器視覺。陶建峰，通信作者，E-mail：jftao@sjtu.edu.cn。