模拟退火TSP问题

2024-08-31 06:18

文章标签 问题模拟退火 tsp

本文主要是介绍模拟退火TSP问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模拟退火算法在求解最优值问题上有很大的优势，前面一篇博文介绍了用模拟退火算法实现求函数的最大、最小值问题。本文主要介绍如何用python实现模拟退火在TSP（旅行商）问题中的应用，源代码请移步pySA。网络上有不少文章介绍模拟退火TSP应用，可以对比着看。我们对实现的算法进行了测试，动态可视化更加形象。

1. TSP 问题描述

这个问题实际上就是求解最小路劲的问题，不过目前pySA实现还不是真正意义上的TSP，TSP问题中要求固定起点，pySA实现的是任意给定数目的地点，地点位置的生成也是随意的，然后模拟退火找到一条最短路劲。实际上要实现TSP也容易，固定起始点即可。

随机生成n个城市的二维位置点
设置初始尝试解，即城市的路劲顺序，以列表[0, 1, 2, …., n]表示顺序，当然这里设置解空间长度chain_length，生成chain_length个随机路劲顺序列表。
产生新解，对尝试解进行更新：常见的是对列表选任意两个值进行交换；还有就是任意选取两个值，在这两个值之间的列表元素进行逆序排序。pySA同时采用上面两种方法进行更新。
模拟退火过程，把最新的最短路劲结果更新为初始尝试解，重复退火。
判断是否结束，最短路劲稳定迭代次数超过50次，结束模拟退火，得到最佳结果。