模拟退火算法 python实现旅行家问题

喜欢ヅ旅行 2022-02-22 16:08 267阅读 0赞

参考链接：

# [模拟退火算法解决TSP问题][TSP] #

# [RE：从0开始的模拟退火算法(python实现）][RE_0_python] #

# [模拟退火算法总结][Link 1] #

详细的步骤在上面的参考文章都详细说明了。总的来说，模拟退火算法就是两层迭代，最外层迭代是模拟退火的过程，也就是温度降低的过程，每迭代一次，温度就会降低一次，起始温度越高，终止温度越低，最终的结果会更好。里面迭代是寻求新解的过程，这层迭代可有可无，但是多了这层迭代就可以多次尝试跳出局部最优解。

寻求新解的过程里，总的来说就是“产生新解—判断—接受/舍弃“，

**产生新解**：根据不同的问题有不同的产生新解问题，这也是为什么很多问题可以用到模拟退火的原因。

**判断**：新解是否比旧解好，如果好，那肯定直接采纳了。不好的话，就要根据概率来看了。

**接受/舍弃**：这里就是根据概率来决定是否接纳更坏的解。接受准则：

![è¿éåå¾çæè¿°][70]![è¿éåå¾çæè¿°][70 1]

**这里注意si'是新解，而si是旧解，顺序不要搞错，否则结果是错误的。**

# **模拟退火的超参数：** #

模型是否能够产生好的结果，最终还是要调参的。

起始温度：30000

终止温度：1e-8

冷却率：0.98

**代码**：

[github地址][github]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzNDE4MDQz_size_16_color_FFFFFF_t_70][]

可以看到结果虽然震荡很厉害，但是总体趋势是下降的

[TSP]: https://blog.csdn.net/qq_34062105/article/details/80468038
[RE_0_python]: https://zhuanlan.zhihu.com/p/37545825
[Link 1]: https://blog.csdn.net/weixin_42528077/article/details/82708978
[70]: https://img-blog.csdn.net/20180527112838203?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MDYyMTA1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: /images/20220222/3d48c4798fea4153a1d61ef4ecab4aa6.png
[github]: https://github.com/jiangliangzhong/Simulated-annealing-Traveler-
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzNDE4MDQz_size_16_color_FFFFFF_t_70]: /images/20220222/87a52ce2475f4448a41378be9fe60874.png