基于蟻群算法的自動鎖螺絲機路徑優化方法

鄧志強+++梁淑芬

摘 要：文章是介紹蟻群算法的應用，隨著自動化技術的高速發展，自動鎖螺絲機也被廣泛的使用，然而對螺絲鎖付路徑沒有得到合理的利用，針對目前螺絲鎖付機器對螺絲鎖付路徑沒有進行合理規劃的問題，使用傳統蟻群算法對螺絲鎖付路徑進行優化， 結合實際應用問題，通過模擬實驗的方式，去調整群算法的參數設置，得到比較優化的結果。并給出了螺絲鎖付優化路徑圖；實驗表明該針對鎖付路徑的合理布局，螺絲鎖付效率得到顯著提高。

關鍵詞：路徑優化；蟻群算法；鎖螺絲機

Abstract： This paper is to introduces the application of ant colony algorithm in the field of automation. With the rapid development of automation technology， the automatic locking screw machine is widely used. However， the screw locking method has not been used rationally. The algorithm of the ant colony algorithm is used to optimize the screw locking path， and the method of simulation is used to adjust the parameter setting of the group algorithm， and the result of comparison optimization is obtained. And the optimal path of screw lock is given. The experiment shows that the efficiency of screw locking is improved greatly.Keywords： path optimization； ant colony algorithm； lock screw machine

1 自動鎖螺絲機路徑問題描述

本文以XY-table型自動鎖螺絲機為基準，設定每個螺絲孔為一個工位，則路徑問題可以用數學圖（Graph）來表示：V={c1，c2，c3，…ci，…cn}；i=1，2，…….n 是所有工位的集合，ci表示第i個工位，n表示工位的數目

E={（r，s）：r，s∈V}；表示所有工位之間的集合；

C={rrs：r，s∈V}；是所有工位之間連接的成本度量（工位之間距離）。

一個路徑最優問題可以表達為：

求解遍歷圖G=（V，E，C），所有的節點一次都回到起始節點，使得到連接這些節點路徑成本最低[1]。

2 蟻群算法簡介

蟻群算法是對自然界螞蟻的尋找路徑的方式進行模擬得到的一個仿生物算法，是由意大利學者Marco Dorigo， Vittorio Maniezzo， Alberto Colorni 提出的一種模擬進化算法。

圖1所示，一個真實的蟻群從蟻巢出發到尋找食物的最佳路程，不論有無障礙，蟻群總是可以找到從最優的路徑。（a）沒有螞蟻從A到F（b）有障礙物的情況，螞蟻到障礙物有不同的選擇，而且選B或者選C是等概率的 （c）更多的螞蟻選擇B到目的。

螞蟻在運動的過程中，可以在它自己所經過的路徑一種信息傳遞的物質，被稱之為信息素（pheromone）[2]是一種生物學激素，另外一螞蟻同樣可以感知到這種生物學激素，并且指導蟻群行進的方向。因此，大量的螞蟻組成的這種群體行為可以表現出一種信息正反饋，當某一路徑的螞蟻越多，信息素濃度越大，被后續螞蟻感知的概率就越高，因此選擇該路徑的直到整個種群找到最佳的路徑。

為了更清晰的解釋蟻群算的原理，先模擬一下螞蟻搜索食物的具體過程。以圖2為例說明，螞蟻搜索食物的過程，信息素的濃度變化的過程，同時也是算法模擬的核心部分。

圖2所示，ABF、ACF都表示螞蟻的行進路程并且設定ACF的路程是ABF的兩倍，（a）表示單次行走，（b）表示一個來回的示意圖。設定每只螞蟻的速度相同，目的地在F，螞蟻從A點出發可以選擇A-B-F或A-C-F路徑。

設定以相同的時間行每一步，（a）圖中，螞蟻從A出發走ABF路線時，時間到達目的F用時記為1個單位時間，而走ACF路線同樣的單位時間到C，只走完路程的一半。經過2倍單位時間的情況，走ABF路線的螞蟻到達終點拿到食物又返回蟻巢，而走ACF路線的螞蟻到達目的地。設定每只螞蟻經過一處所留下的信息素為一個單位。經過4個單位時間后，所有從A出發的螞蟻都取到食物并且返回，此時ABF路徑已經往返了兩次，每一處留下的信息素為4個單位，而經過ACF路線值往返了一趟，每一處的信息素為2個單位，其比值為2：1。尋找食物的過程繼續進行，蟻群在A處派出螞蟻，按照信息素的指導，ABF路線增加一只（共2只），ACF上仍未一只，再次進4個時間單位，ABF和ACF兩條路徑的信息素單位累計為12和4，比值為3：1，按照以上規則繼續，ABF上增一只（共3只）而且ACF上仍然只有一只，再次經過4個時間單位，信息素的比值會變成4：1。繼續進行，最終所有的螞蟻會放棄ACF路線，而選擇ABF路線。這個就是信息素的正反饋效應[3]。

