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

裴佳明 周斌 酈麗

摘要：Traveling Salesman Problem，簡(jiǎn)稱TSP問(wèn)題，也就是我們常說(shuō)的旅行推銷員問(wèn)題，是數(shù)學(xué)中的一種典型問(wèn)題。本文將基于遺傳算法，選取20個(gè)城市作為樣本，利用TSP算法來(lái)制定最優(yōu)化的旅游線路。

關(guān)鍵詞：遺傳算法;TSP算法;最短旅途

中圖分類號(hào)：TP312? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）16-0194-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

我們所說(shuō)的TSP算法基本可以簡(jiǎn)單概述為求解最優(yōu)化的線路組合。具體要求為每個(gè)城市都要走且只走一遍，終點(diǎn)城市同出發(fā)城市為同一個(gè)，在此基礎(chǔ)上實(shí)現(xiàn)所走路程的最短[1-3]。在下文將以20個(gè)城市作為案例分析，探索TSP算法解決旅游線路最優(yōu)問(wèn)題的具體方法。

1 問(wèn)題描述

本文選取了20個(gè)城市，依次編號(hào)為1至20號(hào)，隨機(jī)設(shè)定城市坐標(biāo)，如下圖標(biāo)所示：

立足于遺傳算法的TSP算法具體來(lái)看包含初始化、個(gè)體評(píng)價(jià)、選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算以及經(jīng)過(guò)選擇-交叉-變異運(yùn)算之后的下一群體這六大步驟[4]。其運(yùn)算流程如下：

2 遺傳算法優(yōu)缺點(diǎn)

在具體進(jìn)行算法設(shè)計(jì)之前有必要對(duì)遺傳算法的優(yōu)缺點(diǎn)進(jìn)行分析，以便更好地進(jìn)行算法的設(shè)計(jì)。首先來(lái)看遺傳算法的優(yōu)點(diǎn)主要表現(xiàn)在不必借助輔助信息、在檢索過(guò)程中造成局部最優(yōu)的可能性低、廣泛的表示可行解、可擴(kuò)展、群體搜索以及便于同其他技術(shù)結(jié)合使用等[5]。而遺傳算法的缺點(diǎn)主要表現(xiàn)在以下幾個(gè)方面，像是過(guò)早收斂、缺乏有效的定量分析、效率同其他優(yōu)化方法相比較低、優(yōu)化問(wèn)題的相關(guān)約束難以系統(tǒng)的表示以及編碼不規(guī)則等等。

3 算法設(shè)計(jì)

通常在實(shí)際操作中會(huì)借助二進(jìn)制編碼的形式表現(xiàn)遺傳算法的解空間，需要注意的是這種方法并不能夠表示TSP問(wèn)題的解，需要用十進(jìn)制編碼更為恰當(dāng)[6]。我們將這20個(gè)城市進(jìn)行編號(hào)，從1標(biāo)到20。

假設(shè)從城市8出發(fā)，經(jīng)過(guò)1-20個(gè)城市最后回到城市8的一條路徑，可以自然地用一維數(shù)組來(lái)表示：

對(duì)于所選取的這20個(gè)旅游城市樣本，其TSP算法中，我們?cè)O(shè)定種群的規(guī)模為40，那么采用二維數(shù)組來(lái)表示解的空間就可以寫(xiě)作：tour[40][20]。

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

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

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

這個(gè)交叉過(guò)程保證了城市的唯一性，避免了沖突。

我們也可以將變異理解為外界環(huán)境對(duì)種群的一種影響。對(duì)于本文中所選擇的20個(gè)樣本城市，使其隨機(jī)產(chǎn)生兩個(gè)比20小的整數(shù)，來(lái)對(duì)整體進(jìn)行分割，我們?cè)O(shè)定這一分割的整數(shù)是8和3，具體如下所示：

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

4 實(shí)驗(yàn)結(jié)果分析

5 結(jié)語(yǔ)

綜上所述，對(duì)于這一典型的優(yōu)化組合算法問(wèn)題，在諸多領(lǐng)域都有著廣泛的應(yīng)用，像是物流配送、交通運(yùn)輸以及電路設(shè)計(jì)等等，在國(guó)內(nèi)外的研究都在不斷深化。希望能夠通過(guò)本文基于遺傳算法的TSP算法來(lái)求解20個(gè)樣本城市的最短旅行線路分析，能夠?yàn)槲覈?guó)關(guān)于遺傳算法以及TSP算法的進(jìn)一步深入研究提供一點(diǎn)借鑒經(jīng)驗(yàn)。

參考文獻(xiàn)：

[1] 張立毅，高楊，費(fèi)騰，王玉婧.求解旅行商問(wèn)題的搜尋者遺傳算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2019，49（07）：115-122.

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

[3] 唐天兵，張銘明，蒙祖強(qiáng).混合蛙跳遺傳算法求解旅行商問(wèn)題[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，43（05）：1811-1817.

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

[5] 陳洋卓，李青青，羅天揚(yáng)，等.基于遺傳算法的TSP問(wèn)題優(yōu)化方法[J].科技風(fēng)，2019（01）：59-60.

[6] 郭豐林.基于遺傳算法的旅游線路規(guī)劃研究[J].現(xiàn)代營(yíng)銷（經(jīng)營(yíng)版），2019（01）：134.

【通聯(lián)編輯：李雅琪】