林-克尼漢啟發式演算法

在組合最佳化中，Lin–Kernighan 演算法是解決對稱旅行銷售員問題的最佳啟發式演算法之一。它屬於局部搜尋演算法的範疇，這類演算法將一個旅程（漢米爾頓迴路）作為輸入的一部分，並試圖透過在給定旅程的鄰域中搜尋更短的旅程來進行改善。一旦找到更短的旅程，便從新的旅程開始重複此過程，直到遇到局部最小值。與相關的 2-opt 和 3-opt 演算法一樣，兩個旅程之間的相關「距離」度量是在一個旅程中但不在另一個旅程中的邊的數量；新的旅程是透過將舊旅程的片段以不同順序重新組合而建立的，有時會改變子旅程的遍歷方向。Lin–Kernighan 演算法是自適應的，在每個步驟中沒有固定的邊替換數量，但偏好替換少量邊，例如 2 或 3 條。

推導

對於一個給定的旅行銷售員問題實例 (G,c) ，旅程由其邊集合唯一確定，因此我們不妨將其如此編碼。在局部搜尋的主迴圈中，我們有一個當前旅程 T \subset \mathrm{E}(G) ，並尋找一個新的旅程 T' \subset \mathrm{E}(G) ，使得對稱差 F = T \mathbin{\triangle} T' 不會太大，且新旅程的長度 \sum_{e \in T'} c(e) 小於當前旅程的長度 \sum_{e \in T} c(e) 。由於 F 通常遠小於 T 和 T' ，考慮以下量會很方便： g(F) = \sum_{e \in F \cap T} c(e) - \sum_{e \in F \setminus T} c(e) \quad —— 從 T 切換時使用 F \subseteq \mathrm{E}(G) 的增益 —— 因為 g(T \mathbin{\triangle} T') = \sum_{e \in T} c(e) - \sum_{e \in T'} c(e) ：即當前旅程 T 比新旅程 T' 長多少。簡略地說， k -opt 可以視為檢查所有恰好有 2k 個元素的 F \subseteq \mathrm{E}(G) （其中 k 條邊在 T 中但不在 T' 中，另外 k 條邊在 T' 中但不在 T 中），使得 T \mathbin{\triangle} F 仍然是一個旅程，並尋找一個具有 g(F) > 0 的此類集合。然而，以相反的順序進行這些測試會更容易：首先搜尋具有正增益且看似可行的 F ，然後才檢查 T \mathbin{\triangle} F 是否確實是一個旅程。

定義圖 G 中的一個跡 (trail)，如果其邊交替地屬於 T 和不屬於 T ，則稱之為（相對於 T的）交替跡。因為子圖 \bigl( \mathrm{V}(G),T \bigr) 和 \bigl( \mathrm{V}(G),T' \bigr) 都是 2 -正則圖，子圖 G[T \mathbin{\triangle} T'] = \bigl( \mathrm{V}(G),T \mathbin{\triangle} T'\bigr) 的頂點度數將只會有 0 、 2 和 4 ，且在每個頂點上，來自 T 的關聯邊數量與來自 T' 的數量相同。因此（基本上根據用於尋找歐拉迴路的 Hierholzer 演算法），圖 G[T \mathbin{\triangle} T'] 會分解成封閉的交替跡。因此，可以透過枚舉 G 中的封閉交替跡來找到可能滿足 F = T \mathbin{\triangle} T' （對於某個旅程 T' ）的集合 F \subseteq \mathrm{E}(G) ，即使並非每個封閉交替跡 F 都能使 T \mathbin{\triangle} F 成為一個旅程；它也可能變成一個不連通的 2 -正則子圖。

核心思想

交替跡（封閉或開放的）是透過擴展較短的交替跡來建立的，因此在探索當前旅程 T 的鄰域時，實際上是在探索一個由交替跡組成的搜尋樹。Lin–Kernighan 演算法的核心思想是從這棵樹中移除所有增益 \leq 0 的交替跡。由於以下引理，這樣做並不會妨礙找到每一個具有正增益的封閉跡。

引理。如果 a_0,\dotsc,a_{n-1} 是一串數字，使得 \sum_{i=0}^{n-1} a_i > 0 ，那麼存在這些數字的一個循環排列，使得所有部分和也為正，即，存在某個 k 使得：對於所有 r=0,1,\dotsc,n-1 ， \sum_{i=0}^r a_{(k+i) \bmod n} > 0 。

對於一個封閉交替跡 F = e_0 \, e_1 \, \dots \, e_{n-1} ，可以定義如果 e_i \in T 則 a_i = c(e_i) ，如果 e_i \notin T 則 a_i = -c(e_i) ；那麼總和 \sum\nolimits_{i=0}^{n-1} a_i 就是增益 g(F) 。此處，該引理意味著對於每個具有正增益的封閉交替跡，都存在至少一個起始頂點 v_0 ，使得所有部分跡的增益也為正，因此當搜尋探索從 v_0 開始的交替跡分支時，將會找到 F 。（在此之前，搜尋可能已經考慮過從其他頂點開始的 F 的其他子跡，但因為某些子跡未能滿足正增益約束而退回。）減少需要探索的分支數量直接轉化為執行時間的減少，而越早能對分支進行剪枝越好。

這產生了以下演算法，用於尋找圖中所有封閉的、具正增益的交替跡。

：狀態：一個由三元組 (u,i,g) 組成的堆疊，其中 u \in \mathrm{V}(G) 是一個頂點， i \geq 0 是跡中當前的邊數， g 是當前的跡增益。

對於所有 u \in \mathrm{V}(G) ，將 (u,0,0) 推入堆疊。
當堆疊非空時：
1. 從堆疊彈出 (u,i,g) ，並令 v_i := u 。當前的交替跡現在是 F = \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} 。
2. 如果 i 是偶數則：
3. ：對於每個 u \in \mathrm{V}(G) 使得 v_i u \in T \setminus \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} （最多有兩個這樣的 u），將 \bigl( u, i+1, g+c(v_i u) \bigr) 推入堆疊。
4. 如果 i 是奇數則：
  1. 如果 g > c(v_i v_0) ，則報告 \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} 為一個封閉交替跡，其增益為 g - c(v_i v_0) > 0 。
  2. 對於每個 u \in \mathrm{V}(G) 使得 g > c(v_i u) 且 v_i u \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} （可能有 O(n) 個這樣的 u，也可能沒有），將 \bigl( u, i+1, g-c(v_i u) \bigr) 推入堆疊。
