蟻群算法解決CTSP問題的參數(shù)設(shè)置研究*

楊　惠　韓李濤,2　類延輝　鄭　瑩　吳佳怡

(1.山東科技大學(xué)測繪科學(xué)與工程學(xué)院　青島　266590)(2.海島(礁)測繪技術(shù)國家測繪局重點(diǎn)實(shí)驗(yàn)室　青島　266590)(3.河北建筑工程學(xué)院　張家口　075000)

?

蟻群算法解決CTSP問題的參數(shù)設(shè)置研究*

楊惠1韓李濤1,2類延輝1鄭瑩3吳佳怡1

(1.山東科技大學(xué)測繪科學(xué)與工程學(xué)院青島266590)(2.海島(礁)測繪技術(shù)國家測繪局重點(diǎn)實(shí)驗(yàn)室青島266590)(3.河北建筑工程學(xué)院張家口075000)

摘要由于蟻群算法中參數(shù)較多,設(shè)置不同的參數(shù)值對(duì)計(jì)算結(jié)果的影響很大,目前在參數(shù)設(shè)置方面尚缺乏足夠的理論基礎(chǔ)。對(duì)蟻群算法的基本原理及CTSP問題的解決進(jìn)行了詳細(xì)介紹,重點(diǎn)討論分析了蟻群算法中的各個(gè)參數(shù)對(duì)其性能的影響以及參數(shù)的合理設(shè)置,并嘗試采用參數(shù)循環(huán)組合的枚舉方式對(duì)CTSP問題進(jìn)行了求解,獲得了更優(yōu)的計(jì)算結(jié)果。

關(guān)鍵詞蟻群算法; 中國旅行商問題; 參數(shù)設(shè)置

Class NumberTP301.6

1引言

蟻群算法是由意大利學(xué)者M(jìn). Dorigo等于20世紀(jì)90年代提出的一種新型的模擬進(jìn)化算法,它具有正反饋性、并行性、分布式、魯棒性等特點(diǎn)[1]。蟻群算法通過模擬螞蟻尋找食物源的過程,利用其巧妙的搜索機(jī)制,在一系列復(fù)雜的組合優(yōu)化問題求解中取得了很多成果。M. Dorigo等還將蟻群算法應(yīng)用于解決經(jīng)典的旅行商問題(TSP),并且得到了令人滿意的計(jì)算結(jié)果[2]。蟻群算法這種來自生物界的智能仿生算法已經(jīng)在交通、電力、通信等很多方面表現(xiàn)出相當(dāng)好的性能,具有很大的發(fā)展?jié)摿Α?/p>

由于蟻群算法的參數(shù)空間范圍很大,各參數(shù)之間的關(guān)聯(lián)性十分緊密且沒有明確的規(guī)律,找到最優(yōu)的參數(shù)組合,使蟻群算法的各方面性能都達(dá)到最優(yōu)是一個(gè)極其復(fù)雜的問題,這也是蟻群算法的重要研究方向。目前,蟻群算法的參數(shù)設(shè)置尚沒有完善的理論依據(jù)和具體方法,通常人們都是讓一個(gè)參數(shù)變化,另外幾個(gè)參數(shù)固定不變的方法來對(duì)參數(shù)進(jìn)行選擇,顯然這種方法忽略了參數(shù)之間的相互耦合。本文將蟻群算法應(yīng)用于解決中國旅行商問題(Chinese TSP,CTSP),并通過實(shí)驗(yàn)對(duì)參數(shù)設(shè)置進(jìn)行研究,以求出更好的結(jié)果。

2蟻群算法求解TSP問題

2.1蟻群算法基本原理

生物學(xué)家研究發(fā)現(xiàn),像螞蟻這種視盲動(dòng)物是很難獨(dú)立完成覓食的,自然界中的螞蟻覓食是一種群體性的行為。螞蟻在尋找食物源時(shí)會(huì)集體行動(dòng),每只螞蟻在它經(jīng)過的路徑上釋放一定量的信息素,并且能夠檢測其他螞蟻釋放的信息素。通常,螞蟻會(huì)優(yōu)先選擇信息素濃度較高的路線移動(dòng),并釋放自身的信息素,這就會(huì)增加該條路徑上的信息素濃度,形成了正反饋現(xiàn)象,即信息素濃度強(qiáng)的路徑更強(qiáng),信息素濃度弱的則更弱。隨著越來越多的螞蟻通過該條路徑,最終螞蟻能夠找到一條從巢穴到食物源的最短路徑。同時(shí)人們發(fā)現(xiàn),螞蟻所釋放的信息素會(huì)隨著時(shí)間的推遲而逐漸減少。具體蟻群系統(tǒng)的工作原理見文獻(xiàn)[3]。

