问题标签 [traveling-salesman]

我正在构建一个遗传算法来解决旅行商问题。不幸的是，我在突变出它们并获得更好的结果之前达到了可以维持一千多代的高峰。在这种情况下，哪些交叉和变异算子通常做得很好？

我对整个旅行推销员问题以及stackoverflow都是新手，所以如果我说的一些不太正确的话，请告诉我。

介绍：

我正在尝试为涉及多个国家（地区）内的多个城市（节点）的游戏编写利润/时间优化的多交易算法，其中：

• 在两个相连的城市之间旅行的实际时间总是相同的；
• 城市不是线性连接的（你可以同时在一些城市之间传送）；
• 一些国家（地区）有传送路线，使通过其他国家的最短路径可用。
• 旅行者（或商人）对他的钱包、他的货物的重量以及在某个贸易路线上可交易的数量都有限制。贸易路线可以跨越多个城市。

问题参数：

内存中已经存在一个数据库（python：sqlite），它根据源城市和目的地城市保存交易，中间的最短路径城市作为数组和数量，以及总资本回报率的限制因素（或在没有任何因素限制的情况下，那么只有总资本回报率最高的方法）。

• 我正在尝试在某个预设的时间段（即 30 分钟）内找到最佳利润
• 穿越到一个新城市的行为实际上是同时发生的
• 穿越城市地图通常需要相同的定义时间（即 2 分钟）
• 发起第一个或任何新交易的行为与穿越一个城市地图所需的时间相同（即 2 分钟）
• 我的起点可能实际上没有有效的交易（我必须前往第一个/最近/最好的交易）

到目前为止的伪解决方案

优化

首先，我意识到因为我对所花费的时间有限制，并且我知道每一跳需要多长时间（包括启动交易的 -1），我可以将图表限制为跳数小于或等于 的所有交易max_hops=int(max_time/route_time) -1。我删除了贸易数据库中不属于这个时间限制的元素，修剪了最短路径长度大于max_hops.

我再次进入交易数据库，其中包括我当前城市和不是我当前城市的所有现有交易的起始城市之间的最短路径，并给它们 0% 的回报。我会将这些限制在城市跳数少于 的地方max_hops，并且我还将计算当前城市到起始城市加上交易最短路径跳数的城市是否会超过max_hops并删除那些超过此限制的城市。

然后我采取剩余的交易，(current_city->starting_city)并在所有目的地和起始城市之间添加回报为 0% 的贸易路线，其中啤酒花不超过max_hops

然后，我对所有不在交易数据库中的城市作为起始城市、目的地城市或最短路径城市阵列的一部分进行最后一次修剪。

图表搜索 我留下了一个在时间限制（即 30 分钟）内可行的（小得多的）交易图表。

因为所有连接的节点都是相邻的，所以默认情况下，连接的权重都是 1。我将 %return 除以交易中的跳数，然后取倒数并加上 + 1（这意味着一个权重为 1.01 100％返回路线）。在收益率为 0% 的情况下，我添加 ... 2？

然后它应该返回最有利可图的路线......

问题：

大多，

1. 当我有多余的钱或空间时，如何增加走多条路线的能力，并通过离散的路径寻找单条贸易路线的路线？由于商品在城市内以多种价格和数量销售的性质，会有很多重叠的路线。

2. 我如何惩罚启动新的贸易路线？

3. 在这种情况下，图形搜索甚至有用吗？

在旁注中，

3. 我应该（或不应该）对图表进行哪些类型的修剪/优化？
4. 我的加权方法正确吗？我有一种感觉，它会给我不成​​比例的重量。我应该使用实际回报而不是百分比回报吗？
5. 如果我在 python 中编码，那么python-graph之类的库是否适合我的需求？或者它会为我节省很多开销（据我所知，图形搜索算法可能是计算密集型的）来编写一个专门的函数？
6. 我最好使用 A* 搜索吗？
7. 我应该预先计算交易数据库中的最短路径点并最大化优化，还是应该将其全部留给图形搜索？
8. 你能注意到我可以改进的地方吗？

是否有一种算法或一组算法可以让您找到距任意起始节点的最短步行距离，以便在权重无向图中访问每个节点？它不完全是旅行推销员，因为我不在乎一个节点是否被多次访问。（即使你回到起点也没关系——只要它是访问所有节点所需的最后一个节点，walker 就可以最终到达某个遥远的节点。）它不是最小生成树，因为可能 A-->B-->C-->A-->D 是访问 A、B、C 和 D 的（非唯一）最短路径。我的直觉说这不是这不是一个 NP 问题，因为它没有使 NP 问题如此棘手的限制。当然，我可能完全错了。

