基于遺傳算法求解TSP 問題的研究及Matlab 實現

楊錦濤， 趙春香， 楊成福

（云南師范大學信息學院， 昆明 650500）

0 引 言

TSP 問題、即巡回旅行商問題，是組合優化領域中的一個典型問題。 現實生活中的很多實際應用問題都可以簡化為TSP 問題。 TSP 問題可以用圖論描述為：已知帶權完全圖G， 求一條使得路徑總和最小、且經過所有頂點的回路。 TSP 問題雖然描述簡單、容易理解，但是求解是很困難的。 當問題的規模較小時，僅使用枚舉法就能找到一條最優路徑，但當城市數量較多時，即使用計算機也無法將解全部列舉，要求出TSP 問題的最優解是不可能的。

遺傳算法是一種自組織、自適應的全局尋優算法，因其潛在的并行性、較高的魯棒性，在應用研究方面取得了很多可觀的成果，被廣泛應用于函數優化、組合優化、生產調度、自適應控制、圖像處理、機器學習、數據挖掘、人工生命、遺傳編程等領域。

1975 年，Holland［1］受生物學中生物進化和自然選擇學說的啟發，提出了著名的遺傳算法。 2006年，何燕［2］對遺傳算法進行改進，將其應用到車間調度領域。 2010 年，蔣波［3］將遺傳算法應用于車輛路徑優化問題，指出遺傳算法求解該問題的優越性，并對其做出了改進，實驗證明改進后的遺傳算法能夠有效解決此類問題。 2013 年，喬陽［4］將遺傳算法和Ostu 圖像分割法進行改進后結合在一起進行圖像分割實驗，得到了滿意的結果。

遺傳算法是模擬生物進化的過程發展而來的一種算法，從一定規模的解集（初始種群）開始，通過選擇、交叉和變異，將適應度低的解（個體）淘汰掉，將適應度高的解（個體）保留下來，并產生新的解（個體），生成新的解集（種群），通過不斷地迭代，使解集（種群）中的解（個體）越來越接近問題的最優解。 生物學和遺傳算法概念之間的對應關系見表1。

表1 生物學和遺傳算法概念對照Tab. 1 Comparison of biological and genetic algorithm concepts

本文針對TSP 問題構建完整的遺傳算法體系，將求解TSP 問題幾種常用的交叉算子和變異算子兩兩組合在一起，分別對具體的TSP 問題實例進行求解，從所得的最優解和求解的時間兩方面對實驗結果進行分析和總結，探究使用不同的交叉算子和變異算子時遺傳算法求解對稱式TSP 問題的效果［5］。

1 遺傳算法求解TSP 問題

1.1 編碼

編碼是指按照一定的構造方法，將問題的可行解轉變為遺傳算法能直接處理的個體。 常用的編碼方式有二進制編碼、近鄰編碼、次序編碼、路徑編碼［6］。

使用路徑編碼求解TSP 問題，不僅編碼過程簡單易操作，而且編碼結果非常直觀，即首先對城市進行編號，然后以城市編號作為城市的編碼，因此本文選擇使用路徑編碼方式對城市進行編碼。

1.2 初始種群

一般地，初始種群采用隨機方法生成，如果種群規模為M，則隨機生成M個個體。

1.3 適應度函數

適應度函數用于對種群中的個體進行優劣程度的評價，由于算法在搜索最優解的過程中主要以個體的適應度作為依據，所以如果適應度函數構建不當，很可能導致算法的收斂速度緩慢、甚至無法收斂，即適應度函數直接決定著算法的收斂能力和尋優能力。

對于TSP 問題，適應度函數一般取路徑總和的倒數，具體定義公式見如下：

其中，n表示城市的數量；T＝（t1，t2，…，tn） 為種群中的一個個體；d（ti，tj） 表示城市i到城市j的距離。 TSP 問題為最小值問題，由適應度函數可知，路徑總和與個體適應度呈倒數關系。

1.4 遺傳操作

1.4.1 選擇算子

選擇是用選擇算子對個體進行篩選的過程，這一過程中，差的個體被保留下來的概率小，好的個體被保留下來的概率大，會使種群中的個體向最優解進化。 常用的選擇算子有輪盤賭選擇、最佳個體保存選擇、錦標賽選擇和排序選擇［7］。

輪盤賭選擇是TSP 問題求解最常用的選擇算子，即使用適應度值計算出每個個體被選擇的概率，并根據該概率值對種群中的個體進行選擇。 本文也使用輪盤賭選擇作為選擇算子，并在輪盤賭的基礎上添加最佳個體保存選擇，即把種群中出現過的適應度值最高的個體保留下來，避免種群中優秀的個體在遺傳操作中被淘汰或破壞。

