tsp問題演算法
① 閬椾紶綆楁硶瑙ｅ喅TSP闂棰
1885騫村勾錛岃揪灝旀枃鐢ㄨ嚜鐒墮夋嫨鏉ヨВ閲婄墿縐嶇殑璧鋒簮鍜岀敓鐗╃殑榪涘寲銆
杈懼皵鏂囩殑鑷鐒墮夋嫨瀛﹁村寘鎷涓変釜鏂歸潰錛
涓婁笘綰20騫翠唬錛屼竴浜涘﹁呯敤緇熻＄敓鐗╁﹀拰縐嶇兢閬椾紶瀛﹂噸鏂拌В閲婅揪灝旀枃鑷鐒墮夋嫨鐞嗚猴紝褰㈡垚鐜頒唬緇煎悎榪涘寲璁恆
縐嶇兢閬椾紶瀛﹁や負錛
閬椾紶綆楁硶涓涓庣敓鐗╁︾浉鍏崇殑姒傚康鍜屾湳璇涓庝紭鍖栭棶棰樹腑鐨勬弿榪扮殑鍏崇郴錛
涓婁笘綰60騫翠唬涓鏈燂紝Holland鎻愬嚭浣嶄覆緙栫爜鎶鏈銆
榪欑嶆妧鏈閫傜敤浜庡彉寮傚拰浜ゅ弶鎿嶄綔錛岃屼笖寮鴻皟灝嗕氦鍙変綔涓轟富瑕佺殑閬椾紶鎿嶄綔銆
Holland灝嗚ョ畻娉曠敤浜庤嚜鐒跺拰浜哄伐緋葷粺鐨勮嚜閫傚簲琛屼負鐮旂┒涓錛屽湪1975鍑虹増浜嗗紑鍒涙ц憲浣溾淎daptation in Natural and Artifical System鈥濄
涔嬪悗錛屼粬灝嗙畻娉曞簲鐢ㄥ埌浼樺寲浠ュ強瀛︿範涓錛屽苟灝嗗叾鍛藉悕涓洪仐浼犵畻娉曪紙綆縐癎A錛夈
閬椾紶綆楁硶鍩烘湰鎬濊礬錛
嫻佺▼鍥撅細
鏈甯哥敤絳栫暐錛氳礬寰勭紪鐮
鐩存帴閲囩敤鍩庡競鍦ㄨ礬寰勪腑鐨勪綅緗鏉ユ瀯閫犵敤浜庝紭鍖栫殑鐘舵併
渚嬶細涔濆煄甯俆SP闂棰橈紝璺寰勶細5-4-1-7-9-8-6-2-3
璺寰勭紪鐮侊細(5 4 1 7 9 8 6 2 3)
杈撳叆錛
10鍩庡競鍧愭爣涓猴細
(41, 94)錛(37, 84)錛(54, 67)錛(25, 62)錛(7, 64)錛 (2, 99)錛(68, 58)錛(71, 44)錛(54, 62)錛 (83, 69)
榪愯岀粨鏋滐細
python婧愮爜錛 https://github.com/wangjiosw/GA-TSP
GA鏄涓縐嶉氱敤鐨勪紭鍖栫畻娉曪紝瀹冪殑浼樼偣鏈夛細
闅忕潃璁＄畻鏈烘妧鏈鐨勫彂灞曪紝GA鎰堟潵鎰堝緱鍒頒漢浠鐨勯噸瑙嗭紝騫跺湪鏈哄櫒瀛︿範銆佹ā寮忚瘑鍒銆佸浘鍍忓勭悊銆佺炵粡緗戠粶銆佷紭鍖栨帶鍒躲佺粍鍚堜紭鍖栥乂LSI璁捐°侀仐浼犲︾瓑棰嗗煙寰楀埌浜嗘垚鍔熷簲鐢ㄣ
② tSp Concorder演算法原理
tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。
③ TSP解決之道——蟻群演算法
蟻群演算法java實現以及TSP問題蟻群演算法求解
蟻群演算法原理與應用講解
蟻群演算法原理與應用1 -自然計算與群體智能
1、蟻群演算法(Ant Clony Optimization,ACO)是一種群智能演算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協作而表現出智能行為，從而為求解復雜問題提供了一個新的可能性。
2、是一種仿生學的演算法，是由自然界中螞蟻覓食的行為而啟發。（artificial ants；雙橋實驗）
3、運作機理：當一定路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，後來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度，而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。
4、蟻群演算法歐化過程中的兩個重要原則：
a、螞蟻在眾多路徑中轉移路線的選擇規則。
b、全局化信息素更新規則。信息素更新的實質就是人工螞蟻根據真實螞蟻在訪問過的邊上留下的信息素和蒸發的信息素來模擬真實信息素數量的變化，從而使得越好的解得到越多的增強。這就形成了一種自催化強化學習(Autocatalytic Reinforcement Learning)的正反饋機制。
1、描述：螞蟻數量m；城市之間的信息素矩陣pheromone；每次迭代的m個螞蟻的最短路徑 BestLength；最佳路徑BestTour。 每隻螞蟻都有 ：禁忌表(Tabu)存儲已訪問過的城市，允許訪問的城市表(Allowed)存儲還可以訪問的城市，矩陣（ Delta ）來存儲它在一個循環（或者迭代）中給所經過的路徑釋放的信息素。
2、 狀態轉移概率 ：在搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率。在t時刻螞蟻k由元素（城市）i轉移到元素（城市）j的狀態轉移概率：
τij (t) ：時刻路徑(i, j)上的信息量。ηij=1/dij ：啟發函數。
α為信息啟發式因子 ，表示軌跡的相對重要性，反映了螞蟻在運動過程中積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向於選擇其它螞蟻經過的路徑，螞蟻之間的協作性越強；
β為期望啟發式因子 ，表示能見度的相對重要性，反映螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態狀態轉移概率越接近於貪心規則；
3、 息素更新規則 ：
ρ表示信息素揮發系數；Δτij(t)表示本次循環中路徑(i, j)上的信息素增量，初始時刻Δτij(t) =0。
4、三種信息增量計算方法：
區別：第一種利用了全局信息，在走一圈後更新。二、三中都利用的是局部信息。通常使用第一種。
5、TSP中流程圖
④ 退火演算法的應用領域及示例
作為模擬退火演算法應用，討論旅行商問題(Travelling Salesman Problem,簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i,j) i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。
求解TSP的模擬退火演算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1,……,n}的所有循環排列的集合,S中的成員記為(w1,w2,……,wn)，並記wn+1= w1。初始解可選為(1,……,n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的產生 隨機產生1和n之間的兩相異數k和m,
若k<m,則將
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變為：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變為：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。
也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(w1,w2,……,wn)變換為(u1,u2,……,un)，則代價函數差為：
根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序：
Procere TSPSA:
begin
init-of-T; { T為初始溫度}
S={1,……,n}; {S為初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 從當前迴路S產生新迴路S′}
Δt:=f(S′））-f(S);{f(S)為路徑總長}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：
⑴ 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。
⑵ 退火速度問題。
模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
⑶ 溫度管理問題。
溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式：
T(t+1)=k×T(t)
式中k為正的略小於1.00的常數,t為降溫的次數 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。
缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。
經典模擬退火演算法的缺點：
⑴如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；
⑵如果降溫過程過快，很可能得不到全局最優解。
模擬退火演算法的改進
⑴ 設計合適的狀態產生函數，使其根據搜索進程的需要
表現出狀態的全空間分散性或局部區域性。
⑵ 設計高效的退火策略。
⑶ 避免狀態的迂迴搜索。
⑷ 採用並行搜索結構。
⑸ 為避免陷入局部極小，改進對溫度的控制方式
⑹ 選擇合適的初始狀態。
⑺ 設計合適的演算法終止准則。
也可通過增加某些環節而實現對模擬退火演算法的改進。
主要的改進方式包括：
⑴ 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。
⑵ 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。
⑶ 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。
⑷ 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。
⑸ 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。
⑹上述各方法的綜合應用。
⑤ 爬山演算法（Hill Climbing）解決旅行商問題（TSP）
旅行商問題 TSP（Travelling Salesman Problem）是數學領域中著名問題之一。
TSP問題被證明是 NP完全問題 ，這類問題不者寬腔能用精確演算法實現，而需要使用相似演算法。
TSP問題分為兩類： 對稱TSP （Symmetric TSP）以及 非對稱TSP （Asymmetric TSP）
本文解決的是對稱TSP
假設：A表示城市A，B表示城市B，D(A->B)為城市A到城市B的距離，同理D(B->A)為城市B到城市A的距離
對稱TSP中，D(A->B) = D(B->A)，城巧升市間形成無向圖
非對稱TSP中，D(A->B) ≠ D(B->A)，城市間形成有向圖
現實生活中，可能出現單行線、交通事故、機票往返價格不同等情況，均可以打破對稱性。
爬山演算法是一種局部擇優的方法，採用啟發式方法。直觀的解釋如下圖：
爬山演算法，顧名思義就是 爬山 ，找到第一個山峰的時候就停止，作為演算法的輸出結果。所以，爬首衫山演算法容易把局部最優解A作為演算法的輸出，而我們的目的是找到全局最優解B。
如下圖所示，盡管在這個圖中的許多局部極大值，仍然可以使用 模擬退火演算法（Simulated Annealing） 發現全局最大值。
必要解釋詳見注釋
此處根據經緯度計算城市間距離的公式，請參考 Calculate distance between two latitude-longitude points? (Haversine formula)
此處初始化數據源可以使用 TSPLIB 中所提供的數據，此程序大致闡述爬山演算法的實現。
編寫於一個失眠夜
菜鳥一枚，歡迎評論區相互交流，加速你我成長•ᴗ•。