周茂杰，張翠

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

0 引言

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

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

1 蟻群算法原理

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

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

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

其中：

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

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

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

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

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

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

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

2 蟻群算法改進

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

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

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

圖1 本文算法流程圖

3 實驗及結果分析

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

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

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

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

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

4 結語

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

[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].哈爾濱：哈爾濱工業(yè)大學出版社，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]張永剛，張思博，薛秋實.求解約束滿足問題的改進蟻群優(yōu)化算法[J].通信學報，2013，34（4）：1-7.