2-opt
2-opt
2-opt其實是2-optimization的縮寫，簡言之就是兩元素優化。也可以稱作2-exchange。2-opt algorithm最早是由 croes 發表在Operations Research上的一篇名為A Method for Solving Traveling-Salesman Problems的論文（該論文可在OR資料庫付費下載）中提出的。最初是用於解決TSP問題的演演算法。
2-opt屬於局部搜索演演算法，局部搜索演演算法（local search algorithm）是解決組合優化問題的有效工具。1986年，Glover對局部搜索演演算法進行推廣衍生，提出了禁忌搜索演演算法（tabu search algorithm），如今已經廣為人知並且在組合優化領域中得到了廣泛的應用。
這裡我們就舉一個2-opt演演算法最原始應用的例子——解決TSP問題：
假設有一個旅行商必須要從A城市出發經過BCDEFGH這幾個城市最後回到A城市(可以理解為約束條件)，目標函數是路程最短(更廣義的說是 費用最少)。
首先我們可以任選一個可行解s={A,B,C,D,E,F,G,H,A}，並假設s是最優解Smin。然後使用2-opt演演算法進行問題的求解：隨機選取兩點i和k，將i之前的路徑不變添加到新路徑中，將i到k之間的路徑翻轉其編號后添加到新路徑中，將k之後的路徑不變添加到新路徑中。
原路徑: A ==> B ==> C ==> D ==> E ==> F ==>G ==> H ==> A
i = 4, k =7
新路徑:
1. (A ==> B ==>C)
2. A ==> B ==> C==> (G ==> F ==> E ==> D)
3. A ==> B ==> C==> G ==> F ==> E ==> D (==> H ==> A)
從而獲得一個新的可行解。將可行解代入目標函數可得目標函數值，將其與Smin的目標函數值比較，取兩者目標函數值較小的可行解為Smin，直到找不到比Smin還小的函數值為止。至此，該TSP問題已用2-opt演演算法解決。
很容易將2-opt演演算法推廣到k-opt演演算法，即將上例s中的k個元素進行調換，以更換可行解並檢驗其在目標函數中的優度。
2-opt也叫2-exchange方法。或者說k-exchange，其中k≥2。
TSP問題，即traveling salesman problem——旅行商問題。旅行商問題可以從網際網路查到。