基于遺傳算法的環中國旅行路線優化策略

魏書禾

東北財經大學國際商學院，遼寧大連 116000

引言

當今世界，經濟和社會的高速發展，給人們的休閑娛樂生活帶來了更大的選擇性和多樣性。近年來國家統計局出示的報告顯示國家的旅游業正在逐年高速發展，其中，自助游正在越來越受到人們的追捧[1]。在實際旅游的過程中，自助游所最需要考慮的就是關于路線的規劃，即路徑尋優加上有關費用的問題。那么，在路徑尋優的問題中，如何進行更有效的規劃？如何在城市或者景點之間實現路線的動態規劃和均衡？在實現路線規劃后如何找到用戶滿意度最高的一條路線？通過閱讀大量的參考文獻我們可以發現，大多旅游路線的規劃文獻運用的方法是啟發式的蟻群算法[2-8]；部分文獻則注重于某個省份或地區旅游線路的優化[9-12]

由于蟻群算法具有種群的限制性和約束優化型，針對環中國的旅游線路優化問題，本文擬采用GA遺傳算法，隨機產生種群，用輪盤策略確定個體的適應度，用判斷是否確定個體的舒適度來判斷是否符合優化準則，不斷循環輸出最佳個體和最優解，并且按照一定的交叉概率和交叉方法生成個體和種群并不斷地優化求解。

利用R軟件，我們畫出了中國地理位置的經緯度畫出中國地圖標注省會城市（見圖1）。

一 基本理論支撐

（一）遺傳算法（GA）的基本原理

遺傳算法模擬自然界優勝劣汰的進化現象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量—染色體，向量的每個元素稱為基因. 通過不斷計算各染色體的適應值，選擇最好的染色體，獲得最優解。

（二）遺傳算法（GA）的思想

遺傳算法借鑒生物進化論，遺傳算法將要解決的問題模擬成一個生物進化的過程，通過復制、交叉、突變等操作產生下一代的解，并逐步淘汰掉適應度函數值低的解，增加適應度函數值高的解。這樣進化N代后就很有可能會進化出適應度函數值很高的個體。

（三）遺傳算法（GA）在文中的應用

遺傳算法是一種無約束優化的遺傳算法。在運用時候，可通過數學的方式，利用計算機仿真技術，將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時,相對一些常規的優化算法，通常能夠較快地獲得較好的優化結果。常用來解決路徑尋優問題，以及一系列的優劣決策問題。在本文中，我們的遺傳操作包括以下三個基本遺傳算子：選擇、交叉、變異。

本文選了全國43個主要城市為旅游地，是一個典型的旅行線路的線性規劃模型和圖論模型。通過GA算法的重復循環和多次決策，我們尋找到的最優路徑達到全程最短為38286公里。接著，我們將分為動車和自駕兩種出行方式，分別算出所需花費的費用，并進行比較。

（四）遺傳算法（GA）的流程圖

在文中，我們的目的是根據旅游路線設計的特點與游客信息完成對旅游線路的優化工作。遺傳算法用于解決NP難題，與旅游路線的規劃相契合，因此把遺傳算法應用到旅游路線的規劃中。本次擬合全國43個主要的城市，設定流程控制設計（見圖2）。

圖2 遺傳算法流程圖

二 模型運行與操作

（一）遺傳算法的基本操作

遺傳算法有3個最關鍵步驟：選擇運算，染色體交叉，染色體變異。選擇運算是從舊的種群中選擇適應度高的染色體，放入匹配集（緩沖區），為以后染色體交換、變異，產生新的染色體做準備。

首先設計染色體編碼，把解空間的表示方法轉化成適用于遺傳算法搜索空間中的可行解，即轉化成可用遺傳算法進行處理的基因編碼。本文中43個主要城市的路線優化難題，可用符號編碼的方式，使用數字1—43生成一個隨機排列，作為一個染色體，假定初始的種群中含有10個染色體。

在GA算法進化過程中，依據適者生存的原則，適應度比例法為了劃分種群中個體的優劣的標準。本文研究環中國主要城市的旅游路線規劃，選擇一條路線使得路程最短，從而降低旅途的時間成本和金錢成本，提高旅行的價值最大化。

