遺傳算法求解TSP的研究

周敏

摘 要：遺傳算法通常被認為是自適應(yīng)的隨機搜索算法，與傳統(tǒng)的優(yōu)化方法（枚舉，啟發(fā)式等）相比較，以生物進化為原型，具有很好的收斂性。文章用遺傳算法求解經(jīng)典的旅行商問題，最后使用實驗對算法進行了測試，能夠在短時間內(nèi)找到理想的解。

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

1 意義和目標

文章提出用遺傳算法求解TSP這個古老而有挑戰(zhàn)性的NP問題，利用遺傳算法的原理對個城市進行編碼，從一組隨機產(chǎn)生的初始解開始搜索，種群中的每個染色體是問題的一個解的編碼串，這些染色體在后續(xù)迭代中不斷進化，運算過程中計算每個個體的適應(yīng)度來衡量染色體的好壞。遺傳和變異過程中，根據(jù)選擇規(guī)則選擇部分后代，同時淘汰部分后代，最后算法收斂于最好的染色體，可能是TSP的最優(yōu)解。

2 國內(nèi)外研究現(xiàn)狀

目前對遺傳算法的研究大部分是從算子出發(fā)，提出各種雜交算子，但這些算子一般在實際使用中需要花費較大的工作量，比如已有的OX，PMX，SSX，ERX，CSEX和DPX等。還有其他一種變異算子，這種變異算子以顛倒作為基石，它的工作效率比較高，但也有自身的缺點，就是具有一定的隨機性，從而實現(xiàn)不了對團體中的個別的消息進行再次構(gòu)建。所以，由Michalewicz和郭濤根據(jù)以上兩類算子的優(yōu)缺點進行了結(jié)合，得到了一種比較適合的算子，這種算子叫做Inver-Over，這種算子能夠容易獲取，查找領(lǐng)域?qū)?，它的基本思路是：旅行商問題的核心參數(shù)是城市之間的邊，卻不是這些城市的具地理位置。

另外一些研究者為了提高群體的質(zhì)量，發(fā)明了疫苗，通常稱之為疫苗算法，而這種是一種基因庫的觀念，這種觀念是錄制好基因的集合，通過路徑抓舉、灌輸疫苗來實現(xiàn)的。量子遺傳算法（Q GA）在求解數(shù)值和組合優(yōu)化問題時效率明顯優(yōu)于傳統(tǒng)進化算法，但目前較多被用于求解組合優(yōu)化的背包問題，為了充分發(fā)揮Q GA的優(yōu)點，文中用其求解TSP這一經(jīng)典的NP難問題。首先，文中設(shè)計了一種利用幾率幅值編碼的新的編碼方式，即利用幾率幅值編碼的量子個體與一組向量對應(yīng)，而此向量又與一條可行路徑一一對應(yīng)。這樣的編碼方式不僅縮小了種群規(guī)模，占用較少內(nèi)存，所得的解均可行，而且有效地增強了種群的多樣性；其次，為了繼承比較優(yōu)秀的基因集，通過對量子進行雜交，并且是在量子的個體上的操作來實現(xiàn)的；最后，通過加上兩步的查找，并且是局部查找，從而降低了算法的收斂時間，第一階段主要針對實例中排列稀疏處的城市進行優(yōu)化，第二階段在第一階段的基礎(chǔ)上著重對排列密集處的城市優(yōu)化。據(jù)此，設(shè)計了解TSP的一個新的高效的QGA，并證明了其以概率1收斂到全局最優(yōu)解；測定算法性能的數(shù)值。

3 算法理論分析

達爾文著名的自然選擇學(xué)說，是遺傳算法的來源理論，該算法是一種迭代搜索算法。達爾文的自然選擇學(xué)說認為：生物的變異一般不是定向的，而自然選擇是定向的，只有那些能適應(yīng)環(huán)境的變異類型才能生存下來，產(chǎn)生后代，而那些與環(huán)境不相適應(yīng)的變異類型將可能被淘汰。在自然環(huán)境中，每種生物都有自己的適應(yīng)能力，適應(yīng)能力的不同揭示了不同生物的繁衍能力。

最原始的遺傳算法中，僅僅包含三種最基本的遺傳算子，也就是選擇算子、交叉算子和變異算子，這種最原始的遺傳算法工作的過程是非常簡單的，并且較為人們學(xué)習(xí)，它也是其他的后來發(fā)展的遺傳算法的祖輩。

⑴最原始的遺傳算法的組成部分。遺傳算法中最基本的就是染色體了，它是利用二進制編碼的0和1組成的符號串來表示的，也就是說它的等位基因是由零和一構(gòu)成的。而最初的狀態(tài)下，0和1的符號串是可以隨機的來生成染色體的。

⑵群體中的個體對環(huán)境的適應(yīng)性的得分。決定是否遺傳的概率的大小，這個值是由個體的自適應(yīng)性的大小決定的，可以說，自適應(yīng)行越高，那么遺傳的概率也就越高。這里，要得到這個遺傳的概率，那么初始狀態(tài)下，必須讓每個個體的適應(yīng)性的得分為0或者是大于0的數(shù)。所以，我們必須確定自適應(yīng)性與遺傳的概率的之間的正確規(guī)則。

