遺傳算法 - 旅行商

Question

我經歷過去的試卷，我想了解以下問題：

假設你有N個城市。從每個城市到其他任何城市都是可能的。假設你有一個表格形式的城市之間的距離的完整信息。城市號碼k與城市號碼l之間的距離由d（k，l）給出;例如，從第三城市到第九城市的距離由d（3,9）給出。請注意，d（k，l）= d（l，k）。

旅行商需要訪問所有N個城市，並希望找到連接所有城市的最短路線。使用遺傳算法來解決這個問題。

問題：爲這個問題定義一個合適的適應度函數 並且說是高或低適合度更好。

有沒有人知道我需要爲這個問題做什麼？我真的很難從哪裏開始，需要一些方向。

Answer 1

隨着TSP你想盡量減少行駛距離。有很多不同的方式可以在城市旅行;準確地說是N!/2。

所以，如果你有N = 4，你想要一個整數1-4的數組，每個只發生一次。因此，一些可能的選項是：

[1,4,2,3] 
[4,1,2,3] 
[3,1,4,2] 

然後，通過在列表中，從城市i去i+1，計算距離評價得分。爲列表中的每個城市i做這個（但是最後），並且您有總距離;這是你的分數！

所以對於分數上面的例子是：

// Please note that the integers 1-4 represent cities 
score([1,4,2,3]) = d(1,4) + d(4,2) + d(2,3) 
score([4,1,2,3]) = d(4,1) + d(1,2) + d(2,3) 
score([3,1,4,2]) = d(3,1) + d(1,4) + d(4,2) 

你希望儘量減少距離，從而最大限度地減少了比分。

---

你可以通過創建一個交換兩個城市在列表例如突變功能做到這一點：

[1,4,2,3] -> [4,1,2,3] 
[1,2,3,4] -> [1,3,2,4] 

This video顯示了Javascript實現通過遺傳算法優化的距離的一個很好的例子。