李 旭，汪海妹，劉家保，衛(wèi) 亮

(1．合肥學(xué)院數(shù)學(xué)與物理系，合肥 230601;2．安徽新華學(xué)院公共課程部，合肥 230088)

基于蟻群算法的旅游線路優(yōu)化研究*
——以合肥市為例

李 旭1，汪海妹1，劉家保2，衛(wèi) 亮1

(1．合肥學(xué)院數(shù)學(xué)與物理系，合肥 230601;2．安徽新華學(xué)院公共課程部，合肥 230088)

主要探討了蟻群算法在旅游優(yōu)化線路中的應(yīng)用;以合肥市為例，選取合肥市14個(gè)景點(diǎn)，在Matlab環(huán)境下應(yīng)用蟻群算法得到一條合肥一日游的優(yōu)化旅游線路，并給出相應(yīng)結(jié)果的簡(jiǎn)單分析．

蟻群算法;旅游;優(yōu)化;Matlab

現(xiàn)如今，旅游已成為一種時(shí)尚休閑方式，選擇合適的旅游線路，不僅可以節(jié)約交通時(shí)間，提高交通質(zhì)量，而且可以節(jié)省交通費(fèi)用．因此，如何尋找這樣一條最佳線路顯得尤為重要．至今，已有很多學(xué)者在這個(gè)方面做了大量的研究［1-3］．合肥作為一個(gè)發(fā)展中城市，旅游業(yè)正蓬勃發(fā)展，并以其獨(dú)具特色的自然風(fēng)景吸引了一大批的游客．現(xiàn)將一種優(yōu)化算法——蟻群算法［4，5］，應(yīng)用到合肥市旅游中，經(jīng)仿真后得到相關(guān)景點(diǎn)的一條優(yōu)化線路．

1 蟻群算法原理

螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱為信息素的物質(zhì)．在運(yùn)動(dòng)過(guò)程中螞蟻能感知這種物質(zhì)，并且以此引導(dǎo)螞蟻的運(yùn)動(dòng)方向．在螞蟻覓食過(guò)程中，由于螞蟻只對(duì)周圍一定環(huán)境內(nèi)有感知能力，當(dāng)在它的感知能力范圍以內(nèi)有食物時(shí)，它就直接過(guò)去;否則，則看信息素大小進(jìn)行移動(dòng)．若周圍沒(méi)有信息素作為信息時(shí)，螞蟻會(huì)按照原來(lái)自己運(yùn)動(dòng)的方向慣性運(yùn)動(dòng)下去．而有信息素時(shí)總會(huì)朝信息素多的方向走．當(dāng)螞蟻碰到一個(gè)還未經(jīng)過(guò)的路口時(shí)，它們會(huì)隨機(jī)挑一條道路行走下去，在這過(guò)程中，它本身也會(huì)釋放信息素．而釋放的信息素強(qiáng)度則與路徑長(zhǎng)度有關(guān)，路徑越長(zhǎng)，釋放的信息素濃度越低．于是后來(lái)的螞蟻在經(jīng)過(guò)這個(gè)路口時(shí)，總是會(huì)選擇信息素強(qiáng)度高的路徑．那么即使一開(kāi)始每條路徑上的螞蟻數(shù)量是一樣的，在經(jīng)過(guò)多只螞蟻反復(fù)的選擇后，道路短的路徑上的信息素強(qiáng)度積累比較高，因此最后所有的螞蟻都趨向于選擇該條路徑了，最終整個(gè)蟻群會(huì)找出最優(yōu)路徑．

2 蟻群算法的實(shí)現(xiàn)

1)參數(shù)初始化．設(shè)置最大循環(huán)次數(shù)Ncmax(即有Ncmax批螞蟻)，在有向圖E上，將m個(gè)螞蟻置于n個(gè)城市點(diǎn)上，令有向圖上每條邊(i，j)的初始化信息量τij(t)=const，其中const表示常數(shù)，且初始時(shí)刻Δτij(0)=0．

