如何处理顺序很重要的交叉？

Question

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

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

我已阅读关于置换交叉，但我不完全确定如何解决这个问题。有人能指引我正确的方向或建议吗？

Answer 1

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

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

现在，这并不能保证候选人在交叉之后将是可行的解决方案。为了确保您的解决方案仍然可行，您应该调整交叉点。例如，对于该TSP，考虑序列：

1：A B C d Ë F G H

2：d éģC B F H

选择随机的枢轴（ê在我们的例子）。这导致完成以下序列：

1'：A B C D E。 。 。

2'：A D E。 。 。 。 。

为了有一个有效的解决方案，必须访问所有的顶点。在1'中，F，G和H必须被访问。我们为了它们，因为它们在序列2中2' ，G，C，B，F和H是重新排序，如1：

1' ：ABCD È GFH

2' ： AD E BCFGH

希望这会有所帮助。