蟻群算法求解TSP中的參數(shù)設(shè)置

嚴(yán)小燕+夏桂林

摘要：蟻群算法在求解TSP 中取得了較好的效果，但相對于遺傳算法等優(yōu)化方法，其缺少系統(tǒng)的理論指導(dǎo)，特別是參數(shù)的設(shè)置，通常是根據(jù)經(jīng)驗或反復(fù)試驗來選取合適的參數(shù)值。本文在分析各參數(shù)對蟻群算法性能影響的基礎(chǔ)上，采用均勻設(shè)計法對算法參數(shù)進(jìn)行設(shè)置，并以TSP為例，利用MATLAB進(jìn)行仿真。試驗結(jié)果表明，采用均勻設(shè)計達(dá)到以較少的試驗獲得較好的參數(shù)組合，獲得較好算法性能的目的。

關(guān)鍵詞：蟻群算法；參數(shù)設(shè)置；均勻設(shè)計

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）22-0179-03

Abstract：Ant colony algorithm has good effect in solving Traveling Salesman Problem（TSP）. But compared with the genetic algorithm optimization method， it has less systematic theoretical guidance. Especially in the parameter settings， people usually select appropriate parameter values based on experience or trial. Based on the analysis of the parameters influence on the performance of ant colony algorithm， in this paper， the uniform design method is adopted to set the parameters， TSP is taken as an example， MATLAB is used to simulate.The experimental results show that using uniform design to achieve the better parameter combination with less test and obtain the purpose of better algorithm performance.

Key words：ant colony algorithm； parameter settings； uniform design

1 概述

20世紀(jì)90年代，意大利學(xué)者Dorigo M等人提出通過模擬自然界螞蟻群體覓食行為的過程，來完成對問題求解的優(yōu)化算法，即蟻群算法（Ant Colony Algorithm， ACA）[1]。蟻群算法最先被應(yīng)用于解決旅行商問題（Traveling Salesman Problem， TSP），并取得了較理想的實驗結(jié)果。

蟻群算法的基本思想是在多個螞蟻并行尋找的可行路徑所構(gòu)成的解空間中搜索最優(yōu)解。這其中不可或缺的因素是信息素的釋放，它具有正反饋機(jī)制，可以使搜索過程不斷收斂，最終逼近最優(yōu)解[2]。但蟻群算法的收斂性能對參數(shù)的初始化設(shè)置比較敏感。從蟻群搜索最短路徑的機(jī)理不難看到，有關(guān)參數(shù)的選取直接影響到算法的收斂性和效率。選取合適的參數(shù)組合能夠讓算法收斂速度較快并避免陷入局部最優(yōu)解。但由于蟻群算法參數(shù)組合數(shù)目多，各參數(shù)之間具有關(guān)聯(lián)性，如何選取最優(yōu)的參數(shù)組合使得蟻群算法的性能最佳，目前尚沒有嚴(yán)格理論的支持。通常都是根據(jù)經(jīng)驗或反復(fù)試驗來選取合適的參數(shù)值?；诖?，國內(nèi)外許多學(xué)者在蟻群算法的參數(shù)分析和優(yōu)化組合方面進(jìn)行了大量的研究工作。Dorigo M等對m，ρ，α，β， Q 等主要參數(shù)做了初步的研究；Botee H M [3]等用遺傳算法來求出m，ρ，α，β等參數(shù)的最優(yōu)組合，但算法比較麻煩。段海濱等通過對參數(shù)選擇原則的數(shù)字仿真實驗分析，總結(jié)了一種"三步走"的有效方法來選擇最優(yōu)參數(shù)組合[4]。詹士昌[5]，葉志偉[6]、蔣玲艷[7]、徐紅梅[8]等也在蟻群算法的參數(shù)選擇方面進(jìn)行了研究。

本文對螞蟻數(shù)目m、信息素?fù)]發(fā)因子ρ、信息啟發(fā)式因子α、期望啟發(fā)式因子β、信息素強(qiáng)度Q等重要參數(shù)進(jìn)行研究，并采用均勻設(shè)計法[9]確定試驗方案，獲得算法參數(shù)設(shè)置的最佳組合。

2 蟻群算法的數(shù)學(xué)模型

3 基本蟻群算法的參數(shù)分析

3.1螞蟻數(shù)量m

在TSP中，單只螞蟻完成一次循環(huán)經(jīng)過的路徑是解空間中的一個解，m只螞蟻完成一次循環(huán)則會產(chǎn)生一個子集。顯然，m越大，子集越大，可以提高蟻群算法的全局搜索能力以及算法的穩(wěn)定性，但m過大時，會導(dǎo)致路徑上的信息素變化趨于平均，信息正反饋作用減弱，收斂速度減慢。反之，m越小，子集越小，特別TSP規(guī)模較大時，會使從未被搜索到的路徑上的信息素濃度趨近于0，雖然收斂速度加快，但會出現(xiàn)過早停滯現(xiàn)象。文獻(xiàn)[7]提出：當(dāng)m∈[0.6n， 0.9n]時（n為城市規(guī)模），蟻群算法的求解性能較好。在段海濱的“三步走”策略中，認(rèn)為當(dāng)螞蟻數(shù)目m約為城市規(guī)模n的2/3時，蟻群算法的全局收斂性和收斂速度都比較好。

