Tabu Search — 温和介绍
最近，我参加了 Corsera 上的离散优化课程。我试图解决的问题之一是旅行商问题，即著名的 NP-Hard 优化问题。该课程讲解了如何使用几种算法解决几个实际问题，其中一种算法是禁忌搜索。
今天，在这篇文章中，我将解释该算法并使用 Python 实现它来解决旅行商问题 TSP。
二、什么是禁忌搜索以及我可以在哪里使用它？
禁忌搜索是一种用于解决优化问题的元启发式程序，旨在指导其他方法摆脱局部最小值的陷阱。禁忌搜索用于为各种经典和实际问题寻找最佳和接近最佳的解决方案。从调度到电信，从字符识别到神经网络。为了避免陷入局部最小值，它使用内存，以便能够记住已经利用的动作和解决方案。此外，它还使用记忆功能来允许搜索策略，例如强化和多样化（稍后将对其进行解释）。
禁忌搜索可用于指导其他过程，该过程使用一组动作将一个解决方案转换为另一个解决方案，并为衡量这些动作的吸引力提供指导。动作的示例是在两个任务之间交换，改变变量的值（增加、减少）。
Tabu Search 应用的部分列表：
- 员工排班
- 最大可满足性问题
- 字符识别
- 空间规划与建筑设计
- 电信路径分配
- 概率逻辑问题
- 神经网络模式识别
- 机器调度
- 旅行商问题
- 图形着色
三、禁忌搜索原则
Tabu Search基于三个主要概念：
- 使用基于灵活属性的记忆结构，可以比严格的记忆结构或无记忆系统更彻底地利用评估标准和历史搜索信息。
- 禁忌搜索中根据特定标准评估移动的机制
- 使用从短期到长期的不同时间跨度的记忆功能来实施强化策略——专注于特定区域，再到多样化——推动在新区域的搜索。
四、短期记忆和积极搜索：
禁忌搜索中的短期记忆可以表示为一种积极的利用，旨在使基本移动成为可能。通过列出可以从当前解决方案中得出新解决方案的候选移动列表。
禁忌搜索提供了防止重复某些动作的限制。通过将这些动作视为禁忌（禁忌）……（啊，这就是它被称为禁忌搜索的原因！）。禁忌搜索旨在防止循环回到局部最小值，并广泛地引入搜索以遵循新的轨迹。
但是.. Tabu 如何确定最佳候选人？很简单！使用目标函数！..事情还是不清楚？！别担心，在看到下面的框图之前，我也不明白：
禁忌搜索短期记忆组件——取自[1]
选择最佳候选人——取自[1]
五、举例时间
ِ禁忌搜索的一个简单例子是最小成本生成树问题，其中包括防止某些边出现的约束。该问题可以用五个节点表示，因此生成树由四个边组成，每个边都有一个成本，如下图所示：
生成树问题
在这个问题中，我们需要最小化节点相互连接的成本。这里每条边都用 xi 表示，其中 i=[0..7]，xi 可以取 0 或 1（0 表示边不存在）。每条边都有成本。例如，这里初始解决方案的成本是 6+2+8+0 = 16（相当不错吧）。
但是等等..不要忘记问题的另一部分，有些边是禁止出现..所以让我们在这里加上一些限制：
当我们违反这些限制时，我们会对每个违反单位处以 50 的惩罚。因此，在上图中，我们有 2 次违反，因此惩罚为 100。该生成树的总成本为116 :)
我们需要找到一种成本低且不违反上述约束的解决方案。要应用禁忌搜索，我们需要应用交换变换，即删除一条边并添加另一条边以转换为另一个解决方案。
当我们选择添加一条边时，我们必须以不产生循环的方式删除另一条边。可接受的移动是考虑到违规惩罚成本而具有最低成本的移动。
此处的禁忌限制定义为我们定义为禁忌状态的添加边。这使得被选为禁忌的边只要是禁忌就不会从树中删除。在示例中，我们只允许两条边是禁忌。这意味着任何添加的边在两次迭代中仍然是禁忌。
此处的期望标准是，如果生成的树比迄今为止生成的最佳树更好，则覆盖禁忌状态。我们现在将运行该算法并讨论每次迭代。迭代如下图 1 所示：
迭代 1：从迭代 1 开始，我们可以采取的最佳措施是添加 x3 并删除 x1，这样既不违反约束，又能达到最佳效果。这会将惩罚从 100 减少到 0。同时将成本从 16 增加到 28。X3 现在被视为禁忌。
迭代 2：现在根据禁忌状态规则，我们将 x3 设为禁忌。因此我们不能删除 x3。从剩余的选项中，最佳选择是添加 x7 并删除 x6。然后将 x7 设为禁忌。所选的举动产生的成本比前一个更糟糕。
现在我们有 x3，x7 被视为禁忌。如果我们想采取任何行动，我们都会使成本变得更糟。所以我们处于一种成本很高的状态，我们无法采取任何其他行动，这被称为局部最小值。
迭代 3：现在，由于我们达到了局部最小值，我们可以通过添加 x2 并删除 x3 来覆盖禁忌状态。此举通过生成具有更佳成本的树来满足期望标准，因此我们采取此举。
迭代 4：X2、X7 现在是禁忌。算法将继续添加 x3 并删除 X5。X3 和 X2 现在是禁忌
执行：
我在 Python 中分叉了一个禁忌搜索的实现，并对其进行了改进，以解决旅行商问题，请随意使用和修改代码：
"""
This implementation for tabu search is modified from:
https://www.techconductor.com/algorithms/python/Search/Tabu_Search.php
Reference:
https://www.researchgate.net/publication/242527226_Tabu_Search_A_Tutorial
"""
import copy
import math
def distance(point1, point2):
return math.sqrt((point1.x - point2.x)**2 + (point1.y - point2.y)**2)
def generate_neighbours(points):
"""This function geenrates a 2D distance matrix between all points
Parameters
----------
points : type
Description of parameter `points`.
Returns
-------
type
Description of returned object.
"""
dict_of_neighbours = {}
for i in range(len(points)):
for j in range(i+1, len(points)):
if i not in dict_of_neighbours:
dict_of_neighbours[i] = {}
dict_of_neighbours[i][j]= distance(points[i], points[j])
else:
dict_of_neighbours[i][j] = distance(points[i], points[j])
# dict_of_neighbours[i] = sorted(dict_of_neighbours[i].items(), key=lambda kv: kv[1])
if j not in dict_of_neighbours:
dict_of_neighbours[j] = {}
dict_of_neighbours[j][i] = distance(points[j], points[i])
else:
dict_of_neighbours[j][i] = distance(points[j], points[i])
# dict_of_neighbours[i] = sorted(dict_of_neighbours[i].items(), key=lambda kv: kv[1])
return dict_of_neighbours
def generate_first_solution(nodes, dict_of_neighbours):
start_node = nodes[0]
end_node = start_node
first_solution = []
distance = 0
visiting = start_node
pre_node = None
while visiting not in first_solution:
_tmp = copy.deepcopy(dict_of_neighbours[visiting])
_tmp.pop(pre_node, None)
next_node = min(_tmp.items(), key=lambda x: x[1])[0]
distance += dict_of_neighbours[visiting][next_node]
first_solution.append(visiting)
pre_node = visiting
visiting = next_node
first_solution.append(nodes[0])
distance += dict_of_neighbours[pre_node][end_node]
return first_solution, distance
def find_neighborhood(solution, dict_of_neighbours, n_opt=1):
neighborhood_of_solution = []
for n in solution[1:-n_opt]:
idx1 = []
n_index = solution.index(n)
for i in range(n_opt):
idx1.append(n_index+i)
for kn in solution[1:-n_opt]:
idx2 = []
kn_index = solution.index(kn)
for i in range(n_opt):
idx2.append(kn_index+i)
if bool(
set(solution[idx1[0]:(idx1[-1]+1)]) &
set(solution[idx2[0]:(idx2[-1]+1)])):
continue
_tmp = copy.deepcopy(solution)
for i in range(n_opt):
_tmp[idx1[i]] = solution[idx2[i]]
_tmp[idx2[i]] = solution[idx1[i]]
distance = 0
for k in _tmp[:-1]:
next_node = _tmp[_tmp.index(k) + 1]
distance = distance + dict_of_neighbours[k][next_node]
_tmp.append(distance)
if _tmp not in neighborhood_of_solution:
neighborhood_of_solution.append(_tmp)
indexOfLastItemInTheList = len(neighborhood_of_solution[0]) - 1
neighborhood_of_solution.sort(key=lambda x: x[indexOfLastItemInTheList])
return neighborhood_of_solution
def tabu_search(first_solution, distance_of_first_solution, dict_of_neighbours, iters, size, n_opt=1):
count = 1
solution = first_solution
tabu_list = list()
best_cost = distance_of_first_solution
best_solution_ever = solution
while count <= iters:
neighborhood = find_neighborhood(solution, dict_of_neighbours, n_opt=n_opt)
index_of_best_solution = 0
best_solution = neighborhood[index_of_best_solution]
best_cost_index = len(best_solution) - 1
found = False
while found is False:
i = 0
first_exchange_node, second_exchange_node = [], []
n_opt_counter = 0
while i < len(best_solution):
if best_solution[i] != solution[i]:
first_exchange_node.append(best_solution[i])
second_exchange_node.append(solution[i])
n_opt_counter += 1
if n_opt_counter == n_opt:
break
i = i + 1
exchange = first_exchange_node + second_exchange_node
if first_exchange_node + second_exchange_node not in tabu_list and second_exchange_node + first_exchange_node not in tabu_list:
tabu_list.append(exchange)
found = True
solution = best_solution[:-1]
cost = neighborhood[index_of_best_solution][best_cost_index]
if cost < best_cost:
best_cost = cost
best_solution_ever = solution
elif index_of_best_solution < len(neighborhood):
best_solution = neighborhood[index_of_best_solution]
index_of_best_solution = index_of_best_solution + 1
while len(tabu_list) > size:
tabu_list.pop(0)
count = count + 1
best_solution_ever.pop(-1)
return best_solution_ever, best_cost六、结论：
禁忌搜索是一种元启发式搜索算法，利用短期记忆的思想来避免陷入局部最小值。它已用于许多应用，其中之一就是旅行商问题。谈到 TSP，值得一提的是，解决它的最佳算法是引导局部搜索算法。
七、参考：
我使用以下参考资料作为本文所写的主要信息来源（这确实是禁忌搜索的最佳资源：