周茂杰，張翠

（1.桂林理工大學(xué)，桂林 541004；2.桂林理工大學(xué)博文管理學(xué)院，桂林 541004）

0 引言

近年來，國家對旅游信息化發(fā)展高度重視，相繼出臺了《關(guān)于促進(jìn)智慧旅游發(fā)展的指導(dǎo)意見》、《關(guān)于實(shí)施“旅游+互聯(lián)網(wǎng)”行動計劃的通知》、《關(guān)于促進(jìn)旅游業(yè)與信息化融合發(fā)展的若干意見》等一系列重大政策，利用通訊、信息技術(shù)與旅游業(yè)的結(jié)合，建立智慧旅游產(chǎn)業(yè)。隨著人們的生活水平不斷提高，旅游成為人民幸福生活新指標(biāo)，隨著旅游消費(fèi)升級，游客更需要個性化的旅游產(chǎn)品。在信息化時代，游客需要更加豐富、多元的旅游服務(wù)信息，在外出旅游時，通過各類數(shù)據(jù)信息進(jìn)行自主選擇意識也不斷增強(qiáng)[1]。對于游客而言，合理、舒適、節(jié)約的旅游線路是提升旅行體驗(yàn)的重要標(biāo)準(zhǔn)。智能線路規(guī)劃可以為游客推薦合理的個性化旅游線路，既節(jié)約時間，又減少花銷，可以改善旅游體驗(yàn)，提升旅游目的地的形象，對促進(jìn)當(dāng)?shù)芈糜螛I(yè)的可持續(xù)發(fā)展，實(shí)現(xiàn)旅游服務(wù)智慧化具有重要意義。

旅游線路規(guī)劃要考慮交通網(wǎng)絡(luò)、個人喜好、時間成本和金錢成本等因素。首先，游客可以在各類網(wǎng)站查詢到各類景點(diǎn)及景點(diǎn)間的可達(dá)線路，然后，要確定在各景點(diǎn)間的游覽順序、游覽時間，在兩點(diǎn)間選擇和某種交通方式出行。旅游線路規(guī)劃系統(tǒng)要為游客提供個性化的旅游線路，并對出游時間進(jìn)行合理安排，根據(jù)現(xiàn)有條件，設(shè)計出游客的旅游費(fèi)用支出、時間花費(fèi)較少的線路，是一個在多個約束條件下的組合優(yōu)化問題，本文擬采用蟻群算法解決此問題，并對蟻群算法進(jìn)行改進(jìn)，達(dá)到路徑選擇的優(yōu)化效果。

1 蟻群算法原理

20世紀(jì)90年代初期，意大利學(xué)者M(jìn).Dorigo，V.Ma?niezzo等人首次提出蟻群算法（Ant Colony Algorithm，縮寫為ACO）。蟻群算法是一種仿生進(jìn)化算法，具有種群的啟發(fā)功能，專家們通過模擬自然界中真實(shí)蟻群集體覓食行為得到本算法[2-3]。

單個螞蟻選擇路徑具有隨機(jī)性，但蟻群中的螞蟻根據(jù)一種稱之為信息素的指示信息從巢穴到食物源尋找到最短路徑[4-6]。一群螞蟻尋找食物源時，一只螞蟻?zhàn)哌^某條路時會在經(jīng)過的路留下信息素，后面的螞蟻可以感知信息素，并根據(jù)信息的濃度大小，在所有可以到達(dá)食物源的路徑中逐個比較，最后選擇一條最短路徑，同時在自己走過時也釋放信息素。具體的方法是：對比兩點(diǎn)間各條可達(dá)路徑上的信息素的濃度，當(dāng)某條路徑的信息素濃度比其他的路徑的信息素濃度都要大時，螞蟻選擇這條路徑的概率就大，反之螞蟻選擇信息素濃度小的路徑概率就小。同時，螞蟻在走過某條路時會再次留下信息素，所有的信息素會隨著時間的推移不斷揮發(fā)，這樣一來，螞蟻選擇信息素濃度大的路徑的概率大，走的螞蟻數(shù)量多了后留下的信息素也有所增大。信息素濃度小的路徑螞蟻選擇的概率小，所以走過此路徑的螞蟻數(shù)量少，留下的信息也在減少，隨著信息素的不斷揮發(fā)，螞蟻選擇此路徑的概率越來越小。經(jīng)過多次迭代，螞蟻依據(jù)信息素濃度選擇，最后可以選擇出一條最短路徑，實(shí)現(xiàn)線路的優(yōu)化選擇。

