Python人工智能算法学习禁忌搜索算法求解旅行商问题（TSP）的研究与实现

本文针对旅行商问题（TSP），设计并实现了一种基于禁忌搜索（Tabu Search, TS）的智能优化算法。通过构建包含50个城市的TSP实例，采用禁忌表、邻域搜索和特赦准则等核心机制，有效求解大规模组合优化问题。实验结果表明，该算法在合理时间内能够找到高质量的近似最优解，并通过收敛曲线验证了算法的有效性。

梁下轻语的秋缘

2664人浏览 · 2025-05-28 17:32:58

梁下轻语的秋缘 · 2025-05-28 17:32:58 发布

禁忌搜索算法求解旅行商问题（TSP）的研究与实现

摘要

1. 引言

旅行商问题（TSP）是组合优化领域的经典NP-hard问题，其目标是在给定城市集合及距离矩阵的条件下，寻找一条总距离最短的闭合回路。随着城市规模扩大，精确算法难以在合理时间内求解，因此启发式算法成为研究热点。禁忌搜索算法通过模拟人类记忆机制，能够有效避免局部最优，适用于大规模TSP问题求解。

本文旨在：

设计并实现一种基于禁忌搜索的TSP求解算法
分析算法关键要素（禁忌表、邻域结构、参数设置）对性能的影响
在50个城市规模问题上验证算法有效性
通过可视化分析算法收敛过程

2. 问题描述与数学建模

2.1 TSP问题定义

给定 $n$ 个城市集合 $C=\{c_1,c_2,...,c_n\}$ 及距离矩阵 $D=[dij]n×nD=[d_{ij}]_{n \times n}$ ，其中 $d_{ij}$ 表示城市 $c_i$ 到 $c_j$ 的欧氏距离。要求构造一条哈密顿回路 $π=(π1,π2,...,πn)\pi=(\pi_1,\pi_2,...,\pi_n)$ ，使得总距离 $∑i=1ndπiπi+1\sum_{i=1}^{n}d_{\pi_i \pi_{i+1}}$ 最小，其中 $πn+1=π1\pi_{n+1}=\pi_1$ 。

2.2 实例生成

本文采用随机生成方式构建50个城市坐标，通过公式计算欧氏距离矩阵：
$dij=(xi−xj)2+(yi−yj)2d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$
其中 $x_i,y_i)$ 为城市 $i$ 的坐标，范围在 $[0, 100]$ 区间内均匀分布。

3. 禁忌搜索算法设计

3.1 算法流程

算法包含以下核心模块：

初始解生成
邻域结构构建
禁忌表管理
特赦准则判断
迭代终止条件

算法流程图如下：

在这里插入图片描述

3.2 关键函数实现与参数设置

3.2.1 初始解生成（`generate_initial_solution`）

def generate_initial_solution(n_cities):
    path = list(range(n_cities))
    np.random.shuffle(path)
    if path[0] != 0:
        idx = path.index(0)
        path[0], path[idx] = path[idx], path[0]
    return path

设计理由：强制以0号城市为起点，保证解的空间包含所有可能路径，避免因随机起点导致的解空间偏移。

3.2.2 邻域生成（`generate_neighborhood`）

def generate_neighborhood(path, num_neighbors=100):
    neighborhood = []
    n = len(path)
    for _ in range(num_neighbors):
        i = np.random.randint(1, n)
        j = np.random.randint(1, n)
        while i == j:
            j = np.random.randint(1, n)
        new_path = path.copy()
        new_path[i], new_path[j] = new_path[j], new_path[i]
        swap = tuple(sorted((path[i], path[j])))
        neighborhood.append((swap, new_path))
    return neighborhood

设计原理：

邻域操作：随机交换两个非起点城市（保持起点固定）
邻域大小：100个候选解（平衡探索广度与计算效率）
生成方式：蒙特卡洛随机采样

有效性分析：

交换操作时间复杂度低（ $O (1)$ ）
非起点城市交换保证解的有效性
随机采样覆盖解空间的关键区域

3.2.3 禁忌表管理

3.2.3.1 禁忌表存储

具体代码：

tabu_list = {}  # 禁忌表存储结构
tabu_list[swap] = tabu_tenure  # 禁忌期限设置为7

要素说明：

禁忌对象：以交换的城市对作为禁忌对象（如交换城市A和B，记录为元组(A,B)）
更新策略：每次迭代后，禁忌表中元素的剩余期限减1，期限为0时自动移除
禁忌期限：设为7

3.2.3.2禁忌表更新机制

更新准则：