1.4.2 交叉算子

個體交叉是為了實現種群的更新，而交叉算子是進行交叉的手段，定義了個體之間以怎樣的方式交叉。 對于不同問題，由于編碼方式的不同，交叉算子也有所不同。 對此擬做研究分述如下。

（1）部分匹配交叉（PMX）：首先采用隨機方式在父體中確定2 個位置，由2 個位置確定一個交叉段，然后將2 個父體的交叉段進行交換，最后根據交叉段之間的映射關系消除子代中的重復基因。

（2）順序交叉（OX）：首先從父體中隨機選擇2個位置，由2 個位置確定一個基因段，然后將父體A的該基因段復制到子代A’的對應位置，最后將父體B除父體A被選擇的基因段之外的基因依次復制到子代A’ 的其余位置，同理可得到子代B’。

（3）循環交叉（CX）：首先將父體A的第一個基因復制到子代，然后在父體B中的相同位置查看基因，隨后在父體A中找到該基因復制到子代的相同位置，并在父體B中查看相同位置的基因，重復此步驟，直到在父體B中找到的基因已經在子代中，停止循環，在父體B中找到剩余的基因，并按照順序復制到子代中的剩余位置。

1.4.3 變異算子

變異操作的主要目的是維持種群多樣性，在遺傳算法后期，個體交叉產生新個體的能力弱，通過個體變異可以進一步產生新個體，擴大搜索空間。 接下來給出剖析論述如下。

（1）對換變異。 首先用隨機方式在父體中確定2 個位置，然后交換這2 個位置上的基因。

（2）倒位變異。 用隨機方式在父體中確定2 個位置，以確定一個基因段，然后將其進行逆序排列。

（3）插入變異。 用隨機方式在父體中確定一個位置，以確定一個待插入的基因，再用隨機方式確定2 個位置，以確定插入點，最后將待插入的基因放入插入點。

1.5 遺傳算法求解TSP 問題具體步驟

根據上文選擇的實現技術構建完整的遺傳算法體系后，對TSP 問題實例進行求解的具體步驟如下：

Step 1獲取城市數據，對城市進行編號。

Step 2初始化種群。

Step 3適應度評價。

Step 4執行選擇操作，采用輪盤賭選擇對個體進行篩選，選出足夠數量的個體。

Step 5執行交叉操作，將選擇操作中選出的個體兩兩組合作為父染色體，判斷是否進行交叉，如果進行交叉，則按照選定的交叉算子進行交叉。

Step 6執行變異操作，將執行交叉操作后的每個個體作為父染色體，判斷是否進行變異，如果進行變異，則按照選定的變異算子進行變異。

Step 7完成變異后，執行最佳個體保存策略，判斷當前種群中的最優解是否優于歷史最優解。 如果是，更新歷史最優解，否則找出種群中最差的解，用最優解將其替換掉。

Step 8判斷是否繼續進行迭代，若是，回到Step3；否則，結束迭代，輸出最優解。

將前述的3 種交叉算子和3 種變異算子兩兩組合在一起，共有9 種組合方式，見表2。 基于表2 中列出的9 種組合，重復對TSP 問題進行求解。

表2 9 組交叉算子和變異算子Tab. 2 9 sets of crossover and mutation operators

2 實驗及結果分析

2.1 實驗仿真

本文使用Matlab 實現上文構建的遺傳算法，從TSPLIB 中選擇測試樣例進行具體分析。 TSPLIB 是包含對稱旅行商問題、哈密頓回路問題、以及非對稱旅行商問題的多種實例數據的文件庫，數據規模多樣。 本文在對每個測試樣例進行求解時，改變算法的交叉算子和變異算子，進行多次重復的實驗，從問題的最優解和求解時間兩方面對幾組交叉算子和變異算子求解TSP 問題的效果進行分析比較。

在完成算法的編程后，初步設置參數，對實例Oliver30 進行求解，根據實驗結果對算法的參數進行調整，最終選定迭代次數G為500，交叉概率Pc為0.9，變異概率Pm為0.2，種群規模M根據待求解問題的規模來確定。 一般地，城市個數越多，種群規模越大，對30 個城市的實例Oliver30，種群規模取100。 用上述9 組交叉算子和變異算子分別對Oliver30 求解10 次的結果見表3。

表3 遺傳算法求解Oliver30Tab. 3 Genetic algorithm for Oliver30

