基于遺傳算法的南京周邊城市旅游規劃研究

王夢甜

(南京財經大學，江蘇 南京210023)

一、引言

隨著總體國民經濟水平和人均收入水平的不斷提高，我國社會的主要矛盾已經轉化為人民日益增長的美好生活需要和不平衡不充分的發展之間的矛盾，生活的質量成為當代人們普遍追求的目標。同時人均汽車擁有量的增多使得很多家庭在短暫節假日的時候選擇去周邊城市旅游，這推動了旅游業和經濟的發展。有效的路徑規劃成為出門必備，如何以最短的距離、最小的成本游玩周邊城市成為問題，對于提高居民的生活質量水平具有重要意義。旅游路線規劃問題來源于數學領域中經典的旅行商問題(TSP)，同時也稱為旅行推銷員問題或者貨郎擔貨問題，不僅有理論價值，同時也非常有實際價值，目前廣泛應用于物流行業貨物配送、智能化交通道路控制、網絡路由和計算機等相關領域。旅行商問題(TSP)是數學組合優化問題中典型NP-Hard問題，在小規模下計算好解決但是在大規模的情況下，無法運用傳統數學辦法計算。對于旅行商問題目前解決方法一般主要包括兩種:完全算法解和近似方法解。完全算法指在有限的計算步驟下可以找到問題的最優解，例如經典的分值定界法、Dijkstra算法、動態規劃算法等，但是這種算法缺點在于時間復雜度過高，尤其目前大數據時代無法滿足大規模的數據運算需求。近似算法解指可以在多項式時間內結束，從而得到問題的一個近似解，這種算法相對于前者更優且在實際問題中應用更多，目前研究和應用較多的啟發式算法主要為粒子群算法、蟻群算法和遺傳算法等。縱使有這兩種算法，但是學者們仍然沒有尋找到一個解決TSP問題的完美方案。在這方面的研究很多，國內學者們也取得了較多成果。高海昌等人綜述了蟻群算法、遺傳算法等一系列智能算法，讓人對這些算法有了一個較為清晰的認識；李瑋對使用的遺傳算法中編碼部分采取矩陣編碼方式解決TSP問題；姚明海等主要采取將遺傳算法和其他智能算法相結合的方式解決問題；雷玉梅等對遺傳算法原理進行介紹并且分解進行；吳陽等人通過對遺傳算法的改進研究共享汽車停車點布局，并用MATLAB求解得到最優解；張璽君等人針對目前出租車運行過程效率低下問題，基于改進遺傳算法構建了出租車共乘線路規劃模型，最終可以快速得到優化路徑；徐晨暢和錢松榮基于遺傳算法建立突發公交智能調度并給出相關支援方案；張惠彬等利用構建了事故發生時人員疏散路徑優化并用遺傳算法進行求解。旅行商(TSP)模型用于旅游路徑規劃也有一些成果，吳凱在理論上將定性和定量兩種方法結合進行旅游路線設計；劉倩等利用蟻群算法對景區內車輛調度進行路徑規劃；王慧等為滿足旅游愛好者，設計出遍歷全國所有5A級景點的旅游路徑規劃并用蟻群算法求解；徐書楊等考慮景區內部擁擠度、景點熱度等因素使用蟻群算法規劃景區路徑，從而提升旅客旅游體驗。文章基于目前研究狀況，以江蘇省南京市為中心，距離最短為目標函數，通過經度、緯度來研究其周邊共8個省會城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟南)出行旅游最短路徑，并且利用遺傳算法對其進行求解，結果證明遺傳算法在解決周邊游路徑規劃問題方面具有較高的實用性。

二、旅行商(TSP)問題描述

旅行商(TSP)問題是制定多個城市地點并且知道每兩個城市之間的距離，旅行商人隨機選擇其中一個城市作為起點出發，對所有城市進行訪問并且只訪問一次同時回到最初的城市，尋求最短距離的完整回路。在運籌學中可以用圖論中的無向圖進行解釋，如無向完全圖A＝(V，E，r)，要求遍歷A中每一個節點并且形成簡單的回路，使各邊權重相加之和最小，其中V＝{1，2，…，n}是無向圖中的每個節點集，表示被訪問的城市，E是連接V中兩個不同點之間的邊集，r表示兩城市之間的權重即距離。其數學模型定義如下:

上述中(1)式為所求的目標函數，即旅行商所經過路徑最小值，其中dij表示城市i到城市j的兩地距離，也就是圖論模型中的r值，在文中距離是利用兩個城市的地理坐標(經度、緯度)進行轉化計算得到；(2)式和(3)式表示旅行商有且只經過一次其中的每一個城市；(4)式表示旅行商在整個過程不能形成循環的路徑；(5)式表示是否去過這個城市，用xij＝0表示旅行商未曾經過該城市，xij＝1則表示旅行商已經去過的城市。

