python3 SA模拟退火算法解决100个城市的TSP问题

python3 SA模拟退火算法解决100个城市的TSP问题

由于内容是从自己写的报告(word文件)中复制而来，因此排版可能有问题，建议直接看github中的报告pdf

地址：

摘要：该项目主要是利用局部搜索算法（LS）和模拟退火算法（SA）解决TSP问题。先是使用LS求解TSP问题，再尝试SA问题，比较两者，在效率上SA更占有。最后再在LS的基础上使用SA，再优化SA部分算法，尝试求解TSP问题。选用的TSP测例为eil101（有101个城市）。代码使用python语言编写，因此运算速度因为语言特性比编程语言要低。

1．导言

旅行商问题，即TSP问题（Traveling Salesman Problem），是求最短路径的问题，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。TSP是组合优化问题，可以被证明具有NPC计算复杂性。如果希望暴力搜索其最佳解，其复杂度将是O(n!)，其计算量随着n的增加将轻易超过目前计算机的可能算力。因此我们需要用更智能的方法求解。

于是我们先考虑局部搜索算法。局部搜索算法是贪心算法，他往往往邻域中最好的状态搜索，因此容易进入局部最优结果，而无法跳出局部最优的区域。

第二部分使用模拟退火算法。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法比起局部搜索算法，赋予了一定跳出局部最优解的能力，但能否跳出局部最优解依然依赖随机性。

2．实验过程

       首先使用两种不同的局部搜索算法。

       第一种选择邻域的方法是随机交换两个城市在序列中的顺序。每次循环中产生的候选序列为城市数（以下用Cs表示）*10，并从中选择一个最优的（距离最短的）作为下一步。

       第二种选择邻域的方法是随机交换三个城市在序列中的顺序。每次循环中产生的候选序列为Cs*10，并从中选择一个最优的（距离最短的）作为下一步。

       这两种算法都按以下步骤实现：

1. 录入初始状态，并打乱顺序产生一组随机状态，从这组状态（包括初始状态）中选最佳的状态作为起点；
2. Repeat:
   1. 产生一个集合S
   2. Repeat 10 * Cs times:
      1. 将当前状态加入S
      2. 产生2个（或3个）互不相同的、范围为[1, 城市数-1]的随机数
      3. 以这2个（或3个）随机数作为下标交换城市在序列中的顺序
      4. 将交换后的序列加入S中
   3. 从S中选择一个最优的序列，作为当前状态
   4. 如果当前状态与之前状态一样，则跳出循环。

可以知道，当当前状态与邻域中最佳状态一样时跳出循环，可以理解成到达局部最优解。虽然实际上这个邻域并没有完全覆盖当前状态的所有邻居，但覆盖全部邻居需要(Cs-1) * (Cs-2)（第二种邻域为(Cs-1) * (Cs-2) * (Cs-3)）个数据，将加大每次循环的耗时，而且最终结果同样是会进入局部最优结果而无法跳出。

第二部分在LS的基础上加入SA。

一开始我的SA流程如下：

1. 得到初始状态，设定初温T，降温方式，结束条件
2. 外循环：
   1. 当符合结束条件则跳出循环
   2. 内循环：
      1. 令当前解能量为D0
      2. 通过邻域搜索策略得到一组解并取其中最优（不包括当前状态）解能量为D1
      3. 令ΔE = D1–D0
         1. If ΔE <= 0: 则使P = 1

Else: 使P为e-∆E/T