楊曉敏

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

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

中圖分類號：TP391.9? ? ? ? ? 文獻標(biāo)志碼：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è)內(nèi)的研究熱點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法的基本步驟如下：

⑴ 初始化算法的相關(guān)變量。

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

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

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

⑸ 更新信息素。

⑹ 把禁忌表清零。

3.1 參數(shù)的設(shè)置與仿真結(jié)果的關(guān)系

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

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

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

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

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

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

⑵ 研究Beta值對仿真結(jié)果的影響

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

當(dāng)Beta=1，在第4代的時候收斂。

當(dāng)Beta=5，在第7代的時候收斂。

當(dāng)Beta=10，在第3代的時候收斂。

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

3.2 仿真

根據(jù)上面的分析研究，設(shè)置合適的參數(shù)，當(dāng)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。仿真結(jié)果如圖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 結(jié)論

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

參考文獻（References）：

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

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

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

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

[5] 閆登福.基于距離可達矩陣的自駕游路線優(yōu)化研究[D].東北大學(xué)，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