TSP（traveling salesman problem，旅行商問題）描述的是某一旅行商從某個城市出發通路每個城市一次且僅一次，最後回到出發城市，目标是尋找一條最短的周遊n個城市的路徑。TSP是典型的NP完全問題，其時間複雜度随問題規模的增加按指數形式增長。求解TSP的算法主要有遺傳算法、分支定界法、改良圈算法、模拟退火算法、人工神經網絡算法等方法，遺傳算法求解該TSP問題。遺傳算法是一種模拟自然進化過程的随機化搜尋尋找最優解算法，其主要特點是群體搜尋政策和群體中個體之間的資訊交換，搜尋不以梯度資訊為基礎，尤其适用于處理傳統搜尋方法難以解決的複雜非線性問題，步驟如下：
1.編碼
采用整數排列編碼方法，對于個節點的TSP問題，将節點從1到n進行編号，每個從1到n的全排列都可以作為該問題的一個解，即染色體個數。例如對具有5個節點的TSP問題，3,4,5,1,2就為一個合法的染色體。
2.種群初始化
在完成染色體編碼之後，需要産生一個初始種群作為初始解，初始種群的數目是根據節點規模大小來确定的，一般取值在50~200之間。
3.适應度函數
利用遺傳算法求解最優，就是要找到适應度最大的染色體，适應度函數定義如下：
由上式知适應度函數為恰好周遊個節點并回到出發節點的距離的倒數，優化目标是選取适應度值盡可能大的染色體。
4.選擇操作
選擇操作是按一定的機率從舊群體選擇個體到新群體中，個體适應度值越大，被選中的機率越大。
5.交叉操作
采用部分映射雜交，确定交叉操作的父代，将父代樣本兩兩分組，每組重複以下過程（設節點個數為10）：A. 産生兩個[1,10]區間内的随機整數作為兩個位置參數r1，r2，對兩位置的中間資料進行交叉。B. 交叉後，不重複的數字保留，重複的數字利用中間段的對應關系進行映射消除沖突。
6.變異操作
變異操作是随機選取兩個點将其對換位置，例如産生兩個[1,10]區間内的随機整數作為兩個位置參數r1，r2，對兩位置的資料對換。
7.進化逆轉操作
在選擇、交叉、變異之後引進連續多次的進化逆轉操作，這樣可以增強遺傳算法的局部搜尋能力。進化指的是逆轉算子的單方向性，隻有經逆轉後适應度值變大的染色體才會保留下來。例如産生兩個[1,10]區間内的随機整數作為兩個位置參數r1，r2，對兩位置中間的資料逆轉。
8.終止條件
對每個染色體進行交叉變異，代入适應度函數選出适應度值大的個體進行下一代的交叉、變異以及進化逆轉操作，直到滿足設定的最大遺傳代數結束循環。
遺傳算法流程圖如下圖所示。
