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

1、TSP的幾種求解方法及其優(yōu)缺點一、什么是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 , n j j=1, 2, 3, n);2)非對稱旅行商問題(dijwdji, i, j=1, 2, 3, n)o非對稱旅行商

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

3、合并、最近插入、最遠插入、最近添加、 貪婪插入等。但是，由于構(gòu)造型算法優(yōu)化 質(zhì)量較差，迄今為止已開發(fā)了許多性能較 好的改進型搜索算法，主要有：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）。3） SA狀態(tài)接受函數(shù)的設(shè)計：min1 , exp （-A/t） >random0 , 1準(zhǔn)則是作為接 受

4、新狀態(tài)的條件最常用的方案，其中為 新舊狀態(tài)的目標(biāo)值差，t為“溫度”。4）初溫和初始狀態(tài)：最常用且可理 解的初溫確定方案是，首先隨機產(chǎn)生一組 狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差： | A max| ,然后由式 t0=- max/lnpr ,其中 pr為初始接受概率（理論上應(yīng)接近 1,實 際設(shè)計時也可以?。?。初始狀態(tài)可采用啟 發(fā)式算法（如2opt方法）快速得到一個解， 并以此為SA的初始狀態(tài)。5）退溫函數(shù)的設(shè)計：指數(shù)退溫函數(shù) 是最常用的退溫策略（tk=入tk-1 ,人為退 溫速率）。6）溫度修改準(zhǔn)則和算法終止準(zhǔn)則的設(shè)計：可采用閾值法設(shè)計的“溫度修改” 和”算法終止”兩準(zhǔn)則。禁忌搜索算法基于禁忌搜索

5、算法的一般設(shè)計原則， 對典型的組合優(yōu)化問題 TSP,其算法可以 按如下方案實現(xiàn)：1）初始解：可隨機產(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)前

6、狀態(tài)。6）集中搜索和分散搜索策略：分別 采用在一定步數(shù)的迭代后基于最佳狀態(tài) 進行重新初始化并對其鄰域進行多步趨 化性搜索和對算法的重新隨機初始化或 是根據(jù)頻率信息對一些已知對象進行懲 罰。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

7、, Y表示城市，i表示第幾次訪問，dXY表示 城市間的距離，VXi表示矩陣中的第X行 第i列的元素，則可構(gòu)造出能量函數(shù)為：e 二 X £ £ % + E £ Z 匕+ £ K i 內(nèi)i X£ ZX J ：qEE £如匕Z+v， 上、* i/上 算 r*鬣 t網(wǎng)絡(luò)的動態(tài)方程可表示為；*，個一月EE”. ai內(nèi)¥XK X i/ £電 Wil +%f”)vxi = ft 收)=T 1 + lan j 叢 上l k力這是nx n個神經(jīng)元狀態(tài)方程的通用 表達式。為求得TSP的優(yōu)化結(jié)果，需要求 解nx n個非線性一階聯(lián)立微分方

8、程式， 以得到置換矩陣中nxn個元素的全部狀 態(tài)。例如可采用如下參數(shù)并給定個城市的 位置和相互距離求解n個城市的TSP t=1, A=B=500, C=200, D=500, u0=起始條件為 隨機噪聲，令起始uXi如下式uxt = / + 6Ms I -0 I 珈 W5為,W(1 1 J而u00滿足在t=0時£ XE iVXi=n以利 于收斂7。利用數(shù)值計算方法對此微分方 程組求解，經(jīng)若干次迭代即可求得網(wǎng)絡(luò)各 神經(jīng)元的最終狀態(tài)。蟻群算法方法蟻群算法與其他模擬進化算法一樣，通過候選解組成的群體進化過程來尋找最優(yōu)解。求解TSP的工作過程為：首先將 m只螞蟻按照一定的規(guī)則（例如隨機）分

9、布在n個城市，然后每一只螞蟻尋找出一 條可行路徑并進行局部信息更新，最后尋 出所有螞蟻找到的最好路徑進行全局信 息更新。遺傳算法方法近年來，遺傳算法已被成功的應(yīng)用于 工業(yè)、經(jīng)濟管理、交通運輸、工業(yè)設(shè)計等 不同領(lǐng)域，解決了許多問題。基于遺傳算 法求解TSP的算法實現(xiàn)，以下幾個方面需 要說明：1）遺傳基因編碼方法：目前主要有以下 三種比較有效的方法：順序表示路徑表示布爾矩陣表示2）遺傳操作算子：選擇算子：對于求解 TSP常用的 選擇機制有輪盤賭選擇機制、最佳個體保 存選擇機制、期望值模型選擇機制、排序選擇機制、聯(lián)賽選擇模型機制等。交叉算子：采用順序表示技術(shù)可以 采用基本遺傳算法的交叉操作例如單點

10、交叉、兩點交叉、多點交叉和均勻交叉； 采用路徑表示的可用部分匹配交叉、順序 交叉、循環(huán)交叉、邊重組交叉；采用布爾 矩陣表示的有它獨特的交和并算子。變異算子：采用順序表示的可采用 基本位變異、均勻變異、邊界變異、非均 勻變異和高斯變異；采用路徑表示的可用 位點變異、逆轉(zhuǎn)變異、對換變異和插入變 異。另外適應(yīng)度函數(shù)可取為哈密爾頓圈的 長度的倒數(shù)（無懲罰函數(shù)），初始種群可 用隨機方法產(chǎn)生，再確定相應(yīng)的控制參數(shù) 及可求解?；旌蟽?yōu)化策略方法譬如大規(guī)模TSP的求解，鑒于問題整 體求解的復(fù)雜性，在設(shè)計算法時可以先考 慮空間的分解，利用聚類的方法將問題分 解為若干子問題，然后先用啟發(fā)式方法快 速得到子問題的近似

11、解，而后以其為初始 狀態(tài)利用GA, SA TS等方法和規(guī)則性搜 索在一定的混合方式下進行指導(dǎo)性優(yōu)化， 待各子問題求解完畢用臨近原則確定問 題的整體解，再利用局部改進算法對其作 進一步加工以得到問題的最終解。三、各種方法的優(yōu)缺點及比較由于TSP的典型性，在過去的幾十年 里人們研究了許許多多的求解方法。除了 以上介紹的求解方法以及它們的各種改 進型方法外，還有一些其他的方法也可求 解TSP,比如：n-opt法，貪心算法，爬山 法，回溯法，分支限界法，EP,混沌搜索、 模糊優(yōu)化等。SA, GA和TS作為具有全局優(yōu)化性能 的典型 Meta-heuristic算法代表，與人工 神經(jīng)網(wǎng)絡(luò)統(tǒng)稱為四大現(xiàn)代啟發(fā)

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

13、也容易陷于局部最優(yōu)解， 使搜索停滯；混合優(yōu)化策略若能得到有效 的設(shè)計，真正做到不同方法的取長補短將 會產(chǎn)生更好的優(yōu)化效率。由于很少有論文提供求解 TSP的一些 特定實例的計算時間，而只報道函數(shù)評估 的次數(shù)，這使得不同方法之間的比較略顯 困難，因為不同的算子具有不同的時間復(fù) 雜性。目前的大多數(shù)文獻都是將所提方法 與其他方法作比較，比較中使用的兩類主 要的測試實例為：1）隨機分布的TSP城市。典型情況 是與一個均勻隨機變量相對應(yīng)并假定采 用歐式距離度量。這里，關(guān)于最短的TSP 路徑的期望長度 L3的一個經(jīng)典公式為L3=kn - R,其中n為城市數(shù)目，R是一個 正方形的面積，隨機放置的各城市均位于

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