鄧志強(qiáng)+++梁淑芬

摘 要：文章是介紹蟻群算法的應(yīng)用，隨著自動(dòng)化技術(shù)的高速發(fā)展，自動(dòng)鎖螺絲機(jī)也被廣泛的使用，然而對(duì)螺絲鎖付路徑?jīng)]有得到合理的利用，針對(duì)目前螺絲鎖付機(jī)器對(duì)螺絲鎖付路徑?jīng)]有進(jìn)行合理規(guī)劃的問題，使用傳統(tǒng)蟻群算法對(duì)螺絲鎖付路徑進(jìn)行優(yōu)化， 結(jié)合實(shí)際應(yīng)用問題，通過模擬實(shí)驗(yàn)的方式，去調(diào)整群算法的參數(shù)設(shè)置，得到比較優(yōu)化的結(jié)果。并給出了螺絲鎖付優(yōu)化路徑圖；實(shí)驗(yàn)表明該針對(duì)鎖付路徑的合理布局，螺絲鎖付效率得到顯著提高。

關(guān)鍵詞：路徑優(yōu)化；蟻群算法；鎖螺絲機(jī)

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 自動(dòng)鎖螺絲機(jī)路徑問題描述

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

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

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

一個(gè)路徑最優(yōu)問題可以表達(dá)為：

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

2 蟻群算法簡(jiǎn)介

蟻群算法是對(duì)自然界螞蟻的尋找路徑的方式進(jìn)行模擬得到的一個(gè)仿生物算法，是由意大利學(xué)者M(jìn)arco Dorigo， Vittorio Maniezzo， Alberto Colorni 提出的一種模擬進(jìn)化算法。

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

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

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

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

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

3 算法的應(yīng)用

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

3.1 初始化過程

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

3.2 算法在運(yùn)行時(shí)選擇下一個(gè)節(jié)點(diǎn)

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

3.4 結(jié)束條件

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

4 蟻群算法流程圖

如圖3所示，蟻群算法的簡(jiǎn)要流程：

5 基于蟻群算法對(duì)螺絲鎖付路徑的優(yōu)化模擬

為了提高自動(dòng)鎖螺絲機(jī)的鎖付效率，節(jié)省鎖付時(shí)間，現(xiàn)使用蟻群遺傳算法對(duì)自動(dòng)螺絲機(jī)鎖付的工件的30個(gè)螺絲孔螺絲路徑進(jìn)行路徑優(yōu)化，其中30個(gè)螺絲孔的工位坐標(biāo)為

[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]；

參數(shù)設(shè)置：

實(shí)驗(yàn)中，螞蟻的最佳數(shù)目選擇問題由Dorigo M 等提示了設(shè)計(jì)思路，由于實(shí)現(xiàn)過于復(fù)雜，本次實(shí)驗(yàn)采用相對(duì)比較簡(jiǎn)單的方式，即問題規(guī)模大致是螞蟻數(shù)目的1.5倍時(shí)，蟻群算法的全局收斂性和收斂速度比較好[7]。由于目標(biāo)為30，所有本次實(shí)驗(yàn)的螞蟻的個(gè)數(shù)設(shè)定m=20，最大循環(huán)次數(shù)NC_MAX=300。

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

說明：在表1中，平均值表示將10次運(yùn)行中每次得到的最短路徑長(zhǎng)度的平均值，最優(yōu)值表示10次運(yùn)行路徑中的最小值，最差值表示10次運(yùn)行得到的最大值，差值表示實(shí)驗(yàn)得到的最優(yōu)與最差值字之間的差值。

分析表1得到以下可以參考的結(jié)論，最佳參數(shù)配置是？琢=1，？茁=5，？籽=0.3；在該蟻群算法中，？琢=1其它為默認(rèn)值時(shí)，所得到的平均值比其它值得到的結(jié)果要好，此時(shí)差值是最小的，這說明解結(jié)果穩(wěn)定且符合目標(biāo)要求，？茁=5解的質(zhì)量最高，超過5時(shí)，接結(jié)果遠(yuǎn)離最優(yōu)，對(duì)應(yīng)信息素?fù)]發(fā)因子？籽值在0.1～0.5之間變化不大，取整0.3時(shí)接的結(jié)果質(zhì)量最優(yōu)。最優(yōu)結(jié)果如圖4所示。

以上分析是迭代300次運(yùn)行下的試驗(yàn)結(jié)果，試驗(yàn)時(shí)還增加了不是最佳配置運(yùn)行試驗(yàn)，結(jié)果表明，對(duì)于不是最優(yōu)配置的實(shí)驗(yàn)，即使是增加運(yùn)行次數(shù)得到的結(jié)果也不會(huì)有明顯的改善。

因此，可以？琢=1，？茁=5，？籽=0.3最優(yōu)配置為參考來結(jié)果不同目標(biāo)實(shí)驗(yàn)結(jié)果，得到最優(yōu)解，對(duì)于不同目標(biāo)實(shí)驗(yàn)結(jié)果如表2所示。

6 結(jié)論

在目標(biāo)個(gè)數(shù)不超過20個(gè)時(shí)不需要修改參數(shù)，就能快速的得到最優(yōu)的結(jié)果，而且收斂次數(shù)很低。超過20個(gè)目標(biāo)需要根據(jù)實(shí)際情況來微調(diào)？茁或者？籽的系數(shù)來得到最優(yōu)的結(jié)果；實(shí)驗(yàn)驗(yàn)證在實(shí)際的應(yīng)用中根據(jù)不同的目標(biāo)需求需要具體分析才能得到最優(yōu)的結(jié)果。

參考文獻(xiàn)

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

[2]程冬保. 白蟻信息素研究進(jìn)展[J]. 昆蟲學(xué)報(bào)，2013（04）：419-426.

[3]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，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]杜衡吉，李勇. 蟻群算法中參數(shù)設(shè)置對(duì)其性能影響的研究[J]. 現(xiàn)代計(jì)算機(jī)（專業(yè)版），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]葉志偉，鄭肇葆. 蟻群算法中參數(shù)α、β、ρ設(shè)置的研究——以

TSP問題為例[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004（07）.

作者簡(jiǎn)介：鄧志強(qiáng)（1991，01-），男，民族：漢，學(xué)歷：碩士，方向：電子通信。