算法整理：2-opt求解旅行商（Python代码）

算法思想

通过交换边进行寻优。

算法步骤

1. 把初始解作为当前解

2. 通过交换边生成新解
   

3. 如果新解优于历史最优解，则更新当前解为新解

4. 重复2，3，直到当前解交换了所有的边均不能改善。

代码1·纯函数

def two_opt(I, c):"""Two-opt 旅行商路径优化算法I: 城市编号的listc: 距离矩阵c[i,j]"""best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))best_solution = I[:]improve = Trues = 0while improve:improve = Falsefor i in range(len(I) - 1):for j in range(i + 1, len(I) - 1):if j - i >= 1:  # 确保至少有两个城市在i和j之间delta = (c[best_solution[i - 1], best_solution[j]] +c[best_solution[i], best_solution[j + 1]] -c[best_solution[i - 1], best_solution[i]] -c[best_solution[j], best_solution[j + 1]])if delta < -0.0001:# 进行反转操作best_solution[i:j + 1] = reversed(best_solution[i:j + 1])plot_route(cities, best_solution)best_distance += deltaimprove = Truereturn best_solution, best_distance

• 注意代码中当i == 0时，best_solution[i - 1] =best_solution[- 1]，指向了最后一个城市，由于是TSP问题，并不违反逻辑。

代码2·纯函数+数据+可视化

import time
import numpy as np
import matplotlib.pyplot as pltdef generate_random_cities(num_cities):"""生成随机的城市坐标及距离矩阵"""np.random.seed(3)   # 锁定随机种子cities = np.random.rand(num_cities, 2)  # 生成随机坐标distance_matrix = np.zeros((num_cities, num_cities))for i in range(num_cities):for j in range(num_cities):distance_matrix[i, j] = np.linalg.norm(cities[i] - cities[j])  # 计算欧几里得距离return cities, distance_matrixdef two_opt(I, c):"""Two-opt 旅行商路径优化算法I: 城市编号的listc: 距离矩阵c[i,j]"""best_distance = sum(c[I[i], I[i + 1]] for i in range(len(I) - 1))best_solution = I[:]improve = Trues = 0while improve:improve = Falsefor i in range(len(I) - 1):for j in range(i + 2, len(I) - 1):delta = (c[best_solution[i - 1], best_solution[j]] +c[best_solution[i], best_solution[j + 1]] -c[best_solution[i - 1], best_solution[i]] -c[best_solution[j], best_solution[j + 1]])if delta < -1e-6:# 进行反转操作best_solution[i:j + 1] = reversed(best_solution[i:j + 1])plot_route(cities, best_solution)best_distance += deltaimprove = Truereturn best_solution, best_distancedef plot_route(cities, solution):"""可视化城市和路径"""# 画出路径plt.plot(cities[solution][:, 0], cities[solution][:, 1], color='black', marker='o')plt.plot([cities[solution[0], 0], cities[solution[-1], 0]],[cities[solution[0], 1], cities[solution[-1], 1]], color='black', marker='o')  # 回到起点# 去掉坐标轴黑框ax = plt.gca()ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')ax.spines['left'].set_color('none')ax.spines['bottom'].set_color('none')# 隐藏坐标轴刻度ax.xaxis.set_ticks_position('none')ax.yaxis.set_ticks_position('none')# 隐藏坐标轴刻度标签ax.set_xticks([]) ax.set_yticks([])# 每帧显示时间plt.pause(1)# 清空内容plt.cla()# 主程序
num_cities = 10  # 城市数量
cities, distance_matrix = generate_random_cities(num_cities)
I = list(range(num_cities))  # 编号的集合# 运行 two_opt 算法
optimized_solution, optimized_distance = two_opt(I, distance_matrix)# 打印结果
print("优化后的路径:", optimized_solution)
print("优化后的距离:", optimized_distance)# 可视化优化后的路径
plot_route(cities, optimized_solution)