干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题
旅行商问题TSP
问题描述
有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路以保证其旅行的费用最少？
说明
TSP是经典的NP完全问题。
精确的解决TSP的算法的时间复杂度是O(2^N), 其中N是节点的个数 。
模拟退火算法
模拟退火算法是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解，来源于固体退火原理
模拟退火： 其原理和固体退火的原理近似。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。
算法思想
在搜索过程引入了随机因素，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。
由初始解 i 和控制参数初值 t 开始，对当前解重复“产生新解→计算目标函数差→接受或丢弃”的迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解。
- 若f(Y(i+1))≤ f(Y(i))(即移动后得到更优解)，则总是接受该移动。
- 若 f(Y(i+1)) > f(Y(i)) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。
概率P=e(-△E/T)=e(-(f(s')-f(s))/T)
伪代码
SA伪代码
使用模拟退火算法解决旅行商问题
使用模拟退火算法可以快速地获得一条TSP近似最优路径，思路如下：
- 产生一条新的遍历路径P(i+1)，计算P(i+1)的长度L(P(i+1))
- 若L(P(i+1)) < L(P(i))，则接受P(i+1)为新的路径，否则以模拟退火的概率接受P(i+1) ，然后降温
- 重复步骤1，2直到满足退出条件
