TSP的幾種求解方法及其優(yōu)缺點(diǎn)

1、TSP的幾種求解方法及其優(yōu)缺點(diǎn)一、什么是TSP問(wèn)題旅行商問(wèn)題，簡(jiǎn)稱TSP,即名定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過(guò)各城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G=(V,A),其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，設(shè)D=(dij)是由頂點(diǎn)i和頂點(diǎn)j之間的距離所組成的距離矩陣，要求確定一條長(zhǎng)度最短的Hamilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短距離。旅行商問(wèn)題可分為如下兩類：1)對(duì)稱旅行商問(wèn)題(dij=dji,ni,j=1,2,3,?,n);2)非對(duì)稱旅行商問(wèn)題(dijwdji,?i,j=1,2,3,?,n)。非對(duì)稱旅行商問(wèn)題較難求解，我們一般是探討對(duì)稱旅行商問(wèn)題

2、的求解。若對(duì)于城市V=Vi,V2,V3,?,Vn的一個(gè)訪問(wèn)順序?yàn)門=t1,t2,t3,?,ti,?,tn,其中tiCV(i=1,2,3,?,n),且記tn+1=t1,則旅行商問(wèn)題的數(shù)學(xué)模型為：minL&d"+1TSP是一個(gè)典型的組合優(yōu)化問(wèn)題，并且是一個(gè)NP完全難題，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)。因此，快速、有效地解決TSP有著重要的理論價(jià)值和極高的實(shí)際應(yīng)用價(jià)值。二、主要求解方法基于TSP的問(wèn)題特性，構(gòu)造型算法成為最先開發(fā)的求解算法，如最近鄰點(diǎn)、最近合并、最近插入、最遠(yuǎn)插入、最近添加、貪婪插入等。但是，由

3、于構(gòu)造型算法優(yōu)化質(zhì)量較差，迄今為止已開發(fā)了許多性能較好的改進(jìn)型搜索算法，主要有：1)模擬退火算法2)禁忌搜索算法3)Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法4)蟻群算法5)遺傳算法6)混合優(yōu)化策略模擬退火算法方法1）編碼選擇：采用描述TSP解的最常用的一種策略一一路徑編碼。2） SA狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì)：對(duì)于基于路徑編碼的SA狀態(tài)產(chǎn)生函數(shù)操作，可將其設(shè)計(jì)為：互換操作（SWAP;逆序操作（INV）;插入操作（INS）。3） SA狀態(tài)接受函數(shù)的設(shè)計(jì)：min1,exp（-A/t）>random0,1準(zhǔn)則是作為接受新狀態(tài)的條件最常用的方案，其中為新舊狀態(tài)的目標(biāo)值差，t為“溫度”。4）初溫和初始狀態(tài)：最常用

4、且可理解的初溫確定方案是，首先隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差：|Amax|,然后由式t0=-Amax/lnpr,其中pr為初始接受概率（理論上應(yīng)接近1,實(shí)際設(shè)計(jì)時(shí)也可以?。３跏紶顟B(tài)可采用啟發(fā)式算法（如20Pt方法）快速得到一個(gè)解，并以此為SA的初始狀態(tài)。5）退溫函數(shù)的設(shè)計(jì)：指數(shù)退溫函數(shù)是最常用的退溫策略（tk=Xtk-1,入為退溫速率）.6）溫度修改準(zhǔn)則和算法終止準(zhǔn)則的設(shè)計(jì)：可采用閾值法設(shè)計(jì)的“溫度修改"和“算法終止”兩準(zhǔn)則。禁忌搜索算法基于禁忌搜索算法的一般設(shè)計(jì)原則，對(duì)典型的組合優(yōu)化問(wèn)題TSP,其算法可以按如下方案實(shí)現(xiàn)：1）初始解：可隨機(jī)產(chǎn)生也可基于問(wèn)題信息借助一

5、些啟發(fā)式方法產(chǎn)生以保證一定的初始性能。2）鄰域結(jié)構(gòu)：常用方法是互換（SWAP、插入（INSERT、逆序（INVERSE等操作。3）候選解的選擇：通常取當(dāng)前解的鄰域解集的一個(gè)子集作為候選解集，而取其中的滿足藐視準(zhǔn)則或非禁忌的最優(yōu)狀態(tài)為最佳候選解。4）禁忌表及其長(zhǎng)度：建議嘗試自適應(yīng)長(zhǎng)度法，譬如根據(jù)目標(biāo)值更新的情況或禁忌頻率信息來(lái)適當(dāng)增加或縮短禁忌表長(zhǎng)度。5）藐視準(zhǔn)則：采用若某個(gè)狀態(tài)的性能優(yōu)于“bestsofar”狀態(tài)，則忽視其禁忌屬性，直接選取它為當(dāng)前狀態(tài)。6）集中搜索和分散搜索策略：分別采用在一定步數(shù)的迭代后基于最佳狀態(tài)進(jìn)行重新初始化并對(duì)其鄰域進(jìn)行多步趨化性搜索和對(duì)算法的重新隨機(jī)初始化或是根據(jù)頻

