遗传算法寻路 - 交叉和变异

Question

我想使用遗传算法寻找无向图内的最短路径。关于交叉和突变，我有两个问题。我一直在研究如何在类似的情况下进行交叉操作，最流行的算法似乎是PMX，我对此的理解是在2条父代染色体之间交换部分路径以形成后代。我遇到的问题是，几乎所有的后代都变得无效了，这种情况有很大的空间吗？我想知道如果你能为我确认这一点，如果我错了，请纠正我并解释它。

单独但相关的说明;我对如何做到这一点有了一个想法，但我不知道它是否是一个好主意，只需选择2个父母，他们在他们的路径中共享相同的节点并交叉，那么所有的后代仍然有效。

我的第二个问题是突变;我对如何做到这一点有一个总体的想法;选择一个节点并删除它，并通过替代方法重新链接路径是明智的吗？

谢谢:)！

Answer 1

首先你要研究交叉和变异，因为你说你可能会损失一些有效的父母，但它遗传算法中的“精英”概念。你应该通过你提出的交叉方法来克服。因为在交叉本身，我们有n方法做，我建议你做第二次变化交叉秩序。这不是墨菲定律，所以你会努力实现。