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

1、用遺傳算法解決 旅行商問題姓名：王曉梅學(xué)號：1301281班級：系統(tǒng)工程6班一、問題背景有一個銷售員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路 程的環(huán)路?，F(xiàn)在假設(shè)有10個城市，他們之間的距離如下。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個城市分別編碼為0.12345678,9。要求走完這10個城市，目標(biāo)是使走的距 離最短。二、建立模

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

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

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

6、表示這個染色體被選中，若不小于，將累加下一個染色體的比例，在比較，直 到小于為止，所加的最后一個染色體就是被選中的染色體。循環(huán)一百次產(chǎn)生100個隨機數(shù)來 選擇100個染色體作為下次迭代的父代。6、主函數(shù)先初始化種群，計算適值，選這一代中適值最好的，交叉變異選擇，產(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+)計算種群中每一個染色體適值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é)果很明顯變得不好，說明交叉率太小, 種群中染色體變化太小，會陷入局部最優(yōu)，不利于結(jié)果向好的方向發(fā)展.第空生星a累a吊芻矍*弟、FMS.4 出值上值出值土值土值出值土值土值土值值出 黎沒MNMWMKgQ學(xué)N一Q學(xué)區(qū)梨火青意向9向9問9勺0問1打5對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é)果也是變差，說明變異率太大對會 是結(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