2)下一步可以前往的節(jié)點(diǎn)．記tabuk為禁忌表，用它記錄螞蟻k當(dāng)前所走過(guò)的景點(diǎn)城市集合，該集合隨著tabuk進(jìn)化過(guò)程作動(dòng)態(tài)調(diào)整，直到所有的城市放入到禁忌表中．下一步該走的路從未走過(guò)的景點(diǎn)中取，螞蟻個(gè)體根據(jù)式(1)計(jì)算的概率選擇下一個(gè)城市j并前進(jìn)，j∈{E－tabuk}，

其中，allowedk表示螞蟻下一步可選擇的城市;τij(t)表示信息素函數(shù);α為信息啟發(fā)式因子，表明信息素的相對(duì)重要性;ηij(t)為啟發(fā)函數(shù)，通常取ηij(t)=1/dij，表明距離越短，螞蟻選擇該路徑的可能性越大;β為期望啟發(fā)式因子，表示了啟發(fā)信息的受重視程度．

3)狀態(tài)更新和記錄．螞蟻移動(dòng)到新的城市，路徑長(zhǎng)度增加，修改禁忌表，一次循環(huán)后得到一條路徑．

4)記錄迭代中每一只螞蟻的覓食路線和路線長(zhǎng)度．

5)更新信息素．螞蟻?zhàn)哌^(guò)的路徑上的信息素會(huì)增強(qiáng)，信息素按照式(2)(3)(4)更新如下:

在這里，ρ表示信息素?fù)]發(fā)系數(shù)，Δτij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量表示第k只螞蟻經(jīng)過(guò)城市(i，j)使之增加的信息素量．

6)作最短路徑的閉合圖，輸出最終結(jié)果(最優(yōu)解)．

另外，其流程圖如圖1所示．

圖1 基本蟻群算法程序流程圖

3 蟻群算法在合肥市旅游交通中的應(yīng)用

3．1 數(shù)據(jù)的預(yù)處理

針對(duì)合肥市14個(gè)主要旅游景點(diǎn)(分別是1．徽?qǐng)@2．逍遙津3．省博物館4．李鴻章故居5．植物園6．海洋公園7．大蜀山8．包河公園9．歡樂(lè)島10．明教寺11．花沖公園12．瑤海公園13．環(huán)城公園14．杏花公園)的旅游線路進(jìn)行研究．

3．2 算法的結(jié)果

在求解旅游景點(diǎn)之間最優(yōu)的旅游路線時(shí)，必須要得到景點(diǎn)之間的兩兩距離．查閱相關(guān)資料得到這些景點(diǎn)的經(jīng)緯度坐標(biāo)，景點(diǎn)之間的相互距離可以根據(jù)式(5)和式(6)計(jì)算得出．

其中X(i)，Y(i)分別表示景點(diǎn)i的緯度與經(jīng)度的坐標(biāo);X(j)，Y(j)是j點(diǎn)的緯度與經(jīng)度的坐標(biāo);R是地球半徑．在Matlab仿真中，設(shè)置初始螞蟻數(shù)m=14，最大循環(huán)次數(shù)為nmax=50，信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=10，信息素?fù)]發(fā)系數(shù)ρ=0．6．經(jīng)仿真計(jì)算可得最優(yōu)路徑長(zhǎng)度是46．725 km，其最優(yōu)路徑對(duì)應(yīng)的序號(hào)如表1所示，Matalb仿真結(jié)果見(jiàn)圖2．由上可知，計(jì)算得到的最優(yōu)路徑為瑤海公園→李鴻章故居→逍遙津→明教寺→包河公園→環(huán)城公園→省博物館→杏花公園→大蜀山→植物園→海洋公園→徽?qǐng)@→歡樂(lè)島→花沖公園，且路線總長(zhǎng)為46．725 km．

但在實(shí)際生活中，由于一個(gè)城市的交通道路錯(cuò)綜復(fù)雜，兩地之間通常不會(huì)直線到達(dá)，因此這種由經(jīng)緯度坐標(biāo)得到的距離，比較理想化，在運(yùn)用到實(shí)際中時(shí)會(huì)失去其現(xiàn)實(shí)意義．故下面介紹一種比較合理的距離，并運(yùn)用到線路優(yōu)化中．根據(jù)統(tǒng)計(jì)資料收集得到這14個(gè)景點(diǎn)之間的最短行徑距離，經(jīng)Matlab仿真計(jì)算可得最優(yōu)路徑長(zhǎng)度是65．48 km，其最優(yōu)路徑對(duì)應(yīng)的序號(hào)如表2所示，Matalb仿真結(jié)果見(jiàn)圖3．