6、率信息對(duì)一些已知對(duì)象進(jìn)行懲罰。7）終止條件：給定最優(yōu)狀態(tài)連續(xù)保持不變的最大持續(xù)迭代步數(shù)。大量研究表明禁忌搜索算法具有模擬退火、遺傳算法等智能優(yōu)化算法相當(dāng)?shù)男阅?，甚至更?yōu)越。Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法在用Hopfield網(wǎng)絡(luò)求解優(yōu)化問(wèn)題之前，必須將問(wèn)題映射為相應(yīng)的神經(jīng)網(wǎng)絡(luò)。對(duì)TSP的求解，首先將問(wèn)題的合法解映射為一個(gè)置換矩陣，并給出相應(yīng)的能量函數(shù)，然后將滿足置換矩陣要求的能量函數(shù)的最小值與問(wèn)題的最優(yōu)解相對(duì)應(yīng)。若以X,Y表示城市，i表示第幾次訪問(wèn)，dXY表示城市間的距離，VXi表示矩陣中的第X行第i列的元素，則可構(gòu)造出能量函EXZE匕也+兮ZES心心+上Ki產(chǎn)itX-f,£

7、3;%,J.+低£££（匕1*1+乙川）網(wǎng)絡(luò)的動(dòng)態(tài)方程可表示為；號(hào)與EEGJ-廣*Jtxi/D卬匕+九3匕I=畋/=TI+tanlj用數(shù)為:這是nxn個(gè)神經(jīng)元狀態(tài)方程的通用表達(dá)式。為求得TSP的優(yōu)化結(jié)果，需要求解nxn個(gè)非線性一階聯(lián)立微分方程式，以得到置換矩陣中nxn個(gè)元素的全部狀態(tài)。例如可采用如下參數(shù)并給定個(gè)城市的位置和相互距離求解n個(gè)城市的TSPt=1,A=B=50O,C=200,D=500,血=起始條件為隨機(jī)噪聲，令起始uXi如下式收=】依+跖MI*Q1蜘WuXiWU而u00滿足在t=0時(shí)匯XEiVXi=n以利于收斂7。利用數(shù)值計(jì)算方法對(duì)此微分方程組求解，經(jīng)

8、若干次迭代即可求得網(wǎng)絡(luò)各神經(jīng)元的最終狀態(tài)。蟻群算法方法蟻群算法與其他模擬進(jìn)化算法一樣，通過(guò)候選解組成的群體進(jìn)化過(guò)程來(lái)尋找最優(yōu)解。求解TSP的工作過(guò)程為：首先將m只螞蟻按照一定的規(guī)則（例如隨機(jī)）分布在n個(gè)城市，然后每一只螞蟻尋找出一條可行路徑并進(jìn)行局部信息更新，最后尋出所有螞蟻找到的最好路徑進(jìn)行全局信息更新。遺傳算法方法近年來(lái)，遺傳算法已被成功的應(yīng)用于工業(yè)、經(jīng)濟(jì)管理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域，解決了許多問(wèn)題?；谶z傳算法求解TSP的算法實(shí)現(xiàn)，以下幾個(gè)方面需要說(shuō)明：1）遺傳基因編碼方法：目前主要有以下三種比較有效的方法：順序表示路徑表示布爾矩陣表示2）遺傳操作算子：選擇算子：對(duì)于求解TSP,常

9、用的選擇機(jī)制有輪盤賭選擇機(jī)制、最佳個(gè)體保存選擇機(jī)制、期望值模型選擇機(jī)制、排序選擇機(jī)制、聯(lián)賽選擇模型機(jī)制等。交叉算子：采用順序表示技術(shù)可以采用基本遺傳算法的交叉操作例如單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉；采用路徑表示的可用部分匹配交叉、順序交叉、循環(huán)交叉、邊重組交叉；采用布爾矩陣表示的有它獨(dú)特的交和并算子。變異算子：采用順序表示的可采用基本位變異、均勻變異、邊界變異、非均勻變異和高斯變異；采用路徑表示的可用位點(diǎn)變異、逆轉(zhuǎn)變異、對(duì)換變異和插入變異。另外適應(yīng)度函數(shù)可取為哈密爾頓圈的長(zhǎng)度的倒數(shù)（無(wú)懲罰函數(shù)），初始種群可用隨機(jī)方法產(chǎn)生，再確定相應(yīng)的控制參數(shù)及可求解?；旌蟽?yōu)化策略方法譬如大規(guī)模TSP的

