上一篇寫了遺傳算法的原理，這一篇寫遺傳算法解決旅行商問題的實戰，而且使用python編寫。近幾年python越來越受歡迎，其中主要是簡單易學和上手快，並且編代碼的效率高，甚至有人喊出“人生苦短，我要用python”的口號，所以小編也來湊湊熱鬧。
旅行商問題
旅行商是一個組合優化問題，是一個經典的NP-hard問題，也就是不能在一個可接受的時間範圍內得到最優解的問題。旅行商的問題來自一位商人，這位商人需要從一座城市出發，遊歷每一個城市最後回到出發的城市，商人希望整個遊歷路徑最短。假如現在有A、B、C、D、F、E、G，七個城市並且兩兩城市之間的距離已知。如果從A出發，那麼A->D->B->C->G->E->F->A就是一條遊歷的路徑，並且可以得知其中的總距離，那麼怎麼樣的路徑組合才是最短的路徑？每個路徑的排列都計算一次路徑，找到最短的路徑，這樣的時間複雜度為O(n!)，當n很大時，出現“知數爆炸”問題。
駱駝商人
實戰結果
圖中一共16座城，城市的座標為：
x = [0, 1, 3.7, 3, 4, 2.3, 4, 5.5, 4, 3, 2, 1, 0, 10, 0, 9.6]
y = [0, 8.0, 0, 4, 0, 1, 3.6, 3, 7.3, 4, 9.6, 4, 8.6, 6.1, 2, 1]
在343次迭代的時候取得較優解，優解的距離為41.4，將優解換算為城市的座標點，得到完整的路線圖。
優解路線圖1
另一條路線。
優解路線圖2
隨著迭代次數增加，即不斷的遺傳進化，啟發式的向最優解靠近，漸漸的距離減小，過程雖然曲折。由於初始的路線是隨機生成的，每一次的計算結果都不一樣，找到的最好的解也不一樣，有時陷入局部最優解，有時甚至可以得到全局最優解。
隨著迭代次數增加，距離減小
算法過程
遺傳算法是不斷迭代的過程，其中只有達到了迭代的次數或者解的精度才可以跳出迭代，迭代的過程中總是不斷的進行選擇、交叉和變異。
計算適應度函數就是不斷維護fitness矩陣，其中第一列為適應度，第二列為選擇概率，第三列為累計概率。計算適應度函數主要是為下面的選擇函數準備好數據。
計算適應度函數
選擇函數是通過輪盤賭的方式將遺傳的下一代選擇，並且選擇的時候適應度強的個體被選中的概率按比例增大，數據主要來自fitness矩陣。
選擇函數
交叉函數將兩個個體的染色體相同位置的相同長度的基因互換，交叉之後會產生重複的表現型，代碼中的處理方法是，將兩段交叉的基因中重複的數字去掉，剩下的數字於未交叉的數字映射去重。
交叉函數
相對來說變異的處理十分簡單，隨機選擇一個個體，互換兩個位置上的數字就可以了。
變異函數
已經上傳到Github,但是這裡不能放鏈接。
喜歡我的話，加個關注吧，有更加精彩的內容等著大家。
閱讀更多 算法卡農 的文章
