当序列很重要时，如何处理交叉问题？

Question

当序列很重要时，如何处理交叉问题？

8

如何在必须保持特定排序的情况下跨越两个父代？

例如，在对固定图形的旅行商问题应用遗传算法时，必须考虑到并非所有顶点都可以移动到其他顶点。这使得交叉变异更加困难，因为与TSP不同，其中所有顶点都可以移动到所有其他顶点，当执行交叉变异时，必须在产生合法路径的点上进行。另一种选择是无论如何交叉变异并拒绝非法路径，但风险是计算成本高昂，几乎没有合法路径。

我已经阅读了排列交叉变异的相关内容，但我不确定它如何解决这个问题。有人能指点我正确的方向或提供建议吗？

- user2341412

在达尔文的进化理论中，如果一个新生物不被认可会发生什么？自然界如何处理这种情况？ - San Jacinto

4

它被拒绝了，但达尔文进化论不必担心计算的指数增长。 - user2341412

不确定为什么有那么多关闭投票，这是一个完全有效的（且与主题相关）问题。 - BlueRaja - Danny Pflughoeft

同一个问题，不同的表述：置换的交叉运算符，已经有人之前进行了回答：你所寻找的是有序交叉。 - CmdNtrf

顺便提一下，您从未验证过任何问题的答案。您可以考虑阅读关于页面，以了解如何在网站上行为。 - JonasVautherin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David · Accepted Answer

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

与其意思是“从A到B取边”，不如考虑“从A到B取最短路径”。这样，您的解决方案始终是可行的。您只需预处理一个最短路径矩阵即可。

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

1：ABCDEFGH

2：ADEGCBFH

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

1'：ABCDE...

2'：ADE.....

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

1'：ABCDEGFH

2'：ADEBCFGH

希望这能有所帮助。