模拟退火算法求解 TSP（SAA）

目录

• 项目概览
• 实验结果汇总
  • 个性化实验参数
  • 参数对比结果（v1.0，指数降温 α 对比）
  • 结论分析
• 当前支持功能（v1.7+）
• 项目结构
• 核心实现片段
  • 邻域构造（统一接口）
  • Metropolis 接受准则
  • 温度更新策略（四种）
• 快速开始
• 后续改进方向

---

项目概览

本项目使用 模拟退火算法（Simulated Annealing, SA） 求解旅行商问题（TSP），并围绕不同降温系数进行参数对比实验，分析收敛速度与解质量之间的权衡关系。

---

实验结果汇总

4.1 实验设置

为保证实验可复现性，本文采用固定随机种子，并在相同城市规模、邻域结构与降温框架下开展对比实验。个性化参数设置如下。

参数	值
随机种子	24341
城市数量 N	50
坐标范围	1000 × 1000
初始温度 T_0	1820
终止温度 T_{final}	1.0
每温度内循环次数	200
提前停止参数 patience	44

4.2 退火系数 α 对算法性能的影响

首先，在随机初始解条件下，对指数降温策略中的退火系数 α 进行对比。实验结果如下。

退火系数 α	外循环迭代次数	最优路径长度	耗时（秒）
0.85	47	6012.33	0.10
0.92	91	5824.29	0.19
0.99	747	5487.02	1.63

由表可见，随着退火系数增大，温度下降速度减慢，算法能够在更长时间内保持较强的搜索能力，因此最优路径长度持续下降。其中，α = 0.99 时所得路径最短，为 5487.02，说明慢速降温有助于算法跳出局部最优并获得更优解；但与此同时，外循环次数和运行时间也显著增加。相比之下，α = 0.85 虽然运行最快，但搜索不够充分，最终结果最差；α = 0.92 则在路径质量与运行开销之间表现居中。

综上，实验结果验证了模拟退火算法中的典型规律：降温越慢，搜索越充分，路径质量通常越高，但计算代价也越大。

4.3 不同初始解方法对比实验

在相同 SEED=24341、城市数量 N=50、邻域方法及降温策略保持一致的条件下，进一步比较两种初始解生成方式：

1. random：随机全排列初始解；
2. nearest_neighbor：最邻近贪心初始解。

对应实验结果图中，随机初始解使用 tsp_result_alpha*.png，最近邻贪心初始解使用 tsp_result_nn_alpha*.png；汇总图分别为 tsp_comparison.png 和 tsp_comparison_nn.png。

退火系数 α	随机初始解最优路径	最近邻贪心初解最优路径	质量差（NN - Random）
0.85	6012.33（外循环 47，耗时约 0.10s）	6124.80（外循环 47，耗时约 0.11s）	+112.47（更差）
0.92	5824.29（外循环 91，耗时约 0.19s）	5534.16（外循环 91，耗时约 0.22s）	-290.13（更好）
0.99	5487.02（外循环 561，耗时约 1.25s）	5439.57（外循环 747，耗时约 1.49s）	-47.45（更好）

从结果上看，最近邻贪心初始解并未在所有参数下稳定优于随机初始解：在 α = 0.85 时，其结果反而更差；而在 α = 0.92 和 α = 0.99 时，则取得了更优的最终路径。这说明初始解方法的优劣并不能脱离具体搜索过程单独判断，其效果还会受到降温节奏与停止策略的共同影响。

4.4 早停机制对初始解比较结果的影响

结合结果图可以发现，影响上述现象的关键因素之一在于早停机制与初始解特征之间的耦合。

本实验采用的早停规则为：当 best_len 连续 PATIENCE = 44 轮外循环没有改进时，算法提前终止。该策略在 random 初始解下效果较好，因为随机初解通常较差，前期搜索过程中 best_len 往往会持续下降，因此不容易在搜索尚未充分展开时触发早停。

相比之下，nearest_neighbor 初始解本身质量更高、路径结构也更规整，算法在前期更容易出现“当前最优解保持不变”的平台期。这一阶段虽然没有立即产生新的最优解，但并不意味着搜索已经真正收敛，更可能只是暂时停留在某个局部稳定区域，仍需要更多温度层和邻域扰动来继续跳出。

问题在于，当前早停判据只依据 best_len 是否连续多轮不变，无法区分“真正收敛”与“高质量初解导致的暂时平台”。因此，在 nearest_neighbor 初始解下，平台期更容易被误判为收敛，从而使算法被提前终止。换言之，部分实验结果并不完全反映初始解本身的优劣，而是反映了固定 patience 早停策略对不同搜索节奏的适应性差异。

这一点可以解释原实验中的现象：random 初始解在 patience=44 下能够取得较好结果，而 nearest_neighbor 初始解却可能表现较差。其原因并非最近邻贪心方法本身无效，而是该方法更容易在前期进入平台期，从而与当前早停策略发生冲突。