2.2蟻群算法解決TSP問題基本原理

螞蟻的數(shù)量設(shè)為m,城市的數(shù)量設(shè)為n,城市i與城市j之間的距離設(shè)為dij(i,j=1,2,…,n),t時(shí)刻在城市i與城市j之間路徑上的信息素濃度用τij(t)表示。各個(gè)城市間連接路徑上的初始信息素濃度相同,可設(shè)為τij(0)=τ0。

(1)

螞蟻在釋放信息素的過程中,兩兩城市間連接路徑上的信息素濃度也在逐漸衰減,信息素的揮發(fā)程度用參數(shù)ρ(0<ρ<1)表示。因此,當(dāng)所有螞蟻完成一次路徑循環(huán)后,各個(gè)城市間連接路徑上的信息素濃度需要根據(jù)式(2)進(jìn)行實(shí)時(shí)更新,即

(2)

針對(duì)螞蟻釋放信息素問題,M. Dorigo等曾給出三種不同的模型[2],分別稱之為Ant Cycle System,Ant Quantity System,Ant Density System,其計(jì)算公式如下:

1) Ant Cycle System模型

(3)

其中,Q是一個(gè)常數(shù),表示螞蟻沿路徑循環(huán)一次所釋放的信息素總量;Lk為第k只螞蟻經(jīng)過路徑的長度。

2) Ant Quantity System模型

(4)

3) Ant Density System模型

(5)

在以上三種模型中,Ant Cycle System模型利用螞蟻搜索過的路徑總長計(jì)算路徑上的信息素濃度;Ant Quantity System模型則利用螞蟻經(jīng)過各個(gè)城市間的距離計(jì)算路徑上的信息素濃度;而Ant Density System模型則將螞蟻釋放的信息素濃度值取為恒值,沒有考慮到不同螞蟻經(jīng)過路徑長短的影響。所以,一般都選用Ant Cycle System模型計(jì)算螞蟻釋放在路徑上的信息素濃度,這個(gè)模型表示螞蟻經(jīng)過的路徑長度越短,路徑上的信息素濃度越高[4]。

2.3蟻群算法解決CTSP問題的基本步驟

蟻群算法解決CTSP問題一般需要以下幾個(gè)步驟:計(jì)算城市間相互距離、設(shè)定初始化參數(shù)、構(gòu)建解空間、更新信息素和判斷是否終止,具體如圖1所示。

1) 計(jì)算城市間相互距離:依據(jù)31個(gè)城市的位置坐標(biāo),計(jì)算兩兩城市之間的相互距離,得到對(duì)稱的距離矩陣。

2) 初始化參數(shù):對(duì)相關(guān)的參數(shù)進(jìn)行初始化,如螞蟻數(shù)量m、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素?fù)]發(fā)因子ρ、信息素釋放總量Q、最大迭代次數(shù)iter_max,迭代次數(shù)初值iter=1。

3) 構(gòu)建解空間:將多個(gè)螞蟻隨機(jī)放置在不同的城市作為出發(fā)點(diǎn),對(duì)每個(gè)螞蟻計(jì)算其下一個(gè)待訪問的城市,直到所有螞蟻訪問完所有的城市。

圖1　蟻群算法解決CTSP問題基本步驟流程圖

4) 更新信息素:計(jì)算各個(gè)螞蟻經(jīng)過的路徑長度Lk(k=1,2,…,m),記錄當(dāng)前迭代次數(shù)中的最優(yōu)解。同時(shí)根據(jù)式(2)和式(3)對(duì)各個(gè)城市連接路徑上的信息素濃度進(jìn)行更新。

5) 判斷是否終止:若iter

3參數(shù)設(shè)置分析

3.1參數(shù)設(shè)置對(duì)其性能的影響

在蟻群算法中,螞蟻數(shù)目m、信息啟發(fā)式因子α、期望啟發(fā)式因子β、信息素?fù)]發(fā)因子ρ、信息素強(qiáng)度Q等參數(shù)的設(shè)置及不同的組合,都會(huì)對(duì)蟻群算法的求解性能、計(jì)算效率和結(jié)果的精度產(chǎn)生影響。蟻群算法的參數(shù)空間范圍很大,而且各參數(shù)之間的關(guān)聯(lián)性復(fù)雜,沒有明確的規(guī)律可尋,因此找到最優(yōu)的參數(shù)組合,使蟻群算法的穩(wěn)定性、收斂性、正反饋性等性能達(dá)到最佳,使算法的計(jì)算結(jié)果達(dá)到最優(yōu),這是一個(gè)極其困難的問題,也是蟻群算法研究的重要部分[5]。

