一種基于遺傳算法求解TSP問題的優(yōu)化算法

韓鳳嬌

西南大學(xué)計算機(jī)與信息科學(xué)學(xué)院 重慶 400715

0 引言

旅行商問題是經(jīng)典組合優(yōu)化問題，也是一個NP完全問題。它的求解會隨著問題規(guī)模擴(kuò)大而導(dǎo)致求解時間急速增長。為此我們可以利用遺傳算法這一智能的算法，來試圖獲得問題的較優(yōu)解，并通過反復(fù)改進(jìn)實(shí)驗最終尋求較快較優(yōu)解決方法。

TSP即旅行商問題或稱貨郎擔(dān)問題，該問題描述為：有n個城鎮(zhèn)，其中任意兩個城鎮(zhèn)間都有道路(若沒有則規(guī)定該邊上的權(quán)值為+∞)。一個售貨員要去這n個城鎮(zhèn)售貨，從某城鎮(zhèn)出發(fā)，一次訪問其余n-1個城鎮(zhèn)且每個城鎮(zhèn)只能訪問一次，最后又回到原出發(fā)地。問售貨員要如何安排經(jīng)過n個城鎮(zhèn)的行走路線才能使他走過的路程最短。

求解旅行商問題，其實(shí)質(zhì)是在一個賦權(quán)圖中尋找一條權(quán)值最小的哈密爾頓回路。哈密爾頓回路是指：有任意圖G=(V，E)，G中進(jìn)過所有節(jié)點(diǎn)一次且僅一次(除起點(diǎn)重復(fù)一次)的圈。從中也可以看出，旅行商問題是一個最優(yōu)化的求解問題，它要求問題的解滿足以下三點(diǎn)：(1)它必須是一條回路；(2)該回路能夠經(jīng)過每個事先給出的城鎮(zhèn)且不重復(fù)訪問已經(jīng)過的城鎮(zhèn)；(3)回路的路徑長度是所有可以滿足(1)、(2)的若干回路中最短的。

1 遺傳算法介紹

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進(jìn)化規(guī)律(適者生存，優(yōu)勝劣汰遺傳機(jī)制)演化而來的隨機(jī)化搜索方法。它是由美國的J.Holland教授1975年首先提出，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理和人工生命等領(lǐng)域。

遺傳算法的基本運(yùn)算過程如下：

(1) 編碼：針對要求解的問題，對可能的解用數(shù)串等方式進(jìn)行編碼，如二進(jìn)制串等；

(2) 初始化：設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成N個體作為初始群體P(0)；

(3) 適應(yīng)性評價：計算群體P(t)中每個個體的適應(yīng)度，為其后的選擇、交叉、變異做準(zhǔn)備；

(4) 選擇操作：將選擇算子作用于群體。從而把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代；

(5) 交叉操作：將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作，這是遺傳算法的核心；

(6) 變異操作：將變異算子作用于群體。即是對群體中的個體串的某些基因位置上的基因值作變動；群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t+1)。

(7) 終止條件判斷：若t=T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。

從上述可知，當(dāng)城鎮(zhèn)數(shù)量增加，問題規(guī)模擴(kuò)大時，將難以在有限的時間內(nèi)保證得到旅行商問題的最優(yōu)解。然而，在實(shí)際應(yīng)用中，我們?nèi)羰菬o法得到最優(yōu)的結(jié)果，往往希望得到一個較優(yōu)的結(jié)果來代替它。因此，我們最終希望能夠在城鎮(zhèn)數(shù)量為50或以上的問題中得到良好的結(jié)果。

2 遺傳編碼與種群初始化

利用遺傳算法求解問題，我們先將城鎮(zhèn)從1開始順序編號，以此作為一個單獨(dú)的元素，利用一個長度等于城鎮(zhèn)數(shù)量n且元素兩兩不同的數(shù)字串表示一條回路進(jìn)行染色體編碼。對于路徑A1A2A3……An-2An-1An表示依次經(jīng)過城鎮(zhèn)A1、A2、A3……An-2、An-1、An最后由An回到始點(diǎn)A1。在所使用的實(shí)驗平臺MATLAB中，提供了一個極其有效的函數(shù)randperm(n)，該函數(shù)能夠產(chǎn)生一個n個元素的排列，恰好與我們的編碼方式對應(yīng)。

