在 TSP 问题中，哪种方法会产生更短的行程：最近邻算法还是遗传算法？

Question

这几天我注意到了一些 网络 站点 演示了使用遗传算法的 TS 解决方案。

在 TSP 问题中，哪种方法可以产生更短的行程：最近邻算法还是遗传算法？

Answer 1

由于这两种技术都不能保证最佳解决方案，因此您的里程会有所不同。如果运气好的话，这两种技术都可以胜过另一种。两种技术都有优点和缺点。

最近的邻居：+快速，+简单，-通常不是最佳的

遗传算法：- 更慢， - 更复杂， + 随着时间的推移，解决方案趋于优化

最大的区别在于随机算法，例如 模拟退火 遗传算法可能会随着时间的推移而不断改进 - 让它们运行的​​时间越长，获得最佳解决方案的机会就越大（尽管不能保证）。

由于神经网络速度很快，因此没有什么可以阻止您组合这些技术。运行 NN 以找到可能比随机起始解决方案更好的解决方案。然后，将该解决方案输入到您的遗传算法中，并让它在您认为合适的时间内运行。

如果您对最佳解决方案感兴趣，请查看 林-克尼根启发法 和 线性规划. 。两者都被用来寻找大型旅游的最佳解决方案，包括 这个解决方案 为一个 85,900 城市旅游 和一个 24,978城市瑞典之旅.

这 佐治亚理工学院 TSP 站点 是一个很好的资源。