基于蟻群算法的黃河金三角旅游路線規(guī)劃研究

楊曉敏

摘? 要： 選擇一條合適的旅游路線對于旅游者非常重要。蟻群算法運用到黃河金三角旅游路線的規(guī)劃中，選取黃河金三角的11個景點，把選取的景點轉換為經(jīng)緯度，然后用蟻群算法進行路徑優(yōu)化。通過對蟻群算法的參數(shù)的調整和算法的改進，用Matlab進行仿真實驗，并進行了仿真分析，結果表明，蟻群算法能很快收斂并得到最優(yōu)路徑。

關鍵詞： 旅游路線; 路徑優(yōu)化; 蟻群算法; Matlab

中圖分類號：TP391.9? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2018）12-61-03

Abstract： Choosing a suitable tourist route is very important for tourists. In this paper， ant colony algorithm is applied to the planning of the Yellow River Golden Triangle tourist route， 11 scenic spots in the Yellow River Golden Triangle are selected， and the selected scenic spots are converted into latitude and longitude， then the ant colony algorithm is used for path optimization. Through the adjustment of the parameters of ant colony algorithm and the improvement of the algorithm， simulation experiment is carried out with MATLAB， and the simulation analysis is carried out. The results show that the ant colony algorithm can converge quickly and get the optimal route.

Key words： tourist route; path optimization; ant colony algorithm; MATLAB

0 引言

我國國民經(jīng)濟迅速發(fā)展，人們生活水平普遍提高，休閑方式發(fā)生了巨大改變，我國的旅游業(yè)處于蓬勃發(fā)展的階段。由于我國小長假增多，所以短期旅游線路受到廣大人民群眾的歡迎，如何規(guī)劃一條最佳旅游路線，是行業(yè)內的研究熱點。

旅游路線的規(guī)劃本質是組合優(yōu)化問題，也是一個NP難題，組合優(yōu)化問題很難求出最優(yōu)解，所以我們試圖找到一種近似最優(yōu)解，經(jīng)過研究發(fā)現(xiàn)蟻群算法具有這種特性，所以把蟻群算法應用到旅游路線的規(guī)劃中，幫助我們找到近似最優(yōu)解[1-2]。

1 蟻群算法的優(yōu)點

蟻群算法是20世紀90年代初由意大利學者M.Dorig等人提出的一種模擬進化算法，蟻群算法是一種生物仿生算法，仿照螞蟻的走路行為，建立相應的數(shù)學模型，從而把相應的算法與實際應用結合，使實際問題得到解決。算法的基本思想是螞蟻在覓食的過程中會留下信息素，那么在設計算法的時候給了一個信息素參數(shù)，根據(jù)信息素的濃度來判斷選擇某條路徑的概率。蟻群算法有它本身的缺點，比如收斂速度慢、容易停滯，為了解決蟻群算法的缺陷，很多學者都提出了相應的改進算法，德國學者Thomastuzle和Holerhoos提出的最大最小系統(tǒng)，在解決TSP問題時效果要優(yōu)于一般的算法，還有一些學者把蟻群算法和一些其他的仿生算法相結合，比如意大利學者Fabio Abbattista等人提出了遺傳算法和蟻群算法相結合的組合優(yōu)化算法[3]。蟻群算法的優(yōu)點如下：

⑴ 算法模擬螞蟻的行為，是一種無控制中心，并且為分布式的控制方式。

⑵ 算法的機制屬于正反饋機制。

⑶ 算法的穩(wěn)定性較好，可以應用于眾多的實際問題。

⑷ 是一種多主體協(xié)作的智能算法。

⑸ 易與其他算法融合，解決相應的實際問題。

2 蟻群算法的數(shù)學模型

蟻群算法主要通過螞蟻留下的信息素的數(shù)量來判斷該段路段的重要程度，殘留的信息素與螞蟻選擇該路斷的可能性呈線性相關，留下的信息素越多，選擇的可能性就趙大[4-5]。

蟻群算法的數(shù)學模型，關鍵是狀態(tài)轉移概率，用pijk來給示螞蟻k從城市i轉移到城市j的狀態(tài)轉移概率，j是尚未訪問的城市，則狀態(tài)轉移概率pijk如式⑴所示。

式中，allowedk={0，1，…，n-1}表示螞蟻k下一步允許選擇的城市。α表征信息素重要程度的參數(shù)，β表征啟發(fā)式因子重要程度的參數(shù)[6]。為每只螞蟻設置一個禁忌表，主要用來記錄螞蟻走過的城市，不允許在本次循環(huán)中重復經(jīng)過，循環(huán)結束后禁忌表清空，下次重新記錄。

每完成一次循環(huán)，對信息素進行更新，如式⑵和式⑶所示。

3 蟻群算法在旅游路線規(guī)劃中的應用

