遺傳算法尋路 - 交叉和變異

Question

我想使用遺傳算法尋找無向圖內的最短路徑。關於交叉和突變，我有兩個問題。我一直在研究如何在類似的情況下進行交叉操作，最流行的算法似乎是PMX，我對此的理解是在2條父代染色體之間交換部分路徑以形成後代。我遇到的問題是，幾乎所有的後代都變得無效了，這種情況有很大的空間嗎？我想知道如果你能爲我確認這一點，如果我錯了，請糾正我並解釋它。

單獨但相關的說明;我對如何做到這一點有了一個想法，但我不知道它是否是一個好主意，只需選擇2個父母，他們在他們的路徑中共享相同的節點並交叉，那麼所有的後代仍然有效。

我的第二個問題是突變;我對如何做到這一點有一個總體的想法;選擇一個節點並刪除它，並通過替代方法重新鏈接路徑是明智的嗎？

謝謝:)！

Answer 1

首先你要研究交叉和變異，因爲你說你可能會損失一些有效的父母，但它遺傳算法中的「精英」概念。你應該通過你提出的交叉方法來克服。因爲在交叉本身，我們有n方法做，我建議你做第二次變化交叉秩序。這不是墨菲定律，所以你會努力實現。