用遺傳算法解決旅行商問題

1、用遺傳算法解決 旅行商問題姓名：王曉梅學(xué)號(hào)：1301281班級(jí)：系統(tǒng)工程6班一、問題背景有一個(gè)銷售員，要到n個(gè)城市推銷商品，他要找出一個(gè)包含所有n個(gè)城市的具有最短路 程的環(huán)路?，F(xiàn)在假設(shè)有10個(gè)城市，他們之間的距離如下。0, 107, 24L 190, 124, 80, 316, 76, 152, 157, 107,0, 148, 137, 88, 127, 336, 183, 134, 95, 241, 148,0, 374, 171, 259, 509,317,217, 232, 190, 137, 374,0. 202. 234, 222, 192. 248, 42),124, 88,17

2、1,202,0, 61,392,202. 46,160),( 80, 127, 259, 234, 61,0, 386. 141, 72, 167), 316, 336, 509,222, 392, 386,0, 233,438, 254,( 76, 183, 317,192, 202,141, 233,0, 213, 188,152,134,217,248. 46, 72,438,213,0.206, 157, 95, 232, 42,160, 167, 254, 188, 206,0)將這10個(gè)城市分別編碼為0.12345678,9。要求走完這10個(gè)城市，目標(biāo)是使走的距 離最短。二、建立模

3、型minZZxM/力) /-I j-is.t.元=1(,工川=1”一) /-I= = 1，)1三、設(shè)計(jì)算法1、種群初始化(1) 一條染色體的初始化10個(gè)城市分別對(duì)應(yīng)09這十個(gè)數(shù)，每個(gè)染色體代表一個(gè)解決方法，即09這十個(gè)數(shù)的 一種排序方式，可隨機(jī)產(chǎn)生一個(gè)數(shù)，用取余的方法得到一個(gè)09的數(shù)，依次得到與前而不重 復(fù)的十個(gè)數(shù)，構(gòu)成一個(gè)染色體。(2)種群的初始化這里假設(shè)種群有100個(gè)染色體，也就是循環(huán)100次染色體的初始化可得到一個(gè)種群。2、適值的計(jì)算求相鄰兩個(gè)城市的距離和代表適值，適值越小，表示結(jié)果越好。3、交叉交叉是指從種群中選兩個(gè)染色體作為父代，交叉產(chǎn)生兩個(gè)子代。這里有兩個(gè)問題：（1）怎么選出那兩對(duì)

4、要交叉？這里將100個(gè)染色體分成50組，產(chǎn)生50個(gè)01的隨機(jī)數(shù)對(duì)應(yīng)這50對(duì)父代，若產(chǎn)生的 隨機(jī)數(shù)小于交叉率，表示這對(duì)父代被選中，則進(jìn)行交叉.否則不交叉，保留父代。（2）怎么交叉？采用單點(diǎn)的順序交叉，就是隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)，先將父代1交叉點(diǎn)前后的基因顛倒給 一個(gè)中間變量new,然后比較new每一位與父代2交叉點(diǎn)后面的基因，若相同，令new該 位為-1（目的就是找出并去掉new染色體中與父代2交叉點(diǎn)后面相同的基因），再將new中 不是-1的基因先按順序賦給子代1.再把父代2交叉點(diǎn)后的基因賦給子代1.這樣子代1就 產(chǎn)生了。同樣的方法產(chǎn)生子代2.,完成交叉。4、變異（1）選出變異的染色體隨機(jī)產(chǎn)生099

5、的隨機(jī)數(shù)，產(chǎn)生100個(gè)，分別與種群中100個(gè)染色體對(duì)應(yīng)，比較所產(chǎn)生 的隨機(jī)數(shù)與變異率，若小于變異率，則變異，否則不變異，保留父代。（2）進(jìn)行變異產(chǎn)生09的兩個(gè)隨機(jī)數(shù)，代表這個(gè)染色體當(dāng)中被選中的兩個(gè)基因位，進(jìn)行交換即可。5、選擇采用輪盤賭法，輪盤賭法是在圓盤中占得比例大的被選中的概率大，意味著好的解事占 比例大的，而這里要求的是希望適值越小越好，為解決這個(gè)問題，設(shè)置一個(gè)最大適值，求它 與每一個(gè)染色體的差，差越大對(duì)應(yīng)適值越小，解也就越好，求這100個(gè)差的和，每一個(gè)差占 100個(gè)差的比例，代表在圓盤中所占大小。隨機(jī)產(chǎn)生一個(gè)01的隨機(jī)數(shù)rd,從第一個(gè)染色體開始，比較該隨機(jī)數(shù)與染色體所占的 比例，若小于

6、表示這個(gè)染色體被選中，若不小于，將累加下一個(gè)染色體的比例，在比較，直 到小于為止，所加的最后一個(gè)染色體就是被選中的染色體。循環(huán)一百次產(chǎn)生100個(gè)隨機(jī)數(shù)來 選擇100個(gè)染色體作為下次迭代的父代。6、主函數(shù)先初始化種群，計(jì)算適值，選這一代中適值最好的，交叉變異選擇，產(chǎn)生新的父代。void mainOstatic int maplengthlength.=0,107,241,190,124,80,316,76,152,157),( 107,0,148,137,88,127,336,183,134,95),( 241,148,0,374,171,259,509,317,217,232), 190,13

