林沐霖　何茂森　朱俊明

摘 要 TSP是數(shù)學(xué)領(lǐng)域內(nèi)一道著名的難題之一，如何求解一直是學(xué)術(shù)界研究的熱點(diǎn)問(wèn)題。本文首先闡述了TSP問(wèn)題的基本概念，介紹了TSP問(wèn)題的一般描述及數(shù)學(xué)模型，然后歸納了現(xiàn)有對(duì)TSP問(wèn)題求解的較為有效的方法—蟻群算法和遺傳算法，最后闡述了TSP的應(yīng)用領(lǐng)域。

關(guān)鍵詞 TSP 遺傳算法 蟻群算法

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

1 TSP問(wèn)題的基本概念

TSP（Traveling Salesman Problem）問(wèn)題，可譯為旅行商問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名的組合優(yōu)化類難題之一。

1.1 TSP問(wèn)題的描述

現(xiàn)有對(duì)TSP問(wèn)題的標(biāo)準(zhǔn)描述為：已知有城市數(shù)量為，一位旅行商人從其中的某一個(gè)城市出發(fā)，途中需要經(jīng)過(guò)所有的城市，但經(jīng)過(guò)的次數(shù)有且僅有一次，最后再回到出發(fā)的城市，怎樣規(guī)劃路線才能使旅行商所走的路線最短。

1.2 TSP問(wèn)題的數(shù)學(xué)模型

設(shè)城市集合為V={v1，v2，…，vA}，對(duì)城市的訪問(wèn)順序?yàn)門={t1，t2，…，tA}，其中ti=V（i=1，…A），而且ti+1=t1，則問(wèn)題的目標(biāo)函數(shù)如下：

意為目標(biāo)函數(shù)的最優(yōu)值為所有途徑城市之間的路徑和最短。

1.3 TSP問(wèn)題的分類

從上述描述中可以看出TSP問(wèn)題即是在若干城市或地點(diǎn)之間尋找一條回路，根據(jù)vi→vi+1與vi+1→vi的距離是否相當(dāng)，可以將TSP問(wèn)題分為對(duì)稱TSP問(wèn)題和非對(duì)稱TSP問(wèn)題。

2 TSP問(wèn)題的求解方法

TSP問(wèn)題已經(jīng)被證明是一個(gè)NP-hard問(wèn)題，即在P≠NP的假設(shè)下，找不到一個(gè)多項(xiàng)式時(shí)間算法來(lái)求解其最優(yōu)解。TSP問(wèn)題很容易被描述清楚，但是卻較難找到合適的求解算法，自1932年TSP問(wèn)題出現(xiàn)以來(lái)，已經(jīng)有諸多學(xué)者在研究相關(guān)領(lǐng)域的問(wèn)題，但至今仍為找到有效的方法。

曾經(jīng)傳統(tǒng)的經(jīng)典優(yōu)化算法經(jīng)常被用來(lái)求解TSP問(wèn)題的解，但是當(dāng)城市數(shù)量較大時(shí)，就難以快速找到最優(yōu)解。隨著人工智能的發(fā)展，出現(xiàn)了許多獨(dú)立于問(wèn)題的獨(dú)立算法，如蟻群算法、粒子群算法、遺傳算法、魚群算法、狼群算法等等。這些算法通過(guò)模擬自然界的某些現(xiàn)象而得出求解復(fù)雜問(wèn)題的新思路和新方法。在優(yōu)化領(lǐng)域，這類算法的由于其很好的收斂性和有效性而被廣泛使用。

2.1蟻群算法求解TSP問(wèn)題

蟻群算法最初是通過(guò)對(duì)螞蟻群落的觀察，受蟻群行為特征啟發(fā)而得出的。螞蟻是一種群居昆蟲，在覓食、清理巢穴等活動(dòng)中，彼此依賴、相互協(xié)作共同完成特定的任務(wù)。就個(gè)體來(lái)講，單個(gè)螞蟻的智力和體力是極其有限的，服務(wù)于整個(gè)群落的生存與發(fā)展；就群體來(lái)講，蟻群在行為上的分工協(xié)作、在完成任務(wù)過(guò)程中所體現(xiàn)的自組織特征等反應(yīng)出蟻群具有較高的智能和自我管理能力，具有很高層次組織性，這使得蟻群能夠完成一些復(fù)雜的任務(wù)。

