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

1、一、什么是TSP問題旅行商問題，簡稱TSP,即給定n個城市和兩兩城市之間的距離，要求確定一條經(jīng)過各 城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G= (V, A),其中V為頂點集，A為 各頂點相互連接組成的邊集，設(shè)D= (dij)是由頂點i和頂點j之間的距離所組成的距離矩 陣，要求確定一條長度最短的Hamilton回路，即遍歷所有頂點當(dāng)且僅當(dāng)一次的最短距鷹。旅行商問題可分為如下兩類：1) 對稱旅行商問題(dij=dji, ni, j=l, 2, 3, - , n)；2) 非對稱旅行商問題(dijHdji, b i, j=l, 2, 3, “，n)。非對稱旅行商問題較難求解，我們一般是探討對

2、稱旅行商問題的求解。若對于城市 V=vi, V2, V3, - , Vn的一個訪問順序為 T=tj, t2, ta, - , ti, “，tn,It其中tiGV (i=l, 2, 3,，n),且記S+1=S則旅行商問題的數(shù)學(xué)模型為：加工仏gTSP是一個典型的組合優(yōu)化問題，并且是一個NP完全難題，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種 復(fù)雜問題的集中概括和簡化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)。 因此，快速、有效地解決TSP有著重要的理論價值和極高的實際應(yīng)用價值。二、主要求解方法基于TSP的問題特性，構(gòu)造型算法成為最先開發(fā)的求解算法，如最近鄰點、最近合并、 最近插入、最遠(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è)計：對于基于路徑編碼的SA狀態(tài)產(chǎn)生函數(shù)操作，可將其設(shè)計 為：互換操作(SWAP)；逆序操作(INV)；插入操作(INS)o3) SA狀態(tài)接受函數(shù)的設(shè)計：minl, exp (-A/t) random0, 1準(zhǔn)則是作為接受新 狀態(tài)的條件最常用的方案，其中為新舊狀態(tài)的目標(biāo)值差，

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

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

6、性搜索和對算法的重新隨機(jī)初始化或是根據(jù)頻率信息對一些 已知對象進(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)化問題之前，必須將問題映射為相應(yīng)的神經(jīng)網(wǎng)絡(luò)。對TSP的 求解，首先將問題的合法解映射為一個置換矩陣，并紿出相應(yīng)的能量函數(shù)，然后將滿足置換 矩陣要求的能量函數(shù)的最小值與問題的最優(yōu)解相對應(yīng)。若以X, Y表示城市，i表示第幾次訪問，dXY表示城市間的距離，VXi表示矩陣中的第X行第i列的元素，則可構(gòu)造出能量函E二十工工工側(cè)燈工

7、工工以幾+乙 X i 產(chǎn)i厶 i X YHXff EEvx/-p Z 工工亦 f丿乙、x丿丿乙 X Y#X r網(wǎng)絡(luò)的動態(tài)方程可表示為；數(shù)為:弋A工V“B工V旳Y工XD，鳳丫(8 i+l + 人 r- I 丿 Y這是nXn個神經(jīng)元狀態(tài)方程的通用表達(dá)式。為求得TSP的優(yōu)化結(jié)果，需要求解nXn 個非線性一階聯(lián)立澈分方程式，以得到置換矩陣中nXn個元素的全部狀態(tài)。例如可采用如下參數(shù)并給定個城市的位置和相互距離求解n個城市的TSP： t=l, A=B=500, C=200, D=500, uO=起始條件為隨機(jī)棗聲，令起始uXi如下式% = %）+ 九XiI-Q 1 如 W 嘰Xi W Q 1而u00滿足

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

