随机模拟了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])


Comments