蟻群的特點(diǎn)是并發(fā)性、魯棒性、正反饋性等。在蟻群算法求解問(wèn)題的過(guò)程中，利用蟻群在問(wèn)題空間中同時(shí)構(gòu)造問(wèn)題的多個(gè)解體現(xiàn)了算法的并發(fā)性。蟻群不會(huì)因?yàn)閱蝹€(gè)螞蟻尋找到較差的解或者因?yàn)閱?wèn)題空間發(fā)生改變而使得算法喪失作用。這體現(xiàn)了魯棒性。在螞蟻構(gòu)造問(wèn)題解的過(guò)程中，以蟻群覓食行為為例，會(huì)在經(jīng)過(guò)的解的路上釋放信息素，而解空間中活得信息素越多的路徑，對(duì)螞蟻的吸引力就越大，使更多的螞蟻經(jīng)過(guò)該路徑并進(jìn)一步在上面釋放信息素，這體現(xiàn)了算法的正反饋性。

矯德強(qiáng)等人使用非線性尋優(yōu)算法增強(qiáng)蟻群算法的局部搜索能力，鄭旭峰等人使用K-means聚類算法提高蟻群算法精度等，改進(jìn)了蟻群算法的收斂速度及容易陷入局部最優(yōu)解的問(wèn)題，并將其應(yīng)用在TSP問(wèn)題中。

2.2遺傳算法求解TSP問(wèn)題

遺傳算法的概念是由Holland于1973年受生物進(jìn)化論的啟發(fā)而首次提出的，它是一種通過(guò)模擬生物界自然選擇和遺傳機(jī)制的隨機(jī)搜索算法。

遺傳算法是一種比較通用的優(yōu)化算法，編碼技術(shù)和遺傳操作比較簡(jiǎn)單，主要操作有選擇、交叉和變異。根據(jù)TSP的目的，只是求最短路徑，而傳統(tǒng)解法非常在意得到路徑的過(guò)程，遺傳算法直接將目標(biāo)指向距離最短，因此能較快地得到問(wèn)題的答案。

3 TSP問(wèn)題的應(yīng)用領(lǐng)域

3.1 TSP在物流配送中的應(yīng)用

物流配送是指從貨運(yùn)總公司出發(fā)，將貨物沿途送到指定的各個(gè)分公司，最后返回總公司的配送路線。此類問(wèn)題是在一個(gè)平面區(qū)域內(nèi)對(duì)所有點(diǎn)的遍歷問(wèn)題，即選擇一條閉合線路可以覆蓋所有點(diǎn)，并使得路線在某種條件下達(dá)到最優(yōu)，符合TSP問(wèn)題的數(shù)學(xué)模式，可以將其應(yīng)用于此類問(wèn)題中。

3.2 TSP在機(jī)器人路徑規(guī)劃中的應(yīng)用

機(jī)器人的路徑規(guī)劃問(wèn)題主要是找到一條從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的最佳或次佳路徑，或是在盡可能短的時(shí)間內(nèi)游歷盡可能多的目標(biāo)點(diǎn)，類似于傳統(tǒng)的TSP問(wèn)題，因此同樣可以采用TSP問(wèn)題的方法進(jìn)行求解。

參考文獻(xiàn)

[1] Garey，M.R&D.S.Johnson.Computers and Intractability： A Guide to the Theory of NP-Completeness[M]. San Francisco： Freeman W H， 1979.

[2] 許能闖.基于改進(jìn)蟻群算法的TSP問(wèn)題研究[J].軟件導(dǎo)刊， 2018（02）.

[3] 矯德強(qiáng)，?；搓?yáng).一種改進(jìn)蟻群算法在TSP問(wèn)題上的應(yīng)用[J].科技與創(chuàng)新，2018（01）：145-146.

[4] 鄭旭峰，周健勇.K-means聚類蟻群優(yōu)化算法求解大型TSP問(wèn)題[J].物流科技，2018（02）：37-40