【建模算法】基于模拟退火算法求解TSP问题(Python实现) TSP (traveling salesman problem,旅行商问题)是典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长,到目前为止还未找到一个多项式时间的有效算法。本文探讨了基于模拟退火算法求解TSP问题的Python实现。
一、问题描述 ? 本案例以31个城市为例,假定31个城市的位置坐标如表1所列。寻找出一条最短的遍历31个城市的路径。
城市编号 | X坐标 | Y坐标 | 城市编号 | X坐标 | Y坐标 |
---|---|---|---|---|---|
1 | 1.304 | 2.312 | 17 | 3.918 | 2.179 |
2 | 3.639 | 1.315 | 18 | 4.061 | 2.37 |
3 | 4.177 | 2.244 | 19 | 3.78 | 2.212 |
4 | 3.712 | 1.399 | 20 | 3.676 | 2.578 |
5 | 3.488 | 1.535 | 21 | 4.029 | 2.838 |
6 | 3.326 | 1.556 | 22 | 4.263 | 2.931 |
7 | 3.238 | 1.229 | 23 | 3.429 | 1.908 |
8 | 4.196 | 1.044 | 24 | 3.507 | 2.376 |
9 | 4.312 | 0.79 | 25 | 3.394 | 2.643 |
10 | 4.386 | 0.57 | 26 | 3.439 | 3.201 |
11 | 3.007 | 1.97 | 27 | 2.935 | 3.24 |
12 | 2.562 | 1.756 | 28 | 3.14 | 3.55 |
13 | 2.788 | 1.491 | 29 | 2.545 | 2.357 |
14 | 2.381 | 1.676 | 30 | 2.778 | 2.826 |
15 | 1.332 | 0.695 | 31 | 2.37 | 2.975 |
16 | 3.715 | 1.678 |
三、求解结果 初始路线与初始距离:
文章图片
文章图片
最优路线与最优值:
文章图片
最优轨迹图:
文章图片
四、实现代码
#模拟退火算法求解TSP问题完整代码:
#31座城市TSP问题
import math
import random
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import sys
from numpy.matlib import rand
from matplotlib.artist import getp
import copy#构建初始参考距离矩阵
def getdistance():
for i in range(n):
for j in range(n):
x = pow(city_x[i] - city_x[j], 2)
y = pow(city_y[i] - city_y[j], 2)
distance[i][j] = pow(x + y, 0.5)
for i in range(n):
for j in range(n):
if distance[i][j] == 0:
distance[i][j] = sys.maxsize#计算总距离
def cacl_best(rou):
sumdis = 0.0
for i in range(n-1):
sumdis += distance[rou[i]][rou[i+1]]
sumdis += distance[rou[n-1]][rou[0]]
return sumdis#得到新解
def getnewroute(route, time):
#如果是偶数次,二变换法
'''
注意:数组直接复制是复制地址
例如, current = route
想要得到一个新的有同样内容的数组,应该用: current = copy.copy(route)
'''
current = copy.copy(route)if time % 2 == 0:
u = random.randint(0, n-1)
v = random.randint(0, n-1)
temp = current[u]
current[u] = current[v]
current[v] = temp
#如果是奇数次,三变换法
else:
temp2 = random.sample(range(0, n), 3)
temp2.sort()
u = temp2[0]
v = temp2[1]
w = temp2[2]
w1 = w + 1
temp3 = [0 for col in range(v - u + 1)]
j =0
for i in range(u, v + 1):
temp3[j] = current[i]
j += 1for i2 in range(v + 1, w + 1):
current[i2 - (v-u+1)] = current[i2]
w = w - (v-u+1)
j = 0
for i3 in range(w+1, w1):
current[i3] = temp3[j]
j += 1return currentdef draw(best):
result_x = [0 for col in range(n+1)]
result_y = [0 for col in range(n+1)]for i in range(n):
result_x[i] = city_x[best[i]]
result_y[i] = city_y[best[i]]
result_x[n] = result_x[0]
result_y[n] = result_y[0]
plt.rcParams['font.sans-serif'] = 'SimHei'# 设置中文显示
plt.rcParams['axes.unicode_minus'] = False
plt.xlim(0, 5)# 限定横轴的范围
plt.ylim(0, 4)# 限定纵轴的范围
plt.plot(result_x, result_y, marker='>', mec='r', mfc='w',label=u'路线')
plt.legend()# 让图例生效
plt.margins(0)
plt.subplots_adjust(bottom=0.15)
for i in range(len(best)):
plt.text(result_x[i] + 0.05, result_y[i] + 0.05, str(best[i]+1), color='red')
plt.xlabel('横坐标')
plt.ylabel('纵坐标')
plt.title('轨迹图')
plt.show()def print_route(route):
result_cur_best=[]
for i in route:
result_cur_best+=[i]
for i in range(len(result_cur_best)):
result_cur_best[i] += 1
result_path = result_cur_best
result_path.append(result_path[0])
return result_pathdef solve():
#得到距离矩阵
getdistance()
#得到初始解以及初始距离
route = random.sample(range(0, n), n)
total_dis = cacl_best(route)
print("初始路线:", print_route(route))
print("初始距离:", total_dis)
draw(route)
#新解
newroute = []
new_total_dis = 0.0
best = route
best_total_dis = total_dis
t = T0while True:
if t <= Tend:
break
#令温度为初始温度
for rt2 in range(L):
newroute = getnewroute(route, rt2)
new_total_dis = cacl_best(newroute)
delt = new_total_dis - total_dis
if delt <= 0:
route = newroute
total_dis = new_total_dis
if best_total_dis > new_total_dis:
best = newroute
best_total_dis = new_total_dis
elif delt > 0:
p = math.exp(-delt / t)
ranp = random.uniform(0, 1)
if ranp < p:
route = newroute
total_dis = new_total_dis
t = t * a
print("现在温度为:", t)
print("最优路线:", print_route(best))
print("最优值:", best_total_dis)
draw(best)
if __name__=="__main__":
#读取31座城市坐标
coord = []
with open("data.txt", "r") as lines:
lines = lines.readlines()
for line in lines:
xy = line.split()
coord.append(xy)
coord = np.array(coord)
w, h = coord.shape
coordinates = np.zeros((w, h), float)
for i in range(w):
for j in range(h):
coordinates[i, j] = float(coord[i, j])
city_x=coordinates[:,0]
city_y=coordinates[:,1]
#城市数量
n = coordinates.shape[0]
distance = [[0 for col in range(n)] for raw in range(n)]
#初始温度 结束温度
T0 = 31
Tend = 1e-8
#循环控制常数
L = 10
#温度衰减系数
a = 0.98
solve()
推荐阅读
- 最大和连续子数组的Python程序
- 数学建模|【建模算法】Python调用scikit-opt工具箱中的模拟退火算法求解TSP问题
- 算法|冲刺秋招!最全面的机器学习知识复习及巩固攻略
- 程序员|Python爬虫系列(爬取小说并写入txt文件)
- Python|模拟退火算法解决TSP(python实现 110+行代码)【gif生成】
- 启发式算法|模拟退火算法求解 TSP 问题的代码示例
- #yyds干货盘点# Python训练营Python每日一练----第23天:字符计数
- Python程序设计范例详细指南
- Python使用OpenCV反向播放视频()