使用模拟退火算法求解TSP问题（python实现）

案例和代码参考的是：华中科技大学创新团队WESharp新生培训系列讲座，主讲人：周航

模拟退火（Simulated annealing）是一种通用概率算法，用来在一定时间内寻找在一个很大搜寻空间内的近似最优解。

简介

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。

模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

可以证明，模拟退火算法所得解依概率收敛到全局最优解。 退火算法-中文维基百科

演算步骤

初始化 由一个产生函数从当前解产生一个位于解空间的新解，并定义一个足够大的数值作为初始温度。

迭代过程 迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：

1、由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

2、计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 3、判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′= 0:#当差>0时，以一定概率接受新解 rand = random.uniform(0,1) if rand T_end: for i in range(L): newans = creat_new(ans0) old_dist = totaldistance(ans0) new_dist = totaldistance(newans) df = new_dist - old_dist if df >= 0: rand = random.uniform(0,1) if rand