韓鳳嬌

西南大學計算機與信息科學學院 重慶 400715

0 引言

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

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

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

1 遺傳算法介紹

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

遺傳算法的基本運算過程如下：

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

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

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

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

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

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

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

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

2 遺傳編碼與種群初始化

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

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

2.1 適應性函數

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

2.2 選擇算子

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

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

圖1 回路適應性比率

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

2.3 交叉算子

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

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

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

(3) 根據交叉概率pc實施交叉操作，配對個體在交叉位置處互相交換各自的部分內容，之后按照實際問題適當調整，形成一對新個體。

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

表1 交叉操作示例

2.4 變異算子

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

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

3 實例解析

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

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

3.1 初始化實例種群

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

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

3.2 選擇染色體

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

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

3.3 種群變異

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

3.4 實例運算結果

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

圖2 路徑長度隨迭代次數變化曲線

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

4 算法分析與改進

為更有效的、更直接的評價之前的算法，我們將問題規(guī)模擴大，將城鎮(zhèn)數量增大到最初預想的50個。對于已經生成的鄰接矩陣，設定迭代次數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，對應的路徑長度為1555。

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

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

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

圖3 引入最值的適應性函數的性能圖

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

5 利用遺傳算法求解TSP的注意點

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

在利用遺傳算法求解TSP并對其分析改進后，在此總結出如下注意點：

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

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

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

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

6 結論

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

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

[2]鄧輝文.離散數學[M].北京:清華大學出版社.2006.

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

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

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

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

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

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

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

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

[11]邢桂華.用MATLAB實現中國旅行商問題的求解[J].微計算機應用.2004.

[12]周濤.基于改進遺傳算法的 TSP問題研究[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.