有没有人在标准 ML 中有旅行商问题的解决方案，请告诉我。

我已经尝试了很多但没有成功。

我已经实施了遗传算法来解决旅行商问题（TSP）。当我只使用突变时，我会找到比添加交叉时更好的解决方案。我知道普通的交叉方法不适用于 TSP，所以我同时实现了有序交叉和PMX 交叉方法，但结果都不好。

以下是我正在使用的其他参数：

突变：单交换突变或反向子序列突变（如 Tiendil 所述），突变率测试在 1% 和 25% 之间。

选择：轮盘赌选择

健身功能：1/行程距离

人口规模：测试了 100、200、500，我也运行了 GA 5 次，这样我就有了各种起始人口。

停止条件：2500代

对于相同的 26 点数据集，我通常使用具有高突变率的纯突变得到大约 500-600 距离的结果。添加交叉时，我的结果通常在 800 距离范围内。另一个令人困惑的事情是，我还实现了一个非常简单的爬山算法来解决这个问题，当我运行 1000 次（比运行 GA 5 次更快）我得到大约 410-450 距离的结果，我希望使用 GA 获得更好的结果。

关于为什么我添加交叉时我的 GA 表现更差的任何想法？为什么它的性能比简单的爬山算法差得多，因为一旦找到局部最大值就无法探索，它应该卡在局部最大值上？

我阅读了有关此的各种资料并了解所涉及的原理和概念，但是，没有一篇论文提到如何计算涉及不直接连接的相邻城市（在染色体中）的染色体（代表一条路线）的适应度的细节由一条边（在图中）。

例如，给定一条染色体 1|3|2|8|4|5|6|7，其中每个基因代表一个城市在图/地图上的索引，我们如何计算它的适应度（即总和行进的距离）如果，比如说，城市 2 和 8 之间没有直接的边缘/链接。我们是否遵循某种贪心算法来计算出 2 和 8 之间的路线，并将这条路线的距离加到总距离中？

在将 GA 应用于 TSP 时，这个问题似乎很常见。有做过的朋友请分享一下经验。谢谢。

我阅读了几篇关于如何使用遗传算法和蚁群优化等解决 TSP 的文章和示例代码。但我发现的所有内容都不包括时间（窗口）约束，例如。“我必须在上午 12 点之前到达客户 x）”并假设对称。

有人可以向我指出一些示例代码或文章的方向，这些示例代码或文章解释了如何向 TSP 添加约束以及如何在代码中表示这些约束。

谢谢！

我对两个单词列表的函数感兴趣，它将返回它们之间的顺序不可知的编辑距离。

也就是说，参数将是两个（假设用空格分隔）单词列表，返回值将是列表中单词的编辑（或 Levenshtein）距离的最小总和。

"cat rat bat"和之间的距离"rat bat cat"为0。和之间的距离与和"cat rat bat"之间"fat had bad"的距离相同，4。如果列表中的单词数不相同，则较短的列表将用长度为0的单词填充。"rat bat cat""had fat bad"

我的直觉（没有通过计算机科学课程培养）除了使用蛮力之外没有找到任何其他解决方案：

从第一行开始，选择一列并转到下一行，而无需重新访问您已经访问过的列。一遍又一遍地这样做，直到你尝试了所有的组合。

对我来说，这听起来有点像旅行商问题。是吗，您将如何解决我的特定问题？

假设您有一个像这样的网格（随机制作）：

现在假设您有一辆汽车随机从其中一个白框出发，通过每个白框的最短路径是什么？您可以根据需要多次访问每个白框，并且不能跳过黑框。黑匣子就像墙壁。简而言之，您只能从白盒移动到白盒。

你可以向任何方向移动，甚至是对角线。

两个子问题：

1. 假设您在移动之前知道所有黑盒的位置。
2. 假设您只有在与黑盒相邻的白盒中时才知道黑盒的位置。

有人可以给我一个用于旅行商问题的 2-opt 算法的代码示例。现在我使用最近邻来查找路径，但这种方法远非完美，经过一些研究，我发现 2-opt 算法可以将该路径校正到可接受的水平。我找到了一些示例应用程序，但没有源代码。