基于改進蟻群算法的旅游線路優化

周茂杰，張翠

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

0 引言

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

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

1 蟻群算法原理

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

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

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

其中：

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

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

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

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

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

其中：ρ為小于1的常數，表示信息素的持久性因子，（1-ρ）表示揮發因子，Δτij表示本次螞蟻走過本路徑留下的信息素，下一次遍歷的信息素濃度為本次增加量與上一次揮發后的剩余量之和。

其中：Q為一個常數，可以對其進行設置；Lk表示第k只螞蟻在本次迭代中走過的路徑長度，那么信息素的濃度就與路徑的螞蟻走過的路徑成反比。

2 蟻群算法改進

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

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

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

圖1 本文算法流程圖

3 實驗及結果分析

為了驗證改進行蟻群算法的有效性和收斂性，根據上一節和蟻群算法設計流程，在Windows7系統下，用MATLAB R2015a軟件進行仿真實驗，實驗數據采用30城市TSP標準數據庫，對算法的初始值設置如表1所示。

表1 算法的參數設置

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

圖2 ACO算法與本文算法測試結果對比

圖3 本文算法在200次迭代時得到的最優路徑

4 結語

本文分析了旅游線路問題，并建立數學模型，在線路規劃時采用蟻群算法，并且對基于蟻群算法的旅游線路規劃算法進行改進。首先對ACO蟻群算法進行了分析，然后基于ACO算法進行了改進設計。改進算法在信息素更新前，先和平均路徑總長度進行比較，如果大于平均路徑，說明該螞蟻走過的路徑不是最短的；反之，說明該只螞蟻走過的路徑優于前次，從而使得該路徑轉移概率變大，加快尋優速度。將本算法在MATLAB開發平臺上實現算法進行仿真實驗，得到的最優路徑優于ACO算法。實驗結果驗證了該旅游線路規劃算法的可行性和有效性。

[1]張凌云.智慧旅游:個性化定制和智能化公共服務時代的來臨[J].旅游學刊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]張學敏,張航.基于改進蟻群算法的最短路徑問題研究[J].自動化技術與研究,2009（6）:4-7.

[5]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社，2004.

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

[7]孫力娟.改進的蟻群算法及其在TSP中的應用研究[J].通信學報，2004,25（10）:111-116.

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

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

[10]張永剛，張思博，薛秋實.求解約束滿足問題的改進蟻群優化算法[J].通信學報，2013，34（4）：1-7.