旅行銷售人員 - 演化算法

Question

我瞭解演化算法是如何工作的。我寫了一個在n維空間中找到方程的最大值。

我可以看到使用相同設計解決TSM問題的問題。 當我使用交叉，甚至是變異時，我可能會創建一個人去兩次同一個城市，或者不訪問每個城市。

我可以採取哪些措施來確保我的人口中的每個人只訪問一次每個城市？也就是說，每個人都是有效的答案。

Answer 1

您不能使用相同的設計模式來查找方程的最大值並將其應用於TSP問題。原因在於染色體編碼/解碼在兩個問題上是不同的。 對於數值方程問題，根據您的問題類型，染色體大多可以解碼爲「實際值」/「二進制值」。但是，對於TSP問題，我們必須使用「置換」編碼。這種排列編碼主要用於「組合優化」（https://en.wikipedia.org/wiki/Combinatorial_optimization）

下面是在編碼技術在GA相當不錯的參考網站： http://www.obitko.com/tutorials/genetic-algorithms/encoding.php

這背後的想法「排列編碼/解碼」是：給定n城市的列表，記爲c1，c2，...，cn;染色體將被編碼爲旅行推銷員已經一個一個地旅行的這些城市的順序（例如染色體= c1，c2，...，cn）。通過在這條染色體上應用置換，您可以爲羣體生成不同的染色體，GA運算符將從這裏開始。像這樣編碼染色體可以幫助您避免一個城市不止一次被訪問的問題！

由於您沒有提及任何數據結構或首選編程語言，因此我無法在此處發佈源代碼。如果你仍然想要一些工作版本的例子，你可以通過電子郵件與我聯繫。

Answer 2

解決此問題的常用技術是施加「懲罰」，其中任何具有未訪問城市的染色體都會增加罰分。例如，如果一條染色體有五個城市沒有訪問過，則將5倍懲罰加入到染色體健康分數中。在這種情況下，任何尚未訪問過城市的染色體逐漸從人口中移除，並允許其他人（沒有訪問過的城市中沒有零的個人）在人口中維持。

Answer 3

一種方法是使用雙點有序交叉。這種類型的交叉從一位父母創建一個孩子。選擇兩個親本並選擇染色體上的兩個隨機點。點之間的基因被傳遞給孩子。剩餘的基因從同一父母轉移，但順序是它們出現在第二個父母中。結果是，孩子包含來自單個父母的所有值，但包括來自父母雙方的排序，因此包括特徵。

這裏顯示了使用這種類型的算子求解TSP的兩個例子;

http://johnnewcombe.net/blog/gaf-part-4/

http://johnnewcombe.net/blog/gaf-part-7/

第一這些例子使用整數來引用城市，第二個例子，通過使用基於對象的基因來存儲染色體內的城市簡化了這個。