遺傳算法。一個種羣含有染色體，不會執行條件。我應該怎麼做？

Question

我正在使用遺傳算法研究旅行商問題解決方案。有些染色體含有最短的方式，但它們仍然不合適。

例如，推銷員必須在下午6點到達A市，但使用染色體的解決方案，他會在晚上7點到達那裏。因此，這種解決方案是不正確的。

這個問題該怎麼辦？
首先，我可以改變這些染色體。但我該怎麼做呢？
其次，我可以保留它們。我應該如何做選擇呢？
第三，我可以替換它們，但我不知道應該用什麼來代替。

您能否幫我推薦一些有用的信息？

英語不是我的母語，所以對不起，如果我說錯了什麼。

Answer 1

在我看來，使攜帶這些染色體的樣本最簡單的解決方案是不復存在的。

這意味着，在遺傳算法的每次迭代中，攜帶染色體的可能解決方案「死亡」。這將確保攜帶這種染色體的人羣將保持非常小，並且將不能爲下一代「複製」，並且不會成爲問題 - 因爲具有該染色體的樣本不能在羣體中占主導地位。

Answer 2

如果沒有必要，不要殺死染色體。 只有當種羣變得過大時才殺死染色體。 只需使用交叉和變異算子，也許與精英抽樣策略。

PS： 你讀過關於遺傳算法的Zbigniew Michalewicz嗎？ 我很確定它包含一個銷售員問題示例

Answer 3

您正在處理約束問題。使用GAs來解決這些問題可能會非常棘手，但通常有四種方法可以處理約束條件：

1. 使用這樣的表示法可以使解決方案始終有效。
2. 請勿使用任何約束保留表示法，但要引入一些修正運算符，它可以使無效的解法生效。
3. 處罰（或殺死）無效的解決方案。
4. 使用多目標算法（例如NSGA-II，我最喜歡的算法）並將約束條件轉化爲目標。

最後一個選項是非常有效的，但你必須要能夠測量多少是違反了約束。如果這是可能的，在我看來，這是你的情況 - 你可以總結訪問的期望和實際時間之間的差異，然後這種違反約束的措施只是另一個目標，你優化了原始目標，新的（s）在同一時間。這種方法使算法能夠在所有個體中利用有用的信息，即使它們是無效的。