基于遺傳算法求解TSP 問題的研究及Matlab 實(shí)現(xiàn)

楊錦濤， 趙春香， 楊成福

（云南師范大學(xué)信息學(xué)院， 昆明 650500）

0 引 言

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

遺傳算法是一種自組織、自適應(yīng)的全局尋優(yōu)算法，因其潛在的并行性、較高的魯棒性，在應(yīng)用研究方面取得了很多可觀的成果，被廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、自適應(yīng)控制、圖像處理、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、人工生命、遺傳編程等領(lǐng)域。

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

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

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

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

1 遺傳算法求解TSP 問題

1.1 編碼

編碼是指按照一定的構(gòu)造方法，將問題的可行解轉(zhuǎn)變?yōu)檫z傳算法能直接處理的個體。 常用的編碼方式有二進(jìn)制編碼、近鄰編碼、次序編碼、路徑編碼［6］。

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

1.2 初始種群

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

1.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于對種群中的個體進(jìn)行優(yōu)劣程度的評價，由于算法在搜索最優(yōu)解的過程中主要以個體的適應(yīng)度作為依據(jù)，所以如果適應(yīng)度函數(shù)構(gòu)建不當(dāng)，很可能導(dǎo)致算法的收斂速度緩慢、甚至無法收斂，即適應(yīng)度函數(shù)直接決定著算法的收斂能力和尋優(yōu)能力。

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

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

1.4 遺傳操作

1.4.1 選擇算子

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

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

1.4.2 交叉算子

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

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

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

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

1.4.3 變異算子

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

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

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

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

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

根據(jù)上文選擇的實(shí)現(xiàn)技術(shù)構(gòu)建完整的遺傳算法體系后，對TSP 問題實(shí)例進(jìn)行求解的具體步驟如下：

Step 1獲取城市數(shù)據(jù)，對城市進(jìn)行編號。

Step 2初始化種群。

Step 3適應(yīng)度評價。

Step 4執(zhí)行選擇操作，采用輪盤賭選擇對個體進(jìn)行篩選，選出足夠數(shù)量的個體。

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

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

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

Step 8判斷是否繼續(xù)進(jìn)行迭代，若是，回到Step3；否則，結(jié)束迭代，輸出最優(yōu)解。

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

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

2 實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)仿真

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

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

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

以文獻(xiàn)［8］中求得的最優(yōu)解423.74 作為參考值，從表3 可以看出第2 組、第5 組、第8 組交叉算子和變異算子的求解結(jié)果都比較接近參考最優(yōu)解，且較穩(wěn)定，說明參數(shù)設(shè)置較合理。 其中一次求解的收斂曲線如圖1 所示，最優(yōu)路線如圖2 所示。 其中，以圓圈標(biāo)記的點(diǎn)為路線起點(diǎn)，其與路線終點(diǎn)用虛線相連，其余路線用實(shí)線連接。

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

圖2 Oliver30 最優(yōu)路線圖Fig. 2 Optimal roadmap of Oliver30

2.2 實(shí)驗(yàn)結(jié)果

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

其中，Opt是TSPLIB 數(shù)據(jù)集提供的最優(yōu)解。

實(shí)驗(yàn)結(jié)果見表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

為了方便對比，將每個實(shí)例求解結(jié)果中的偏差率（Dr） 和求解的平均時間（Time） 分別統(tǒng)計(jì)在一起，由于實(shí)例ulysses16 問題規(guī)模小，坐標(biāo)數(shù)據(jù)也容易處理，不管選擇哪種交叉算子和變異算子，求解結(jié)果都很接近最優(yōu)解，因此在進(jìn)行偏差率的比較時不將其考慮在內(nèi)，具體見表9、表10。

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

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

3 實(shí)驗(yàn)結(jié)論

根據(jù)上述實(shí)驗(yàn)結(jié)果，可以得出如下結(jié)論：

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

（2）表10 是采用每組交叉算子和變異算子求解每個實(shí)例10 次所花時間的平均值，所花的時間越少，說明算法的搜索速度越快，執(zhí)行效率越高，由于變異操作比較簡單，所以遺傳算法的執(zhí)行效率主要由交叉操作決定。 從表10 中可以看出，遺傳算法采用順序交叉和循環(huán)交叉時，即使采用不同的變異算子，所花的時間也基本相同，但是采用部分匹配交叉所花的時間會因?yàn)樽儺愃阕拥牟煌兴煌?對于每一個實(shí)例，在得到的解的質(zhì)量差別不大的情況下，遺傳算法使用部分匹配交叉所花的時間最多，使用循環(huán)交叉所花的時間最少。

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

4 結(jié)束語

本文對幾種常用的交叉算子和變異算子求解TSP 問題的效果進(jìn)行了研究。 實(shí)驗(yàn)結(jié)果表明，在幾種常用的交叉算子和變異算子中，選擇循環(huán)交叉和逆轉(zhuǎn)變異算法的執(zhí)行效率最高，尋優(yōu)能力最好，這能為遺傳算法中交叉算子和變異算子的選擇提供一定的參考，同時有利于設(shè)計(jì)出更好的交叉算子和變異算子，提高算法的性能。