求解ＴＳＰ問題的改進遺傳算法

摘要：旅行商問題(TSP)是遺傳算法得以成功應用的典型問題。文章對遺傳算法加以改進，提出了新的選擇策略和交叉算子，并且引入了兄弟競爭的策略來加快收斂速度和全局搜索能力。把該算法應用在不同類型的TSP問題的求解上，表現出了比傳統遺傳算法更好的收斂性和計算效率。說明改進算法是有效的。關鍵詞：旅行商問題(TSP)；遺傳算法(GA)；交叉算子；兄弟競爭策略

0 引言

旅行商問題(Traveling salesman Problem，簡記為TSP)自1932年K．Menger提出以來，已引起各個領域許多研究者的興趣。它是一個古老而又困難的問題，是一種典型組合優化問題(combinatorial Optimization Problem)，并且也是一種NP完全問題(Nondeterministic Polynomial Complete Problem)。TSP問題可以描述為：一個推銷員要到n(n>2)個城市推銷貨物，從某個城市出發，經過其余各個城市一次且僅僅一次，然后回到出發點，求其最短行程，即尋找一條巡回路徑。

TSP問題主要有兩類：一類是任兩個城市間的距離都是對稱的，假設點i和點j之間的距離為d_ij則d_ij=d_ji，它對應的是圖論中的無向圖；另一類是兩個城市間的距離是非對稱的，即d_ij≠d_ji它對應的是圖論中的有向圖。

TSP問題中，可能的路徑總數與城市數目n是成指數型增長的，一般很難精確地求出其最優解，因而尋找出有效的近似求解算法就具有重要的意義。很多實際應用問題，如印制電路板的鉆孔路線方案，連鎖店的貨物配送路線，列車編組等，經過簡化處理后，均可建模為TSP問題，因而對TSP問題求解方法的研究具有重要實際價值。另外，所有NP完全問題在數學上都等價于TSP問題，它的研究對于科學和工程技術領域中大量組合優化問題，尤其是其中的NP完全問題的求解有著極為重要的價值。

目前針對TSP問題已有許多種解法，如窮舉搜索法(Ex-hansfive Search Method)、貪心法(Greedy Method)、動態規劃法(Dynamic Programming Method)、分支界定法(Branch-And-Bound)等。這些方法都存在著一個共同的問題就是當城市數目N較大時，會產生所謂的“組合爆炸”問題。如當N=50時，用每秒計算一億次的巨型計算機采用窮舉搜索法計算，所需時間為5×10“年。數年來，又有人提出了一些優化技術，如模擬退火、遺傳算法和神經計算等，并且取得了一定的進展。其中遺傳算法具有良好的全局搜索能力，是目前解決各種優化問題的有效方法。

1 遺傳算法

遺傳算法(genetic algorithms，簡稱GA)是J.Holland于1975年受生物進化論的啟發而提出的。遺傳算法是一種借鑒生物界自然選擇和自然遺傳學機理的迭代自適應概率性搜索算法，是基于“適者生存”的一種高度并行、隨機和自適應的優化算法，它將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷變化，包括復制、交叉和變異等操作，最終收斂到“最適應環境”的個體，從而求得問題的最優解或滿意解。其具體算法如下：

(1)初始化：確定解的基因表示，設置遺傳算法的重要參數(群體規模n，迭代次數gen，交叉概率P_c，變異概率P_m)，并隨機產生n個初始個體P(0)={a₁，a₂，...，a_n}作為初始種群，其中ai表示第i個個體。

(2)計算適應度評價函數：對群體P(t)中的每一個個體a_i計算它的適應度函數fitness(a_i)，i=l，2，3，...，n。

(3)選擇操作：根據個體適應度，以一定的選擇算子，從P(t)解集中選擇一些優良個體進入下一代。

(4)交叉操作：以交叉概率P。對當前群體中個體的部分結構加以替換和重組。

(5)變異操作：以較小的變異概率P_m改變當前群體中個體的某個或某些基因。群體P(t)經過選擇、交叉和變異后得到下一個群體P(t+1)；

(6)終止條件判斷：如果滿足終止條件，則將當前群體中具有最大適應度的個體作為最優解，終止計算。否則返回(2)。

遺傳算法具有良好的全局搜索能力，常用于求解TSP問題。但傳統的遺傳算法收斂速度慢并且易于陷入局部最優解。針對這一缺點，本文提出了一種求解TSP問題的改進遺傳算法，對適應度函數的選擇、遺傳操作的設計以及重要參數的設置，都進行了改進。該算法應用于TSP問題的求解，表現出比傳統遺傳算法更好的收斂性和計算效率。

2 對求解TSP問題遺傳算法的改進設計