3.2 信息素?fù)]發(fā)因子ρ

3.3 信息啟發(fā)因子α和期望啟發(fā)因子β

3.4 信息素強(qiáng)度Q

信息素強(qiáng)度Q是螞蟻完成一次循環(huán)在所經(jīng)過的路徑上所釋放的信息素總量。它使得算法在正反饋機(jī)制作用下以合理的速度搜索到全局最優(yōu)解。Q越大，在螞蟻已走過的路徑上信息素濃度的累積越快，正反饋作用會占主導(dǎo)地位，算法收斂速度快。但由于TSP的規(guī)模不同，路徑長度各不相同，Q的取值應(yīng)與TSP的規(guī)模相對應(yīng)，確保信息素總量更新在可控制范圍內(nèi)。

綜上，蟻群算法中各參數(shù)的作用是緊密耦合的，參數(shù)設(shè)置組合直接影響著算法的性能。

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

均勻設(shè)計是一種非常有效的多因素多水平試驗設(shè)計優(yōu)化方法，應(yīng)用到蟻群算法的多參數(shù)設(shè)置中，值得一試。

按照表3，因素個數(shù)為5，選取均勻表中的1、3、4、8、10列，將表1中m，α，β，ρ，Q5個因素水平分別放在對應(yīng)的表2的5列上面，得到試驗方案如表4所示。

表4中括號內(nèi)的數(shù)值表示初始參數(shù)的實際取值。對每個參數(shù)組合運(yùn)行15次，每次運(yùn)行的最大循環(huán)次數(shù)為500次，取15次試驗的平均值和最優(yōu)解所得的結(jié)果如表5所示。

從表5可以看出平均值最小為第9組（426.4738），最優(yōu)解的最低值出現(xiàn)在第2組（424.6354）。另第5組也取得較優(yōu)值。

分析以上3組參數(shù)組合，給出一組新的參數(shù)組合13：m=27，α=0.8，β=4.2，ρ=0.42，Q=1200。對第5組，第9組和第13組參數(shù)分別進(jìn)行15次試驗，將迭代次數(shù)設(shè)置為200，得出如表6所示的對比結(jié)果：

以上3組參數(shù)求出的最優(yōu)解相同（425.649），第13組參數(shù)的平均值最優(yōu)。結(jié)果如圖1、圖2、圖3所示。

5 結(jié)束語

蟻群算法中各參數(shù)的設(shè)置直接影響著算法的性能，本文以ACS為例，采用均勻設(shè)計法結(jié)合各參數(shù)較好取值范圍確定試驗方案，通過MATLAB仿真試驗，以較少的試驗次數(shù)獲得了較好的蟻群算法參數(shù)組合。

參考文獻(xiàn)：

[1]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents.IEEE Transaction on Systems， Man， and Cybernetics-Part B， 1996， 26（1）：29-41.

[2]郁磊，史峰，王輝，等.MATLAB智能算法30個案例分析[M].2版.北京：北京航空航天大學(xué)出版社，2015：205-206.

[3]Botee H M，Bonabeau E. Evolving ant colony optimization. Advances in Complex Systems，1998，1（2）：149-159.

[4]段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2005.

[5]詹士昌，徐婕. 蟻群算法中有關(guān)參數(shù)的最優(yōu)選擇[J].科技同報，2003，19（5）：381-386.

[6]葉志偉，鄭肇葆. 蟻群算法中參數(shù)α、β、ρ設(shè)置的研究[J].武漢大學(xué)學(xué)報，2004，29（7）：597-601.

[7]蔣玲艷，張軍，鐘樹鴻.蟻群算法的參數(shù)分析[J].計算機(jī)工程與應(yīng)用，2007，43（20）：31-36.

[8]徐紅梅，陳義保，劉加光，王燕濤.蟻群算法中參數(shù)設(shè)置的研究[J].山東理工大學(xué)學(xué)報，2008，22（1）：7-11 .

[9]方開泰. 均勻設(shè)計與均勻設(shè)計表[M]. 北京：科學(xué)出版社，1994.

[10]黃永青，梁昌勇，張祥德. 基于均勻設(shè)計的蟻群算法參數(shù)設(shè)定.控制與決策[J]，2006，21（1）：93-96.

[11]Dorigo M， Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation， 1997， 1（1）：53-66.