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

用遗传算法解决旅行商问题 姓名：王晓梅学号：1301281 班级：系统工程6班一、问题背景有一个销售员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。现在假设有10个城市，他们之间的距离如下。 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, 137, 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将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。二、建立模型 三、设计算法1、种群初始化（1）一条染色体的初始化10个城市分别对应09这十个数，每个染色体代表一个解决方法，即09这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个09的数，依次得到与前面不重复的十个数，构成一个染色体。（2）种群的初始化这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。2、适值的计算求相邻两个城市的距离和代表适值，适值越小，表示结果越好。3、交叉交叉是指从种群中选两个染色体作为父代，交叉产生两个子代。这里有两个问题：（1） 怎么选出那两对要交叉？这里将100个染色体分成50组，产生50个01的随机数对应这50对父代，若产生的随机数小于交叉率，表示这对父代被选中，则进行交叉，否则不交叉，保留父代。（2） 怎么交叉？采用单点的顺序交叉，就是随机产生一个交叉点，先将父代1交叉点前后的基因颠倒给一个中间变量new，然后比较new每一位与父代2交叉点后面的基因，若相同，令new该位为-1（目的就是找出并去掉new染色体中与父代2交叉点后面相同的基因），再将new中不是-1的基因先按顺序赋给子代1，再把父代2交叉点后的基因赋给子代1，这样子代1就产生了。同样的方法产生子代2.，完成交叉。4、变异（1）选出变异的染色体随机产生099的随机数，产生100个，分别与种群中100个染色体对应，比较所产生的随机数与变异率，若小于变异率，则变异，否则不变异，保留父代。（2）进行变异产生09的两个随机数，代表这个染色体当中被选中的两个基因位，进行交换即可。5、选择采用轮盘赌法，轮盘赌法是在圆盘中占得比例大的被选中的概率大，意味着好的解事占比例大的，而这里要求的是希望适值越小越好，为解决这个问题，设置一个最大适值，求它与每一个染色体的差，差越大对应适值越小，解也就越好，求这100个差的和，每一个差占100个差的比例，代表在圆盘中所占大小。随机产生一个01的随机数rd，从第一个染色体开始，比较该随机数与染色体所占的比例，若小于表示这个染色体被选中，若不小于，将累加下一个染色体的比例，在比较，直到小于为止，所加的最后一个染色体就是被选中的染色体。循环一百次产生100个随机数来选择100个染色体作为下次迭代的父代。6、主函数 先初始化种群，计算适值，选这一代中适值最好的，交叉变异选择，产生新的父代。void main()static 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, 137, 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.initializePop(); /产生初始种群for(int i=0;igen;i+) /开始迭代ga.sel_pop0.sumfitness=0;ga.pool_pop.fitness=definenum; /用来比较筛选找种群中最小的适值 for(int j=0;jpopsize;j+) /计算种群中每一个染色体适值 ga.old_popj.evaluate(); for(int j=0;jpopsize;j+) /选择最好的适值 if(ga.old_popj.fitnessga.pool_pop.fitness) for(int q=0;qlength;q+) ga.pool_pop.codeq=ga.old_popj.codeq; ga.pool_pop.fitness=ga.old_popj.fitness; ga.selectChr(); /选择 ga.crossover(); /交叉 ga.mutate(); /变异 cout输出第“i+1代最好路线; ga.pool_pop.evaluate(); ga.pool_pop.toprint();system(pause);四，结果1、迭代50次，交叉率0.8，变异率0.3的结果。2迭代50次，交叉率0.5，变异0.3的结果，结果很明显变得不好，说明交叉率太小，种群中染色体变化太小，会陷入局部最优，不利于结果向好的方向发展。3、迭代50次，交叉率0.8，变异率0.9的结果，结果也是变差，说明变异率太大对会是结果向着不好的方向发展。4、 迭代100次，交叉率0.8，变异0.3的结果，相比较第一种情况而言，结果差不多，说明迭代50次，差不多已经达到稳定。五、总结在