7、7,374,0,202,234,222,192,248,42, 124,88,171,202,0,61,392,202,46,160), 80,127,259,234,61,0,386,141,72,167), 316,336,509,222,392,386,0,233,438,254),( 76,183,317,192,202,141,233,0,213,188), 152,134,217,248,46,72,438,213,0,206, 157,95,232,42,160,167,254,188,206,0);GA ga;ga. initializePopO ;產(chǎn)生初始種群for(int

8、i=0;igen;i+)開始迭代(ga. sel_pop.O. sumfitness=0;ga. pool_pop. f itness=def inenum;用來比較篩選找種群中最小的適值for(int j=0;jpopsize;j+)計(jì)算種群中每一個(gè)染色體適值ga. old_popj. evaluate0;jfor(int j=0;jpopsize;j+)選擇最好的適值if(ga. old_popjj. fitnessga. pool_pop. fitness)for (int q=0;q1ength;q+) (ga. pool_pop. codeq.=ga. old_popj. codeq

9、;ga. pool-pop. fitness=ga. old_popj. fitness;)ga. selectChr 0 ;/選擇ga. crossover () ;/ 交叉ga. mutate () ;，丁變芥cout輸出第“i+l9-3-6-7-5-0-4-8-2-11-9-3-6-7-5-0-4-8-2-11-9-3-6-7-5-0-4-8-2-11-9-3-6-7-5-0-4-8-2-12-1-9-3-6-7-0-4-8-5-25-8-?-6-9-3-1-2-8-4-52-1-9-3-6-7-0-4-8-5-22-1-3-9-6-7-0-4-8 5-22-1-3-9-6-7-0-4-

10、8-5-22-1-3-9-6-7-0-4-8-5-22-1-3-9-6-7-0-4-8-5-25-4-9-3-6-7-0-2-1-8-52迭代50次，交叉率0.5,變異0.3的結(jié)果，結(jié)果很明顯變得不好，說明交叉率太小, 種群中染色體變化太小，會(huì)陷入局部最優(yōu)，不利于結(jié)果向好的方向發(fā)展.第空生星a累a吊芻矍*弟、FMS.4 出值上值出值土值土值出值土值土值土值值出 黎沒MNMWMKgQ學(xué)N一Q學(xué)區(qū)梨火青意向9向9問9勺0問1打5對(duì)6向6向6向8向3向3% Ati 9 9 -TH 0 An 4 -TH 5 AH 2 Ati 6 Ad 6 6 -TH 0 ? AH 9 鄉(xiāng)二 弋4弋4弋5弋B弋4弋4弋

11、4弋4弋q弋4弋4弋4建 甲m甲甲If 1甲工甲1甲工甲1fl甲工祗練緣路路子 子 力 戈 最最線 各 ?3 D:My DocumentsDccumentsVisual Studio 2010ProjectsyichuanDebugyichuan.exe3、迭代50次，交叉率0.8,變異率0.9的結(jié)果，結(jié)果也是變差，說明變異率太大對(duì)會(huì) 是結(jié)果向著不好的方向發(fā)展。M3 D;My Document5DocumcntsVi5ual Studio 2010ProjectsyichudnDebugyichuan.exeLJlS I 23一67- 一出值出值出值曾出值出值出息,44,47塞趣萼曹曹萼鬻萼鱉

12、注.50:急LI 7Ah 0 At 2 AL 1 At 4- zt 9 tk 7 At 9tl n Ah 4 AL 5 z? XJ13弋 3f.1G弋154、16弋16弋15弋15弋15V. 61616建4 -2x 5 -84、迭代100次，交叉率0.8,變異0.3的結(jié)果，相比較第一種情況而言，結(jié)果差不多, 說明迭代50次，差不多已經(jīng)達(dá)到穩(wěn)定，S3 D:My D o c u m e nt sDo c u ms nt sVi s u a I Studio 2010ProjectsyichuarDebugyichuan.exe,值出值出值出值出值出值出值出 石學(xué)一曹mi m-：13389。代的最好

13、路線:1代的最好路線.5 133R92代的最好路線:：133893代的最好路線:：133894代的最好路線:：129M95代的最好路線:：129096代的最好路線:：1290以代的最好路線.,129698代的最好路線,：129699代的最好路線:：13381。代的最好路線：1358意鍵繼續(xù) 8 5-0-7-6-3-9-4-2-1-88-5-0-7-6-2-9-4-1-2-88-5-0-?-6-3-9-4-2-1-88-5-0-?-6-3-9-4-2-1-85-4-0-?-6-3-9-1-2-8-55-4-0-7-63-9-1-2-8 58-5-0-7-6-3-9-1-4-2-88-0-7-6-3-9-1