蟻群算法的原理是根據(jù)信息素的濃度進(jìn)行路經(jīng)選擇。首先，在n個城市里隨機(jī)放置m只螞蟻，位于某個城市i的第k只螞蟻選擇下一個城市j的概率為Pk（i,j），可以表示為：

其中：

τ(i,j)是兩個城市i和j間信息素濃度，概率與信息度成正比；

η(i,j)=1/d(i,j)是一個啟發(fā)信息，d（i,j）表示城市 i和j間的距離，啟發(fā)信息與兩點(diǎn)間距離成反比；

α和β為信息啟發(fā)因子，反映了信息素與啟發(fā)信息的重要性；

tabuk表示螞蟻k已經(jīng)訪問過的城市列表，也稱之為禁忌列表。

螞蟻按照概率選擇的方法選擇路徑對所有城市進(jìn)行遍歷，完成遍歷后，需要按照信息的增加及揮發(fā)進(jìn)行更新，更新方法如公式（2）所示。

其中：ρ為小于1的常數(shù)，表示信息素的持久性因子，（1-ρ）表示揮發(fā)因子，Δτij表示本次螞蟻?zhàn)哌^本路徑留下的信息素，下一次遍歷的信息素濃度為本次增加量與上一次揮發(fā)后的剩余量之和。

其中：Q為一個常數(shù)，可以對其進(jìn)行設(shè)置；Lk表示第k只螞蟻在本次迭代中走過的路徑長度，那么信息素的濃度就與路徑的螞蟻?zhàn)哌^的路徑成反比。

2 蟻群算法改進(jìn)

蟻群算法系統(tǒng)可以用式（1）和式（2）表示，在式中可以看出算法的性能會受到啟發(fā)因子α、信息素濃度τ(i,j)、啟發(fā)式因子β、局部更新信息素的持久性因子ρ等等影響，算法的收斂性也會受到各參數(shù)組合的影響。參數(shù)ρ表示信息素的持久性因子，同時也反映了揮發(fā)率。信息素的更新采用了正反饋機(jī)制，容易造成一種信息素累積，導(dǎo)致算法陷入局部最優(yōu)解。

本文針對蟻群算法存在著收斂速度慢、容易陷入局部最優(yōu)的缺陷，對算法進(jìn)行改進(jìn)。信息素持久性因子ρ的大小可以影響到蟻群算法的全局搜索能力，同時，也可以影響到算法的收斂速度，所以ρ不宜過大或者過小，要根據(jù)實(shí)際情況適時改變；在公式（3）中，Q是一個常數(shù)，表示信息素強(qiáng)度，Lk表示第k只螞蟻在本次對路徑的遍歷中所走過的總長度。從公式（3）可以看出，螞蟻所走的某次遍歷中走過的路徑越短，即LK越小，越大，說明這只螞蟻在路上留下的信息素也就越多，所有的信息素疊加后，得到Δτij也就越大，最終得到的pij也就越大，說明后續(xù)螞蟻經(jīng)過這條路徑的概率越大。本文要根據(jù)LK的作用進(jìn)行算法的改進(jìn)，針對LK只考慮了第K只螞蟻?zhàn)哌^的路徑長度的問題，對前K-1只螞蟻所走的路徑進(jìn)行綜合比較后，進(jìn)行加權(quán)后計算信息素濃度，增加全局影響因素。

