问题概述
给定29座城市， 求解旅行商从第一座城市开始， 访问每一座城市一次后， 回到起始城市的最短路径。
29座城市坐标依次如下：(360, 1980), (1150, 1760), (630, 1660), (40, 2090), (750, 1100), (750, 2030), (1030, 2070), (1650, 650), (1490, 1630), (790, 2260), (710, 1310), (840, 550), (1170, 2300), (970, 1340), (510, 700), (750, 900), (1280, 1200) , (230, 590), (460, 860), (1040, 950), (590, 1390), (830, 1770), (490, 500), (1840, 1240), (1260, 1500), (1280, 790), (490, 2130), (1460, 1420), (1260, 1910)
方法概述
我们不可能将所有情况全部列举出来， 寻求最小答案， 这样计算量实在太大。本文将分别采用局部搜索算法和禁忌搜索算法尝试解决TSP问题，并分析两种方法的利弊。
局部搜索算法
给定初始路径， 进行路径变换， 生成若干路径， 并从中选择比当前路径更短的路径， 重复迭代若干次， 直至找到的最短路径不变。
Python代码实现如下:
city = [(0, (360, 1980)), (1, (1150, 1760)), (2, (630, 1660)), (3, (40, 2090)), (4, (750, 1100)),
(5, (750, 2030)),(6, (1030, 2070)), (7, (1650, 650)), (8, (1490, 1630)), (9, (790, 2260)),
(10, (710, 1310)),(11, (840, 550)), (12, (1170, 2300)), (13, (970, 1340)), (14, (510, 700)),
(15, (750, 900)),(16, (1280, 1200)), (17, (230, 590)), (18, (460, 860)), (19, (1040, 950)),
(20, (590, 1390)),(21, (830, 1770)), (22, (490, 500)), (23, (1840, 1240)), (24, (1260, 1500)),
(25, (1280, 790)),(26, (490, 2130)), (27, (1460, 1420)), (28, (1260, 1910))]
# 初始路径
road = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
def cost_road(road):
"""
通过两点间距离公式计算总路径距离，从城市0出发回到城市0
:param road: 当前路径
:return distance: 路径距离
"""
distance = ((city[0][1][0]-city[road[0]][1][0])**2+(city[0][1][1]-city[road[0]][1][1])**2)**0.5
for i in range(27):
distance += ((city[road[i]][1][0]-city[road[i+1]][1][0])**2 +
(city[road[i]][1][1]-city[road[i+1]][1][1])**2)**0.5
distance += ((city[road[27]][1][0]-city[0][1][0])**2+(city[road[27]][1][1]-city[0][1][1])**2)**0.5
return distance
def neighbours(road):
"""
通过交换当前路径中的两座城市生成领域路径，并从中挑选比当前路径更短的路径
由于初始城市固定，所以共生成378种不同的路径
:param road: 当前路径
:return best_cost:最短距离, best_road:最短路径
"""
length = len(road)
roads = []
best_cost = cost_road(road)
best_road = road
# 生成领域路径存放于roads
for i in range(length):
for j in range(i+1, length):
temp = road[:]
temp[i], temp[j] = temp[j], temp[i]
roads.append(temp)
# 搜寻最短距离，最短路径
for each_road in roads:
each_cost = cost_road(each_road)
if each_cost < best_cost:
best_cost = each_cost
best_road = each_road
return best_cost, best_road
# 循环搜索最短路径，直到最短路径，最短距离不发生变化
costs = []
while 1:
cost, road = neighbours(road)
costs.append(cost)
if len(costs) > 3 and costs[-1] == costs[-2] == costs[-3]:
break
通过以上代码很容易找到局部最优解[3, 2, 5, 26, 9, 12, 6, 28, 1, 8, 23, 7, 25, 11, 14, 22, 17, 18, 15, 4, 20, 10, 13, 19, 16, 27, 24, 21]， 路径距离为10273.335954787268。显然这不是全局最优解， 例如选取[3, 26, 5, 9, 12, 6, 28, 1, 24, 16, 27, 8, 23, 7, 25, 19, 11, 22, 17, 14, 18, 15, 4, 13, 10, 20, 2, 21]，计算路径距离为9111.60741390125。
禁忌搜索算法
相对比于局部搜索算法， 禁忌搜索算法通过接受第二短路径甚至第三、第四短路径而不是一直采纳最短路径，从而避免一直停留在局部最短路径。
本例中采用随机交换当前路径中两个城市40次，从而生成40种不同的领域路径，采取的禁忌表长度为3， 终止准则为迭代次数， 迭代次数为4000次。
Python代码实现如下：
import random
city = [(0, (360, 1980)), (1, (1150, 1760)), (2, (630, 1660)), (3, (40, 2090)), (4, (750, 1100)),
(5, (750, 2030)), (6, (1030, 2070)), (7, (1650, 650)), (8, (1490, 1630)), (9, (790, 2260)),
(10, (710, 1310)), (11, (840, 550)), (12, (1170, 2300)), (13, (970, 1340)), (14, (510, 700)),
(15, (750, 900)), (16, (1280, 1200)), (17, (230, 590)), (18, (460, 860)), (19, (1040, 950)),
(20, (590, 1390)), (21, (830, 1770)), (22, (490, 500)), (23, (1840, 1240)), (24, (1260, 1500)),
(25, (1280, 790)), (26, (490, 2130)), (27, (1460, 1420)), (28, (1260, 1910))]
# 当前路径road
road = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
def cost_road(road):
"""
通过两点间距离公式计算总路径距离，从城市0出发回到城市0
:param road: 当前路径
:return distance: 路径距离
"""
distance = ((city[0][1][0]-city[road[0]][1][0])**2+(city[0][1][1]-city[road[0]][1][1])**2)**0.5
for i in range(27):
distance += ((city[road[i]][1][0]-city[road[i+1]][1][0])**2+
(city[road[i]][1][1]-city[road[i+1]][1][1])**2)**0.5
distance += ((city[road[27]][1][0]-city[0][1][0])**2+(city[road[27]][1][1]-city[0][1][1])**2)**0.5
return distance
def neighbours(road, tabu_list):
"""
通过随机交换当前路径中两座城市的方式生成领域路径，
本例共生成40种不同的路径，并依据路径距离从小到大排序，
若领域中最短路径距离小于历史最优距离或，则更新当前路径和历史最优，
若领域中最短路径大于历史最优但不位于禁忌表中，则更新当前路径，
若最短路径位于禁忌表中，则考虑第二短路径......
:param road: 当前路径
:param tabu_list: 禁忌表
:return road: 更新后的当前路径, best_road: 历史最优路径
"""
roads = []
path = road[:]
move_list = []
# best_cost: 历史最短距离, best_road: 历史最短路径
global best_cost
global best_road
# 生成40种领域路径存放于roads中，并按距离排序
for ix in range(40):
move = random.sample(path, 2)
move.sort()
temp = road[:]
if move in move_list:
continue
move_list.append(move)
first = temp.index(move[0])
second = temp.index(move[1])
temp[first], temp[second] = temp[second], temp[first]
cost = cost_road(temp)
roads.append((move, cost, temp))
roads.sort(key=lambda x: x[1])
# 从领域中最短路径开始进行判断，是否更新历史最优和当前路径
if roads[0][0] not in tabu_list or roads[0][1] < best_cost:
if roads[0][1] < best_cost:
best_cost = roads[0][1]
best_road = roads[0][2]
road = roads[0][2]
tabu_list.append(roads[0][0])
elif roads[1][0] not in tabu_list:
road = roads[1][2]
tabu_list.append(roads[1][0])
elif roads[2][0] not in tabu_list:
road = roads[2][2]
tabu_list.append(roads[2][0])
else:
road = roads[3][2] # 极少情况下，领域中前三种路径均位于禁忌表中，选取第四种路径
# 维持禁忌表长度为3
if len(tabu_list) > 3:
tabu_list.pop(0)
return road, best_road
# tabu_list: 禁忌表, best_road: 历史最短路径, best_cost: 历史最短距离
tabu_list = []
best_road = road
best_cost = cost_road(road)
# 循环迭代4000次，既搜寻终止条件为迭代次数耗尽
for ix in range(4000):
road, best_road = neighbours(road, tabu_list)
由于生成领域路径的随机性， 每次运行算法都将得到不同的最短路径，我所运行后最短路径为[26, 9, 12, 6, 28, 1, 24, 16, 27, 8, 23, 7, 25, 19, 11, 17, 22, 14, 18, 15, 4, 13, 10, 20, 2, 21, 5, 3]，最短距离为9300.9636202749。随着领域范围的改变，禁忌表长度的改变，迭代次数的改变，也将得到不同的最短路径。所以很难确定是否找到的路径一定是全局最短路径。
问题分析
通过以上两种方法的比较， 不难看出局部搜索算法的局限性很大，很容易陷入局部最优解；而禁忌搜索算法通过接受非最优解，从而达到更加宽广的搜索范围，避免停留在局部最优解。
但此种禁忌搜索算法更像是在碰运气找最优解，有时难免重复做出丢西瓜捡芝麻的决策，从而大幅度降低寻找最优解的效率，以至于迭代了成百上千次依然没有找到全局最优解。