表1 最優(yōu)路徑對(duì)應(yīng)的序號(hào)(根據(jù)經(jīng)緯度)

表2 最優(yōu)路徑對(duì)應(yīng)的序號(hào)(根據(jù)行徑距離)

可以看到，最優(yōu)路徑是省博物館→杏花公園→李鴻章故居→逍遙津→明教寺→包河公園→環(huán)城公園→花沖公園→瑤海公園→植物園→大蜀山→徽?qǐng)@→海洋公園→歡樂(lè)島，距離為68．45 km．

由此看到，與前一種方法相比，雖然最優(yōu)路徑距離由46．725 km變?yōu)榱?8．45 km，但考慮實(shí)際情況，最終采用68．45 km作為合肥一日游的最優(yōu)路徑的距離，這更為貼近真實(shí)的最優(yōu)線路長(zhǎng)度．

圖2 最優(yōu)路徑的圖形(根據(jù)經(jīng)緯度)

圖3 最優(yōu)路徑的圖形(根據(jù)行徑距離)

4 結(jié)語(yǔ)

蟻群算法魯棒性強(qiáng)，適應(yīng)性好，易與其他算法相結(jié)合［7］，在數(shù)據(jù)挖掘、聚類分析等方面都有所應(yīng)用．將蟻群算法運(yùn)用到合肥市的旅游線路優(yōu)化之中，簡(jiǎn)單易懂，且蟻群算法在求解景點(diǎn)比較少時(shí)運(yùn)行速度也非?？?，體現(xiàn)了其在求解復(fù)雜優(yōu)化問(wèn)題上的優(yōu)越性．得到的結(jié)果對(duì)實(shí)際旅游線路的選擇具有一定的指導(dǎo)意義．

［1］徐秀花，程曉錦，寇怡．蟻群算法在旅游交通線路中的應(yīng)用［J］．北京印刷學(xué)院，2013，21(2):48-50

［2］張紀(jì)會(huì)．自適應(yīng)蟻群算法［J］．控制理論與應(yīng)用，2000，17(1):1-3

［3］聶雷剛，李詠梅，余元惠．基于聚類分析算法的智能旅游規(guī)劃［J］．電腦開(kāi)發(fā)與應(yīng)用，2011，25(2):28-30

［4］COLORNI A，DORIGO M，MANIEZZO V．Distributed Optimization by Antcolonies［C］//Proc of 1st European Conf Artificial Life．Pans France:Elsevier，1991

［5］GLOVER F．Tabu Search［J］．ORSA Journal on Computing，1989，1(3):899-1499

［6］段海濱．蟻群算法原理及其應(yīng)用［M］．北京:科學(xué)出版社，2005

［7］成偉．蟻群算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)辨識(shí)混沌系統(tǒng)［J］．重慶工商大學(xué):自然科學(xué)版，2009，26(2):156-161

Research on Tour Route Optimization Based on Ant Swarm Algorithm——Taking Hefei City as an Example

LI Xu1，WANG Hai-mei1，LIU Jia-bao2，WEI Liang1
(1．Department of Mathematics and Physics，Hefei University，Hefei 230601，China; 2．Department of General Course Teaching，Xinhua University，Anhui Hefei 230088，China)

This paper mainly discusses the application of ant swarm algorithm to tour route optimization，obtains an optimized tour route for a daily tour in Hefei City based on ant swarm algorithm under matlab environment taking an example of selecting 14 scenic spots in Hefei City and gives the corresponding brief analysis．

ant swarm algorithm;tour;optimization;matlab

U121

A

1672－058X(2015)02－0067－04

10．16055/j．issn．1672－058X．2015．0002．014

責(zé)任編輯:田 靜

校 對(duì):李翠薇

2014－05－10;

2014－07－12．

大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目(201311059068);合肥學(xué)院自然科學(xué)研究項(xiàng)目(13KY04ZR)．

李旭(1982－)，男，安徽六安人，碩士，助教，從事智能算法理論及應(yīng)用研究．