遺傳算法求解旅行商問題

程榮

摘 要：旅行商問題是一個(gè)組合優(yōu)化問題，具有重要的實(shí)際意義。而遺傳算法是求解旅行商問題的典型算法之一。本文首先介紹了旅行商問題的定義以及它的研究背景、發(fā)展現(xiàn)狀和常用算法。在此基礎(chǔ)上，詳細(xì)闡述了遺傳算法原理。通過改進(jìn)這些算子，改進(jìn)了傳統(tǒng)的遺傳算法，提高了算法的效率，降低了它的時(shí)間及空間復(fù)雜度。本文使用路徑總長度的倒數(shù)作為適應(yīng)度函數(shù)，保證了解向著最優(yōu)化方向發(fā)展。然后選擇部分交叉算子來產(chǎn)生新個(gè)體，保證了迭代的效率。變異算子利用位點(diǎn)變異，使算法變得簡單，易行。最后，使用MATLAB 語言進(jìn)行編程，解決了城市數(shù)目分別為15和25時(shí)的兩個(gè)實(shí)際問題。通過對(duì)這兩個(gè)問題的收斂速度的對(duì)比、分析，總結(jié)了遺傳算法求解旅行商問題的特點(diǎn)。

關(guān)鍵詞：旅行商問題； 遺傳算法； MATLAB

旅行商問題是優(yōu)化組合問題研究中一個(gè)著名而經(jīng)典的問題，它的研究價(jià)值也就不言而喻。在實(shí)際問題里，一個(gè)大家都熟知的例子就是利用機(jī)器給電路板鉆孔的優(yōu)化設(shè)計(jì)問題。此外旅行商問題的實(shí)際應(yīng)用還體現(xiàn)在交通管理規(guī)劃方面。交通管理的主要的目的是在復(fù)雜的地理網(wǎng)絡(luò)結(jié)構(gòu)中優(yōu)化決定車輛的線路來減少交通費(fèi)用。旅行商問題的應(yīng)用例子還包括：設(shè)計(jì)安全，合理，有效率的交通網(wǎng)，從而減少交通擁堵；如何來規(guī)劃出更好地物流線路，縮小運(yùn)營界產(chǎn)生的成本，減少資源消耗等。

由于旅行商問題具有這么重要的實(shí)際意義，求解旅行商問題算法也就隨之發(fā)展起來。最早的解決方法是線性規(guī)劃，后來陸續(xù)產(chǎn)生了多種求解旅行商問題的算法。其中大致可以分為精確算法，近似算法，智能算法。精確算法：線性規(guī)劃，動(dòng)態(tài)規(guī)劃，分支定界；近似算法包括：插入法，Clark& Wright算法，生成樹算法，最近鄰算法，概率算法等。近年來也出現(xiàn)了許多新的智能算法。像諸如模擬退火，蟻群算法以及遺傳算法等等。

本文首先介紹了什么是旅行商問題，然后簡單介紹了目前解決旅行商問題所用到的一些算法。之后詳細(xì)介紹了什么是遺傳算法，遺傳算法的實(shí)現(xiàn)原理，以及遺傳算法的構(gòu)成。然后利用常用的MATLAB軟件，使用遺傳算法解決了幾個(gè)實(shí)際問題。通過算法以及結(jié)果分析，找出遺傳算法的優(yōu)缺點(diǎn)，并進(jìn)一步提出了改進(jìn)的遺傳算法。

1 旅行商問題

1.1 問題描述

旅行商問題，也叫貨郎擔(dān)問題，目的是求解最優(yōu)線路，是一類經(jīng)典的規(guī)劃類問題。旅行商問題是指，一個(gè)旅行商，要去往n個(gè)不同的城市，需要每個(gè)城市都去，并且僅僅去一次，再回到最初的城市，形成一個(gè)環(huán)路，從眾多可能路徑中求解出一個(gè)最短的路徑。

1.2 數(shù)學(xué)模型

我們將xij設(shè)定為決策變量。沒有直接從城市i到達(dá)城市j的路線，我們將其賦值為xij=0。如果商人直接從城市i到達(dá)城市j，我們用xij=1來表示。我們?cè)谏鲜瞿Ｐ偷玫降?個(gè)式子中，第一個(gè)式子保障了路徑之和最小，第二個(gè)和第三個(gè)式子分別保障從某個(gè)城市出來和進(jìn)入都只是一次。而第四個(gè)式子則保障了走過的所有路徑都沒有回路。其中C表示集合C中元素個(gè)數(shù)。

2 算例分析

2.1 問題描述

一個(gè)旅行商人要從某一個(gè)城市出發(fā)，經(jīng)過所有的城市，并且每個(gè)城市只能走一次。最終回到出發(fā)的城市，求解一個(gè)最短路徑。

2.2 問題分析

1）編碼方式。

我們這里使用十進(jìn)制編碼方式。把旅行商途經(jīng)的城市的順序序號(hào)作為遺傳算法的編碼。假設(shè)15 個(gè)城市的序號(hào)為1，2，…，15，那么它的任意一個(gè)全排列i1，i2，…，i15就是一個(gè)數(shù)據(jù)編碼，表示一個(gè)染色體，每個(gè)染色體就代表一個(gè)解，不同解是靠染色體上不同的基因i決定的。

2）適應(yīng)度函數(shù)。

由于旅行商問題的規(guī)劃模型的目標(biāo)函數(shù)是要求解最小值，所以適應(yīng)度函數(shù)就用路徑的總長度的倒數(shù)來表示。這樣，符合了遺傳算法的優(yōu)勝略汰的搜索策略。

