序列重要时如何处理交叉？

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'： AD E。。。。。

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

1'：ABCD E GFH

2'：AD E BCFGH

希望这可以帮助。