基于模拟退火算法的TSP路径优化系统

资 源 简 介

本项目开发了一套基于MATLAB的智能优化系统，专门用于求解经典的NP-hard组合优化问题——旅行商问题（TSP）。系统的核心目标是在给定一系列城市和各城市位置坐标的情况下，寻找一条经过所有城市一次且仅一次最后回到起点的最短闭环路径。程序基于模拟退火算法（Simulated Annealing, SA）的物理退火原理设计，通过模拟固体退火过程中的热力学规律，在解空间中进行随机搜索。功能实现细节包括：1. 数据处理模块，支持随机生成指定数量的城市坐标或从外部数据文件导入城市位置；2. 核心算法引擎，实现了基于交换、逆转、插入等多种策略的邻域解构造方法，并集成Metropolis接受准则，允许算法在搜索初期以一定概率接受较差解，从而有效避免陷入局部最优陷阱，确保算法具有全局寻优能力；3. 温度控制机制，包含初始温度设定、指数降温策略及终止条件判断；4. 动态可视化模块，能够在算法运行过程中实时动态绘制路径连线图的优化过程，并同步生成路径总长度随迭代次数变化的收敛曲线，帮助用户直观分析算法性能。该工具可广泛应用于物流配送路径规划、电路板钻孔路径优化以及各类离散组合优化问题的教学与研究。

详 情 说 明

基于模拟退火算法的旅行商问题(TSP)求解系统

项目简介

本项目是一个基于MATLAB开发的智能优化系统，旨在利用模拟退火算法（Simulated Annealing, SA）求解经典的NP-hard组合优化问题——旅行商问题（TSP）。系统通过模拟物理退火过程中的热力学原理，结合多种邻域搜索策略，在给定的城市列表中寻找一条经过所有城市一次且仅一次并最终回到起点的最短闭环路径。该程序集成了数据生成、核心算法解算、动态可视化展示及收敛分析功能。

功能特性

• 随机数据生成：系统自动在 $[0, 100]$ 的二维平面区域内生成指定数量（默认为30个）的随机城市坐标，并计算城市间的欧几里得距离矩阵。
• 混合邻域搜索策略：为了增强算法跳出局部最优的能力，程序内置了三种不同的路径扰动机制（交换、逆转、插入），在迭代过程中随机选择使用。
• Metropolis 接受准则：严格遵循模拟退火原理，不仅接受更优解，还依据玻尔兹曼概率准则以一定概率接受较差解，确保全局搜索能力。
• 动态可视化界面：提供双窗口实时展示。左侧窗口动态绘制当前的路径连接图，右侧窗口实时更新最短路径长度的收敛曲线，直观呈现优化过程。
• 指数降温机制：采用几何级数降温策略，配合内循环（马尔可夫链）稳定机制，平衡搜索速度与解的质量。

算法实现与核心逻辑

该系统基于MATLAB脚本编写，其核心执行流程与逻辑如下：

1. 初始化阶段

程序首先清除工作区环境，并初始化算法的关键物理参数：

• 初始温度 ($T_0$)：设定为1000，确保算法初期具有较高的接受劣解概率。
• 终止温度 ($T_{end}$)：设定为0.001，控制算法结束条件。
• 降温系数 ($alpha$)：设定为0.98，控制温度下降的速率（指数降温）。
• 链长 ($L$)：设定为100，即在每个温度下进行的迭代次数（马尔可夫链长度）。

2. 解空间构建与距离计算

• 系统随机生成30个城市的二维坐标。
• 构建 $N times N$ 的距离矩阵，计算所有城市点对之间的欧几里得距离，以便后续快速查询路径成本。
• 随机生成一个初始的城市访问序列（随机排列），并计算其初始总距离作为基准。

3. 核心循环（模拟退火过程）

算法包含外循环（温度控制）和内循环（等温Metropolis抽样）：

• 邻域构造（扰动策略）：在内循环中，程序通过 randi([1, 3]) 随机选择以下三种策略之一来产生新解：

1. 交换 (Swap)：随机选取两个位置的城市进行交换。 2. 逆转 (Reverse)：随机选取一段子路径，将其顺序颠倒（类似于2-opt操作，通常对解在二维平面上的解交叉消除非常有效）。 3. 插入 (Insertion)：将随机选中的一个城市从原位置取出，插入到另一个随机位置。

• 能量评估与接受判定：

* 计算新路径的总距离。 * 计算能量由差 $Delta E = NewDist - CurrentDist$。 * 贪婪准则：如果 $Delta E < 0$（新路径更短），直接接受新解，并更新全局最优记录。 * Metropolis准则：如果 $Delta E ge 0$（新路径变长），生成一个 $[0, 1]$ 的随机数 $r$，若 $r < exp(-Delta E / T)$，则接受该劣解。这允许算法“爬坡”以跳出局部最优陷阱。

4. 降温与迭代

• 完成一轮内循环（$L$ 次迭代）后，根据公式 $T = T times alpha$ 进行降温。
• 记录当前温度下的全局最优距离，用于后续绘制收敛曲线。

5. 动态可视化

为了兼顾运行速度与观察体验，程序设置了绘图刷新频率（plotFreq），每隔指定的降温次数刷新一次图形界面：

• 路径图：绘制城市散点（红色）和当前最优路径连线（蓝色），并标记起点和城市编号。
• 收敛曲线：绘制随降温次数变化的最短路径长度曲线，帮助用户判断算法是否收敛。

使用方法

1. 确保计算机上已安装 MATLAB 软件。
2. 将脚本文件保存在本地目录中。
3. 直接运行脚本。
4. 程序将自动弹出一个图形窗口，显示“模拟退火算法求解TSP”。
5. 观察左侧的路径优化动态过程和右侧的收敛曲线。
6. 运行结束后，命令行窗口将输出最优路径长度、具体的访问城市顺序，图形窗口将保留最终的优化结果。

系统要求

• MATLAB R2016a 或更高版本（代码使用基础函数，兼容性较好）。
• 不需要额外的工具箱（Toolbox）。