本文使用R統計軟件實現編程，由城市之間的距離矩陣，每條染色體（即43個主要城市的一個隨機排列）中每個基因的距離的和，作為適應度的運算結果。距離的和越小，路線越短，實現旅游路線的優化。

（二）選擇方法

本文采用常見的輪盤賭的方式，選取適應值大的作為個體作為父體，賭輪是按個體的適應度進行選擇的，適應值大的個體則選取，適應值小的個體剔除。

交叉操作：隨機選擇2個個體，在對應位置交換若干個基因片段，提示保證每個個體依然是1—43的隨機排列，本文采用的交叉率為0.8。

變異操作：隨機選取個體的2個基因進行交換以實現變異操作，本文采用的變異概率為0.2。

（三）全國43個城市旅游路線GA算法優化

本文對收斂速度機進行控制，種群規模提取500，總共進行1000次迭代，交叉概率0.8，變異概率取0.2，利用R軟件進行計算，結果如圖3環中國旅行路線圖所示。

圖3 環中國旅行路線圖

通過R軟件對坐標進行標準化后擬合得到的單向閉合的旅行線路圖形，可見遺傳算法對旅游線路的選擇有明顯的優化作用，達到全程最短里程數。并在經過844次的迭代后趨于平穩，得出全局最短距離為38286公里。利用GA算法得到最優的路線為：

大連—丹東—吉林—齊齊哈爾—沈陽—哈爾濱—牡丹江—長春—二連浩特—北京—濟南—杭州—福州—南昌—深圳—廣州—桂林—株洲—徐州—合肥—南京—上海—青島—石家莊—太原—錦州—武漢—鄭州—成都—貴陽—柳州—南寧—長沙—重慶—昆明—拉薩—西寧—烏魯木齊—蘭州—西安—呼和浩特—銀川—天津—大連。優化后的旅游線路，不但路程最短，用時最短，從而實現旅游價值的最大化。

GA進化迭代過程如圖4，橫坐標表示迭代的次數，縱坐標表示適應度即距離的倒數。從圖中可以清晰地看出，當迭代到850次左右，適應度函數趨于平穩，平穩值為2.6119*10-5。起倒數為38286公里。

圖4 GA進化迭代過程圖

（四）按照兩種不同交通工具計算費用

采用自駕游方式出行：假設在旅行中自駕游每天行駛500公里、每三天中有一天行駛1000公里，每公里費用1元，每人每天食宿為230元；那么38286公里共花去大約58天時間，得到四個人的總費用為：

230×58×4＋ 38286=91646（元），完成 43個中國主要城市的旅行共計花去91646元。

采用動車出行方式：

動車基價是由線路和車輛等級（運行速度）共同決定的，一般情況下：

在200km/h的速度下，一等座基價大約是0.37元/公里，二等座基價大約是0.30元/公里。

在300km/h的速度下，一等座基價大約是0.74元/公里，二等座基價大約是0.46元/公里。

按照動車二等座200km/h計算，每公里0.30元票價標準，在城市停留天數與自駕游一致58天；進行得到4個人環游43座城市的費用為：

230×58×4+38286×0.3×4=99303.2元，完 成43個中國主要城市的旅行共計花去99303.2元。

對比兩種出行方式，4個伙伴自駕游的費用較節省。

三 結語

本文針對從大連出發，每人費用1萬元的條件下，4個人環游中國43個主要的城市之旅。首先采用遺傳算法（GA）對中國主要43個城市進行環中國旅行路線進行優化，利用種群是10個，交叉率0.8,變異率0.2 ，進行1000次的GA算法迭代，得到最短路徑。共計38286公里。分別采用自駕游和動車出行的方式計算費用，得出結論：自駕游出行方式能夠更加節省。

未來可以對本課題進行更加細致的研究，精確計算景區的游玩時間以及在城市的停留時間；把GA算法優化旅游線路中做得更加精確。比如適應度函數可以添加不同的權重等。