3 算法的應用

假定算法中需要用到的機器螞蟻數量為m，并且每個螞蟻都用自己的內存，內存中有一個禁忌表（Tabu）用來存儲螞蟻已經到訪過的位置，表示在以后的搜索中將不再會訪問禁忌表中的標記，同時還有一個允許訪問的工位標記表（Allowed）來存儲螞蟻可以訪問的工位；另外還有一個矩陣（Delta）用來存儲螞蟻在一個循環中所經過的路徑的信息素，所有工位之間的信息素用矩陣pheromone表示。最短路徑bestLength，最佳路徑為bestPath；設定NC_max為最大迭代次數。

3.1 初始化過程

設定在開始時刻，bestLength初始化為一個非常大的數（正無窮）[4]，bestPath數組為空。Allowed表中加入所有的工位節點并且設置所有螞蟻的Delta矩陣為0，Tabu表為空。隨機選取它們的起始位置，在Tabu表中加入初始工位（隨機選?。┕濣c，并且Allowed中去掉該節點。

3.2 算法在運行時選擇下一個節點

算法要求遍歷每個工位節點，選擇下一個節點只能從Allowed表中某一概率（公式1）搜索到，每次選擇到哪個工位節點，則把該工位節點加入到Tabu表，同時也必須從Allowed表中刪除該節點，對于每只機器螞蟻來說該過程重復（n-1）次，遍歷所有的節點。此時，將初始節點加入到Tabu（禁忌）表中，Tabu表中這個時候的元素個數為n+1（n位螺絲孔個數），Allowed表中的標記全部清空，不允許任何節點被訪問。 下一步按照（公式2）計算每只機器螞蟻的Delta矩陣值并保存，最后計算出最佳路徑，先比較每個螞蟻的路徑長短，然后和bestLength比較，如果其長度比bestLength小，則需要把該值賦值給bestLength，并且把Tabu（禁忌）賦值給BeatPath，即為最佳路徑[8][9][11]。

3.4 結束條件

如果達到最大代數MAX_GEN，算法終止，轉到第（5）步（輸出最優值）；否則，重新初始化所有的螞蟻的Delt矩陣所有元素初始化為0，Tabu表清空，Allowed表中加入所有的城市節點[10]。隨機選擇它們的起始位置（也可以人工指定）。在Tabu中加入起始節點，Allowed中去掉該起始節點，重復執行（2），（3），（4）步。

4 蟻群算法流程圖

如圖3所示，蟻群算法的簡要流程：

5 基于蟻群算法對螺絲鎖付路徑的優化模擬

為了提高自動鎖螺絲機的鎖付效率，節省鎖付時間，現使用蟻群遺傳算法對自動螺絲機鎖付的工件的30個螺絲孔螺絲路徑進行路徑優化，其中30個螺絲孔的工位坐標為

[45.2，14.15]；[76.85，9.49]；[107.42，18.4]；[178.31，130.62]；

[140.6，10.33]；[168.74，9.11]；[175.93，48.37]；

[196.92，132.6]；[150.3，142.16]；[140.96，133.49]；

[138.94，101.42]；[125.1，89.6]；[124.53，70.13]；

[99.96，61.23]；[97.41，78.1]；[77.6，92.35]；[49.88，54.29]；

[74.82，30.16]；[80.11，36.06]；[94.78，28.46]；[8.83，53.96]；

[27.46，86.3]；[29.4，114.1]；[38.76，86.59]；[41.34，122.96]；

[62.45，132.3]；[83.99，118.96]； [109.5，125.92]；

[136.26，118. 4]；[170.2，95.1]；

參數設置：

實驗中，螞蟻的最佳數目選擇問題由Dorigo M 等提示了設計思路，由于實現過于復雜，本次實驗采用相對比較簡單的方式，即問題規模大致是螞蟻數目的1.5倍時，蟻群算法的全局收斂性和收斂速度比較好[7]。由于目標為30，所有本次實驗的螞蟻的個數設定m=20，最大循環次數NC_MAX=300。