另外，為了保持初試種群的多樣性，我們可以將初始種群的染色體數(shù)量控制在問題規(guī)模n與2n之間。

2.1 適應(yīng)性函數(shù)

適應(yīng)性函數(shù)值是評價一個染色體好壞的依據(jù)，具有良好適應(yīng)性的染色體應(yīng)當(dāng)在遺傳過程中具有更高的存活能力。就該問題而言，由于TSP要求得到一條路徑較短的回路，那么路徑長度較短的回路應(yīng)該具有更高的適應(yīng)性，存在負(fù)相關(guān)。為此，我們可以將路徑的倒數(shù)作為適應(yīng)性函數(shù)值，也就是令染色體x的適應(yīng)性函數(shù)為， RouteLength表示回路的長度：

2.2 選擇算子

計算完各染色體的適應(yīng)性之后，就應(yīng)當(dāng)以它們的適應(yīng)性函數(shù)值為依據(jù)對染色體進(jìn)行選擇。在這里，我們選常用的輪賭選擇方法。比率的計算公式如下：

其中，r(xi)為第i個染色體的比率，f(xi)為第i個染色體的適應(yīng)性函數(shù)值，n為種群染色體總數(shù)。染色體適應(yīng)性越好，比率越大，被選中的概率也就越大。由以上公式得到的回路適應(yīng)性比率可以構(gòu)成一個總和為 100%的輪盤，通過輪盤指針旋轉(zhuǎn)確定所選染色體。若指針取值屬于區(qū)間(0，1)且上述示例對應(yīng)輪盤圖1所示，則可以方便的確認(rèn)當(dāng)下指針?biāo)鶎?yīng)該選取的染色體。

圖1 回路適應(yīng)性比率

例如，當(dāng)指針取值為0.8時，由于71.99% < 0.8 = 80% <84.86%，因而該取染色體4。

2.3 交叉算子

交叉操作一般分為如下幾個步驟：

(1) 從待交配的種群中選取要交配的一對個體；

(2) 根據(jù)位串長度 L，對要交配的一對個體隨機(jī)選取一個或多個交叉位置；

(3) 根據(jù)交叉概率pc實(shí)施交叉操作，配對個體在交叉位置處互相交換各自的部分內(nèi)容，之后按照實(shí)際問題適當(dāng)調(diào)整，形成一對新個體。

通常使用的遺傳算子又包括一點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、一致交叉，這里我們選擇一種一點(diǎn)交叉的方式來完成該步操作。以下我們舉例說明這種交叉方式，為方便理解，選取路徑長度(城鎮(zhèn)個數(shù))為 8，交叉的兩個元素分別加以標(biāo)記，具體操作如表1所示。

表1 交叉操作示例

2.4 變異算子

變異是遺傳算法的又一必要操作，也是保持種群多樣性的有效手段。當(dāng)然，變異在遺傳過程中并不是經(jīng)常出現(xiàn)的，因而變異概率pm一般取的很小。

對于TSP，染色體的變異與之前的交叉操作類似，某個元素的改變(變?yōu)榕c自身不相等的另一個元素)必然無法保持回路特性，因而需要進(jìn)行調(diào)整。例如，染色體1-2-3-4-5-6-7-8在第6位發(fā)生變異，不妨設(shè)由元素2取代它看，之

3 實(shí)例解析

由于城鎮(zhèn)數(shù)量太大，會因染色體過長而導(dǎo)致問題求解過程的敘述過于冗長，不利于直觀的理解。而問題規(guī)模的大小對算法的思想并沒有直接的影響，故在此僅以一個 10城鎮(zhèn)的無向圖作為例子進(jìn)行求解。通過分析城鎮(zhèn)數(shù)，我們產(chǎn)生一個鄰接矩陣D如下所示：

在此我們選擇交叉概率pc=0.8，變異概率pm=0.005，初始種群大小為20，而迭代次數(shù)定為200次。

3.1 初始化實(shí)例種群

通過相應(yīng)的函數(shù)我們可以得到一個大小為 20的初始化種群，在TSP問題中每條回路的路徑長度等于回路各邊權(quán)值的總和，例如任意一條回路 i1-i2-i3-i4-i5-i6-i7-i8-i9-i10，路徑長度dtotal對應(yīng)的數(shù)學(xué)表達(dá)式為：

