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

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

0 引言

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

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

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

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

1 遺傳算法

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

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

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

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

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

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

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

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

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

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

2.1問題的表述和編碼

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

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

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

2.2初始群體的選取

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

2.3適應(yīng)度函數(shù)的構(gòu)造

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

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

2.4選擇策略

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

2.5交叉策略

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

假設(shè)有n個城市1，2，…，n，染色體編碼采用路徑表示?，F(xiàn)有待交叉的雙親：

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

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

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

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

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

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

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

2.6變異策略

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

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

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

2.7算法終止條件和重要參數(shù)選擇

本文設(shè)定一個最大迭代次數(shù)maxgen來結(jié)束算法。maxgen的具體取值要根據(jù)所要解決的TSP問題的具體的城市規(guī)模來確定。

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

2.8實現(xiàn)流程

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

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

(3)若gen>maxgen，則輸出該代中最優(yōu)的個體的適應(yīng)度的倒數(shù)；

(4) gen=gen+1；

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

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

3 實例應(yīng)用驗證

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

3.1非對稱TSP問題仿真實驗

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

3.2對稱TSP問題仿真實驗

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

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

3.3結(jié)果分析

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

(1)兩個規(guī)模較小的實例計算都找到了最優(yōu)解，而且收斂速度非?？臁?/p>

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

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

4 結(jié)束語

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