type
Post
status
Published
date
Feb 24, 2022
slug
基于模拟退火算法使用Python求解TSP问题
summary
基于模拟退火算法使用Python求解TSP问题
tags
算法
路径问题
物流
category
Python
icon
password
Property
Jul 18, 2022 03:23 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])
路径图
路径图
迭代
迭代
 
以哔哩哔哩专栏为后端进行Github Action自动部署的Hexo博客爬取哔哩哔哩历史——基于selenium-pyecharts库

  • Waline
  • Giscus