基于模拟退火算法使用Python求解TSP问题

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

Tags: Python笔记