遺傳算法求解TSP問(wèn)題MATLAB實(shí)現(xiàn)

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

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

3、的回路。若對(duì)與城市 v=v1,v2,v3 -vn的一個(gè)訪問(wèn)順序?yàn)?t=(t1,t2,t3 - ,tn)，其中 ti C v(i=1,2,.n), 且記tn+1=t1,則旅行上問(wèn)題的數(shù)學(xué)模型為式1 :min I =8d(t(i),t(i +1) (i =1,.,n)(1)2. 遺傳算法與粒子群算法2.1遺傳算法遺傳算法的基本原理是通過(guò)作用于染色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題，它需要對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)度值來(lái)選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)，在遺傳算法中，通過(guò)隨機(jī)方式產(chǎn)生若干個(gè)所求解問(wèn)題的數(shù)字編碼，即染色體，形成初始種群；通過(guò)適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)

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

5、遺傳算法過(guò)程圖如圖1:3結(jié)束圖1:遺傳算法過(guò)程框圖3.遺傳算法MATLAB代碼實(shí)現(xiàn)遺傳算法中控制參數(shù)如下：Clist城市的坐標(biāo)，dislist城市距離矩陣，inn初始種群的大小，gnmax最大代數(shù)，pc交叉概率,pm變異概率。3.1開始準(zhǔn)備先讀入文件，讀入 574個(gè)城市坐標(biāo)讀入矩陣，并計(jì)算城市距離。如代碼：Clist = zeros (574 2):a, y=t ext read (7 iq574. tspn .'強(qiáng)i演fKf');(:, l)=x;2)=y; figure (1)10 C 10) grid on scatter (Clist Clift j 2)> f

6、) grid onCit jrNum=size (Clisl,】)；for i=l:nCity蜘十算城市間距離，假設(shè)距離為歐幾里德葩數(shù)fcr 1:nCityj) ( (xyCity(i, D-yCitytj, 1) *2*-(aryCity(i, 2)-xyCity(jJ 2) ) *2) *0. 5 ; endend遺傳算法對(duì)求解問(wèn)題本身是一無(wú)所知的，這里采用隨機(jī)生成初始化種群，如下：for i=l：inns (ij :) =raridperni(CityNujn);end計(jì)算適應(yīng)度值，適應(yīng)度值是根據(jù)適應(yīng)度函數(shù)來(lái)計(jì)算的，如適應(yīng)度函數(shù)代碼如下：furict ion f,p=objf(5j di

7、slist).;inn=size(sj 1). %讀取種群大小for i=1:irmf (i)=CalDist (dislist j s (i, : ?) : %計(jì)算函數(shù)值,即適應(yīng)度end禺計(jì)算選擇概率fsum=0 ；for i=1:innf sum=f suiv+f ，endfor i=1iinnps ti)=f(i)15/fsun,end盟計(jì)算梟積概率P =ps(l) hfor i=2:innp(i)=p(i-l)+ps(i):endP二P ；end3.3選擇操作選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代產(chǎn)生后代個(gè) 體，如代碼：function melnKel(*p)

8、:inn=size(pj1)；濟(jì)從種群中選擇兩個(gè)個(gè)體for 1=1:2rand; %產(chǎn)生一個(gè)隨機(jī)數(shù)prand=p-r;戶1；while prandtjXOj=j+l；end哭比(i)uj；賢選中個(gè)體的序號(hào)endend3.4交叉操作許多生物的繁衍是通過(guò)染色體的交叉完成的，在遺傳算法中使用這一概念，并把交叉作為遺傳算法的一個(gè)操作算子，其實(shí)現(xiàn)過(guò)程是對(duì)選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率Pc,在選擇的位置實(shí)行交換，目的在于產(chǎn)生新的基因組合，即新的個(gè)體(這里由于源代碼太多不列出)3.5變異操作是按一定概率隨機(jī)改變某個(gè)個(gè)體的基因值，以變異概率Pm對(duì)某個(gè)個(gè)體的某些位執(zhí)行變異，在

9、變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，如代碼：funct i on(snew, pm);snnew=anew;a (pit)；if pnm=1cl= round (rand* (bn-2) +1;c2= round (rand* (bn-2) + l;chbl=inin(clJ c2):chb2uK (clj c2);x=sriew(chbl+l: chb25 ;snnewtchb 1+1: chb2)=f liplr (x);endend最后根據(jù)具體條件判斷是否返回或是繼續(xù)，最后當(dāng)滿足條件是輸出適應(yīng)度最優(yōu)群體。4實(shí)驗(yàn)分析實(shí)驗(yàn)硬件環(huán)境為普通筆記本電腦，內(nèi)存 2GB CP堀率2.0GHz。軟件環(huán)境

10、為 Windows XP Professional SP3 操作系統(tǒng)，Matlab7.1。實(shí)驗(yàn)對(duì)象是574個(gè)城市的旅行商問(wèn)題。讀入574個(gè)城市的坐標(biāo)，如圖 1:圖1 : 574個(gè)城市坐標(biāo)的兩種顯示4.1.改變種群數(shù)量的對(duì)比當(dāng)參數(shù)設(shè)置為種群大小為100,最大迭代次數(shù)2000,交叉概率0.85,變異概率為0.05的時(shí)候?qū)?74個(gè)城市求解，如圖2。當(dāng)參數(shù)設(shè)置為種群大小為50,最大迭代次數(shù) 2000,交叉概率0.85,變異概率為 0.05的時(shí)候?qū)?74個(gè)城市求解，如圖3。當(dāng)參數(shù)設(shè)置為種群 50,最大迭代次數(shù)為 5000,交叉概率0.85,變異概率為0.05的時(shí)候?qū)?74個(gè)城市求解，如圖 4.圖2:種群