蟻群算法中各參數的作業是緊密耦合的，其中對算法性能起著關鍵作用的是信息素啟發式因子？琢，期望啟發式因子？茁和信息素揮發因子？籽三個參數。信息強度Q對算法的影響有賴于上述3個參數的配置以及對算法模型的選取，Q對算法性能的影響情況顯然有較大的差異[12]，本文采用的是ant-cycle模型，試驗是改變一個參數，其它參數不變的策略來探討參數設置對蟻群算法的性能的影響，默認設置參數為？琢=1，？茁=1，？籽=0.3，Q=100，每組數據實驗10次取平均值。實驗得到的模擬結果如表1所示。

說明：在表1中，平均值表示將10次運行中每次得到的最短路徑長度的平均值，最優值表示10次運行路徑中的最小值，最差值表示10次運行得到的最大值，差值表示實驗得到的最優與最差值字之間的差值。

分析表1得到以下可以參考的結論，最佳參數配置是？琢=1，？茁=5，？籽=0.3；在該蟻群算法中，？琢=1其它為默認值時，所得到的平均值比其它值得到的結果要好，此時差值是最小的，這說明解結果穩定且符合目標要求，？茁=5解的質量最高，超過5時，接結果遠離最優，對應信息素揮發因子？籽值在0.1～0.5之間變化不大，取整0.3時接的結果質量最優。最優結果如圖4所示。

以上分析是迭代300次運行下的試驗結果，試驗時還增加了不是最佳配置運行試驗，結果表明，對于不是最優配置的實驗，即使是增加運行次數得到的結果也不會有明顯的改善。

因此，可以？琢=1，？茁=5，？籽=0.3最優配置為參考來結果不同目標實驗結果，得到最優解，對于不同目標實驗結果如表2所示。

6 結論

在目標個數不超過20個時不需要修改參數，就能快速的得到最優的結果，而且收斂次數很低。超過20個目標需要根據實際情況來微調？茁或者？籽的系數來得到最優的結果；實驗驗證在實際的應用中根據不同的目標需求需要具體分析才能得到最優的結果。

參考文獻

[1]Othon Michail，Paul G. Spirakis. Traveling salesman problems in temporal graphs[J]. Theoretical Computer Science，2016.

[2]程冬保. 白蟻信息素研究進展[J]. 昆蟲學報，2013（04）：419-426.

[3]段海濱.蟻群算法原理及其應用[M].北京：科學出版社，2005.

[4]A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery[J]. International Journal of Automation & Computing，2009，01：97-102.

[5]Marco Dorigo，Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem

[6]M. Dorigo， V. Maniezzo， and A.Colorni， "The ant system： optimization by a colony of cooperating agents，" IEEE Transactions on Systems， Man， and Cybernetics-Part B， vol. 26，No.2pp.29-41， 1996.

[7]杜衡吉，李勇. 蟻群算法中參數設置對其性能影響的研究[J]. 現代計算機（專業版），2012，13：3-7.

[8]Zhi-Wei Ye；Zhao-Bao Zheng Research on the configuration of parameter alpha， beta， rho in ant algorithm exemplified by TSP，Proceedings of the International Conference on Machine Learning and Cybernetics， 2003，4；2106～211.

[9]Vasko， F J， Bobeck， J D， Governale， M A， Rieksts， D J， Keffer， J D，"A statistical analysis of parameter values for the rank-based ant colony optimization algorithm for the traveling salesperson problem" EN， 2011，Vol.62（6），pp.1169-1176.

[10]Tenbrink Thora， Wiener Jan. The verbalization of multiple strategies in a variant of the traveling salesperson problem.[J]. Cognitive Processing， 2009，10（2）.

[11]R. Moeini， M.H. Afshar，Constrained Ant Colony Optimisation Algorithm for the layout and size optimisation of sanitary sewer networks，Urban Water Journal， 2013，Vol.10（3），pp.154-173.

[12]葉志偉，鄭肇葆. 蟻群算法中參數α、β、ρ設置的研究——以

TSP問題為例[J].武漢大學學報（信息科學版），2004（07）.

作者簡介：鄧志強（1991，01-），男，民族：漢，學歷：碩士，方向：電子通信。