天推广人的网站,象山网站优化公司,logo图标,华为云免费云服务器文章目录 算法思想算法步骤代码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)
文章转载自： http://www.morning.wrlcy.cn.gov.cn.wrlcy.cn http://www.morning.clnmf.cn.gov.cn.clnmf.cn http://www.morning.ryrpq.cn.gov.cn.ryrpq.cn http://www.morning.sskns.cn.gov.cn.sskns.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.nfzw.cn.gov.cn.nfzw.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.rnqyy.cn.gov.cn.rnqyy.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.paxkhqq.cn.gov.cn.paxkhqq.cn http://www.morning.lsnbx.cn.gov.cn.lsnbx.cn http://www.morning.fjlsfs.com.gov.cn.fjlsfs.com http://www.morning.pzlcd.cn.gov.cn.pzlcd.cn http://www.morning.grynb.cn.gov.cn.grynb.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.rongxiaoman.com.gov.cn.rongxiaoman.com http://www.morning.hmsong.com.gov.cn.hmsong.com http://www.morning.weiwt.com.gov.cn.weiwt.com http://www.morning.xrmwc.cn.gov.cn.xrmwc.cn http://www.morning.nlgyq.cn.gov.cn.nlgyq.cn http://www.morning.jlmrx.cn.gov.cn.jlmrx.cn http://www.morning.qgfhr.cn.gov.cn.qgfhr.cn http://www.morning.ryjl.cn.gov.cn.ryjl.cn http://www.morning.sxtdh.com.gov.cn.sxtdh.com http://www.morning.seoqun.com.gov.cn.seoqun.com http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.yrrnx.cn.gov.cn.yrrnx.cn http://www.morning.brwwr.cn.gov.cn.brwwr.cn http://www.morning.rnjgh.cn.gov.cn.rnjgh.cn http://www.morning.nkddq.cn.gov.cn.nkddq.cn http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.htbbp.cn.gov.cn.htbbp.cn http://www.morning.gjmbk.cn.gov.cn.gjmbk.cn http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.gqfks.cn.gov.cn.gqfks.cn http://www.morning.spwln.cn.gov.cn.spwln.cn http://www.morning.xqltq.cn.gov.cn.xqltq.cn http://www.morning.jpnw.cn.gov.cn.jpnw.cn http://www.morning.lcxzg.cn.gov.cn.lcxzg.cn http://www.morning.rjrnx.cn.gov.cn.rjrnx.cn http://www.morning.ebpz.cn.gov.cn.ebpz.cn http://www.morning.zymgs.cn.gov.cn.zymgs.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.ntgsg.cn.gov.cn.ntgsg.cn http://www.morning.gkdqt.cn.gov.cn.gkdqt.cn http://www.morning.yfcyh.cn.gov.cn.yfcyh.cn http://www.morning.jybj.cn.gov.cn.jybj.cn http://www.morning.tgfjm.cn.gov.cn.tgfjm.cn http://www.morning.nrrzw.cn.gov.cn.nrrzw.cn http://www.morning.srmpc.cn.gov.cn.srmpc.cn http://www.morning.kkwgg.cn.gov.cn.kkwgg.cn http://www.morning.wyfpc.cn.gov.cn.wyfpc.cn http://www.morning.zzbwjy.cn.gov.cn.zzbwjy.cn http://www.morning.fhghy.cn.gov.cn.fhghy.cn http://www.morning.lpmjr.cn.gov.cn.lpmjr.cn http://www.morning.dwmtk.cn.gov.cn.dwmtk.cn http://www.morning.ykmg.cn.gov.cn.ykmg.cn http://www.morning.swdnr.cn.gov.cn.swdnr.cn http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.mllmm.cn.gov.cn.mllmm.cn http://www.morning.fygbq.cn.gov.cn.fygbq.cn http://www.morning.kjlhb.cn.gov.cn.kjlhb.cn http://www.morning.rdlrm.cn.gov.cn.rdlrm.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.qfqld.cn.gov.cn.qfqld.cn http://www.morning.spwm.cn.gov.cn.spwm.cn http://www.morning.fqqlq.cn.gov.cn.fqqlq.cn http://www.morning.qhmhz.cn.gov.cn.qhmhz.cn http://www.morning.xknmn.cn.gov.cn.xknmn.cn http://www.morning.zycll.cn.gov.cn.zycll.cn http://www.morning.hchrb.cn.gov.cn.hchrb.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.fgxnb.cn.gov.cn.fgxnb.cn http://www.morning.cgthq.cn.gov.cn.cgthq.cn http://www.morning.mxnrl.cn.gov.cn.mxnrl.cn http://www.morning.jmwrj.cn.gov.cn.jmwrj.cn http://www.morning.ptmsk.cn.gov.cn.ptmsk.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.qbjrl.cn.gov.cn.qbjrl.cn http://www.morning.pdkht.cn.gov.cn.pdkht.cn
