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

WORD格式可编辑 专业知识分享 用遗传算法解决旅行商问题 姓名：王晓梅 学号：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个城市分别对应0~9这十个数，每个染色体代表一个解决方法，即0~9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0~9的数，依次得到与前面不重复的十个数，构成一个染色体。 （2）种群的初始化 这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。 2、适值的计算 求相邻两个城市的距离和代表适值，适值越小，表示结果越好。 3、交叉 交叉是指从种群中选两个染色体作为父代，交叉产生两个子代。 这里有两个问题： 怎么选出那两对要交叉？ 这里将100个染色体分成50组，产生50个0~1的随机数对应这50对父代，若产生的随机数小于交叉率，表示这对父代被选中，则进行交叉，否则不交叉，保留父代。 怎么交叉？ 采用单点的顺序交叉，就是随机产生一个交叉点，先将父代1交叉点前后的基因颠倒给一个中间变量new，然后比较new每一位与父代2交叉点后面的基因，若相同，令new该位为-1（目的就是找出并去掉new染色体中与父代2交叉点后面相同的基因），再将new中不是-1的基因先按顺序赋给子代1，再把父代2交叉点后的基因赋给子代1，这样子代1就产生了。 同样的方法产生子代2.，完成交叉。 4、变异 （1）选出变异的染色体 随机产生0~99的随机数，产生100个，分别与种群中100个染色体对应，比较所产生的随机数与变异率，若小于变异率，则变异，否则不变异，保留父代。 （2）进行变异 产生0~9的两个随机数，代表这个染色体当中被选中的两个基因位，进行交换即可。 5、选择 采用轮盘赌法，轮盘赌法是在圆盘中占得比例大的被选中的概率大，意味着好的解事占比例大的，而这里要求的是希望适值越小越好，为解决这个问题，设置一个最大适值，求它与每一个染色体的差，差越大对应适值越小，解也就越好，求这100个差的和，每一个差占100个差的比例，代表在圆盘中所占大小。 随机产生一个0~1的随机数rd，从第一个染色体开始，比较该随机数与染色体所占的比例，若小于表示这个染色体被选中，若不小于，将累加下一个染色体的比例，在比较，直到小于为止，所加的最后一个染色体就是被选中的染色体。循环一百次产生100个随机数来选择100个染色体作为下次迭代的父代。 6、主函数 先初始化种群，计算适值，选这一代中适值最好的，交叉变异选择，产生新的父代。 void main() { static int map[length][length]= { { 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,