摘要：旅行商問題(TSP)是遺傳算法得以成功應(yīng)用的典型問題。文章對遺傳算法加以改進(jìn)，提出了新的選擇策略和交叉算子，并且引入了兄弟競爭的策略來加快收斂速度和全局搜索能力。把該算法應(yīng)用在不同類型的TSP問題的求解上，表現(xiàn)出了比傳統(tǒng)遺傳算法更好的收斂性和計(jì)算效率。說明改進(jìn)算法是有效的。關(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ā)點(diǎn)，求其最短行程，即尋找一條巡回路徑。

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

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

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

1 遺傳算法

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

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

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

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

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

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

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

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

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

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

2.1問題的表述和編碼

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

Grefenstette編碼方式在進(jìn)行單點(diǎn)雜交時，左側(cè)部分的旅程-不發(fā)生變化，所以這種方法的適用性存在一定的問題。近鄰表示法的缺點(diǎn)是排列不一定對應(yīng)一合法回路，產(chǎn)生小圈現(xiàn)象，從而使得操作比較復(fù)雜，且遺傳算子打斷好路徑的概率較大，因此，該算法的性能較差。矩陣表示的遺傳操作比較復(fù)雜，并具有盲目性，也未充分利用城市間距離的信息。而路徑表示是旅程對應(yīng)的基因編碼的最自然、簡單和符合邏輯的表示方法，并且由于編碼遍歷了每一個節(jié)點(diǎn)，所以不會產(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)生都采用完全的隨機(jī)方式。本文綜合考慮所采用的路徑編碼的特點(diǎn)以及算法的效率，采用在隨機(jī)產(chǎn)生個體基因的同時加入了對所產(chǎn)生的非法基因判定和啟發(fā)式修改的機(jī)制。所謂的啟發(fā)式修改即找出距離較近的城市。

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

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

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

2.4選擇策略

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

2.5交叉策略

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

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

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

因?yàn)椴捎玫氖锹窂奖硎?，所以將上述染色體看成一個環(huán)，即a_1n的下—個城市為a₁₁。

(1)首先隨機(jī)確定—個當(dāng)前城市currentcity，并將其加入到子代中。假設(shè)產(chǎn)生—個隨機(jī)數(shù)為2，則選出Parl中的第二個城市a₁₂為當(dāng)前的城市，即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)如果左、右鄰接城市中已存在于子代中，選擇不在子代中的左、右次鄰接的城市來進(jìn)行距離的比較。假設(shè)上述的a₁₁已經(jīng)在子代中了，則選取a₁₁的左鄰接城市a_1n(因?yàn)橄鄬τ赾urrentcity=a₁₂來說，a₁₁是a₁₁左鄰接城市)，如果a_1n不在子代中則比較d_a1n，a12。如果在則選擇a_1n的左鄰接城市進(jìn)行距離的比較，依此類推直至所選取的城市不在子代中。

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

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

2.6變異策略

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

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

加入小范圍競爭、擇優(yōu)操作是從加快收斂速度和全局搜索性能兩方面考慮的。具體操作為：對待變異的染色體進(jìn)行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實(shí)現(xiàn)流程

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

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

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

(4) gen=gen+1；

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

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

3 實(shí)例應(yīng)用驗(yàn)證

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

3.1非對稱TSP問題仿真實(shí)驗(yàn)

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

3.2對稱TSP問題仿真實(shí)驗(yàn)

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

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

3.3結(jié)果分析

從上述的TSP實(shí)例中可以看出：

(1)兩個規(guī)模較小的實(shí)例計(jì)算都找到了最優(yōu)解，而且收斂速度非常快。

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

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

4 結(jié)束語

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