10、求解，鑒于問(wèn)題整體求解的復(fù)雜性，在設(shè)計(jì)算法時(shí)可以先考慮空間的分解，利用聚類的方法將問(wèn)題分解為若干子問(wèn)題，然后先用啟發(fā)式方法快速得到子問(wèn)題的近似解，而后以其為初始狀態(tài)利用GASATS等方法和規(guī)則性搜索在一定的混合方式下進(jìn)行指導(dǎo)性優(yōu)化，待各子問(wèn)題求解完畢用臨近原則確定問(wèn)題的整體解，再利用局部改進(jìn)算法對(duì)其作進(jìn)一步加工以得到問(wèn)題的最終解。三、各種方法的優(yōu)缺點(diǎn)及比較由于TSP的典型性，在過(guò)去的幾十年里人們研究了許許多多的求解方法。除了以上介紹的求解方法以及它們的各種改進(jìn)型方法外，還有一些其他的方法也可求解TSP,比如：n-opt法，貪心算法，爬山法，回溯法，分支限界法，EP,混沌搜索、模糊優(yōu)化等。SA,

11、GA和TS作為具有全局優(yōu)化性能的典型Meta-heuristic算法代表，與人工神經(jīng)網(wǎng)絡(luò)統(tǒng)稱為四大現(xiàn)代啟發(fā)式算法。蟻群算法是90年代初才被提出的全新的算法，而混合優(yōu)化策略由于缺乏嚴(yán)格且豐富的理論研究和效率分析也是近年來(lái)也才得到發(fā)展和應(yīng)用。概括地講，SA算法的實(shí)驗(yàn)性能具有質(zhì)量高、初值魯棒性強(qiáng)、通用易實(shí)現(xiàn)的優(yōu)點(diǎn)，最大缺點(diǎn)是往往優(yōu)化過(guò)程較長(zhǎng)；GA的兩個(gè)最顯著的優(yōu)點(diǎn)是隱含并行性和全局解空間搜索，但實(shí)際應(yīng)用時(shí)易出現(xiàn)早熟收斂和收斂性能差等缺點(diǎn)；TS算法是一種局部搜索能力很強(qiáng)的全局迭代尋優(yōu)算法，不足之處在于對(duì)初始解較強(qiáng)的依賴f和串行的迭代搜索過(guò)程；Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法具有簡(jiǎn)單、規(guī)范、快速等優(yōu)點(diǎn)，

12、但是其優(yōu)化性和魯棒性比較差；蟻群算法是一種本質(zhì)并行的算法，但其搜索時(shí)間比較長(zhǎng)，也容易陷于局部最優(yōu)解，使搜索停滯；混合優(yōu)化策略若能得到有效的設(shè)計(jì)，真正做到不同方法的取長(zhǎng)補(bǔ)短將會(huì)產(chǎn)生更好的優(yōu)化效率。由于很少有論文提供求解TSP的一些特定實(shí)例的計(jì)算時(shí)間，而只報(bào)道函數(shù)評(píng)估的次數(shù)，這使得不同方法之間的比較略顯困難，因?yàn)椴煌乃阕泳哂胁煌臅r(shí)間復(fù)雜性。目前的大多數(shù)文獻(xiàn)都是將所提方法與其他方法作比較，比較中使用的兩類主要的測(cè)試實(shí)例為：1)隨機(jī)分布的TSP城市。典型情況是與一個(gè)均勻隨機(jī)變量相對(duì)應(yīng)并假定采用歐式距離度量。這里，關(guān)于最短的TSP路徑的期望長(zhǎng)度L3的一個(gè)經(jīng)典公式為L(zhǎng)3=knR,其中n為城市數(shù)目，R是

13、一個(gè)正方形的面積，隨機(jī)放置的各城市均位于該正方形之內(nèi)，k為一個(gè)經(jīng)驗(yàn)常數(shù)，稱為Held-Karp下界。對(duì)于n城市的隨機(jī)歐氏TS(n>100),k與n的期望比例關(guān)系為k=+。Bonomi和Lutton建議采用k=。2)TSP公共測(cè)試實(shí)例庫(kù)(TSPLIB18)。它還提供了有文獻(xiàn)報(bào)道的最優(yōu)解或目前已知的最好解。四、結(jié)論對(duì)于TSP,目前還不存在能找到完美解的方法，這個(gè)問(wèn)題是NP難的：目前還沒有任何我們只能產(chǎn)生一些近似完美算法能在與城市總數(shù)呈多項(xiàng)式關(guān)系的時(shí)間復(fù)雜性下找到完美解。解，在合理的運(yùn)行時(shí)間里使其與完美解盡可能的接近。從目前發(fā)表的各種求解TSP的論文的結(jié)論來(lái)看，少于100個(gè)城市的TSP例子很適合于用全局優(yōu)化技術(shù)求解，但是要考慮城市規(guī)模比這大得多的TSP實(shí)例則需要采用啟發(fā)式方法。為了進(jìn)一步提高算法的全局優(yōu)化能力，避免搜索過(guò)程陷入局部極小，現(xiàn)已提出的改進(jìn)策略主要有：并行多鄰域搜索，平滑優(yōu)化曲面形狀，引進(jìn)重升溫、嫡抽