ruby - 需要帮助以适应遗传算法以“解决”Ruby 上的旅行推销员

Question

我刚刚下载了 ai4r 库http://ai4r.rubyforge.org/我正在使用遗传算法从多个地方获得一条好的路线，就像这样：

http://ai4r.rubyforge.org/geneticAlgorithms.html

但我需要能够设置一个起始城市。

关于如何在“固定”起始城市上使用它的任何线索？

Answer 1

一般来说，不查看特定于 Ruby 的实现，您可以只删除起始城市，并假设后面的第一条边是从您的起始城市到 GA 生成的任何内容。只需确保第一条边包含在成本/适应度函数中。

Answer 2

旅行商问题的解决方案是往返，因此与起始城市无关。找到解决方案后，您可以将往返的任何城市作为您的起始城市。

编辑：如果您不需要返回起始城市，您可以通过删除离开起始城市的两个距离中较大的一个来选择结束城市。如果您在最终解决方案中删除整个往返行程中的最大距离，您将获得非往返行程的总体最短行程。这可能是他们在您链接的网页上所做的（都柏林 - 莫斯科看起来是最昂贵的方向）。但是，请注意，该页面的作者使用了错误的维也纳位置，马德里似乎也关闭了。

需要起始城市的另一种方式是当您有额外的时间窗口限制时。此约束指定对于您需要在特定时间到达的每个城市，在这种情况下称为您的起始城市的“车站”具有涵盖整个行程的时间窗口。然而，TSPtw 是一个复杂得多的问题，通常需要高级遗传算子。如果您只使用一辆车，您还可以将 TSPtw 建模为 CVRPtw（带时间窗的容量车辆路线问题）。您可以在HeuristicLab中尝试我们的 VRP 实现来解决这个问题。如果您需要进一步的支持，我们有一个邮件列表。

Answer 3

你从 GA 到 TSP 得到的答案是一个循环，这意味着第一个城市就是你想要的。例如，如果答案是[3 4 2 6 1 5]，并且我希望第一个城市是 2，那么我可以将解决方案“滚动”到[2 6 1 5 3 4]。

虽然，如果在评估函数中指定第一个城市，您可以将问题减少 1。在这种情况下，您必须考虑到必须修改个人以考虑到这一点。例如，如果您将第一个城市设置为 #2（6 个城市的问题），并且您有一个人是[1 2 3 4 5]（6 个城市减一个）。要评估的个人是[2 1 3 4 5 6]。