哪种方法可以在 TSP 问题中产生更短的路径：最近邻算法还是遗传算法？
Over the last few days I have noted a few web sites that demonstrated TS solution using genetic algorithms.
Which is approach produces the shorter tour in the TSP problem: nearest neighbour or genetic algorithms?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于这两种技术都不能保证最佳解决方案，因此您的里程会有所不同。 如果运气好的话，这两种技术都可以胜过另一种。 两种技术都有优点和缺点。
最近邻：+快速、+简单、-通常不是最优的
遗传算法：-较慢、-更复杂、+随着时间的推移，解决方案趋于最优
最大的区别在于像 模拟退火 和遗传算法可能会随着时间的推移而不断改进 - 让它们运行的时间越长，效果就越明显您有机会获得最佳解决方案（尽管不能保证）。
由于神经网络速度很快，因此没有什么可以阻止您组合这些技术。 运行 NN 来找到可能比随机更好的起始解决方案。 然后，将该解决方案输入到您的遗传算法中，并让它在您认为合适的时间内运行。
如果您对最佳解决方案感兴趣，请查看 Lin-Kernighan 启发式 和线性规划。 两者都用于寻找大型旅游的最佳解决方案，包括此解决方案 85,900 城市游览 和 24,978 个城市瑞典之旅。
佐治亚理工学院 TSP 网站是一个很好的资源。
Since neither technique guarantees an optimal solution, your mileage will vary. With a little luck, either technique can out-perform the other. Both techniques have pros and cons.
Nearest neighbor: +fast, +simple, -usually not optimal
Genetic algorithm: -slower, -more complex, +solutions trend toward optimal over time
The big difference is that randomized algorithms like simulated annealing and genetic algorithms may continue to improve over time - the longer you let them run, the more chances you have for an optimal solution(though there are no guarantees).
Since NN is fast, there's nothing stopping you from combining the techniques. Run NN to find a possibly-better-than-random starting solution. Then, feed that solution into your genetic algorithm and let it run as long as you feel is appropriate.
If you're interested in optimal solutions, check out the Lin-Kernighan heuristic and Linear Programming. Both were used to find optimal solutions for large tours including this solution for a 85,900 city tour and a 24,978 city Sweden tour.
The Georgia Tech TSP site is a great resource.