1) 螞蟻數(shù)目對(duì)算法性能的影響

蟻群算法具有并行性的特點(diǎn),即每個(gè)螞蟻可以按照自己的規(guī)則在同一時(shí)刻內(nèi)同時(shí)行動(dòng),所以當(dāng)螞蟻數(shù)目增多時(shí),蟻群算法的全局搜索能力及穩(wěn)定性會(huì)增強(qiáng),但當(dāng)螞蟻的數(shù)目繼續(xù)增加到某個(gè)值后,之前被搜索過的路徑上的信息素濃度變化將會(huì)趨于某個(gè)定值,信息的正反饋?zhàn)饔脺p小,算法的收斂速度變慢;反之,當(dāng)螞蟻數(shù)目減小時(shí),算法搜索的隨機(jī)性會(huì)降低,此時(shí)雖然收斂速度加快,但也降低了算法的全局收斂性能,算法的穩(wěn)定性變差,算法運(yùn)行結(jié)果會(huì)出現(xiàn)過早停滯現(xiàn)象[6]。

2) 啟發(fā)式因子對(duì)算法性能的影響

在螞蟻的運(yùn)動(dòng)過程中,啟發(fā)式因子α反映路徑上累積的信息素濃度在蟻群搜索機(jī)制中的相對(duì)重要程度,它的值越大,則螞蟻選擇之前走過的路徑的概率越大,這就會(huì)減弱蟻群搜索的隨機(jī)性;反之,當(dāng)啟發(fā)式因子α值過小時(shí),則容易使蟻群的路徑搜索過早陷入局部最優(yōu)解,最終可能找到的這條路徑并非是最優(yōu)路徑[7]。

3) 期望啟發(fā)因子對(duì)算法性能的影響

在引導(dǎo)蟻群搜索的過程中,期望啟發(fā)因子β代表啟發(fā)式信息的相對(duì)重要程度。在整個(gè)蟻群尋優(yōu)過程中,β的大小反映了算法的先驗(yàn)性和確定性因素這二者的作用強(qiáng)度,β越大,在某個(gè)局部點(diǎn)上螞蟻選擇局部最短路徑的概率越大,算法更容易陷入局部最優(yōu),從而收斂到一些并不高明的解上。

4) 信息素?fù)]發(fā)因子對(duì)算法性能的影響

信息素?fù)]發(fā)因子ρ表示信息素的揮發(fā)程度,它的取值直接影響到蟻群算法的全局搜索能力和收斂速度。當(dāng)ρ較大時(shí),之前搜索過的路徑再次被選擇的可能性增大,這對(duì)算法的隨機(jī)性和全局搜索能力都產(chǎn)生不利影響。而當(dāng)ρ較小時(shí)對(duì)算法的影響具有兩面性,一方面,未被搜索過的路徑上的信息量將迅速減少,減小了算法的搜索空間,使算法容易陷入局部最優(yōu)解;另一方面,之前被搜索路徑上的信息素增量減小,這使得搜索空間增大,算法陷入局部最優(yōu)的概率減小,同時(shí)降低了算法的收斂性[8]。

5) 信息素強(qiáng)度對(duì)算法性能的影響

在Ant Cycle System模型中,信息素強(qiáng)度用Q表示,它反映了螞蟻沿路徑循環(huán)一周釋放的信息素總量。當(dāng)Q的值越大,算法的收斂性會(huì)越高,同時(shí)由于反饋性加強(qiáng),使得螞蟻的搜索空間減小,算法陷入局部最優(yōu)的概率也會(huì)增大。

3.2參數(shù)設(shè)置對(duì)求解精度的影響

目前關(guān)于蟻群算法的參數(shù)設(shè)置,理論成果較為稀少,主要是靠經(jīng)驗(yàn)和實(shí)驗(yàn)來設(shè)定的[9]。蟻群算法中Ant Cycle System模型應(yīng)用最多,以此為例,其參數(shù)設(shè)定最好的經(jīng)驗(yàn)結(jié)果為0≤α≤5;0≤β≤5;0.1≤ρ≤0.99;10≤Q≤10000[10]。此時(shí)給出的參數(shù)建議只是一個(gè)范圍,為了獲得最優(yōu)求解結(jié)果,仍然需要在各個(gè)參數(shù)的建議取值范圍內(nèi)為每個(gè)參數(shù)設(shè)定確定的值。