以文獻［8］中求得的最優解423.74 作為參考值，從表3 可以看出第2 組、第5 組、第8 組交叉算子和變異算子的求解結果都比較接近參考最優解，且較穩定，說明參數設置較合理。 其中一次求解的收斂曲線如圖1 所示，最優路線如圖2 所示。 其中，以圓圈標記的點為路線起點，其與路線終點用虛線相連，其余路線用實線連接。

圖1 Oliver30 收斂曲線Fig. 1 Convergence curve of Oliver30

圖2 Oliver30 最優路線圖Fig. 2 Optimal roadmap of Oliver30

2.2 實驗結果

從TSPLIB 中選擇測試樣例進行求解，本文總共選擇了5 個實例，分別是ulysses16、dantzig42、eil51、eil76、eil101，根據問題的規模為每個實例設置合適的種群規模（M）。 其中，ulysses16、dantzig42、eil51 實例的種群規模取100，eil76 實例的種群規模取150，eil101 實例的種群規模取200，分別用上述9組交叉算子和變異算子求解10 次，記錄10 次求解結果的最好值（Best）、 平均值（AVR） 和偏差率（Dr），以及求解的平均時間（Time），這里的偏差率可由式（2） 來計算：

其中，Opt是TSPLIB 數據集提供的最優解。

實驗結果見表4～表8。

表4 遺傳算法求解ulysses16Tab. 4 Genetic algorithm for ulysses16

表5 遺傳算法求解dantzig42Tab. 5 Genetic algorithm for dantzig42

表6 遺傳算法求解eil51Tab. 6 Genetic algorithm for eil51

表7 遺傳算法求解eil76Tab. 7 Genetic algorithm for eil76

表8 遺傳算法求解eil101Tab. 8 Genetic algorithm for eil101

為了方便對比，將每個實例求解結果中的偏差率（Dr） 和求解的平均時間（Time） 分別統計在一起，由于實例ulysses16 問題規模小，坐標數據也容易處理，不管選擇哪種交叉算子和變異算子，求解結果都很接近最優解，因此在進行偏差率的比較時不將其考慮在內，具體見表9、表10。

表9 偏差率對比Tab. 9 Deviation rate comparison

表10 求解平均時間對比Tab. 10 Comparison of average solving time

3 實驗結論

根據上述實驗結果，可以得出如下結論：

（1）表9 中的偏差率描述了采用不同的交叉算子和變異算子時，所求得的最優解與TSPLIB 中給出的最優解的差距，偏差率越小，說明算法求得的結果越接近最優解，算法的尋優能力越好。 從表9 中可以看出，第2 組數據總是小于第1 組和第3 組、第5 組數據總是小于第4 組和第6 組、第8 組數據總是小于第7 組和第9 組，這說明每種交叉算子和逆轉變異組合在一起時，問題的求解結果總是比與對換變異和插入變異組合在一起時更接近最優解。 由此可知，遺傳算法使用逆轉變異作為變異算子時比選擇對換變異和插入變異作為變異算子的尋優能力更強。

（2）表10 是采用每組交叉算子和變異算子求解每個實例10 次所花時間的平均值，所花的時間越少，說明算法的搜索速度越快，執行效率越高，由于變異操作比較簡單，所以遺傳算法的執行效率主要由交叉操作決定。 從表10 中可以看出，遺傳算法采用順序交叉和循環交叉時，即使采用不同的變異算子，所花的時間也基本相同，但是采用部分匹配交叉所花的時間會因為變異算子的不同而有所不同。 對于每一個實例，在得到的解的質量差別不大的情況下，遺傳算法使用部分匹配交叉所花的時間最多，使用循環交叉所花的時間最少。

綜上所述，對于比較簡單的TSP 問題，由于使用遺傳算法總能求得與最優解很接近的解，所以選擇何種交叉算子和變異算子對算法的尋優能力影響不大，但是使用部分匹配交叉會花費比較多的時間，會導致算法的執行效率低，因此交叉算子選擇循環交叉比較合適。 對于不是總能求得最優解的TSP問題，與對換變異和插入變異相比，使用逆轉變異會使算法具有更強的尋優能力，找到的最優解更接近最優解，使用部分匹配交叉和順序交叉會花費比循環交叉更多的時間，使算法的執行效率變低，而且找到的最優解也不會更優。

4 結束語

本文對幾種常用的交叉算子和變異算子求解TSP 問題的效果進行了研究。 實驗結果表明，在幾種常用的交叉算子和變異算子中，選擇循環交叉和逆轉變異算法的執行效率最高，尋優能力最好，這能為遺傳算法中交叉算子和變異算子的選擇提供一定的參考，同時有利于設計出更好的交叉算子和變異算子，提高算法的性能。