針對第一條路徑 1-5-6-4-7-9-8-2-3-10，它的路徑長度dtotal=8+44+12+16+70+76+75+25+4+53 =383。以此類推，我們可以得到各個染色體的適應(yīng)性。

3.2 選擇染色體

該步驟中，利用函數(shù)rand隨機(jī)生成0到1內(nèi)的數(shù)據(jù)，根據(jù)輪盤算法原理，重復(fù)20次后可以得到第1代種群。

將種群中兩兩配對在既定的交叉概率下進(jìn)行交叉操作，即染色體1與2配對，3與4配對……依此類推，若種群中染色體個數(shù)為奇數(shù)，則最后一個染色體保留。經(jīng)過此操作，我們可以得到第一代染色體交叉后的結(jié)果。

3.3 種群變異

首先確定一個要變異的位置P1，之后隨機(jī)生成一個與該位置上元素不同的另一元素E，找到元素E的位置P2，最后交換P1、P2上的元素。例如，4-7-3-8-1-9-10-6-2-5選取了位置 P1為9，隨機(jī)產(chǎn)生的元素E為7對應(yīng)位置P2為2，標(biāo)記后的位串此操作，我們可以得到第一代染色體變異后的結(jié)果。

3.4 實(shí)例運(yùn)算結(jié)果

依照以上步驟迭代指定次數(shù)后，最終得到路徑為6-5-1-10-9-3-2-7-8-4，路徑長度為214。對該實(shí)例重復(fù)運(yùn)算多次后，偶爾有路徑長度212的回路出現(xiàn)，但概率較低，從而可以認(rèn)定該結(jié)果為一個較優(yōu)解。此外，我們在程序中還設(shè)置了最小路徑長度向量及平均路徑長度向量分別記錄每次迭代中的最短和平局路徑長度，由此繪制出平均路徑長度與最短路徑長度隨迭代次數(shù)變化的曲線如圖2。

圖2 路徑長度隨迭代次數(shù)變化曲線

由上面的變化曲線圖我們可以看到，迭代過程中最小和平均路徑長度函數(shù)曲線卻表現(xiàn)出一種不穩(wěn)定性，其波動顯示該算法的求解存在一定的瑕疵。當(dāng)城鎮(zhèn)數(shù)量增加時，能否得到較優(yōu)解還未定。

4 算法分析與改進(jìn)

為更有效的、更直接的評價之前的算法，我們將問題規(guī)模擴(kuò)大，將城鎮(zhèn)數(shù)量增大到最初預(yù)想的50個。對于已經(jīng)生成的鄰接矩陣，設(shè)定迭代次數(shù)800，交叉概率pc為0.8，變異概率pm為0.005，種群大小為75。最終求得一個解回路為：19-48-50-44-25-41-15-11-28-42-35-12-26-22-32-9-37-4-20-36-8-46-38-40-43-27-29-45-2-24-17-39-1-18-7-30-31-14-21-3-16-5-10-49-34-23-13-47-33-6，對應(yīng)的路徑長度為1555。

利用路徑長度的倒數(shù)作為適應(yīng)性函數(shù)能夠解決適應(yīng)性與路徑長度負(fù)相關(guān)的問題?？陕窂介L度一般較長，尤其是問題規(guī)模擴(kuò)大時，不同的路徑長度所對應(yīng)的適應(yīng)性函數(shù)值部分過大部分過小，最后導(dǎo)致輪賭選擇時個別不同染色體被選取的可能性相差甚遠(yuǎn)。

任意一個種群的各個路徑長度中，必然存在最大值與最小值，于是考慮讓路徑長度最短的回路取得適應(yīng)性為 1，而最長的回路取得適應(yīng)性為0，其他回路則介于0和1之間。那么得到新的適應(yīng)性函數(shù)為：

再來看之前的例子，適應(yīng)性依次為：1、0.75、0.5、0.25、0，被選概率為 40%、30%、20%、10%和 0%。表現(xiàn)出線性遞減的特性，并且淘汰了路徑長度最長的回路。再次運(yùn)行程序查看性能圖(如圖3所示)。

圖3 引入最值的適應(yīng)性函數(shù)的性能圖