在CTSP問題中,通常人們采用的策略是先確定參數(shù)重要性,然后按照重要性次序依次讓一個(gè)參數(shù)變化,其他參數(shù)固定的方法來對(duì)參數(shù)進(jìn)行選擇[11～12],這種方法忽略了參數(shù)之間的耦合,求解出的最優(yōu)路徑長度不能保證是最短路徑,如文獻(xiàn)[4]的最優(yōu)結(jié)果是15601.9195。

為了消除各個(gè)參數(shù)之間可能存在的非獨(dú)立耦合關(guān)系,本文嘗試采用循環(huán)組合的枚舉方式進(jìn)行最優(yōu)結(jié)果求解,即在蟻群算法解決CTSP的基礎(chǔ)上,按照5≤m≤50,0≤α≤5,0≤β≤5,0.1≤ρ≤0.5,1≤Q≤10000由外到里的順序逐層循環(huán)嵌套。通過做大量的參數(shù)循環(huán)計(jì)算,本文找到了比文獻(xiàn)[4]更優(yōu)的CTSP路徑。表1是本文方法某次循環(huán)執(zhí)行獲得的最好計(jì)算結(jié)果以及對(duì)應(yīng)的參數(shù)設(shè)置、迭代次數(shù)和最短路徑。從該表中可以發(fā)現(xiàn),在該組參數(shù)的設(shè)定下,不僅取得了更優(yōu)的結(jié)果,而且迭代次數(shù)也更少一些,算法的收斂速度更快。

表1　測試結(jié)果比較

圖2中可以清晰看到,本文方法所得到的最優(yōu)路徑的距離更短。圖3可以發(fā)現(xiàn)隨著迭代次數(shù)的增加,最短距離與平均距離均呈不斷下降的趨勢,直到最短距離不再變化時(shí),說明已找到最優(yōu)路徑。而本文方法達(dá)到最佳路徑時(shí)的迭代次數(shù)也相對(duì)少一些。

圖2　本文方法與文獻(xiàn)[4]方法獲取的最優(yōu)化路徑對(duì)比

圖3　本文方法和文獻(xiàn)[4]方法的各代最短距離與平均距離對(duì)比

通過對(duì)比可見,參數(shù)的設(shè)置對(duì)于路徑的長度和迭代次數(shù)都會(huì)產(chǎn)生重要影響,只讓一個(gè)參數(shù)變化,其他參數(shù)固定的策略對(duì)參數(shù)進(jìn)行選擇,顯然還不夠合理,通過多層循環(huán)嵌套能夠得出最優(yōu)化的結(jié)果。

4結(jié)語

蟻群算法的參數(shù)設(shè)置通常都是根據(jù)經(jīng)驗(yàn)或?qū)嶒?yàn)反復(fù)試湊,或者通過讓一個(gè)參數(shù)變化,另外幾個(gè)參數(shù)固定不變的方法來選擇參數(shù),這顯然無法使蟻群算法的收斂性和計(jì)算效率達(dá)到最優(yōu)。在蟻群算法解決CTSP問題的過程中,本文對(duì)參數(shù)的設(shè)置進(jìn)行實(shí)驗(yàn)分析,從蟻群算法參數(shù)之間的非獨(dú)立性出發(fā),通過多層循環(huán)策略找到了一個(gè)更優(yōu)化的結(jié)果,

為蟻群算法求解TSP問題相關(guān)研究提供了參考。當(dāng)然,本文方法運(yùn)算量較大,如何在保證計(jì)算精度的前提下減小運(yùn)算量是后續(xù)研究的重點(diǎn)。

參 考 文 獻(xiàn)

[1] Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies[C]//Dorigo M. Proceedings of the 1st European Conference on Artificial Life. Paris: Elsevier Publishing,1991:134-42.

[2] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems, Man, and Cybernetics-Part B,1996,26(1):29-41.

[3] 郭倩倩.蟻群算法的改進(jìn)及其在車輛路徑問題中的應(yīng)用[D].成都:西南交通大學(xué),2007:9-11.

GUO Qianqian. Improvement of Ant Colony Algorithm and Its Application in Vehicle Routing Problem[D]. Chengdu: Southwest Jiaotong University,2007:9-11.

[4] 史峰,王輝,郁磊,等.智能算法30個(gè)案例分析[M].北京:北京航空航天大學(xué)出版社,2011:206-215.

SHI Feng, WANG Hui, YU Lei, et al. 30 Case Analysis of Intelligent Algorithm[M]. Beijing: Beihang University Press,2011:206-215.

[5] 王軍.蟻群算法求解TSP時(shí)參數(shù)設(shè)置的研究[J].科學(xué)技術(shù)與工程,2007,7(17):4501-4503.

