基于遺傳算法解決TSP問題[1]

1、遺傳算法求解TSP問題的MATLAB實現(xiàn)Flash 摘要：旅行商問題（TSP）是一個經(jīng)典的優(yōu)化組合問題，本文采用遺傳算法來求解TSP問題，深入討論了遺傳算法解決TSP問題的求解過程，并通過MATLAB對算法進行了實現(xiàn)，最后對實驗結(jié)果進行分析，并與粒子群算法進行對比和分析。關(guān)鍵字：TSP；遺傳算法；粒子群算法0.引言旅行商問題是一個經(jīng)典的優(yōu)化組合問題，它可以擴展到很多問題，如電路布線、輸油管路鋪設(shè)等，但是，由于TSP問題的可行解數(shù)目與城市數(shù)目N是成指數(shù)型增長的，是一個NP難問題，因而一般只能近似求解，遺傳算法（GA）是求解該問題的較有效的方法之一，當然還有如粒子群算法，蟻群算法，神經(jīng)網(wǎng)絡(luò)算法等優(yōu)

2、化算法也可以進行求解。遺傳算法是美國學(xué)者Holland根據(jù)自然界“物競天擇，適者生存”現(xiàn)象而提出的一種隨機搜索算法，本文采用MATLAB來實現(xiàn)遺傳算法解決TSP問題。1.旅行商問題旅行商問題可以具體描述為：已知n個城市之間的相互距離，現(xiàn)有一個推銷員從某一個城市出發(fā)，必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回到出發(fā)城市，如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短。用圖論術(shù)語來表示，就是有一個圖g=(v,e),其中v是定點5，e是邊集，設(shè)d=(dij)是有頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的最短距離的回

3、路。若對與城市v=v1,v2,v3vn的一個訪問順序為t=(t1,t2,t3,tn)，其中tiv(i=1,2,.n),且記tn+1=t1,則旅行上問題的數(shù)學(xué)模型為式1： （1）2.遺傳算法與粒子群算法2.1遺傳算法 遺傳算法的基本原理是通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題，它需要對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)度值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會，在遺傳算法中，通過隨機方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加遺傳操作，經(jīng)過遺產(chǎn)操作后的個體集合形成下一代新的

4、種群，對這個新的種群進行下一輪的進化。2.2遺傳算法的過程遺傳算法的基本過程是：1. 初始化群體。2. 計算群體上每個個體的適應(yīng)度值3. 由個體適應(yīng)度值所決定的某個規(guī)則選擇將進入下一代個體。4. 按概率Pc進行交叉操作。5. 按概率Pm進行變異操作。6. 沒有滿足某種停止條件，則轉(zhuǎn)第2步，否則進入第7步。7. 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)界。停止條件有兩種：一是完成了預(yù)先給定的進化代數(shù)則停止；二是種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進時停止。遺傳算法過程圖如圖1：圖1：遺傳算法過程框圖3.遺傳算法MATLAB代碼實現(xiàn)遺傳算法中控制參數(shù)如

5、下： Clist城市的坐標，dislist城市距離矩陣，inn初始種群的大小，gnmax最大代數(shù)，pc交叉概率,pm變異概率。3.1開始準備先讀入文件，讀入574個城市坐標讀入矩陣，并計算城市距離。如代碼：3.2初始化種群遺傳算法對求解問題本身是一無所知的，這里采用隨機生成初始化種群，如下：計算適應(yīng)度值，適應(yīng)度值是根據(jù)適應(yīng)度函數(shù)來計算的，如適應(yīng)度函數(shù)代碼如下：3.3選擇操作選擇的目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代產(chǎn)生后代個體，如代碼：3.4交叉操作許多生物的繁衍是通過染色體的交叉完成的，在遺傳算法中使用這一概念，并把交叉作為遺傳算法的一個操作算子，其實現(xiàn)過程是對選中用于

6、繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率Pc，在選擇的位置實行交換，目的在于產(chǎn)生新的基因組合，即新的個體（這里由于源代碼太多不列出）3.5變異操作是按一定概率隨機改變某個個體的基因值，以變異概率Pm對某個個體的某些位執(zhí)行變異，在變異時，對執(zhí)行變異的串的對應(yīng)位求反，如代碼：最后根據(jù)具體條件判斷是否返回或是繼續(xù)，最后當滿足條件是輸出適應(yīng)度最優(yōu)群體。4實驗分析實驗硬件環(huán)境為普通筆記本電腦，內(nèi)存2GB，CPU頻率2.0GHz。軟件環(huán)境為Windows XP Professional SP3操作系統(tǒng)，Matlab7.1。實驗對象是574個城市的旅行商問題。讀入574個城市的坐標，如圖1

