天推广人的网站,搭建游戏服务器,微营销平台有哪些,全县网站建设管理工作会议召开文章目录 算法思想算法步骤代码1纯函数代码2纯函数数据可视化 算法思想
通过交换边进行寻优。
算法步骤 把初始解作为当前解 通过交换边生成新解 如果新解优于历史最优解#xff0c;则更新当前解为新解 重复2#xff0c;3#xff0c;直到当前解交换了所有的边均不能改… 文章目录 算法思想算法步骤代码1·纯函数代码2·纯函数数据可视化 算法思想
通过交换边进行寻优。
算法步骤 把初始解作为当前解 通过交换边生成新解 如果新解优于历史最优解则更新当前解为新解 重复23直到当前解交换了所有的边均不能改善。
代码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], colorblack, markero)plt.plot([cities[solution[0], 0], cities[solution[-1], 0]],[cities[solution[0], 1], cities[solution[-1], 1]], colorblack, markero) # 回到起点# 去掉坐标轴黑框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)
