局部搜索的基本步骤如下:
- 构造初始解 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
完整代码
示例