停止

作為一個枚舉演算法，這有些許瑕疵，因為它可能會以不同的起始點多次報告同一個跡，但 Lin–Kernighan 演算法不在乎，因為它通常在找到第一個符合條件的結果後就中止枚舉。然而，應當指出：

Lin–Kernighan 演算法不僅要求找到一個具正增益的封閉交替跡 F ，還額外要求 T \mathbin{\triangle} F 是一個旅程。
Lin–Kernighan 演算法還以多種方式限制搜尋，最明顯的是關於搜尋深度（但不只如此）。上述無限制的搜尋最終仍會終止，因為當 i = 2n 時， T 中已無未被選取的邊，但這遠遠超出了實際可探索的範圍。
在大多數迭代中，人們希望快速找到一個更好的旅程 T' ，因此可能希望惰性生成搜尋樹中的同級節點，而不是在探索第一個節點前就將所有同級節點列出。

基本 Lin–Kernighan 演算法

基本形式的 Lin–Kernighan 演算法不僅執行了與上述枚舉相對應的局部搜尋，還引入了兩個參數來縮小搜尋範圍。

回溯深度 p_1 是回溯後交替跡長度的上限；超過此深度，演算法最多只會探索一種擴展交替跡的方式。標準值為 p_1 = 5 。
不可行深度 p_2 是一個交替路徑長度，超過此長度後，演算法便開始要求關閉當前跡（無論這樣做的增益如何）必須能交換成一個新的旅程。標準值為 p_2 = 2 。

因為長度為 p_1 的交替跡有 O( n^{\lfloor p_1/2 \rfloor} ) 個，且演算法的最後一輪可能需要檢查所有這些跡才能斷定當前旅程是局部最佳的，所以我們得到 \lfloor p_1/2 \rfloor （標準值為 2 ）作為演算法複雜度指數的下界。Lin 和 Kernighan 報告其演算法的平均總執行時間中， n 的經驗指數為 2.2 ，但其他實作者在重現此結果時遇到了困難。最壞情況下的執行時間似乎不可能是多項式的。

以如上的堆疊來描述，演算法如下：：輸入：一個旅行銷售員問題的實例 (G,c) ，以及一個旅程 T \subset \mathrm{E}(G) ：輸出：一個局部最佳的旅程：變數：

一個由三元組 (u,i,g) 組成的堆疊，其中 u \in \mathrm{V}(G) 是一個頂點， i \geq 0 是跡中當前的邊數， g 是當前的跡增益，

當前交替跡中的頂點序列 v_0, v_1, \dotsc ，

為當前旅程找到的最佳交換邊集合 F ，及其對應的增益 g^* 。

：將堆疊初始化為空。：重複

設定 g^* := 0 且 F := \varnothing 。

對於所有 u \in \mathrm{V}(G) ，將 (u,0,0) 推入堆疊。

當堆疊非空時：

從堆疊彈出 (u,i,g) 並令 v_i := u 。

如果 i 是偶數則

對於每個 u \in \mathrm{V}(G) 使得 v_i u \in T \setminus \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} ，

如果滿足以下條件，則將 \bigl( u, i+1, g+c(v_i u) \bigr) 推入堆疊： i \leq p_2 ，或 u v_0 \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i u \} 且 T \mathbin{\triangle}

\{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i u, u v_0 \} 是一個旅程（漢米爾頓性檢查）

否則（ i 為奇數）：

如果 g > c(v_i v_0) 、 g - c(v_i v_0) > g^* ，且 T \mathbin{\triangle}

