禁忌搜索（Tabu Search）是一种元启发式算法，旨在通过增强局部搜索机制来解决复杂的组合优化问题。为了避免算法陷入局部最优解或循环，它引入了禁忌表等策略。
1. 问题定义
我们考虑一个优化问题，在解空间 上寻找最优解 ，使得目标函数 最小化（或最大化) 。目标可以表示为:
2. 邻域定义
定义解 的邻域为一个集合 ，它包含通过局部操作从 生成的解:
邻域结构 可以依赖于问题类型。
这里借助于TSP问题举两个例子。
（1）交换操作：在旅行商问题中，解可以表示为一个城市的排列。通过交换两个城市的顺序，可以生成邻域解。
若解 ，交换城市 和 ，得到邻域解 。
（2）插入操作：在TSP中，可以选择某个城市，将其从当前位置插入到另一个位置。例如，将城市 移动到 之前或之后。
若解 ，可以将城市 移动到位置 1 ，得到邻域解 。
3. 禁忌表定义
禁忌搜索通过维护一个动态的禁忌表 ，来记录最近 次访问过的解或操作，避免算法陷入局部最优解或循环。形式化表示为:
其中， 为当前迭代的时间步， 是禁忌表的长度。禁忌表通过跟踪操作或属性（如解中变量的交换)，而非具体解本身。禁忌表可以看作一个队列结构，随着新解进入，最早进入的解被移出。
4. 解的选择
在第 次迭代时，从当前解 的邻域 中选择下一个候选解 ，但要求该解不属于禁忌表 或满足准许准则。数学表示为:
若在禁忌表中的解 满足准许准则 (Aspirational Criteria)，即其目标函数值优于当前的最优解 ，则即使 ，也可以选择该解:
if
此处，准许准则提供了一种"跳过禁忌"的机制，允许探索更优的解。
5. 目标函数更新
每次迭代时，禁忌搜索维护一个当前最优解 ，表示迭代过程中的全局最优解。目标函数值随着迭代不断更新:
当找到新的解 ，如果其目标函数值优于当前最优解 ，则更新最优解:
if
6. 禁忌表更新
在每次迭代中，禁忌表 需要更新。更新方式为将当前操作或解的某些特征（例如局部交换操作）加入禁忌表，同时移除最早进入的元素，使得禁忌表保持固定长度
禁忌表可以看作一个队列结构，每次迭代时移除最早进入的元素并加入新的元素。
7. 复杂度分析
禁忌搜索的复杂度取决于以下几个因素:
（1）邻域大小: 每次迭代时，需要计算邻域 的所有解的目标函数值，复杂度为 ，其中 为邻域的大小；
（2）禁忌表查询: 每次迭代时，需要检查候选解是否在禁忌表中，复杂度为 ，其中 是禁忌表的大小；
（3）迭代次数: 通常设置一个最大迭代次数 ，因此总的时间复杂度为 。
禁忌搜索的时间复杂度与邻域大小、禁忌表长度以及最大迭代次数呈线性关系。
8.代码实现（python）
import randomimport numpy as npimport matplotlib.pyplot as plt# 计算路径的总距离def calculate_total_distance(route, distance_matrix):total_distance = 0for i in range(len(route) - 1):total_distance += distance_matrix[route[i], route[i + 1]]total_distance += distance_matrix[route[-1], route[0]] # 回到起点的距离return total_distance# 2-opt 邻域操作：反转路径中的一段def two_opt(route, i, k):new_route = route[:i] + route[i:k + 1][::-1] + route[k + 1:]return new_route# 绘制路径def plot_route(coords, route, title="Route", iteration=None):plt.figure(figsize=(8, 6))x_coords = [coords[city][0] for city in route] + [coords[route[0]][0]]y_coords = [coords[city][1] for city in route] + [coords[route[0]][1]]plt.plot(x_coords, y_coords, 'bo-', markersize=10, label="Path")plt.scatter(x_coords, y_coords, color='red', s=100, zorder=5)for i, city in enumerate(route):plt.text(coords[city][0], coords[city][1], f"{city}", fontsize=12, ha='center', va='center')plt.title(f"{title} {'(Iteration: ' + str(iteration) + ')' if iteration is not None else ''}")plt.xlabel('X Coordinate')plt.ylabel('Y Coordinate')plt.grid(True)plt.show()# 禁忌搜索主算法def tabu_search(coords, distance_matrix, initial_route, tabu_tenure, max_iterations):n = len(initial_route) # 城市数量best_route = initial_route.copy() # 最优路径best_distance = calculate_total_distance(best_route, distance_matrix) # 最优路径的总距离current_route = best_route.copy()current_distance = best_distancetabu_list = np.zeros((n, n)) # 禁忌表，记录禁忌的城市对iteration = 0while iteration < max_iterations:iteration += 1best_candidate = Nonebest_candidate_distance = float('inf')# 生成邻域解并选择最优解for i in range(1, n - 1):for k in range(i + 1, n):candidate_route = two_opt(current_route, i, k)candidate_distance = calculate_total_distance(candidate_route, distance_matrix)if (tabu_list[current_route[i], current_route[k]] == 0 orcandidate_distance < best_distance):if candidate_distance < best_candidate_distance:best_candidate = candidate_routebest_candidate_distance = candidate_distance# 更新当前解current_route = best_candidatecurrent_distance = best_candidate_distance# 更新禁忌表for i in range(1, n - 1):for k in range(i + 1, n):if tabu_list[current_route[i], current_route[k]] > 0:tabu_list[current_route[i], current_route[k]] -= 1# 将新的交换操作加入禁忌表tabu_list[current_route[i], current_route[k]] = tabu_tenure# 更新全局最优解if current_distance < best_distance:best_route = current_route.copy()best_distance = current_distance# 每隔 20 次迭代绘制一次当前路径if iteration % 20 == 0 or iteration == max_iterations:plot_route(coords, current_route, title="Current Route", iteration=iteration)print(f"Iteration {iteration}, Best Distance: {best_distance}")return best_route, best_distance# 示例：城市的坐标coords = {0: (0, 0),1: (1, 5),2: (5, 1),3: (10, 5),4: (7, 8)}# 根据坐标生成距离矩阵def create_distance_matrix(coords):n = len(coords)distance_matrix = np.zeros((n, n))for i in range(n):for j in range(n):distance_matrix[i][j] = np.sqrt((coords[i][0] - coords[j][0])**2 + (coords[i][1] - coords[j][1])**2)return distance_matrixdistance_matrix = create_distance_matrix(coords)# 初始路径initial_route = list(range(len(distance_matrix)))# 参数：禁忌表长度和最大迭代次数tabu_tenure = 5max_iterations = 100# 执行禁忌搜索best_route, best_distance = tabu_search(coords, distance_matrix, initial_route, tabu_tenure, max_iterations)# 绘制最优路径plot_route(coords, best_route, title="Best Route")print("Best Route:", best_route)print("Best Distance:", best_distance)