递减机制：每代所有禁忌项期限减1
淘汰机制：期限≤0的禁忌项被移除
新增机制：当前采用的交换操作加入禁忌表

设计理由：

动态管理禁忌表大小，避免内存膨胀
确保禁忌对象有明确的生命周期
优先保留近期操作的禁忌状态

代码实现：

# 更新禁忌表
for key in list(tabu_list.keys()):
    tabu_list[key] -= 1  # 禁忌期限递减
    if tabu_list[key] <= 0:
        del tabu_list[key]  # 移除过期项

# 添加新禁忌项
tabu_list[swap] = tabu_tenure

3.2.4 特赦准则（Aspiration Criterion）

if swap in tabu_list:
    if new_distance < best_distance:
        # 允许打破禁忌

设计理由：当候选解的质量显著优于当前最优解时，即使其对应操作被禁忌，仍允许接受该解，避免错过全局最优。

4. 实验与分析

4.1 参数设置依据

参数	设置值
禁忌期限	7
邻域规模	100
最大迭代次数	1000

4.2 实验结果

最优路径：总距离747.55（如图1所示）
收敛曲线：如图2所示，算法在200次迭代内快速收敛，后续迭代保持稳定

在这里插入图片描述
图1 禁忌搜索TSP路径图

在这里插入图片描述

图2 禁忌搜索收敛曲线

5. 结论

本文实现的禁忌搜索算法通过以下创新点有效求解大规模TSP：

采用强制起点策略保证解空间完整性
设计动态禁忌表管理机制平衡探索与开发
引入特赦准则避免优质解丢失

实验表明，算法在50城市规模下能够快速收敛至高质量解，验证了算法的有效性。未来可研究自适应参数调整机制以进一步提升性能。

6.附录：完整代码

import numpy as np
import matplotlib.pyplot as plt

def generate_initial_solution(n_cities):
    """生成初始可行解（旅行商路径）
    
    Args:
        n_cities (int): 城市数量
        
    Returns:
        list: 初始路径列表，保证以0号城市为起点
    """
    # 生成0~n-1的完整排列
    path = list(range(n_cities))
    # 随机打乱路径顺序
    np.random.shuffle(path)
    # 确保路径以0号城市为起点（强制调整）
    if path[0] != 0:
        idx = path.index(0)
        path[0], path[idx] = path[idx], path[0]
    return path

def calculate_path_distance(path, distance_matrix):
    """计算路径总距离（含闭环）
    
    Args:
        path (list): 城市访问顺序列表
        distance_matrix (ndarray): 距离矩阵(n x n)
        
    Returns:
        float: 总路径距离
    """
    total_distance = 0
    n = len(path)
    for i in range(n):
        # 计算当前城市到下一个城市的距离（i+1取模实现闭环）
        total_distance += distance_matrix[path[i]][path[(i+1)%n]]
    return total_distance

def generate_neighborhood(path, num_neighbors=100):
    """生成邻域解集合（通过2-opt交换）
    
    Args:
        path (list): 当前路径
        num_neighbors (int): 生成邻域解数量
        
    Returns:
        list: 包含(swap_pair, new_path)元组的列表
    """
    neighborhood = []
    n = len(path)
    for _ in range(num_neighbors):
        # 随机选择两个非起点城市进行交换（索引从1开始）
        i = np.random.randint(1, n)
        j = np.random.randint(1, n)
        while i == j:  # 确保选择不同城市
            j = np.random.randint(1, n)
            
        new_path = path.copy()
        new_path[i], new_path[j] = new_path[j], new_path[i]
        # 记录交换的城市对（排序后作为禁忌对象）
        city_i, city_j = path[i], path[j]
        swap = tuple(sorted((city_i, city_j)))
        neighborhood.append((swap, new_path))
    return neighborhood

