algorithm - 当顺序很重要时如何处理交叉？

Question

当孩子必须有特定的顺序时，如何跨越两个父母？

例如，当将遗传算法应用于顶点/边的固定图上的旅行推销员问题时，您必须应对并非所有顶点都可以传播到其他顶点的事实。这使得交叉变得更加困难，因为与所有顶点都可能到达所有其他顶点的 TSP 不同，当执行交叉时，它必须在产生合法路径的点上完成。另一种选择是无论如何都交叉并拒绝非法路径，但风险是巨大的计算成本和很少甚至没有合法路径。

我读过关于排列交叉的文章，但我不完全确定这如何解决这个问题。有人可以指出我正确的方向或建议吗？

Answer 1

排序应该尽可能地不成为遗传编程的约束。也许您应该考虑为您的解决方案选择另一种格式。例如，在您的 TSP 中，考虑密码子 A->B。

您可以考虑“采用从 A 到 B 的最短路径”，而不是“从 A 到 B 的边缘”。这样，您的解决方案总是可行的。您只需预先计算一个最短路径矩阵作为预处理。

现在，这并不能保证候选人在您的交叉后将成为可行的解决方案。您的分频器应进行调整，以确保您的解决方案仍然可行。例如，对于 TSP，请考虑以下序列：

1：ABCD E FGH

2 : AD E GCBFH

随机选择一个枢轴（在我们的示例中为E）。这将导致完成以下序列：

1' ：ABCD E。. .

2'：广告E。. . . .

必须访问所有顶点才能获得有效的解决方案。在 1' 中，必须访问 F、G 和 H。我们按照顺序 2 对它们进行排序。在 2' 中，G、C、B、F 和 H 重新排序为 1：

1' : ABCD E GFH

2' : AD E BCFGH

希望这可以帮助。