用遗传算法解决旅行商问题

1、用遗传算法解决 旅行商问题姓名：王晓梅学号：1301281班级：系统工程6班一、问题背景有一个销售员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路 程的环路。现在假设有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个城市，目标是使走的距 离最短。二、建立模

3、型minZZxM/力) /-I j-is.t.元=1(,工川=1”一) /-I= = 1，)1三、设计算法1、种群初始化(1) 一条染色体的初始化10个城市分别对应09这十个数，每个染色体代表一个解决方法，即09这十个数的 一种排序方式，可随机产生一个数，用取余的方法得到一个09的数，依次得到与前而不重 复的十个数，构成一个染色体。(2)种群的初始化这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。2、适值的计算求相邻两个城市的距离和代表适值，适值越小，表示结果越好。3、交叉交叉是指从种群中选两个染色体作为父代，交叉产生两个子代。这里有两个问题：（1）怎么选出那两对

4、要交叉？这里将100个染色体分成50组，产生50个01的随机数对应这50对父代，若产生的 随机数小于交叉率，表示这对父代被选中，则进行交叉.否则不交叉，保留父代。（2）怎么交叉？采用单点的顺序交叉，就是随机产生一个交叉点，先将父代1交叉点前后的基因颠倒给 一个中间变量new,然后比较new每一位与父代2交叉点后面的基因，若相同，令new该 位为-1（目的就是找出并去掉new染色体中与父代2交叉点后面相同的基因），再将new中 不是-1的基因先按顺序赋给子代1.再把父代2交叉点后的基因赋给子代1.这样子代1就 产生了。同样的方法产生子代2.,完成交叉。4、变异（1）选出变异的染色体随机产生099

5、的随机数，产生100个，分别与种群中100个染色体对应，比较所产生 的随机数与变异率，若小于变异率，则变异，否则不变异，保留父代。（2）进行变异产生09的两个随机数，代表这个染色体当中被选中的两个基因位，进行交换即可。5、选择采用轮盘赌法，轮盘赌法是在圆盘中占得比例大的被选中的概率大，意味着好的解事占 比例大的，而这里要求的是希望适值越小越好，为解决这个问题，设置一个最大适值，求它 与每一个染色体的差，差越大对应适值越小，解也就越好，求这100个差的和，每一个差占 100个差的比例，代表在圆盘中所占大小。随机产生一个01的随机数rd,从第一个染色体开始，比较该随机数与染色体所占的 比例，若小于

6、表示这个染色体被选中，若不小于，将累加下一个染色体的比例，在比较，直 到小于为止，所加的最后一个染色体就是被选中的染色体。循环一百次产生100个随机数来 选择100个染色体作为下次迭代的父代。6、主函数先初始化种群，计算适值，选这一代中适值最好的，交叉变异选择，产生新的父代。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 ;产生初始种群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的结果，结果很明显变得不好，说明交叉率太小, 种群中染色体变化太小，会陷入局部最优，不利于结果向好的方向发展.第空生星a累a吊刍矍*弟、FMS.4 出值上值出值土值土值出值土值土值土值值出 黎没MNMWMKgQ学N一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 乡二 弋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的结果，结果也是变差，说明变异率太大对会 是结果向着不好的方向发展。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的结果，相比较第一种情况而言，结果差不多, 说明迭代50次，差不多已经达到稳定，S3 D:My D o c u m e nt sDo c u ms nt sVi s u a I Studio 2010ProjectsyichuarDebugyichuan.exe,值出值出值出值出值出值出值出 石学一曹mi m-：13389。代的最好

13、路线:1代的最好路线.5 133R92代的最好路线:：133893代的最好路线:：133894代的最好路线:：129M95代的最好路线:：129096代的最好路线:：1290以代的最好路线.,129698代的最好路线,：129699代的最好路线:：13381。代的最好路线：1358意键继续 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