蟻群算法用于解決NP難題，與旅游路線的規(guī)劃相契合，因此把蟻群算法應用到旅游路線的規(guī)劃中。本次仿真實驗選取黃河金三角的11個景點，分別位于山西省、陜西省、河南省。通過百度地圖得到了11個景點的經(jīng)緯度，11個景點的經(jīng)緯度如表1所示。

算法的基本步驟如下：

⑴ 初始化算法的相關變量。

⑵ 將m只螞蟻放到n個城市上。

⑶ 螞蟻按照式⑴的概率函數(shù)選擇下一城市。

⑷ 記錄本次迭代的最佳路線。

⑸ 更新信息素。

⑹ 把禁忌表清零。

3.1 參數(shù)的設置與仿真結果的關系

⑴ 螞蟻數(shù)量m值對仿真結果的影響

研究m值不同， Alpha=0.5、Beta=1、Rho=0.1、NC_max=200、Q=100迭代次數(shù)的變化情況。

當m=31時，得到的路徑為8—5—6—4—1—9—10—11—2—3—7，在第2次迭代時收斂，最短距離為288.4376。

當m=21時，得到的路徑為5—6—4—1—9—10—11—2—3—7—8，在第5次迭代時收斂，最短距離為288.4376。

當m=11時，得到的路徑為5—6—4—1—9—10—11—2—3—7—8，在第六次迭代時收斂，最短距離為288.4376。

從以上仿真結果可以看出，螞蟻數(shù)量影響算法的收斂速度，但是如果螞蟻數(shù)量遠遠大于31時，效果將不明顯，所以選擇合適的螞蟻數(shù)量是非常必要的。同時還可以發(fā)現(xiàn)由于實際中晉城所處的地理位置，所以在遍歷時有時做為起點，有時做為終點。

⑵ 研究Beta值對仿真結果的影響

研究當Beta值不同，m=31、Alpha=0.5、Rho=0.1、NC_max=200、Q=100迭代次數(shù)的變化情況。

當Beta=1，在第4代的時候收斂。

當Beta=5，在第7代的時候收斂。

當Beta=10，在第3代的時候收斂。

實驗結果表明，Beta值和收斂次數(shù)之間沒有線性關系，要根據(jù)經(jīng)驗值取得最佳值。

3.2 仿真

根據(jù)上面的分析研究，設置合適的參數(shù)，當m=31、Alpha=0.5、Beta=1、Rho==0.1、NC_max=200、Q=100，可以得到一個最優(yōu)路徑為：8—5—6—4—1—9—10—11—2—3—7。仿真結果如圖1所示。

3.3 仿真分析

通過仿真實驗可以看出，算法在第5次迭代的時侯就已經(jīng)收斂，得到的路徑為8—5—6—4—1—9—10—11—2—3—7，最短路徑為288.4376，通過分析可知，路徑基本按照省份呈三個集群，分別是景點8、5、6、4屬于山西省，景點1、9、10、11屬于陜西省，景點3，2、7屬于河南省，基本符合實際。

4 結論

本文研究了蟻群算法在旅游路線規(guī)劃中的應用，并研究了算法參數(shù)對仿真結果的影響，發(fā)現(xiàn)螞蟻個數(shù)對收斂速度的影響較大，在一定范圍內呈線性增長，而Beta值對算法的收斂沒有呈現(xiàn)線性的關系，需要根據(jù)經(jīng)驗得到合適的參數(shù)。通過仿真實驗表明，算法具有較好的收斂性，能快速找到最優(yōu)路徑。不足之處是沒有考慮實際道路對整個路線規(guī)劃的影響，后續(xù)研究應該把實際道路抽象成權值和費用兩個參數(shù)加入到算法的仿真中，可以得到更符合實際的結果。

參考文獻（References）：

[1] 李進立，韋程東，劉廣會，王一茸.旅游路線規(guī)劃問題[J].廣西示范學院學報，2016.3：30-37

[2] 吳小芳，龔丹丹.大嶺山森林公園特色旅游路線設計及系統(tǒng)開發(fā)[J].福建林業(yè)科技，2015（2）：174-178

[3] 金飛虎，洪炳熔，高慶吉.基于蟻群算法的自由飛行空間機器人路徑規(guī)劃[J].機器人，2002.24（6）：526-529

[4] 魏平，熊偉清.用于一般函數(shù)優(yōu)化的蟻群算法[J].寧波大學學報（理工版），2001.14（4）：52-55

[5] 閆登福.基于距離可達矩陣的自駕游路線優(yōu)化研究[D].東北大學，2012.

[6] Dennis Huisman， Albert P. M. Wagelmans. A solution?approach for dynamic vehicle and crew scheduling[J]. European Journal of Operational Research Volume： 172， Issue： 2， July 16，2006：453-471