4.5 实验结论与改进方向

综合以上实验，可以得到以下结论：

1. 退火系数越大，算法降温越慢，搜索越充分，通常可以得到更优路径，但运行时间也显著增加。
2. 最近邻贪心初始解并非始终优于随机初始解，其效果与降温策略和停止策略密切相关。
3. 固定的 patience=44 在 random 初始解下较为有效，但在 nearest_neighbor 初始解下可能因前期平台期而过早触发，影响最终结果。
4. 因此，在比较不同初始解方法时，必须同时考虑停止机制，否则容易对初始解优劣作出片面判断。

为进一步提高实验结论的可靠性，后续可以从以下方向继续改进：

• 适当增大 nearest_neighbor 情况下的 PATIENCE；
• 暂时关闭早停，固定外循环上限后再比较不同初始解的最终结果；
• 设计更稳健的早停判据，例如同时结合温度、接受率和当前解变化幅度，而不是仅依据 best_len 是否连续不变。

---

当前支持功能（v1.10+）

• 邻域方法：2-opt（O(1) 增量）、swap（O(1) 增量）、insert（整路重算）
• 降温策略：exponential（指数）、linear（线性）、logarithmic（对数）、adaptive（自适应）
• 初始解方法：random（随机全排列）或 nearest_neighbor（最邻近贪心），通过 config.py 中的 INITIAL_TOUR_METHOD 控制
• 配置化切换：通过 config.py 中的 NEIGHBOR_METHOD 与 COOLING_STRATEGY 选择策略，无需改源码
• 提前停止机制：通过 config.py 中的 PATIENCE 控制“连续无最优改进轮数”到达阈值后提前终止外循环

---

项目结构

文件名	说明
config.py	实验参数配置文件，包含问题规模、退火参数、邻域方法、降温策略、初始解方法与早停参数等
tsp_simulated_annealing.py	主算法实现文件，包含城市生成、距离矩阵计算、不同邻域操作、不同降温策略及结果可视化
README.md	项目说明文档，包含算法设计、实验结果分析与使用说明
LOG.md	实验日志，记录版本迭代与功能更新
tsp_result_alpha085.png	随机初始解下，α = 0.85 的单组实验结果图（路径、长度、温度、接受率）
tsp_result_alpha092.png	随机初始解下，α = 0.92 的单组实验结果图（路径、长度、温度、接受率）
tsp_result_alpha099.png	随机初始解下，α = 0.99 的单组实验结果图（路径、长度、温度、接受率）
tsp_comparison.png	随机初始解下，不同 α 参数的汇总对比图
tsp_result_nn_alpha085.png	最近邻贪心初始解下，α = 0.85 的单组实验结果图（路径、长度、温度、接受率）
tsp_result_nn_alpha092.png	最近邻贪心初始解下，α = 0.92 的单组实验结果图（路径、长度、温度、接受率）
tsp_result_nn_alpha099.png	最近邻贪心初始解下，α = 0.99 的单组实验结果图（路径、长度、温度、接受率）
tsp_comparison_nn.png	最近邻贪心初始解下，不同 α 参数的汇总对比图

---

核心实现片段

邻域构造（统一接口）

# 2-opt：O(1) 增量计算
new_tour, delta_E = move_2opt(tour, dist_matrix)

# swap：O(1) 增量计算（非相邻情形）
new_tour, delta_E = move_swap(tour, dist_matrix)

# insert：整路重算
new_tour, delta_E = move_insert(tour, dist_matrix)

Metropolis 接受准则

if delta_E < 0:
    # 优于当前解 -> 无条件接受
    current_tour, current_len = new_tour, new_len
else:
    # 劣于当前解 -> 以 Boltzmann 概率接受
    if np.random.random() < np.exp(-delta_E / T):
        current_tour, current_len = new_tour, new_len

温度更新策略（四种）

if T_d == 'exponential':
    T *= alpha  # 指数降温
elif T_d == 'linear':
    T -= linear_step  # 线性降温
elif T_d == 'logarithmic':
    T = T0 / np.log(outer_iter + 2)  # 对数降温
elif T_d == 'adaptive':
    # 自适应降温（按接受率调节）
    acc_rate = accepted / inner_iter
    if acc_rate > 0.6:
        T *= 0.90
    elif acc_rate < 0.2:
        T *= 0.98
    else:
        T *= 0.95
T = max(T, T_final)  # 温度下界保护

---

快速开始

python tsp_simulated_annealing.py

如需调参，请编辑 config.py 中的相关配置（如 ALPHAS、INNER_ITER、NEIGHBOR_METHOD、COOLING_STRATEGY）。

---

后续改进方向

• 多次独立运行统计（10~30 次，记录 mean/std/best/worst）
• 邻域混合策略（2-opt + insert 自适应切换）