11、為100最大迭代次數(shù)為2000的TSP問(wèn)題求解結(jié)果圖3:種群為50最大迭代次數(shù)為2000的TSP問(wèn)題求解結(jié)果圖4:種群為50最大迭代次數(shù)為5000的TSP問(wèn)題求解結(jié)果通過(guò)上述種群大小可知迭代越大求解的結(jié)果越優(yōu)化，但是確花費(fèi)了大量時(shí)間，種群越大求解的結(jié)果更優(yōu)化， 所以在時(shí)間和求解優(yōu)化解要權(quán)衡，而且改變交叉概率和變異概率也同樣影響著收斂速度和優(yōu)化解的得到。另外從圖可以看出， 算法迭代并沒有穩(wěn)定， 那是因?yàn)榈拇螖?shù)不夠，造成解的搜索沒有穩(wěn)定和優(yōu)化，迭代次數(shù)一般可以上萬(wàn)次4.2粒子群算法求解當(dāng)參數(shù)為50個(gè)粒子迭代10次，局部?jī)?yōu)化使用 2-Opt算法，如圖4。位子群算法（PS?！繄D5: 50個(gè)粒子10

12、次迭代的粒子群TSP問(wèn)題求解結(jié)果當(dāng)參數(shù)為50個(gè)粒子迭代30次，局部?jī)?yōu)化使用 2-Opt算法，如圖5。杭子群算法零。）圖6: 50個(gè)粒子30次迭代的粒子群TSP問(wèn)題求解結(jié)果當(dāng)參數(shù)為30個(gè)粒子迭代30次，局部?jī)?yōu)化使用 2-Opt算法，如圖6。成于群算注訴$。）圖7: 30個(gè)粒子30次迭代的粒子群TSP問(wèn)題求解結(jié)果根據(jù)實(shí)驗(yàn)結(jié)果50粒子10迭代時(shí)最短路徑為 42176, 50個(gè)粒子30次迭代是最短路徑為41619, 30個(gè)粒子30次迭代時(shí)最短路徑為 40809, 30個(gè)粒子30次迭代時(shí)解最優(yōu)，可以看出 最優(yōu)解的得出并不是只受迭代次數(shù)或是粒子數(shù)影響，在其它條件不變的情況下，兩種都對(duì)解的求解有影響，如果考

13、慮其它因素的話，求解更加復(fù)雜。4.3遺傳算法同粒子群算法對(duì)比取兩個(gè)實(shí)驗(yàn)的最優(yōu)解結(jié)果，即50粒子群30次迭代的粒子群算法同種群大小為1200的遺傳算法的對(duì)比，如圖 8,圖9. 應(yīng)子群算注PS。）圖8: 30個(gè)粒子30次迭代的粒子群TSP問(wèn)題求解結(jié)果圖9:種群大小為100迭代2000次的TSP問(wèn)題求解結(jié)果采用兩種算法對(duì)同一 TSP問(wèn)題進(jìn)行求解，從實(shí)驗(yàn)明顯可見粒子群算法比遺傳算法得到 的解更加優(yōu)化，而且所花費(fèi)的時(shí)間也比遺傳算法少得多。造成這種實(shí)驗(yàn)結(jié)果的原因可能是算法本身的適應(yīng)問(wèn)題，可能是粒子群算法更適合解此 類問(wèn)題；另一方面，可能是遺傳算法的參數(shù)設(shè)置不能達(dá)到最優(yōu)解，因?yàn)檫z傳算法的種群大小，最大迭代次數(shù)，交叉概率和變異概率的設(shè)定對(duì)算法的收斂和最優(yōu)解的得到有很大影響，可能是我們?cè)O(shè)定的這些參數(shù)不夠準(zhǔn)確，如在遺傳算法中我們只設(shè)置了2000次的最大迭代次數(shù)，明顯不能滿足要求， 要得到更好的優(yōu)化解， 就必須設(shè)置好算法的參數(shù)，目前有許多研究都在改進(jìn)算法，以達(dá)到滿意的效果。5總結(jié)本文采用MATLAB實(shí)現(xiàn)遺傳算法求解 TSP問(wèn)題，并根據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行了分析， 遺傳算 法是一種智能優(yōu)化算法，它的實(shí)現(xiàn)有些關(guān)鍵點(diǎn)，一是串的編碼方式，本質(zhì)就是問(wèn)題編碼，串長(zhǎng)