模拟退火算法求解TSP问题(python)

👉TSP旅行商问题

旅行商问题大家都应该非常熟悉了，解法也很多，比如贪婪算法、Dijkstra算法等等，本文参考《MATLAB智能算法30个案例分析（第2版）》中第19章的内容，利用模拟退火算法求解TSP问题并给出了python实现版本
TSP问题描述如下：

👉TSP模拟退火算法

关于模拟退火算法的原理，书籍和文章均比较多，这里就不再赘述，大家可以参考其他博文，或阅读《MATLAB智能算法30个案例分析（第2版）》这本书。

👉程序及运行结果（笔者python环境为3.7）

import copy
import math
import random
import matplotlib.pyplot as plt

# 初始温度
T0 =1000# 终止温度
Tend =1e-3# 个温度下的迭代次数（链长）
L =200# 降温速率
q =0.9# 各个城市的坐标
X =[(16.4700,96.1000),(16.4700,94.4400),(20.0900,92.5400),(22.3900,93.3700),(25.2300,97.2400),(22.0000,96.0500),(20.4700,97.0200),(17.2000,96.2900),(16.3000,97.3800),(14.0500,98.1200),(16.5300,97.3800),(21.5200,95.5900),(19.4100,97.1300),(20.0900,92.5500)]# 构建距离矩阵defbuild_distance():# 初始化城市距离矩阵
    distance =[[0for _ inrange(len(X))]for _ inrange(len(X))]# 计算各个城市之间的距离for i inrange(len(X)):
        pos1 = X[i]for j inrange(i+1,len(X)):
            pos2 = X[j]
            distance[i][j]=pow((pow(pos1[0]- pos2[0],2)+pow(pos1[1]- pos2[1],2)),0.5)
            distance[j][i]= distance[i][j]return distance

# 产生新的路径解defgen_new_path(path):
    new_path = copy.copy(path)# 随机产生两个索引
    idx1 = random.randint(0,len(path)-1)
    idx2 = random.randint(0,len(path)-1)# 交换路径中的两个城市
    temp = new_path[idx1]
    new_path[idx1]= new_path[idx2]
    new_path[idx2]= temp
    return new_path

# 计算路径总距离defpath_distance(path, distance):
    total_distance =0.0# 循环路径上所有城市进行计算，到最后一个城市返回出发城市for i inrange(len(path)):if i ==len(path)-1:
            total_distance += distance[path[i]][path[0]]else:
            total_distance += distance[path[i]][path[i +1]]return total_distance

# Metropolis准则函数defmetropolis(old_path, new_path, distance, t):# 路径的能量即路径上各城市距离之和# 新路径的能量函数和旧路径的能量函数之差
    delta = path_distance(new_path, distance)- path_distance(old_path, distance)# 若新路径能量低于旧路径，则接受新路径解if delta <0:return copy.copy(new_path), path_distance(new_path, distance)# 若新路径能量高于旧路径，则按exp(-delta/t)概率接受新路径解if math.exp(-delta/t)>= random.uniform(0,1):return copy.copy(new_path), path_distance(new_path, distance)# 不接受新路径解return copy.copy(old_path), path_distance(old_path, distance)# 绘制结果defdraw_result(best, file_name="tsp_sa"):# 各个城市的横纵坐标
    x =[pos[0]for pos in X]
    y =[pos[1]for pos in X]# 绘图中文设置
    plt.rcParams['font.sans-serif']=['SimHei']# 显示中文标签
    plt.rcParams['axes.unicode_minus']=False# 清空画布
    plt.clf()# 绘制箭头for i inrange(len(X)):# 箭头开始坐标
        start = X[best[i]]# 箭头结束坐标
        end = X[best[i +1]]if i <len(best)-1else X[best[0]]
        plt.arrow(start[0], start[1], end[0]- start[0], end[1]- start[1], head_width=0.2, lw=1, length_includes_head=True)# 绘制城市编号for i inrange(len(X)):
        plt.text(x[best[i]], y[best[i]],"{}".format((best[i]+1)), size=15, color="r")
    plt.xlabel(u"横坐标")
    plt.ylabel(u"纵坐标")
    plt.savefig(file_name +".png", dpi=800)# 绘制进化过程defdraw_evolution(evolution):
    x =[i for i inrange(len(evolution))]# 清空画布
    plt.clf()
    plt.plot(x, evolution)
    plt.savefig('tsp_sa_evolution.png', dpi=800)# 模拟退火算法defsimulated_annealing():# 城市距离矩阵
    distance = build_distance()# 城市个数
    city_cnt =len(distance)# 初始化城市路径，这里可以随机生成，也可以跟书中的初始路径保持一致# path = random.sample(range(0, city_cnt), city_cnt)
    path =[10,13,2,8,5,3,12,6,7,0,11,4,1,9]# 绘制初始路径
    draw_result(path,"init_path")# 初始路线长度
    total_distance = path_distance(path, distance)print("初始路线：",[p +1for p in path])print("初始总距离：", total_distance)# 温度
    t = T0
    # 进化过程，每一次迭代的路径总距离
    evolution =[]# 循环直到冷却后停止while t > Tend:for _ inrange(L):# 产生新路径
            new_path = gen_new_path(path)# 更新最佳路径及对应的距离
            path, total_distance = metropolis(path, new_path, distance, t)# 更新进化过程
            evolution.append(total_distance)# 降温
        t = t * q
    # 打印退火后信息print("结束温度为：", t)print("最佳路线：",[p +1for p in path])print("最佳距离：", total_distance)# 绘制最佳路径
    draw_result(path,"tsp_sa_best")# 绘制进化过程
    draw_evolution(evolution)if __name__ =="__main__":
    simulated_annealing()

程序打印信息如下：

初始路线： [11, 14, 3, 9, 6, 4, 13, 7, 8, 1, 12, 5, 2, 10]
初始总距离： 56.0122140089359
结束温度为： 0.0009120344560464498
最佳路线： [14, 2, 1, 10, 9, 11, 8, 13, 7, 12, 6, 5, 4, 3]
最佳距离： 29.340520066994227

运行结果下图所示：

路径总距离随着迭代的进行逐步稳定，如下图所示：

笔者水平有限，若有不对的地方欢迎评论指正