type
Post
status
Published
date
Feb 24, 2022
slug
基于模拟退火算法使用Python求解TSP问题
summary
基于模拟退火算法使用Python求解TSP问题
tags
算法
路径问题
物流
python
category
编程
icon
password
Property
Nov 3, 2022 02:17 AM
随机模拟了30个客户点,计算经过30个客户点的最短路。
采用了模拟退火算法,T0设置为3000℃。
import math import random import turtle from matplotlibimport pyplotas plt # 计算a,b两点间的距离defdis(a, b): return math.sqrt(math.pow(a[0]- b[0], 2)+ math.pow(a[1]- b[1], 2)) # 创建nums个随机点defcre_points(nums): res= [] for iin range(nums): res.append([random.randint(-300, 300), random.randint(-300, 300)]) return res # 计算一条路径的总长度defsum_dis(res): s= 0 for iin range(len(res)- 1): s= s+ dis(res[i], res[i+ 1]) s= s+ dis(res[0], res[len(res)- 1]) return s # 随机变换路径中的顺序defchange_res(res0): res= [] for iin range(len(res0)): res.append(res0[i]) num= int(len(res)/ 5) if num< 2: num= 2 r= [] for iin range(num): r0= random.randint(0, len(res)- 1) while r0in r: r0= random.randint(0, len(res)- 1) r.append(r0) for iin range(len(r)): r0= random.randint(0, len(r)- 1) temp= res[r[i]] res[r[i]]=res[r[r0]] res[r[r0]]=temp return res # 计算种群中所有路径中的最短路径defkl_min(kl, res): all_res= [] all_dis= [] for iin range(kl): a= change_res(res) all_res.append(a) all_dis.append(sum_dis(a)) return min(all_dis), all_res[all_dis.index(min(all_dis))] # 计数(非主要)defjishu(T0, r, Ts): num= 0 T= T0 while T> Ts: num= num+ 1 T= T* r return num # 主方法defsa(res): T0= 3000 r= 0.995 Ts= 0.01 kl= 500 T= T0 temp_min= sum_dis(res) num= jishu(T0, r, Ts) num1= 0 min_list= [] while T> Ts: # 计数for iin range(100): if num1==(i+1)*int(num/100): print(str(i+1)+"%") num1= num1+ 1 #T= T* r a= kl_min(kl, res) if a[0]<= temp_min: res= a[1] temp_min= a[0] else: df= a[0]- temp_min p= math.exp(-df/ T) if random.randint(1, 100)/ 100<= p: res= a[1] temp_min= a[0] min_list.append(temp_min) return res, min_list # 迭代图表defplot(linlist): y= [] for iin range(len(linlist)): y.append(i) plt.plot(y, linlist, label='linear') plt.xlabel('x label') plt.ylabel('y label') plt.title("Simple Plot") plt.legend() plt.show() # 画图defdraw(res): turtle.setup() turtle.hideturtle() turtle.speed(10) turtle.penup() turtle.goto(res[0][0], res[0][1]) turtle.pendown() for iin range(len(res)): turtle.goto(res[i][0], res[i][1]) turtle.dot(5, "blue") turtle.goto(res[0][0], res[0][1]) turtle.mainloop() res= cre_points(30) a= sa(res) plot(a[1]) print(a[1][len(a[1])-1]) draw(a[0])


- Author:竟何
- URL:https://lylelove.top/article/%E5%9F%BA%E4%BA%8E%E6%A8%A1%E6%8B%9F%E9%80%80%E7%81%AB%E7%AE%97%E6%B3%95%E4%BD%BF%E7%94%A8Python%E6%B1%82%E8%A7%A3TSP%E9%97%AE%E9%A2%98
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts