局部搜尋的基本步驟如下:
- 構造初始解 s s s;
- 定義 s s s的鄰域 δ ( s ) \delta(s) δ(s);
- 在鄰域 δ ( s ) \delta(s) δ(s)中搜尋新的解 s ′ s' s′;
- 令 s : = s ′ s:=s' s:=s′, 重複上述步驟直到滿足停止條件.
在實際中局部搜尋可以作為其它算法的補充, 目的是進一步提升解的品質. 下面我們以經典的旅行商問題(Traveling Salesman Problem)為例來介紹局部搜尋.
旅行商問題
已知 n n n個頂點 1 , 2 , … , n 1, 2, \ldots, n 1,2,…,n以及任意兩點的距離 d i , j ∈ R + d_{i,j}\in\mathbb{R}^+ di,j∈R+. 我們要找到一條經過所有頂點的回路(Tour)使得回路的總長度最短.
(圖檔來自wiki)
局部搜尋 - 2opt
- 令 s = { ( i 1 , i 2 ) , ( i 2 , i 3 ) , … , ( i n , i 1 ) } s=\{(i_1, i_2), (i_2, i_3), \ldots, (i_n, i_1)\} s={(i1,i2),(i2,i3),…,(in,i1)}, 其中 i j ∈ { 1 , 2 , … , n } i_j\in \{1, 2, \ldots, n\} ij∈{1,2,…,n}代表一個可行解, 即 n n n條鄰接的弧(Arc). 構造一個初始解.
- 定義 s s s的鄰域 δ ( s ) \delta(s) δ(s): 考慮 s s s的任意兩條弧 ( u , v ) (u, v) (u,v)和 ( s , t ) (s, t) (s,t), 交換它們之間的連接配接關系得到 ( u , s ) (u, s) (u,s)和 ( v , t ) (v, t) (v,t)(如下圖所示):
算法設計技巧: 局部搜尋(Local Search) - 搜尋 s ′ ∈ δ ( s ) s'\in \delta(s) s′∈δ(s), 如果 d ( s ′ ) < d ( s ) d(s') < d(s) d(s′)<d(s)(其中 d ( s ) d(s) d(s)代表回路 s s s的總長), 則把 s ′ s' s′作為新的解.
- 當結果不能提升或者達到最大循環次數時停止.
Python實作
-
TSP2opt._apply_2opt
-
TSP2opt.solve
class TSP2opt(object):
def __init__(self, d):
"""
:param d: distance matrix, d[i][j] - distance between node i and node j.
"""
self._d = d
self._iter = 0 # 記錄疊代次數
self._result = None
self._result_length = 0
self._tours = [] # 記錄中間的計算結果
def _init_tour(self):
n = len(self._d)
return [(i, i+1) for i in range(n-1)] + [(n-1, 0)]
@staticmethod
def _apply_2opt(tour, i, j):
""" Apply 2opt to arc i and j.
:param tour: list of arcs, e.g. tour of 4 vertices: [(0, 1), (1, 2), (2, 3), (3, 0)]
:param i: arc i of the tour
:param j: arc j of the tour.
:return: a new tour (feasible solution)
"""
u, v = tour[i]
s, t = tour[j]
part1 = tour[0:i]
part2 = [(u, s)]
part3 = [(tour[i+j-k][1], tour[i+j-k][0])for k in range(i+1, j)]
part4 = [(v, t)]
part5 = tour[j+1:]
return part1 + part2 + part3 + part4 + part5
def _is_2opt_make_improvement(self, tour, i, j):
"""
給定tour, 判斷2opt(i,j)是否可以縮短總路程.
"""
u, v = tour[i]
s, t = tour[j]
if self._d[u][v] + self._d[s][t] > self._d[u][s] + self._d[v][t]:
return True
return False
def _get_tour_length(self, tour):
return sum([self._d[i][j] for (i, j) in tour])
def solve(self, max_iter=10000):
n = len(self._d)
self._result = self._init_tour()
self._result_length = self._get_tour_length(self._result)
self._tours.append(self._result) # 記錄中間結果
improvement = 1
while improvement >= 1:
s0 = self._result_length
for i in range(n):
for j in range(i+1, n):
if self._iter == max_iter:
return self
if self._is_2opt_make_improvement(self._result, i, j):
self._result = self._apply_2opt(self._result, i, j)
self._tours.append(self._result) # 記錄中間結果
self._result_length = self._get_tour_length(self._result)
print("iter = %d, tour length = %d" %
(self._iter, self._get_tour_length(self._result)))
self._iter += 1
improvement = self._result_length - s0
return self
def print_result(self):
print("==== result ====")
print("tour:", [arc[0] for arc in self._result])
print("tour length:", self._result_length)
def get_tours(self):
return self._tours
完整代碼
示例