基于遺傳算法的TSP算法求解20大城市最短旅途

裴佳明 周斌 酈麗

摘要：Traveling Salesman Problem，簡稱TSP問題，也就是我們常說的旅行推銷員問題，是數學中的一種典型問題。本文將基于遺傳算法，選取20個城市作為樣本，利用TSP算法來制定最優化的旅游線路。

關鍵詞：遺傳算法;TSP算法;最短旅途

中圖分類號：TP312? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）16-0194-02

開放科學（資源服務）標識碼（OSID）：

我們所說的TSP算法基本可以簡單概述為求解最優化的線路組合。具體要求為每個城市都要走且只走一遍，終點城市同出發城市為同一個，在此基礎上實現所走路程的最短[1-3]。在下文將以20個城市作為案例分析，探索TSP算法解決旅游線路最優問題的具體方法。

1 問題描述

本文選取了20個城市，依次編號為1至20號，隨機設定城市坐標，如下圖標所示：

立足于遺傳算法的TSP算法具體來看包含初始化、個體評價、選擇運算、交叉運算、變異運算以及經過選擇-交叉-變異運算之后的下一群體這六大步驟[4]。其運算流程如下：

2 遺傳算法優缺點

在具體進行算法設計之前有必要對遺傳算法的優缺點進行分析，以便更好地進行算法的設計。首先來看遺傳算法的優點主要表現在不必借助輔助信息、在檢索過程中造成局部最優的可能性低、廣泛的表示可行解、可擴展、群體搜索以及便于同其他技術結合使用等[5]。而遺傳算法的缺點主要表現在以下幾個方面，像是過早收斂、缺乏有效的定量分析、效率同其他優化方法相比較低、優化問題的相關約束難以系統的表示以及編碼不規則等等。

3 算法設計

通常在實際操作中會借助二進制編碼的形式表現遺傳算法的解空間，需要注意的是這種方法并不能夠表示TSP問題的解，需要用十進制編碼更為恰當[6]。我們將這20個城市進行編號，從1標到20。

假設從城市8出發，經過1-20個城市最后回到城市8的一條路徑，可以自然地用一維數組來表示：

對于所選取的這20個旅游城市樣本，其TSP算法中，我們設定種群的規模為40，那么采用二維數組來表示解的空間就可以寫作：tour[40][20]。

對于如何選擇合適的種群規模應該有所依據，不能單純地追求大規模，單純的大規模種群容易導致計算成本的增加，而且TSP算法也難以改進。像是本文中20個城市的TSP算法，采取小規模的種群即可。種群初始化時，先產生1，2，…，20的一條規則路徑，然后用Collections.shuffle將他們打亂順序，保證這條路徑變成了一條隨機的路徑，這樣產生了一個個體;同樣地產生種群里其他個體。

TSP算法的設計需要考慮適應度以及交叉操作。適應度在面對不同的問題時，其定義方式也有所不同，不過一般是用它來表明解或是個體的優劣程度。如果我們假設這20個城市（k1、k2……k20）是一個整數編碼的染色體，那么適應度就是正好走完這20個樣本城市，回到出發點城市的最短距離的一個倒數。TSP算法中優化選擇的目標就是確保適應度函數值能夠是盡可能大的染色體，一般而言，適應度的函數值比較大的染色體，質量也更優越。在對所有種群的個人進行適應值求取后，就會將所求得的適應度最大的個人進行保存，等演化結束后，這一個體就是最優解。

至于交叉操作，可以稱得上是遺傳算法中最主要的一種操作方式。借助交叉操作，能夠獲得新的個體，所獲得的新個體能夠體現出父輩的個體特征，所表現的是一種信息交換的理念。如果將父輩的樣本進行分組，則每一組的計算過程如下：

這個交叉過程保證了城市的唯一性，避免了沖突。

我們也可以將變異理解為外界環境對種群的一種影響。對于本文中所選擇的20個樣本城市，使其隨機產生兩個比20小的整數，來對整體進行分割，我們設定這一分割的整數是8和3，具體如下所示：

這一變異操作的優點在于它能夠保持原有片段路徑，改變的只是整個路徑同兩端點的連接，而倒序前后的切割段路徑還是同之前一般，是一種有所選擇的取舍，能夠盡可能的保證所得到的后代是合理的途徑。

4 實驗結果分析

5 結語

綜上所述，對于這一典型的優化組合算法問題，在諸多領域都有著廣泛的應用，像是物流配送、交通運輸以及電路設計等等，在國內外的研究都在不斷深化。希望能夠通過本文基于遺傳算法的TSP算法來求解20個樣本城市的最短旅行線路分析，能夠為我國關于遺傳算法以及TSP算法的進一步深入研究提供一點借鑒經驗。

參考文獻：

[1] 張立毅，高楊，費騰，王玉婧.求解旅行商問題的搜尋者遺傳算法[J].數學的實踐與認識，2019，49（07）：115-122.

[2] 岳鵬齊.基于遺傳算法解決TSP問題探索[J].現代信息科技，2019，3（04）：10-12.

[3] 唐天兵，張銘明，蒙祖強.混合蛙跳遺傳算法求解旅行商問題[J].廣西大學學報（自然科學版），2018，43（05）：1811-1817.

[4] 劉云飛.基于TSP問題的仿生算法比較[J].電子技術與軟件工程，2019（02）：110-111.

[5] 陳洋卓，李青青，羅天揚，等.基于遺傳算法的TSP問題優化方法[J].科技風，2019（01）：59-60.

[6] 郭豐林.基于遺傳算法的旅游線路規劃研究[J].現代營銷（經營版），2019（01）：134.

【通聯編輯：李雅琪】