WANG Jun. Study on the Parameter Setting of TSP with Ant Colony Algorithm[J]. Science, Technology and Engineering,2007,7(17):4501-4503.

[6] 葉志偉,鄭肇葆.蟻群算法中參數(shù)α、β、ρ設(shè)置的研究——以TSP問題為例[J].武漢大學(xué)學(xué)報(bào),2004,29(7):597-600.

YE Zhiwei, ZHENG Zhaobao. Setting Parameter Research of α、β、ρ in Ant Colony Algorithm — Take the TSP Problem as an Example[J]. Journal of Wuhan University,2004,29(7):597-600.

[7] 徐紅梅,陳義保,劉加光,等.蟻群算法中參數(shù)設(shè)置的研究[J].山東理工大學(xué)學(xué)報(bào),2008,22(1):7-11.

XU Hongmei, CHEN Yibao, LIU Jiaguang, et al. Study on Parameter Setting in Ant Colony Algorithm[J]. Journal of Shandong University of Technology,2008,22(1):7-11.

[8] 杜衡吉,李勇.蟻群算法中參數(shù)設(shè)置對(duì)其性能影響的研究[J].現(xiàn)代計(jì)算機(jī),2012,5:3-7.

DU Jiheng, LI Yong. Study on the Effect of Parameter Setting on the Performance of Ant Colony Algorithm[J]. Modern Computer,2012,5:3-7.

[9] 李敏,吳浪,張開碧.求解旅行商問題的幾種算法的比較研究[J].重慶郵電大學(xué)學(xué)報(bào),2008,20(5):624-626.

LI Min, WU Lang, ZHANG Kaibi. Comparison of Several Algorithms for Solving Traveling Salesman Problem[J]. Journal of Chongqing University of Posts and Telecommunications,2008,20(5):624-626.

[10] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005:100-114.

DUAN Haibin. Principle and Application of Ant Colony Algorithm[M]. Beijing: Science Press,2005:100-114.

[11] 李明海,邢桂華.用Matlab實(shí)現(xiàn)中國旅行商問題的求解[J].微計(jì)算機(jī)應(yīng)用,2004,25(2):218-222.

LI Minghai, XING Guihua. Solving the Problem of Chinese Traveling Salesman with MATLAB[J]. Micro Computer Application,2004,25(2):218-222.

[12] 燕忠,袁春偉.用蟻群優(yōu)化算法求解中國旅行商問題[J].電路與系統(tǒng)學(xué)報(bào),2004,9(3):122-126.

YAN Zhong, YUAN Chunwei. Solving the Chinese Traveling Salesman Problem with Ant Colony Optimization Algorithm[J]. Journal of Circuits and Systems,2004,9(3):122-126.

Parameters Setting of Ant Colony Algorithm for CTSP Problem

YANG Hui1HAN Litao1,2LEI Yanhui1ZHENG Ying3WU Jiayi1

(1. Geomatics College, Shandong University of Science and Technology, Qingdao266590)(2. Key Laboratory of Surveying and Mapping Technology on Island and Reed, SBSM, Qingdao266590)(3. Hebei Institute of Civil Engineering, Zhangjiakou075000)

AbstractThere are many parameters in the ant colony algorithm, and setting of different parameter values has a great influence on the calculation results. At present adequate theoretical basis is short in terms of parameter setting. In this paper, the basic principle of ant colony algorithm and the solution of CTSP problem are introduced in detail. It also emphatically discusses and analyzes the influence of various parameters on ant colony algorithm and setting the rational parameters. The enumerate method of parametric loop combination is used to solve the CTSP problem and a better result is obtained.

Key Wordsant colony algorithm, CTSP, parameter setting

* 收稿日期:2015年11月7日,修回日期:2015年12月24日

基金項(xiàng)目:國家自然科學(xué)基金項(xiàng)目(編號(hào):41201381);山東省“泰山學(xué)者”建設(shè)工程專項(xiàng)經(jīng)費(fèi)項(xiàng)目資助。

作者簡介:楊惠,女,碩士研究生,研究方向:地理信息系統(tǒng)應(yīng)用與研發(fā)。韓李濤,男,博士,副教授,碩士生導(dǎo)師,研究方向:海洋測繪、路徑規(guī)劃。類延輝,女,碩士研究生,研究方向:室內(nèi)定位。鄭瑩,女,碩士,講師,研究方向:制圖綜合。吳佳怡,女,碩士研究生,研究方向:室內(nèi)GIS。

中圖分類號(hào)TP301.6

DOI:10.3969/j.issn.1672-9722.2016.05.003