⑶遺傳算子：這里我們只談到了三個最基本的遺傳算子：使用比例選擇算子的是選擇算子；使用單點交叉算子的是交叉算子；使用基本位變異算子或均勻位變異算子是變異算子。

⑷每一種算法都有自己的參數(shù)，那么遺傳算法的參數(shù)包括以下：M：群體中的個體的總數(shù)是多少，也就是說，群體的多少問題；S：作為遺傳算法，它在進化過程中，什么時候停止的問題；Pc：這是指交叉的概率；Pm：這是指變異的概率。

4 算法的技術(shù)路線

（1）編寫代碼，用代碼來回答問題。（2）模擬一個原始的群體，這個群體的規(guī)模是固定的。（3）這一步需要計算每個個體的適應(yīng)性程度，前面已經(jīng)講到了，適應(yīng)度大，那么個體就好，適應(yīng)度小，那么個體就差。（4）若終止條件T（a：最優(yōu)個體保持20代不變；b：t>500；c：平均適應(yīng)度與最優(yōu)個體適應(yīng)度之差小于e，e是任意小的正實數(shù)；只要滿足其中一條就終止）滿足，則算法終止；否則，計算概率

并以概率pi從P（t）中隨機選取一些個體構(gòu)成一個種群RP（t）。（5）為了得到一個新的交叉后的種群，應(yīng)該由交叉概率獲取。最后再以概率pm，再進行變異，從而生成一個新的種群P（t+1）。（6）t=t+1，如不滿足終止條件轉(zhuǎn)（3）。

5 數(shù)據(jù)實驗及結(jié)果

本實驗的硬件環(huán)境：Intel（R） Core（TM）2 Duo CPU T5800 @2。00GHz 1。99GHz，2。00GB的內(nèi)存。本實驗的軟件環(huán)境：Dev-C++編譯器對程序進行編譯執(zhí)行。實驗對標準的TSPLIB 20個城市進行了計算，程序輸入的初值為20個城市的坐標（城市數(shù)，城市的橫坐標，城市的縱坐標）。通過讀取文件input。txt中的20個城市的坐標進行計算，計算結(jié)果保存在文件out。txt中。程序運行時需在相同目錄下新建文件input。txt和out。txt，將20個城市的坐標放在input。txt中。程序經(jīng)過10次運算，計算結(jié)果最優(yōu)值為：25。800371507 ，具體的路徑為： 8 4 2 17 6 20 13 5 16 18 7 19 10 15 9 12 3 1 14 11。

6 結(jié)語

該算法對求解大型的TSP性能不優(yōu)，后續(xù)工作主要是研究優(yōu)化的遺傳算法求解大型的TSP。遺傳算法具備自身很多的優(yōu)點，尤其是同傳統(tǒng)的一些優(yōu)化方法進行比較的時候，因為遺傳算法具有非常優(yōu)秀的收斂性，并且工作的時間上花費較少，在工作的精準度上也比較優(yōu)秀。具體的優(yōu)點在實踐中的應(yīng)用可以看出來，特別是在文章中的旅行商問題的解決上可以看出來。但就像前述講過的，在解決大規(guī)模的問題上，可能遺傳算法就會遜色很多了。

實驗過程中對于如何確定GA有關(guān)參數(shù)最佳范圍是一個難題，如迭代次數(shù)的選擇和運行時間兩方面的權(quán)衡問題，以及遺傳概率和變異概率的選擇等。后續(xù)的工作是尋求優(yōu)化的遺傳算法對TSP進行求解。

[參考文獻]

[1]Grover L K.A fast quant um mechanical algorithm for database search/ /Proceedings of the 28th ACM Sympium Theory Computing.Philadelphia，Pennsylvania，USA，1996：212-219.

[2]Deut sch D，Jozsa R.Rapid solution of problems by quantum computation/ / Proceedings of t he Royal Society London A.London，UK，1992，439：553-558.

[3]吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法.計算機學(xué)報[J].2001，24（12）：1329-1333.

[4]楊輝，康立山，陳毓屏.一種基于構(gòu)建基因庫求解TSP問題的遺傳算法[J].計算機學(xué)報，2003，26（12）：1753-1758.

[5]周智，萬穎瑜，陳國良，等.基于局部最優(yōu)解的歸約算法：一般方法和在TSP問題上的應(yīng)用[R].合肥：國家高性能計算中心，1999.

[6]康立山，謝云，尤矢勇，等.非數(shù)值并行算法（第一冊）：模擬退火算法[M].北京：科學(xué)出版社，1997.

[7]趙春英，張鈴.求解貨郎擔問題（TSP）的佳點集遺傳算法[J].計算機工程與應(yīng)用，2001，37（3）：83-84.

[8]朱文興，傅清祥.一個基于填充函數(shù)變換的對稱TSP問題的局部搜索算法[J].計算機學(xué)報，2002，25（7）：701-707.

[9]王偉.人工神經(jīng)網(wǎng)絡(luò)原理與應(yīng)用[M].北京：北京航空航天大學(xué)出版社，1995.