該圖像中有一明顯的向下尖峰，且較之前有更多最小路徑長度點(diǎn)位于1800以下，就此決定選用該函數(shù)為新的適應(yīng)性函數(shù)。

5 利用遺傳算法求解TSP的注意點(diǎn)

遺傳算法借鑒了生物遺傳的思想，選擇、交叉、變異就是遺傳算法的關(guān)鍵所在，其中尤以交叉操作影響最大。若是交叉方式不當(dāng)，導(dǎo)致迭代結(jié)果無法收斂，則會使算法陷入僵局，算法也就失去了意義。這也意味著，交叉算子的選取是重中之重！

在利用遺傳算法求解TSP并對其分析改進(jìn)后，在此總結(jié)出如下注意點(diǎn)：

(1) 選擇良好的適應(yīng)性函數(shù)。適應(yīng)性的好壞，本質(zhì)上是由回路自身決定的，如何恰如其分的量化這種優(yōu)劣程度，使其具有較好的區(qū)分度是一個適應(yīng)性函數(shù)所必備的性質(zhì)；

(2) 必須使用收斂的交叉算子。研究者無論是利用該算法求解還是進(jìn)一步改進(jìn)，在設(shè)計交叉操作時，若不能保證算子收斂，很有可能導(dǎo)致求解功虧一簣；

(3) 保證一定的種群多樣性。種群多樣性的存在，能夠幫助在交叉等操作中得到更優(yōu)的子代，從而突顯出遺傳算法的價值。

總之，要利用遺傳算法求解TSP，必須在掌握基礎(chǔ)理論及操作的基礎(chǔ)上，盡量保持原有的優(yōu)良性征，恰當(dāng)評價，合理改進(jìn)算子，保證算法收斂。

6 結(jié)論

本次研究過程中，通過對遺傳算法核心思想的思考，在解決TSP問題上得到了啟發(fā)。因為最初適應(yīng)性函數(shù)及交叉算子選取不當(dāng)，導(dǎo)致在選擇操作和交叉操作分別出現(xiàn)無法合理區(qū)分和無法有效收斂的現(xiàn)象。此后，一方面通過改進(jìn)適應(yīng)性函數(shù)，增加區(qū)分度加強(qiáng)了選擇的有效性；另一方面利用改進(jìn)順序交叉算子并大膽采用淘汰機(jī)制，保證并加快了收斂能力。最終通過幾方面的結(jié)合，改進(jìn)原有算法，達(dá)到了有限時間內(nèi)求取較優(yōu)解目的。

[1]畢曉君.信息智能處理技術(shù)[M].北京:電子工業(yè)出版社.2010.

[2]鄧輝文.離散數(shù)學(xué)[M].北京:清華大學(xué)出版社.2006.

[3]任春玉.基于混合遺傳算法的TSP問題優(yōu)化研究[J].哈爾濱商業(yè)大學(xué)學(xué)報.2007.

[4]Negnevistsky,M.顧力栩,沈晉惠譯.人工智能——智能系統(tǒng)指南[M].北京:機(jī)械工業(yè)出版社.2010.

[5]劉雁兵,劉付顯.基于遺傳算法的 TSP問題求解與仿真[J].電光與控制.2007.

[6]張春霞,王蕊.基于遺傳算法求解 TSP問題的算法設(shè)計[J].安陽工學(xué)院學(xué)報.2007.

[7]鄭阿奇.MATLAB實(shí)用教程[M].北京:電子工業(yè)出版社.2004.

[8]李飛,白艷萍.用遺傳算法求解旅行商問題[J].中北大學(xué)學(xué)報.2007.

[9]劉青鳳,李敏.基于遺傳算法的TSP問題優(yōu)化求解[J].計算機(jī)與現(xiàn)代化.2008.

[10]翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解 TSP問題[J].淮南師范學(xué)院學(xué)報.2009.

[11]邢桂華.用MATLAB實(shí)現(xiàn)中國旅行商問題的求解[J].微計算機(jī)應(yīng)用.2004.

[12]周濤.基于改進(jìn)遺傳算法的 TSP問題研究[J].微電子學(xué)與計算機(jī).2004.

[13]Merz P.A comparison of memetic recombination operators for the traveling salesman problem[A].Proceedings of the Genetic and Evolutionary Computation Conference(GECCO).2002.