\{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} 是一個旅程（漢米爾頓性檢查），則令 F := \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} 且 g^* := g - c(v_i v_0) 。

對於每個 u \in \mathrm{V}(G) 使得 g > c(v_i u) 且 v_i u \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} ，將 \bigl( u, i+1, g-c(v_i u) \bigr) 推入堆疊。

結束判斷。

令 (u,j,g) 為堆疊頂部元素（窺視，非彈出）。如果 i \leq j 則

如果 g^* > 0 則

設定 T := T \mathbin{\triangle} F （更新當前旅程）並清空堆疊。

否則如果 i > p_1 則

從堆疊中彈出所有滿足 j > p_1 的元素 (u,j,g)

結束判斷

結束迴圈

：直到 g^*=0 。：返回 T

因此，所考慮的交替跡的長度沒有被明確限制，但在超過回溯深度 p_1 後，最多只會考慮一種擴展當前跡的方式，這原則上阻止了這些探索提高執行時間複雜度的指數。

限制

上述方法找到的封閉交替跡都是連通的，但兩個旅程的對稱差 T \mathbin{\triangle} T' 未必如此，因此一般來說，這種交替跡的方法無法探索一個跡 T 的完整鄰域。關於 Lin–Kernighan 啟發式演算法的文獻中，使用「循序交換」(sequential exchanges) 一詞來描述那些可由單一交替跡描述的交換。然而，最小的非循序交換會替換 4 條邊，並由兩個各有 4 條邊的迴路組成（2 條邊加入，2 條邊移除），因此與典型的 Lin–Kernighan 交換相比，它的長度較長，且與所有 4 邊交換的完整集合相比，這種交換的數量很少。

在 Lin 和 Kernighan 的至少一個實作中，在宣告一個旅程為局部最佳之前，會有一個額外的最終步驟，考慮這種 4 邊的非循序交換，這意味著除非對搜尋引入進一步的約束（Lin 和 Kernighan 實際上也這麼做了），否則產生的旅程是 4-opt 的。文獻對於 Lin–Kernighan 啟發式演算法本身確切包含哪些內容，以及哪些算是進一步的改進，描述得相當模糊。

對於非對稱 TSP，使用正增益交替跡來尋找有利交換的想法較不實用，因為在不允許反轉片段方向的情況下，可以重新排列旅程片段以產生新旅程的方式較少。兩個片段只能拼接在一起以重現原始旅程。三個片段只能以一種方式拼接成不同的旅程，而其對應的交替跡無法擴展成一個封閉跡來將四個片段重新排列成一個新旅程。要重新排列四個片段，就需要一次非循序交換。

檢查漢米爾頓性

Lin–Kernighan 啟發式演算法在兩個地方檢查候選旅程 T \mathbin{\triangle} F 的有效性：一是在決定是否已找到更好旅程時，二是在搜尋樹中向下探索時，作為一個由不可行深度 p_2 控制的約束。具體來說，在較深的搜尋深度，只有當 T \mathbin{\triangle} \{ v_0 v_1, v_1 v_2, \dotsc, v_{2k} v_{2k+1}, v_{2k+1} v_0 \} 是一個旅程時，頂點 v_{2k+1} 才會被附加到交替跡上。根據設計，該邊集合構成 G 中的一個 2-因子，因此需要確定的是該 2-因子是由單一的漢米爾頓迴路組成，還是由多個迴路組成。

如果將這個子問題簡單地設定為將 n 條邊的集合作為輸入提供給一個子程序，那麼這個檢查的時間複雜度將會是 O(n) ，因為必須走遍整個旅程才能確定它確實是一個漢米爾頓迴路。對於此測試的第二種用途來說，這個速度太慢了，因為對於每個從 T 中取出超過 2 條邊的交替跡，都需要執行此測試。如果追蹤更多資訊，這個測試則可以在常數時間內完成。

這裡一個有用的自由度是，可以選擇步驟 2.3.2 遍歷所有頂點的順序；特別是，可以沿著已知的旅程 T 進行。從 T 中選取 k 條邊後，剩餘的子圖 \bigl( \mathrm{V}(G), T \setminus \{ v_0 v_1, \dotsc, v_{2k-2} v_{2k-1} \} \bigr) 由 k 條路徑組成。在考慮第 (k+1) 條邊 v_{2k} v_{2k+1} 時進行的漢米爾頓性測試的結果，僅取決於 v_{2k} 位於這些路徑中的哪一條，以及 v_{2k+1} 是在 v_{2k} 之前還是之後。因此，在為 v_{2k-1} 執行步驟 2.3.2 時，檢查 2k 個不同情況就足夠了；就 v_{2k+1} 而言，此測試的結果可以是繼承來的資訊，而不需要重新計算。

參考資料

外部連結

LKH implementation
Concorde TSP implementation
LK Heuristic in Python

Category:組合最佳化 Category:組合演算法 Category:啟發式演算法 Category:旅行銷售員問題