我正在研究使用遺傳算法（GA）解決旅行商問題（TSP）的迷你學術作業。我遵循一個非常簡單的經典表示法，用於存儲陣列中的城市和遊覽，例如，10個城市之旅可以表示爲9-1-0-4-3-8-6-5-2-7，依此類推。 對於GAs有一些相當基礎的知識，對於將TSP應用不同類型的突變時遵循什麼樣的方法，我有點困惑。假設我們的路線表示爲路線，並且變量率表示在變量m_rate中。在GA中應用突變來解決旅行推銷員
[1]簡單的插入突變
說我們有：1-2-3-4-5-6-7-8-9。然後我們選擇一個隨機城市，比如索引5，然後選擇一個隨機插入索引，如2，那麼突變的染色體是：1-2-6-3-4-5-7-8-9。
現在，這裏是我做申請突變什麼：
for (int i=0; i<route.length; i++) {
if (m_rate<Math.random()) {
// Pick a random city
int randomCity = 0 + (int)(Math.random() * (((route.length-1) - 0) + 1));
// Do the insertion and shift the array where appropriate
}
}
換句話說，我通過循環的路線每一個城市，看到的突變條件是否成立（m_rate>的Math.random（ ）），如果它真的那麼我停在那個索引處，然後在不使用變異概率變量的情況下隨機選擇一個插入點。 只要沒有遇到數組的末尾，我就繼續將相同的事情應用於其餘的每個城市或索引。 這是一個正確的方法嗎？一旦我應用了第一次突變，我應該停止還是跳出循環？突變概率是否應該以某種方式參與選擇插入點？儘管這對我來說似乎沒有多大意義。 如果有多個城市在染色體或路徑上發生突變的可能性，染色體是否有可能被轉移？換句話說，如果我最終做了第二次或第三次突變，將染色體逆轉爲初始形式（突變之前），會發生什麼？
[2]相互交換突變。
在染色體中選擇一個隨機城市，然後選擇第二個隨機城市並交換這兩個城市。例如，在路線1-5-2-8-0-9-3-7-4-6。如果我們最終選擇了索引2和索引7，那麼突變的染色體是：1-5-7-8-0-9-3-2-4-6。
我通過在路由每個城市穿越和檢驗概率條件，然後直接選擇一個隨機的城市沒有施加任何形式的突變率與交換以下類似的方法上面插入突變。上述相同的排序問題，適用在這裏..
[3]反轉突變。
這是最棘手的一個。給定一個染色體，如：1-2-3-4-5-6-7-8-9，我們選擇的突變切割仿指數2到索引5，然後反轉該subroute ==> 1-2-6-5- 4-3-7-8-9。
但是，您如何應用此？你是否循環路線，然後根據突變率選擇一個城市，然後直接選擇另一個指標來確定子路徑的長度？做一次突變並退出？在這種實現中，如果我們突變最終爲0-9或0-（長度-1），那麼整個染色體或途徑是否可以突變顛倒整個事物？在這種情況下，真正的突變率的價值是什麼？我有點丟在這裏......
我提前做這個太長時間道歉..但我希望對這些問題發表任何意見，或者如果有人能指示我詳細討論這些問題的任何資源。我已經看過那裏的一些研究論文，但沒有多少人已經接觸到這種細節和細節。
謝謝。
嗨本，謝謝你的評論。我真的不確定您的非GA近似值是什麼意思，我發現這種表示法在使用GA時甚至在研究人員中被廣泛使用，主要是因爲它的簡單性。我已經考慮過使用二維矩陣表示，但是它不允許在交叉和變異方面有任何的靈活性，並且實現起來有點複雜。至於突變和交叉，我肯定遵循你指出的第二種選擇，不使用懲罰函數並確保每個產生的染色體合法或有效。 – hesperus