韓鳳嬌

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

0 引言

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

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

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

1 遺傳算法介紹

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

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

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

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

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

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

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

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

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

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

2 遺傳編碼與種群初始化

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

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

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

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

2.2 選擇算子

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

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

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

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

2.3 交叉算子

交叉操作一般分為如下幾個(gè)步驟：

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

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

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

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

表1 交叉操作示例

2.4 變異算子

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

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

3 實(shí)例解析

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

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

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

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

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

3.2 選擇染色體

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

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

3.3 種群變異

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

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

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

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

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

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

為更有效的、更直接的評(píng)價(jià)之前的算法，我們將問(wèn)題規(guī)模擴(kuò)大，將城鎮(zhèn)數(shù)量增大到最初預(yù)想的50個(gè)。對(duì)于已經(jīng)生成的鄰接矩陣，設(shè)定迭代次數(shù)800，交叉概率pc為0.8，變異概率pm為0.005，種群大小為75。最終求得一個(gè)解回路為：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，對(duì)應(yīng)的路徑長(zhǎng)度為1555。

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

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

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

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

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

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

[6]張春霞,王蕊.基于遺傳算法求解 TSP問(wèn)題的算法設(shè)計(jì)[J].安陽(yáng)工學(xué)院學(xué)報(bào).2007.

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

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

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

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

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

[12]周濤.基于改進(jìn)遺傳算法的 TSP問(wèn)題研究[J].微電子學(xué)與計(jì)算機(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.