用Python模拟退火算法解决TSP问题：从物理退火到代码实现的保姆级拆解

用Python模拟退火算法解决TSP问题从物理退火到代码实现的保姆级拆解想象一下你是一位需要走访20个城市的销售经理如何规划路线才能使总行程最短这个看似简单的问题在计算机科学中被称为旅行商问题TSP已被证明是NP难问题。今天我们将从金属退火的物理现象出发带你理解模拟退火算法如何优雅地解决这类组合优化难题并用Python代码完整实现这一过程。1. 从金属退火到算法灵感1983年Kirkpatrick等科学家观察到金属退火过程中的原子运动与优化问题惊人的相似性。当金属被加热到高温时原子处于高能态随机运动剧烈随着温度缓慢降低原子逐渐趋向能量最低的稳定排列。这种自然现象启发了模拟退火算法的诞生。算法与物理过程的对应关系金属温度 → 控制参数T原子排列 → 问题解系统能量 → 目标函数值温度下降 → 搜索范围收缩注意算法中的温度只是数学概念与真实温度无关它控制着接受劣解的概率。2. 算法核心Metropolis准则模拟退火最精妙之处在于它允许算法以一定概率接受比当前解更差的解这种机制有效避免了陷入局部最优。接受概率由Metropolis准则决定def acceptance_probability(delta, temperature): if delta 0: # 新解更优 return 1.0 return math.exp(-delta / temperature) # 以概率接受劣解关键参数设置经验值参数典型范围作用初始温度1e5-1e7决定初始接受劣解的概率降温系数0.8-0.99控制温度下降速度终止温度0.1-1算法停止条件马尔可夫链长100-1000每个温度下的迭代次数3. TSP问题建模与解表示对于n个城市的TSP问题我们采用排列编码表示解。例如对于5个城市的问题[0,3,1,4,2]表示访问顺序为城市0→3→1→4→2→0。目标函数计算def total_distance(path): distance 0 for i in range(len(path)-1): distance dist_matrix[path[i]][path[i1]] distance dist_matrix[path[-1]][path[0]] # 回到起点 return distance4. Python实现详解4.1 初始解生成随机排列产生初始解确保覆盖整个搜索空间initial_solution np.random.permutation(num_cities)4.2 邻域搜索2-opt操作通过交换两个城市的位置产生新解def two_opt_swap(current_route): new_route current_route.copy() i, j sorted(np.random.choice(len(new_route), 2, replaceFalse)) new_route[i:j1] new_route[i:j1][::-1] # 反转子路径 return new_route4.3 完整算法流程def simulated_annealing(cities, temp10000, cooling_rate0.99, min_temp0.1): current_solution generate_random_route(cities) best_solution current_solution.copy() while temp min_temp: for _ in range(100): # 每个温度迭代100次 new_solution two_opt_swap(current_solution) cost_diff total_distance(new_solution) - total_distance(current_solution) if cost_diff 0 or random.random() math.exp(-cost_diff/temp): current_solution new_solution.copy() if total_distance(current_solution) total_distance(best_solution): best_solution current_solution.copy() temp * cooling_rate # 降温 return best_solution5. 参数调优与可视化降温策略对比指数降温T αT (α∈(0,1))线性降温T T - ΔT对数降温T T0 / log(1k)实验表明对于TSP问题初始温度设为城市间平均距离的10倍降温系数0.95-0.99效果较好。结果可视化def plot_route(cities, route): plt.figure(figsize(10,6)) x [cities[i][0] for i in route] [cities[route[0]][0]] y [cities[i][1] for i in route] [cities[route[0]][1]] plt.plot(x, y, o-, markersize8) plt.title(fOptimal Route: Distance {total_distance(route):.2f}) plt.show()6. 性能优化技巧距离矩阵预计算提前计算并存储所有城市间距离增量计算只重新计算受交换影响的路段距离并行退火同时运行多个退火过程保留最佳解自适应参数根据接受率动态调整降温速率# 增量计算示例 def delta_distance(route, i, j): n len(route) a, b route[i], route[(i1)%n] c, d route[j], route[(j1)%n] return (dist_matrix[a][c] dist_matrix[b][d]) - (dist_matrix[a][b] dist_matrix[c][d])7. 算法变体与扩展应用模拟退火算法经过适当修改可应用于多种组合优化问题车辆路径问题增加载重约束调度问题处理时间窗口限制布局优化如芯片布线、仓库货架排列对于超大规模TSP问题可以考虑以下改进结合局部搜索算法使用基于分区的策略引入记忆机制禁忌表在实际项目中我发现初始温度设置对结果影响显著。过高的初始温度会导致计算时间过长而过低则可能无法跳出局部最优。经过多次测试将初始温度设为目标函数初始值的1.5倍左右通常能取得较好平衡。