在上一節所述的利用遺傳算法求解問題的過程中，主要技術問題有：問題的表述和編碼；適應函數的構造；初始群體的選取；選擇、交叉、變異策略的選取；重要參數的設定；算法終止條件。下面將根據TSP問題的特點以及傳統遺傳算法求解TSP所存在的問題，對GA求解過程進行改進。

2.1問題的表述和編碼

問題的表述和編碼是構造遺傳算法的第一步，一個好的編碼可以清楚地表達問題的特征，它將影響整個算法的每一步。對于求解TSP問題，通常有Grefenstette編碼、近鄰表示、路徑表示、矩陣表示等多種方法。

Grefenstette編碼方式在進行單點雜交時，左側部分的旅程-不發生變化，所以這種方法的適用性存在一定的問題。近鄰表示法的缺點是排列不一定對應一合法回路，產生小圈現象，從而使得操作比較復雜，且遺傳算子打斷好路徑的概率較大，因此，該算法的性能較差。矩陣表示的遺傳操作比較復雜，并具有盲目性，也未充分利用城市間距離的信息。而路徑表示是旅程對應的基因編碼的最自然、簡單和符合邏輯的表示方法，并且由于編碼遍歷了每一個節點，所以不會產生子回路。

考慮到路徑表示是最符合邏輯也是最自然的表示方法，所以本文中選擇此編碼表示方法。例如：2-5-4-8-9—7-6-1-3-10可以表示為[2 5 4 8 9 7 6 1 3 10]，表示從城市2出發，依次經過城市5、4、8、9、7、6、1、3、10然后返回城市2的一條路徑。

2.2初始群體的選取

在求解TSP問題的傳統遺傳算法中，初始種群的產生都采用完全的隨機方式。本文綜合考慮所采用的路徑編碼的特點以及算法的效率，采用在隨機產生個體基因的同時加入了對所產生的非法基因判定和啟發式修改的機制。所謂的啟發式修改即找出距離較近的城市。

2.3適應度函數的構造

適應度函數的設計是遺傳算法的—個重要方面。一般來說，所設計的適應度函數要求具有單值、非負、最大化、合理、一致性、計算量小、通用性強的特點。由于TSP問題是—個求解最小值的問題，考慮到路徑編碼的特點以及適應度函數的設計要求，本文對遺傳算法的適應度函數設計如下：

為所獲得路徑的距離之和。顯然，距離之和越小，則適應度函數的數值就越大，該路徑也就越好。

2.4選擇策略

選擇算子設計為兩部分：復制選擇算子和生存選擇算子。復制選擇是指為了進行交叉操作對種群中的個體進行的選擇，生存選擇是從進行了交叉操作之后的群體中進行的選擇。在具體求解中復制選擇算子采用順序(ranking)選擇：首先根據適應度對各個個體進行排序，然后依據概率選擇個體進行交叉操作。生存選擇采用父輩個體和子代個體共同競爭的機制。

2.5交叉策略

本文結合貪心方法和邊重組交叉算子的特點提出了一種適合求解TSP問題的新的交叉算子，其具體描述如下：

假設有n個城市1，2，…，n，染色體編碼采用路徑表示。現有待交叉的雙親：

Parl=(a₁₁，a₁₂，a₁₃，…a_1n)，Par2=(a₂₁，a₂₂，a₂₃，…，a_2n)。

因為采用的是路徑表示，所以將上述染色體看成一個環，即a_1n的下—個城市為a₁₁。

(1)首先隨機確定—個當前城市currentcity，并將其加入到子代中。假設產生—個隨機數為2，則選出Parl中的第二個城市a₁₂為當前的城市，即currentcity=a₁₂，將a₁₂加入到子代中。

(2)在Par2中找到與currentcity相同的城市，并判斷cur-rentcity在兩個父代中的左、右鄰接城市是否在子代中，如不在則比較它們與currentcity之間的距離，記與currentcity距離最小的那個鄰接城市為下一個currentcity，并將其加入到子代中。假設a₁₂在Par2中為的a₂₃，判斷a₁₁、a₁₃、a₂₂、a₂₄是否在子代中，如不在則比較出d_a11，a12、d_a12，a13、d_a22，a23和d_a23，a24，設d_a22，a23為距離最小的，則currentcity=a₂₂，將a₂₂加入到子代中。

(3)如果左、右鄰接城市中已存在于子代中，選擇不在子代中的左、右次鄰接的城市來進行距離的比較。假設上述的a₁₁已經在子代中了，則選取a₁₁的左鄰接城市a_1n(因為相對于currentcity=a₁₂來說，a₁₁是a₁₁左鄰接城市)，如果a_1n不在子代中則比較d_a1n，a12。如果在則選擇a_1n的左鄰接城市進行距離的比較，依此類推直至所選取的城市不在子代中。

(4)重復(2)、(3)步驟直至完整地生成子代。