9、比較有效的方法： 順序表示 路徑表示 布爾矩陣表示2）遺傳操作算子： 選擇算子：對于求解TSP,常用的選擇機(jī)制有輪盤賭選擇機(jī)制、最佳個體保存選擇機(jī) 制、期望值模型選擇機(jī)制、排序選擇機(jī)制、聯(lián)賽選擇模型機(jī)制等。 交叉算子：采用順序表示技術(shù)可以采用基本遺傳算法的交叉操作例如單點交叉、兩點 交叉、多點交叉和均勻交叉；采用路徑表示的可用部分匹配交叉、順序交叉、循環(huán)交叉、邊 重組交叉；采用布爾矩陣表示的有它獨特的交和并算子。 變異算子：采用順序表示的可采用基本位變異、均勻變異、邊界變異、非均勻變異和 高斯變異；采用路徑表示的可用位點變異、逆轉(zhuǎn)變異、對換變異和插入變異。另外適應(yīng)度函 數(shù)可取為哈密爾頓圈的長度

10、的倒數(shù)（無懲罰函數(shù)），初始種群可用隨機(jī)方法產(chǎn)生，再確定相 應(yīng)的控制參數(shù)及可求解?；旌蟽?yōu)化策略方法譬如大規(guī)模TSP的求解，鑒于問題整體求解的復(fù)雜性，在設(shè)計算法時可以先考慮空間的 分解，利用聚類的方法將問題分解為若干子問題，然后先用啟發(fā)式方法快速得到子問題的近 似解，而后以其為初始狀態(tài)利用GA, SA, TS等方法和規(guī)則性搜索在一定的混合方式下進(jìn)行 指導(dǎo)性優(yōu)化，待各子問題求解完畢用臨近原則確定問題的整體解，再利用局部改進(jìn)算法對其 作進(jìn)一步加工以得到問題的最終解。三、各種方法的優(yōu)缺點及比較由于TSP的典型性，在過去的幾十年里人們研究了許許多多的求解方法。除了以上介紹 的求解方法以及它們的各種改進(jìn)型方

11、法外，還有一些其他的方法也可求解TSP,比如：n-opt 法，貪心算法，爬山法，回溯法，分支限界法，EP,混沌搜索、模糊優(yōu)化等。SA, GA和TS作為具有全局優(yōu)化性能的典型Meta-heuristic算法代表，與人工神經(jīng)網(wǎng) 絡(luò)統(tǒng)稱為四大現(xiàn)代啟發(fā)式算法。蟻群算法是90年代初才被提出的全新的算法，而混合優(yōu)化 策略由于缺乏嚴(yán)格且豐富的理論研究和效率分析也是近年來也才得到發(fā)展和應(yīng)用。概括地 講，SA算法的實驗性能具有質(zhì)量高、初值魯棒性強(qiáng)、通用易實現(xiàn)的優(yōu)點，最大缺點是往往 優(yōu)化過程較長；GA的兩個最顯著的優(yōu)點是隱含并行性和全局解空間搜索，但實際應(yīng)用時易 出現(xiàn)早熟收斂和收斂性能差等缺點；TS算法是一種局部

12、搜索能力很強(qiáng)的全局迭代尋優(yōu)算法, 不足之處在于對初始解較強(qiáng)的依賴性和串行的迭代搜索過程；Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化算法 具有簡單、規(guī)范、快速等優(yōu)點，但是其優(yōu)化性和魯棒性比較差；蟻群算法是一種本質(zhì)并行的 算法，但其搜索時間比較長，也容易陷于局部最優(yōu)解，使搜索停滯；混合優(yōu)化策略若能得到 有效的設(shè)計，真正做到不同方法的取長補(bǔ)短將會產(chǎn)生更好的優(yōu)化效率。由于很少有論文提供求解TSP的一些特定實例的計算時間，而只報道函數(shù)評估的次數(shù)， 這使得不同方法之間的比較略顯困難，因為不同的算子具有不同的時間復(fù)雜性。目前的大多 數(shù)文獻(xiàn)都是將所提方法與其他方法作比較，比較中使用的兩類主要的測試實例為：1) 隨機(jī)分布的T

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