三、遺傳算法模型構建

遺傳算法想法來源于自然界，是繼承了生物學中的遺傳思想“優勝劣汰” ，模仿自然界生物的進化機制，將自然界生物的繁殖、交配以及基因突變等相關概念引入整個算法過程，實質上是一種并行且高效的全局搜索方法。遺傳算法在尋求最優解的過程中能夠自動獲得關于整個搜索空間的知識，并且能夠很好地改變自己的搜索過程從而獲得整個問題的最優解。遺傳算法主要原則還是根據生物學中的適者生存，在所有可行解中找到一個近似最優解，而且后面的每一代遺傳過程中根據個體在該環境下的適應度再進行選擇從而得到一個更優解，這個新個體相對于原來的個體能夠更好地適應環境。遺傳算法目前是較多領域中獲取最優解的一種啟發式算法。

文章在構建旅行商問題模型和了解遺傳算法相關知識基礎上采取了具體的遺傳算法，主要步驟如下:

Step1:編碼。在一般問題中，多數學者在使用遺傳算法的時候會采取二進制編碼，但是本文在TSP問題中采取順序表示的編碼方式，順序中每個數字代表一個城市，不同順序經過城市連起來為一條新染色體即為一個解。論文以南京周邊8個省會城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟南)為例，城市編碼選取為1～8的數字，假如生成的染色體序列號為12345678，則代表旅行商人從城市1出發依次經過城市2、3、4、5、6、7、8最終再回到出發點城市1的一條回路路徑。

Step2:初始化。隨機選擇一些數量的個體(文中初始數量為100)組成最初的種群即初始解。

Step3:評估。初始化的個體優劣程度是不一樣的，為了使最終結果更優，在每次選擇的過程中要選擇最優個體，因此在評估階段使用函數來評判個體的適應度決定其優劣程度，從而為下一步個體選擇提供依據，通常適應度函數是由目標函數轉化而來，文中目標函數是求解最小值，則使適應度函數值最大，因此采取目標函數的倒數值作為適應度值即可，因此適應度函數設置如下:

Step4:選擇。遺傳算法中選擇操作是使用輪盤賭的方式，從上一代種群中選擇出較好的個體來進行繁衍子代，個體被選擇的概率值與其適應度值相關，根據Step3得到適應度的值，個體適應度值越高其被選擇到的概率則越大，個體i被選擇的概率為P，其中m為初始化的種群數量。計算公式如下:

Step5:交叉操作。基因交叉產生后代，將上一步選擇的兩個個體作為父代進行交叉操作以產生新的子代，文中操作方法是在[1，8](共8個省會城市)之間隨機選取選取兩個整數r1和r2，將兩者之間的部分交換，文中設置的交叉概率為Pc＝0.7。

Step6:變異操作。指在新產生的個體上進行突變的操作，主要維持種群子代的多樣性，具體方法是在[1，8]區間上隨機選擇兩個數r1和r2，然后將個體上這兩個數字交換，從而得到變異個體，文章實驗中變異概率設置為Pm＝0.02。

Step7:結束。文章的終止條件為算法收斂準則是否滿足，如果滿足各步驟則輸出相應的結果，否則返回至Step2進行循環迭代直到最終輸出結果。其主要流程圖見圖1:

圖1 遺傳算法流程圖

四、實驗結果及分析

根據上面所構建的模型和具體的遺傳算法步驟，文章基于Python語言對遺傳算法進行代碼實現，利用遺傳算法對模型求解。首先獲取8個省會城市或直轄市(上海、南京、合肥、杭州、武漢、南昌、鄭州、濟南)的地理位置坐標，通過對地理位置的轉化求解8個城市先后游玩的最短距離。

在設定的參數以及算法收斂原則情況下得到最優結果為25.943488，具體路徑為南京—合肥—杭州—南昌—武漢—上海—濟南—鄭州，具體路線圖如下圖2所示。綜上所述，南京周邊8個省會城市旅游最短路徑得以解決，可見遺傳算法對于解決南京城市周邊游路徑規劃問題效果顯著，對上述八個城市居民采取周邊游都具有很好的建議；但是論文仍有不足，第一，各城市數據采取的地理經緯度導致最終距離很小，這與真實地圖數據有點差距，但是整體結果符合真實地圖；第二，本實驗中是將遺傳算法中各參數固定，但是對于不同的參數可能會出現不同情況，綜上這些不足在未來實驗中可以繼續改進。

圖2 最短路徑圖