3）初始群體的產(chǎn)生。

隨機(jī)生產(chǎn)一個(gè)大小為N且每條染色體上的基因長度都是的n初始種群，作為第一代個(gè)體。

4）選擇過程。

我們需要構(gòu)造一個(gè)∑f（xi）合適的隸屬函數(shù)p=f（xi）∑f（xi）。然后計(jì)算出種群中每個(gè)遺傳個(gè)體的適應(yīng)度f（xi），從而得到種群中遺傳個(gè)體適應(yīng)度的和。那么我們就可以用來表示個(gè)體被選中的概率。

5）交叉過程。

首先設(shè)定交叉概率pc=0.9。其次，根據(jù)這一概率，選出要進(jìn)行交叉操作的個(gè)體，并將它們兩兩配對(duì)。然后在染色體上1～n-1個(gè)基因編號(hào)之間隨機(jī)地選出兩個(gè)，之間的基因作為接下來將要進(jìn)行交叉的對(duì)象。

6）變異過程。

進(jìn)行完交叉操作后，以變異概率pm=0.2從群體中選出要進(jìn)行變異的遺傳個(gè)體。然后，隨機(jī)地從1～n-1之間選擇兩個(gè)數(shù)作為變異點(diǎn)，將基因進(jìn)行交換。

7）復(fù)制操作。

復(fù)制過程就是將適應(yīng)度值打的個(gè)體直接復(fù)制到下一代，從而不至于丟掉性質(zhì)較優(yōu)的解。

2.3 問題求解結(jié)果

將程序放到MATLAB軟件中執(zhí)行，得到了如下結(jié)果：

2.3.1 城市數(shù)為15時(shí)的運(yùn)行結(jié)果

（1）隨機(jī)產(chǎn)生的初始解的路徑總長度為4.7950e+004。

（2）迭代次數(shù)設(shè)置為c=100時(shí)的最優(yōu)解路徑的總長度為：2.5025e+004。

可以看出，迭代100次，產(chǎn)生了不錯(cuò)的優(yōu)化效果。

但這是不是接近最終的最優(yōu)解呢？下面我們又將迭代次數(shù)設(shè)置為了C=200，路徑總長度為：2.4619e+004。

通過兩結(jié)果進(jìn)行比較知，迭代100次時(shí)基本上得到了近似最優(yōu)解，而且迭代次數(shù)越多，得到的解越優(yōu)。

2.3.2 城市數(shù)為25時(shí)的運(yùn)行結(jié)果

（1）隨機(jī)產(chǎn)生的初始解路徑總長度1.1297e+005。

（2）迭代次數(shù)設(shè)置為c=100時(shí)的最優(yōu)解路徑總長度為46737e+004。

（3）迭代次數(shù)設(shè)置為C=300時(shí)路徑總長度為：4.5038e+004。

容易看出，當(dāng)城市的個(gè)數(shù)增加到25個(gè)時(shí)，迭代100次產(chǎn)生的結(jié)果與最優(yōu)解的偏差還有點(diǎn)大，需要繼續(xù)迭代。

繼續(xù)進(jìn)行迭代次數(shù)為500時(shí)的實(shí)驗(yàn)，路徑總長度為： 44838e+004。這一結(jié)果接近200次迭代的解。也就是當(dāng)?shù)螖?shù)到200次時(shí)，為近似最優(yōu)解。

2.4 結(jié)果評(píng)價(jià)

通過運(yùn)用遺傳算法對(duì)上面兩個(gè)問題（城市數(shù)分別為15和25）求解結(jié)果可以看出，運(yùn)用遺傳算法能夠求解旅行商問題。對(duì)于同一個(gè)問題，隨著搜索次數(shù)的增多，所得到的解一般會(huì)在一定范圍內(nèi)波動(dòng)，并且越來越好。但當(dāng)增加到某一值時(shí)，函數(shù)的收斂會(huì)趨于平緩（這時(shí)可以認(rèn)為達(dá)到了最優(yōu)解）。通過15個(gè)樣本城市和25個(gè)樣本城市的迭代求解過程可以發(fā)現(xiàn)，當(dāng)我們的樣本數(shù)量比較多時(shí)，我們需要的循環(huán)搜索的次數(shù)就越多，求解完成需要的時(shí)間就越長。而且，通過上面的結(jié)果對(duì)比表我們可以發(fā)現(xiàn)，遺傳算法求解過程中，初始解是隨機(jī)產(chǎn)生的，對(duì)于每一次的求解，初始解的不同，問題收斂的情況也就不同，產(chǎn)生的最終解也不同。由此可見，遺傳算法對(duì)初始解比較敏感，而且由于初始解是算法隨機(jī)生成，不能人為控制，所以不容易把握。

參考文獻(xiàn)：

[1]于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策，2014（8）：1483-1488.

[2]威廉·J·庫克，J.Cook，郭凱聲.旅行商問題[J].環(huán)球科學(xué)，2012（7）：19.

[3]章新華.遺傳算法及其應(yīng)用[J].火力與指揮控制，1997，18（4）：59-64.

[4]吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2004，21（2）：69-73.

[5]梁艷春，馮大鵬，周春光.遺傳算法求解旅行商問題時(shí)的基因片段保序[J].系統(tǒng)工程理論與實(shí)踐，2000，20（4）：7-12.

[6]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].國防工業(yè)出版社，1999.

[7]李敏強(qiáng)，徐博藝.遺傳算法與神經(jīng)網(wǎng)絡(luò)的結(jié)合[J].系統(tǒng)工程理論與實(shí)踐，1999，19（2）：65-69.