artificial-intelligence - 哪种方法在 TSP 问题中产生更短的旅行：最近邻或遗传算法？

Question

在过去的几天里，我注意到一些网站展示 了使用遗传算法的 TS 解决方案。

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

Answer 1

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

最近的邻居：+fast，+simple，-通常不是最优的

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

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

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

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

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