7、：圖1：574個城市坐標的兩種顯示4.1.改變種群數(shù)量的對比當參數(shù)設(shè)置為種群大小為100，最大迭代次數(shù)2000，交叉概率0.85，變異概率為0.05的時候?qū)?74個城市求解，如圖2。 當參數(shù)設(shè)置為種群大小為50，最大迭代次數(shù)2000，交叉概率0.85，變異概率為0.05的時候?qū)?74個城市求解，如圖3。 當參數(shù)設(shè)置為種群50，最大迭代次數(shù)為5000，交叉概率0.85，變異概率為0.05的時候?qū)?74個城市求解，如圖4.圖2：種群為100最大迭代次數(shù)為2000的TSP問題求解結(jié)果圖3：種群為50最大迭代次數(shù)為2000的TSP問題求解結(jié)果圖4：種群為50最大迭代次數(shù)為5000的TSP問題求解結(jié)果通

8、過上述種群大小可知迭代越大求解的結(jié)果越優(yōu)化，但是確花費了大量時間，種群越大求解的結(jié)果更優(yōu)化，所以在時間和求解優(yōu)化解要權(quán)衡，而且改變交叉概率和變異概率也同樣影響著收斂速度和優(yōu)化解的得到。另外從圖可以看出，算法迭代并沒有穩(wěn)定，那是因為迭代的次數(shù)不夠，造成解的搜索沒有穩(wěn)定和優(yōu)化，迭代次數(shù)一般可以上萬次4.2粒子群算法求解當參數(shù)為50個粒子迭代10次，局部優(yōu)化使用2-Opt算法，如圖4。圖5：50個粒子10次迭代的粒子群TSP問題求解結(jié)果當參數(shù)為50個粒子迭代30次，局部優(yōu)化使用2-Opt算法，如圖5。圖6：50個粒子30次迭代的粒子群TSP問題求解結(jié)果當參數(shù)為30個粒子迭代30次，局部優(yōu)化使用2-O

9、pt算法，如圖6。圖7：30個粒子30次迭代的粒子群TSP問題求解結(jié)果根據(jù)實驗結(jié)果50粒子10迭代時最短路徑為42176，50個粒子30次迭代是最短路徑為41619，30個粒子30次迭代時最短路徑為40809，30個粒子30次迭代時解最優(yōu)，可以看出最優(yōu)解的得出并不是只受迭代次數(shù)或是粒子數(shù)影響，在其它條件不變的情況下，兩種都對解的求解有影響，如果考慮其它因素的話，求解更加復(fù)雜。4.3 遺傳算法同粒子群算法對比取兩個實驗的最優(yōu)解結(jié)果，即50粒子群30次迭代的粒子群算法同種群大小為1200的遺傳算法的對比，如圖8，圖9.圖8：30個粒子30次迭代的粒子群TSP問題求解結(jié)果圖9：種群大小為100迭代2

10、000次的TSP問題求解結(jié)果采用兩種算法對同一TSP問題進行求解，從實驗明顯可見粒子群算法比遺傳算法得到的解更加優(yōu)化，而且所花費的時間也比遺傳算法少得多。造成這種實驗結(jié)果的原因可能是算法本身的適應(yīng)問題，可能是粒子群算法更適合解此類問題；另一方面，可能是遺傳算法的參數(shù)設(shè)置不能達到最優(yōu)解，因為遺傳算法的種群大小，最大迭代次數(shù)，交叉概率和變異概率的設(shè)定對算法的收斂和最優(yōu)解的得到有很大影響，可能是我們設(shè)定的這些參數(shù)不夠準確，如在遺傳算法中我們只設(shè)置了2000次的最大迭代次數(shù)，明顯不能滿足要求，要得到更好的優(yōu)化解，就必須設(shè)置好算法的參數(shù)，目前有許多研究都在改進算法，以達到滿意的效果。5總結(jié) 本文采用MATLAB實現(xiàn)遺傳算法求解TSP問題，并根據(jù)實驗結(jié)果進行了分析，遺傳算法是一種智能優(yōu)化算法，它的實現(xiàn)有些關(guān)鍵點，一是串的編碼方式，本質(zhì)就是問題編碼，串長度及編碼形式對算法收斂影響極大；二是適應(yīng)函數(shù)的確定，這是選擇的基礎(chǔ)；三是自身參數(shù)的設(shè)定，其中重要的是