首先，假設(shè)最優(yōu)路徑一般都會在較短路徑中得到，所以增加較短路徑的影響力。螞蟻k走過全程以后，在信息素更新前，先和平均路徑總長度進(jìn)行比較，如果說明這一只螞蟻所走路徑劣于前K-1只螞蟻?zhàn)哌^路徑的平均值，在最優(yōu)路徑上的可能性較小，螞蟻留下的信息素應(yīng)相應(yīng)減小，使得此路徑的選擇概率減??；反之，如果Lk＜Laverage，說明這一只螞蟻?zhàn)哌^的路徑優(yōu)于前K-1只螞蟻?zhàn)哌^路徑的平均值，在最優(yōu)路徑上的可能性增加，螞蟻留下的信息素相應(yīng)增加，從而使得該路徑選擇概率變大，加快尋優(yōu)速度，同時考慮了全局最優(yōu)性，減小了局部最優(yōu)的可能性。具體的方是在計算第K只螞蟻的信息素時，即計算在Δτkij時，加入影響因子λ，計算公式如式（4）所示，令對Lk加權(quán)后，增加走過全局短路徑的影響力，增加了算法全局最優(yōu)性表現(xiàn)。本文算法圖1所示。

圖1 本文算法流程圖

3 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證改進(jìn)行蟻群算法的有效性和收斂性，根據(jù)上一節(jié)和蟻群算法設(shè)計流程，在Windows7系統(tǒng)下，用MATLAB R2015a軟件進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)采用30城市TSP標(biāo)準(zhǔn)數(shù)據(jù)庫，對算法的初始值設(shè)置如表1所示。

表1 算法的參數(shù)設(shè)置

對30城市TSP問題加以測試，用傳統(tǒng)ACO算法與本文算法計算最優(yōu)路徑，對于不同的迭代次數(shù)得到最短路徑長度果，如圖2所示，在相同的迭代次數(shù)條件下，本文算法所得到的最短距離比傳統(tǒng)ACO算法要小，而且在150次迭代與200次迭代的結(jié)果相同，算法趨于收斂，所以本文算法收斂的速度要快。本算法在200次迭代時所得的最優(yōu)路徑如圖3所示。

圖2 ACO算法與本文算法測試結(jié)果對比

圖3 本文算法在200次迭代時得到的最優(yōu)路徑

4 結(jié)語

本文分析了旅游線路問題，并建立數(shù)學(xué)模型，在線路規(guī)劃時采用蟻群算法，并且對基于蟻群算法的旅游線路規(guī)劃算法進(jìn)行改進(jìn)。首先對ACO蟻群算法進(jìn)行了分析，然后基于ACO算法進(jìn)行了改進(jìn)設(shè)計。改進(jìn)算法在信息素更新前，先和平均路徑總長度進(jìn)行比較，如果大于平均路徑，說明該螞蟻?zhàn)哌^的路徑不是最短的；反之，說明該只螞蟻?zhàn)哌^的路徑優(yōu)于前次，從而使得該路徑轉(zhuǎn)移概率變大，加快尋優(yōu)速度。將本算法在MATLAB開發(fā)平臺上實(shí)現(xiàn)算法進(jìn)行仿真實(shí)驗(yàn)，得到的最優(yōu)路徑優(yōu)于ACO算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了該旅游線路規(guī)劃算法的可行性和有效性。

[1]張凌云.智慧旅游:個性化定制和智能化公共服務(wù)時代的來臨[J].旅游學(xué)刊2012,27（2）:3-5.

[2]Colomi A,Dorigo M,Maniezzo V.Didtributed Optimization by Ant Colonies[C].Proc of the First European Conference of Artificial Life.Paris:Elsevier Publishing,1991.

[3]Dorigo M,Ganbardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Trans on Evolutionary Computation,1997,1（1）:53-66.

[4]張學(xué)敏,張航.基于改進(jìn)蟻群算法的最短路徑問題研究[J].自動化技術(shù)與研究,2009（6）:4-7.

[5]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

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

[7]孫力娟.改進(jìn)的蟻群算法及其在TSP中的應(yīng)用研究[J].通信學(xué)報，2004,25（10）:111-116.

[8]吳華鋒,陳信強(qiáng)，毛奇凰.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報，2013，34（4）：165-170.

[9]姜坤霖,李美安，張宏偉.面向旅行商問題的蟻群算法改進(jìn)[J].計算機(jī)應(yīng)用，2015，35（S2）:114-117.

[10]張永剛，張思博，薛秋實(shí).求解約束滿足問題的改進(jìn)蟻群優(yōu)化算法[J].通信學(xué)報，2013，34（4）：1-7.