由上述介紹可以看出，結合邊重組交叉算子和貪心方法的這種交叉算子可以使交叉后的子代在保證可行性的同時，又在很大程度上很好地繼承了父代的優秀基因，迅速優化適應值，達到交叉的目的。

2.6變異策略

為了改善遺傳算法的局部搜索能力，并且考慮到所采用的編碼方式，本文采用逆轉變異，并在過程中加入了小范圍競爭、擇優的操作。

所謂逆轉變異是在染色體上隨機地選擇兩點，將兩點之間的子串反轉插入。如染色體[1 5 2 4 8 3 9 6 10 7]，假設隨機的兩個點為2和6，則將2和6之間的[4 8 3 9]按照反向順序插入到原來的染色體中，即為[1 5 2 9 3 8 4 6 10 7]。

加入小范圍競爭、擇優操作是從加快收斂速度和全局搜索性能兩方面考慮的。具體操作為：對待變異的染色體進行n次(3～5次)變異操作，生成n個不同的個體，選出其中最高適應度的個體加入到子代中。

2.7算法終止條件和重要參數選擇

本文設定一個最大迭代次數maxgen來結束算法。maxgen的具體取值要根據所要解決的TSP問題的具體的城市規模來確定。

遺傳算法中需要選擇的參數主要有：染色體的長度、群體規模、交叉概率Pc和變異概率Pm等。這些參數對遺傳算法的性能影響很大，它們的具體數值要根據所要解決的TSP問題來確定。

2.8實現流程

(1)確定重要參數的具體數值，隨機生成多個染色體群體(初始化中有非法路徑判斷機制)作為父群體，代數gen=0；

(2)對父代中的個體計算其適應度并排序；

(3)若gen>maxgen，則輸出該代中最優的個體的適應度的倒數；

(4) gen=gen+1；

(5)依據概率選擇個體進行n(n=3～5)次交叉、變異操作，選取適應度最高的放入子代；

(6)計算子代的適應度，并將其和父代放在一起進行適應度的排序，選取最高的popsize(popsize為群體規模)個作為新一代的群體，返回(3)。

3 實例應用驗證

筆者使用matlab6.5對改進的遺產算法在Win2000 pro-fessional操作系統上作了大量的仿真實驗，并且針對不同類型的TSP問題作了算法的測試。對典型的TSP問題的測試結果如下。

3.1非對稱TSP問題仿真實驗

表1為非對稱9個城市的TSP問題。在算例中，取種群規模popsize=20，Pc=0.3，Pm=0.8。將算法運行了100次，每次最多只是遺傳到第3代就收斂到最優化解9(3-9-5-4-2-7-8-6-1)，平均占用CPU時間為0.0703s。

3.2對稱TSP問題仿真實驗

在表2所示的對稱10個城市TSP問題的算例中，同樣取種群規模popsize=20，為Pc=0.3，Pm=0.8。將算法運行了100次，每次最多只是遺傳到第5代就收斂到最優化解151(1-3-6-4-5-7-8-9-2-10)，平均占用CPU時間為0.1203s。

以上兩個TSP實例的城市規模都不大，再把該改進算法用于求解著名的中國旅行商問題，取種群規模為50，最大迭代次數為100，Pc=0.3，Pm=0.8。將算法運行了50次，最差解得到15608公里，大多數情況下可以得到最優解15404公里(也是目前中國旅行商問題的最優解)及其附近的解，其中一條最優路線為：北京－哈爾濱－長春－沈陽－天津－濟南－合肥－南京－上海－杭州－臺北－福州－南昌－武漢－長沙－廣州－海口－南寧－貴陽－昆明－成都－拉薩－烏魯木齊－西寧－蘭州－銀川－西安－鄭州－石家莊－太原－呼和浩特。平均占用CPU時間為8.1032s。

3.3結果分析

從上述的TSP實例中可以看出：

(1)兩個規模較小的實例計算都找到了最優解，而且收斂速度非常快。

(2)即使對于規模較大的TSP問題，該改進算法也能很快地找到最優解，而且解的質量非常好，非常穩定，說明了該改進算法具備很強的全局搜索能力。

(3)無論是對稱的TSP問題或是非對稱的TSP問題，該改進算法都可以對其進行求解，說明該改進算法的適應性很廣。

4 結束語

本文提出了一種針對TSP問題的改進遺傳算法。考慮到TSP問題的特點以及傳統的遺傳算法在求解TSP問題上表現出來的收斂速度慢并且易于陷入局部最優解的弱點，文中對傳統的遺傳算法進行了一系列的改進：設計一個新的選擇策略和交叉算子，并且引入了兄弟競爭的策略來加快收斂速度和全局搜索能力。把該算法應用在不同類型的TSP問題的求解上，表現出了比傳統遺傳算法更好的收斂性和計算效率。因此，具有一定的實用價值。