def tabu_search(distance_matrix, max_iterations=1000, tabu_tenure=7, neighborhood_size=100):
    """禁忌搜索算法主函数
    
    Args:
        distance_matrix (ndarray): 距离矩阵
        max_iterations (int): 最大迭代次数
        tabu_tenure (int): 禁忌期限（禁忌表存活周期）
        neighborhood_size (int): 每次迭代生成的邻域解数量
        
    Returns:
        tuple: (最优路径, 最优距离, 收敛历史记录)
    """
    n_cities = distance_matrix.shape[0]
    # 初始化当前解和全局最优解
    current_solution = generate_initial_solution(n_cities)
    current_distance = calculate_path_distance(current_solution, distance_matrix)
    best_solution = current_solution.copy()
    best_distance = current_distance
    
    # 禁忌表结构：{swap_pair: remaining_tenure}
    tabu_list = {}
    history = []  # 记录每次迭代的最优距离

    for iteration in range(max_iterations):
        # 生成当前解的邻域候选解
        candidates = generate_neighborhood(current_solution, neighborhood_size)
        candidate_list = []
        for swap, new_path in candidates:
            # 计算每个候选解的路径距离
            distance = calculate_path_distance(new_path, distance_matrix)
            candidate_list.append((swap, new_path, distance))
        # 按距离升序排序候选解
        candidate_list.sort(key=lambda x: x[2])

        best_candidate = None
        # 遍历候选解寻找最优解（考虑禁忌表）
        for candidate in candidate_list:
            swap, new_path, new_distance = candidate
            if swap in tabu_list:
                # 特赦准则：当候选解优于全局最优时，打破禁忌
                if new_distance < best_distance:
                    best_candidate = candidate
                    best_solution = new_path.copy()
                    best_distance = new_distance
                    break
            else:
                # 选择第一个非禁忌的最优候选解
                best_candidate = candidate
                break

        if best_candidate:
            # 更新当前解和禁忌表
            swap, new_path, new_distance = best_candidate
            current_solution = new_path
            current_distance = new_distance
            
            # 更新禁忌表：所有条目期限减1，过期条目移除
            for key in list(tabu_list.keys()):
                tabu_list[key] -= 1
                if tabu_list[key] <= 0:
                    del tabu_list[key]
            # 添加新禁忌对象
            tabu_list[swap] = tabu_tenure
            
            # 更新全局最优解
            if new_distance < best_distance:
                best_solution = new_path.copy()
                best_distance = new_distance
        history.append(best_distance)

        # 每100次迭代输出当前最优
        if iteration % 100 == 0:
            print(f"Iteration {iteration}, Best Distance: {best_distance:.2f}")

    return best_solution, best_distance, history

# 生成随机距离矩阵（50个城市）
n_cities = 50
np.random.seed(42)  # 固定随机种子保证可重复性
coordinates = np.random.rand(n_cities, 2) * 100  # 生成0-100范围的坐标
distance_matrix = np.zeros((n_cities, n_cities))
for i in range(n_cities):
    for j in range(n_cities):
        if i != j:
            dx = coordinates[i][0] - coordinates[j][0]
            dy = coordinates[i][1] - coordinates[j][1]
            distance_matrix[i][j] = np.sqrt(dx**2 + dy**2)

# 运行禁忌搜索
best_path, best_dist, history = tabu_search(distance_matrix)

# 可视化结果（改进版）
plt.figure(figsize=(10, 6))
x = [coordinates[city][0] for city in best_path + [best_path[0]]]
y = [coordinates[city][1] for city in best_path + [best_path[0]]]

# 绘制路径连线
plt.plot(x, y, '--', color='gray', alpha=0.6, linewidth=1)

# 单独绘制起点/终点（0号城市）
start_end_x = coordinates[0][0]
start_end_y = coordinates[0][1]
plt.plot(start_end_x, start_end_y, 
         'p',  # 五角星标记
         color='red', 
         markersize=12,
         markeredgecolor='black',
         markeredgewidth=1,
         label='Start/End (City 0)')

# 绘制其他城市点
other_cities_x = [coordinates[i][0] for i in range(n_cities) if i != 0]
other_cities_y = [coordinates[i][1] for i in range(n_cities) if i != 0]
plt.plot(other_cities_x, other_cities_y, 
         'o',  # 圆圈标记
         color='dodgerblue',
         markersize=6,
         alpha=0.8,
         label='Other Cities')

# 添加路径方向箭头（每隔10个城市添加一个箭头）
for i in range(0, len(best_path), max(1, len(best_path)//10)):
    plt.annotate('',
                 xytext=(x[i], y[i]),
                 xy=(x[i+1], y[i+1]),
                 arrowprops=dict(arrowstyle='->', color='gray', lw=0.5),
                 fontsize=8)
# 路径曲线
plt.title(f"Optimal TSP Path (Distance: {best_dist:.2f})", fontsize=12)
plt.xlabel("X Coordinate", fontsize=10)
plt.ylabel("Y Coordinate", fontsize=10)
plt.grid(True, linestyle='--', alpha=0.3)
plt.legend(loc='upper right', fontsize=9)
plt.tight_layout()
plt.show()

# 绘制收敛曲线
plt.figure(figsize=(10, 6))
plt.plot(history, linewidth=1)
plt.title("Convergence Curve of Tabu Search")
plt.xlabel("Iteration")
plt.ylabel("Best Distance")
plt.grid(True)
plt.show()