周敏

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

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

1 意義和目標(biāo)

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

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

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

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

3 算法理論分析

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

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

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

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

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

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

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

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

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

5 數(shù)據(jù)實(shí)驗(yàn)及結(jié)果

本實(shí)驗(yàn)的硬件環(huán)境：Intel（R） Core（TM）2 Duo CPU T5800 @2。00GHz 1。99GHz，2。00GB的內(nèi)存。本實(shí)驗(yàn)的軟件環(huán)境：Dev-C++編譯器對(duì)程序進(jìn)行編譯執(zhí)行。實(shí)驗(yàn)對(duì)標(biāo)準(zhǔn)的TSPLIB 20個(gè)城市進(jìn)行了計(jì)算，程序輸入的初值為20個(gè)城市的坐標(biāo)（城市數(shù)，城市的橫坐標(biāo)，城市的縱坐標(biāo)）。通過讀取文件input。txt中的20個(gè)城市的坐標(biāo)進(jìn)行計(jì)算，計(jì)算結(jié)果保存在文件out。txt中。程序運(yùn)行時(shí)需在相同目錄下新建文件input。txt和out。txt，將20個(gè)城市的坐標(biāo)放在input。txt中。程序經(jīng)過10次運(yùn)算，計(jì)算結(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é)語

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

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

[參考文獻(xiàn)]

[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問題分段求解算法.計(jì)算機(jī)學(xué)報(bào)[J].2001，24（12）：1329-1333.

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

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

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

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

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

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