需要帮助来调整遗传算法来“解决”问题红宝石上的旅行推销员
我刚刚下载了 ai4r 库 http://ai4r.rubyforge.org/ 并且我正在使用遗传算法来获取来自多个地方的好路线，就像这样：
http://ai4r.rubyforge.org/genicAlgorithms.html
但我需要能够设置一个起始城市。
关于如何在“固定”起始城市上使用它的任何线索？
I just downloaded ai4r library http://ai4r.rubyforge.org/ and i am using the genetic algorithm to get a good route from multiple places, just like this:
http://ai4r.rubyforge.org/geneticAlgorithms.html
But i need to be able to set a start city.
Any clue on how to use this on a "fixed" start city?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一般来说，不考虑 Ruby 特定的实现，您可以只删除起始城市，并假设后面的第一条边是从您的起始城市到 GA 生成的任何内容。只需确保第一条边包含在成本/适应度函数中即可。
In general, not looking at the Ruby-specific implementation, you can just remove the start city, and assume that the first edge followed is from your start city to whatever the GA produces. Just make sure that first edge is included in the cost/fitness function.
旅行推销员问题的解决方案是往返，因此与出发城市无关。找到解决方案后，您可以选择往返中的任何城市作为起始城市。
编辑：如果您不需要返回起始城市，您可以通过删除离开起始城市的两个距离中较大的一个来选择结束城市。如果您在最终解决方案中删除整个往返中的最大距离，您将获得非往返的整体最短旅行。这可能就是他们在您链接的网页上所做的（都柏林 - 莫斯科看起来是最昂贵的方向）。然而，请注意，该页面的作者使用了错误的维也纳位置，而马德里似乎也有问题。
当您需要起始城市的另一种方式是当您有额外的时间窗口限制时。此约束指定对于您需要在特定时间到达的每个城市，在这种情况下称为您的起始城市的“站点”有一个涵盖整个行程的时间窗口。然而，TSPtw 是一个复杂得多的问题，通常需要高级遗传算子。如果您仅使用一辆车，您还可以将 TSPtw 建模为 CVRPtw（带时间窗的容量车辆路径问题）。您可以尝试 HeuristicLab 中的 VRP 实现来解决此问题。如果您需要进一步的支持，我们有一个邮件列表。
The solution of a traveling salesmen problem is a round-trip and is therefor independent of a start-city. After you have found your solution you can take any city of the round-trip as your start-city.
EDIT: If you do not need to return to your start-city, you can select the end city, by removing the larger of the two distances that leave your start city. If you remove in your final solution the largest distance in the whole round-trip you get the overall shortest tour that is not a round-trip. This is likely what they did on the web page you linked (Dublin - Moscow looks to be the most expensive direction). However, note that the authors of that page used a wrong location for Vienna and Madrid seems to be off as well.
Another way of when you'll be needing a start-city is when you have an additional time window constraint. This constraint specifies that for each city you need to be there at a certain time, the "depot" as your start-city is called in this case has a time window that covers the whole trip. However the TSPtw is a much more complex problem and often requires advanced genetic operators. You can also model the TSPtw as a CVRPtw (Capacitated Vehicle Routing Problem with Time Windows) if you use just one vehicle. You can try our VRP implementation in HeuristicLab to solve this problem. We have a mailing list if you require further support.
您从 GA 到 TSP 得到的答案是一个循环，这意味着第一个城市就是您想要的城市。例如，如果答案是
[3 4 2 6 1 5]，并且我希望第一个城市是 2，那么我可以将解决方案“滚动”到[2 6 1 5 3 4]。不过，如果在评估函数中指定第一个城市，则可以将问题减少 1。在这种情况下，您必须考虑到必须修改个人才能解决此问题。例如，如果您将第一个城市设置为 #2（6 个城市的问题），并且您有一个个体为
[1 2 3 4 5]（6 个城市减 1）。要评估的个体是[2 1 3 4 5 6]。The answer you'll get from the GA to the TSP is a cycle, that means that the first city is the on that you desire. For example, if the answer is
[3 4 2 6 1 5], and I want the first city to be 2 then I can "roll" the solution to[2 6 1 5 3 4].Although, you can reduce your problem by 1 if in your evaluation function you specify the first city. In that case you must take into account that the individuals must be modified to account this. For example, if you set the first city to #2 (problem of 6 cities) and you have an individual that is
[1 2 3 4 5](6 cities minus one). The individual to evaluate is[2 1 3 4 5 6].