禁忌搜索算法（TS算法）求解实例---旅行商问题 (TSP)

一、采用TS求解 TSP

求解代码在文中，后续会出其他算法求解TSP问题，你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的
遗传算法（GA算法）求解实例—旅行商问题 (TSP)
粒子群算法（PSO算法）求解实例—旅行商问题 (TSP)
模拟退火算法（SA算法）求解实例—旅行商问题 (TSP)
蚁群算法（ACO算法）求解实例—旅行商问题 (TSP)
注意每次运行算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣，我把原理性的东西放在后面，大家如果需要写数模论文可以拿去，但是记得需要改一改，要不然查重过不去。

二、 旅行商问题

2.1 实际例子：求解 6 个城市的 TSP

假设有 6 个城市，其坐标如下：

城市	X 坐标	Y 坐标
0	10	20
1	30	40
2	20	10
3	40	30
4	10	10
5	50	20

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):return np.sqrt(np.sum((city1 - city2) ** 2))# 计算总旅行距离
def total_distance(path):distance = 0for i in range(len(path) - 1):distance += calculate_distance(cities[path[i]], cities[path[i + 1]])distance += calculate_distance(cities[path[-1]], cities[path[0]])  # 回到起点return distance# 生成初始解
def generate_initial_solution(num_cities):return list(np.random.permutation(num_cities))# 生成邻域解（通过交换路径中的两个城市）
def get_neighborhood(solution):neighbors = []for i in range(len(solution)):for j in range(i + 1, len(solution)):neighbor = solution.copy()neighbor[i], neighbor[j] = neighbor[j], neighbor[i]neighbors.append(neighbor)return neighbors# 禁忌搜索算法主函数
def tabu_search(cities, tabu_size=10, max_iter=500):num_cities = len(cities)# 初始化禁忌表tabu_list = []# 生成初始解current_solution = generate_initial_solution(num_cities)current_distance = total_distance(current_solution)# 初始化最佳解best_solution = current_solution.copy()best_distance = current_distancefor iteration in range(max_iter):# 生成所有邻域解neighbors = get_neighborhood(current_solution)neighbors_distances = [(neighbor, total_distance(neighbor)) for neighbor in neighbors]# 在禁忌表之外选择最优邻域解next_solution = Nonenext_distance = float('inf')for neighbor, distance in neighbors_distances:if neighbor not in tabu_list and distance < next_distance:next_solution = neighbornext_distance = distance# 更新当前解current_solution = next_solutioncurrent_distance = next_distance# 更新禁忌表tabu_list.append(current_solution)if len(tabu_list) > tabu_size:tabu_list.pop(0)# 更新全局最佳解if current_distance < best_distance:best_solution = current_solution.copy()best_distance = current_distanceprint(f"Iteration {iteration + 1}: Best distance = {best_distance:.2f}")return best_solution, best_distance# 运行禁忌搜索算法
best_path, best_distance = tabu_search(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

2.4 代码运行结果截屏（后续和其他算法进行对比）

三、 如何修改代码？

这一部分是重中之重，大家参加数学建模肯定是想跑出自己的结果，所以大家只需要把自己遇到的数学问题，抽象成TSP问题，然后修改代码的城市坐标，然后运行即可。

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])

3.1 减少城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30]
])

3.2 增加城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[30, 40],[20, 10],[10, 10],[50, 20]
])

四、 禁忌搜索算法 (Tabu Search, TS) 原理

4.1 TS算法定义

禁忌搜索算法 (Tabu Search, TS) 是一种基于局部搜索的启发式优化算法，由 Fred Glover 在 1986 年提出。禁忌搜索算法通过维护一个“禁忌表”来记录最近访问过的解或搜索路径，从而避免算法在搜索过程中陷入循环或局部最优解。通过合理的禁忌策略和多样化策略，TS 算法能够跳出局部最优解，找到全局最优解或近似最优解。

4.2 TS算法算法的基本思想

禁忌搜索算法的核心思想是对局部搜索进行改进。传统的局部搜索算法可能会因为陷入局部最优解或搜索循环而难以找到全局最优解。禁忌搜索算法通过在每次迭代中选择当前邻域中的最优解作为下一步搜索方向，并使用一个称为“禁忌表”的数据结构来记录已访问过的解或路径，从而避免回到先前访问过的解。禁忌表的内容会动态更新，以使得搜索能够进行更广泛的探索。

4.3 TS算法算法的工作原理

1. 初始化：

   • 随机生成一个初始解 s 作为当前解。
   • 设置一个空的禁忌表 T 和最大禁忌表长度 L，定义最大迭代次数 max_iter。

2. 生成邻域解：

   • 对当前解 s，生成其邻域解集合 N(s)。通常，邻域解是通过对当前解的微小修改（如交换、移位等）生成的多个新解。

3. 选择最优邻域解：

   • 在邻域解集合 N(s) 中，选择一个不在禁忌表中的最佳解 s'，使得其目标函数值最优（通常是最小化问题中的最小值）。
   • 若所有邻域解均在禁忌表中，则可以选择一个禁忌解作为当前解。

4. 更新禁忌表：

   • 将新的解 s' 添加到禁忌表 T 中，以避免在未来的搜索过程中重新访问该解。
   • 若禁忌表长度超过最大限制 L，则删除最早加入的解。

5. 更新当前解和全局最优解：

   • 将当前解 s 更新为新解 s'。
   • 如果 s' 的目标函数值优于全局最优解 s*，则更新全局最优解 s*。

6. 迭代和终止：

   • 重复步骤 2-5，直到达到最大迭代次数 max_iter 或找到满意解为止。

4.4 TS算法算法的关键要素

1. 禁忌表（Tabu List）：

   • 禁忌表是一个用来存储禁忌解的集合，用于防止搜索过程中的循环和回溯。禁忌表的长度 L 通常设定为一个固定值，当禁忌表超过最大长度时，将最早的解移出禁忌表。

2. 邻域结构：

   • 邻域结构决定了每次搜索所能达到的解空间范围。常见的邻域操作有交换、移位、反转等操作。

3. 禁忌策略：

   • 禁忌策略决定了哪些解被列入禁忌表。在一般情况下，禁忌解是根据一定规则选定的，以确保多样化搜索和有效避免循环。

4. 解的多样化策略：

   • 在搜索过程陷入局部最优时，解的多样化策略用于打破停滞状态，推动搜索进入新的区域。

4.5 TS算法算法的优缺点

4.5.1 优点

• 跳出局部最优：通过禁忌表机制，TS 算法能够有效避免局部最优解，继续在解空间中进行搜索。
• 灵活性强：TS 算法可以应用于多种优化问题，通过调整邻域结构和禁忌策略，可以针对不同问题进行适应性调整。
• 易于实现：相较于一些复杂的优化算法，TS 算法较为简单，易于实现。

4.5.2 缺点

• 计算开销较大：在大规模问题中，生成邻域解和维护禁忌表可能会带来较高的计算开销。
• 参数敏感：算法性能对禁忌表长度、邻域结构和禁忌策略较为敏感，需要根据具体问题进行调优。
• 不保证全局最优解：虽然 TS 算法能跳出局部最优，但不能保证一定找到全局最优解。

4.6 TS算法算法的应用场景

• 旅行商问题 (TSP)：寻找经过所有城市的最短路径。
• 车辆路径问题 (VRP)：优化多辆车在多个配送点的路径。
• 生产调度与资源分配：如工作车间调度、工厂生产排程、任务分配等。
• 网络设计与路由优化：优化计算机网络或物流网络中的节点连接和路由路径。
• 组合优化问题：如背包问题、图着色问题、设备布局问题等。