楊錦濤， 趙春香， 楊成福

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

0 引 言

TSP 問題、即巡回旅行商問題，是組合優(yōu)化領(lǐng)域中的一個(gè)典型問題。 現(xiàn)實(shí)生活中的很多實(shí)際應(yīng)用問題都可以簡化為TSP 問題。 TSP 問題可以用圖論描述為：已知帶權(quán)完全圖G， 求一條使得路徑總和最小、且經(jīng)過所有頂點(diǎn)的回路。 TSP 問題雖然描述簡單、容易理解，但是求解是很困難的。 當(dāng)問題的規(guī)模較小時(shí)，僅使用枚舉法就能找到一條最優(yōu)路徑，但當(dāng)城市數(shù)量較多時(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)度低的解（個(gè)體）淘汰掉，將適應(yīng)度高的解（個(gè)體）保留下來，并產(chǎn)生新的解（個(gè)體），生成新的解集（種群），通過不斷地迭代，使解集（種群）中的解（個(gè)體）越來越接近問題的最優(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í)間兩方面對實(shí)驗(yàn)結(jié)果進(jìn)行分析和總結(jié)，探究使用不同的交叉算子和變異算子時(shí)遺傳算法求解對稱式TSP 問題的效果［5］。

1 遺傳算法求解TSP 問題

1.1 編碼

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

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

1.2 初始種群

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

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

適應(yīng)度函數(shù)用于對種群中的個(gè)體進(jìn)行優(yōu)劣程度的評價(jià)，由于算法在搜索最優(yōu)解的過程中主要以個(gè)體的適應(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） 為種群中的一個(gè)個(gè)體；d（ti，tj） 表示城市i到城市j的距離。 TSP 問題為最小值問題，由適應(yīng)度函數(shù)可知，路徑總和與個(gè)體適應(yīng)度呈倒數(shù)關(guān)系。

1.4 遺傳操作

1.4.1 選擇算子

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

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

1.4.2 交叉算子

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

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

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

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

1.4.3 變異算子

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

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

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

（3）插入變異。 用隨機(jī)方式在父體中確定一個(gè)位置，以確定一個(gè)待插入的基因，再用隨機(jī)方式確定2 個(gè)位置，以確定插入點(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)度評價(jià)。

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

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

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

Step 7完成變異后，執(zhí)行最佳個(gè)體保存策略，判斷當(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ī)模多樣。 本文在對每個(gè)測試樣例進(jìn)行求解時(shí)，改變算法的交叉算子和變異算子，進(jìn)行多次重復(fù)的實(shí)驗(yàn)，從問題的最優(yōu)解和求解時(shí)間兩方面對幾組交叉算子和變異算子求解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ī)模來確定。 一般地，城市個(gè)數(shù)越多，種群規(guī)模越大，對30 個(gè)城市的實(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 個(gè)實(shí)例，分別是ulysses16、dantzig42、eil51、eil76、eil101，根據(jù)問題的規(guī)模為每個(gè)實(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），以及求解的平均時(shí)間（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

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

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

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

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

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

（1）表9 中的偏差率描述了采用不同的交叉算子和變異算子時(shí)，所求得的最優(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)變異組合在一起時(shí)，問題的求解結(jié)果總是比與對換變異和插入變異組合在一起時(shí)更接近最優(yōu)解。 由此可知，遺傳算法使用逆轉(zhuǎn)變異作為變異算子時(shí)比選擇對換變異和插入變異作為變異算子的尋優(yōu)能力更強(qiáng)。

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

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

4 結(jié)束語

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