资源描述：
《用遗传算法解决旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、姓名：王晓梅学号：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
2、,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)将这1()个城市分别编码为0,1，2,3,4,5,6,7,8,9。要求走完这1()个城市，目标是使走的距离最短。二、建立模型n打;=17=1s.t.SXy=1(’#=1
3、”.”/=17=1三、设计算法1、种群初始化(1)一条染色体的初始化10个城市分别对应0〜9这十个数，每个染色体代表一个解决方法，即0〜9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0〜9的数，依次得到与前面不重复的+•个数，构成一个染色体。(2)种群的初始化这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。2、适值的计算求相邻两个城市的距离和代表适值，适值越小，表示结果越好。3、交叉交叉是指从种群屮选两个染色体作为父代，交叉产生两个子代。这里有两个问题：(1)怎么选出那两对要交叉？这里将100个染色体分成50
4、组，产生50个0〜1的随机数对应这50对父代，若产生的随机数小于交叉率，表示这对父代被选中，则进行交叉，否则不交叉，保留父代。(2)怎么交叉？采用单点的顺序交叉，就是随机产生一个交叉点，先将父代1交叉点前后的基因颠倒给—个中间变量new，然后比较new每一位与父代2交叉点后面的基因，若相同，令new该位为-1(目的就是找出并去掉new染色体中与父代2交叉点后面相同的基因)，再将new中不是-1的基因先按顺序赋给子代1，再把父代2交叉点后的基因赋给子代1,这样子代1就产生了。同样的方法产生子代2.,完成交叉。4、变异(1)选出变异的染色体随机产生0〜99的随
5、机数，产生100个，分别与种群屮10()个染色体对应，比较所产生的随机数与变异率，若小于变异率，则变异，否则不变异，保留父代。(2)进行变异产生0〜9的两个随机数，代表这个染色体当屮被选屮的两个基因位，进行交换即可。5、选择采用轮盘赌法，轮盘赌法是在圆盘中A得比例大的被选中的概率大，意味着好的解事占比例大的，而这里要求的是希望适值越小越好，为解决这个问题，设置一个最大适值，求它与每一个染色体的差，差越大对应适值越小，解也就越好，求这100个差的和，每一个差占100个差的比例，代表在圆盘中所占大小。随机产生一个0〜1的随机数rd,从第一个染色体开始，比较该随
6、机数与染色体所占的比例，若小于表示这个染色体被选中，若不小于，将累加下一个染色体的比例，在比较，直到小于为止，所加的最后一个染色体就是被选中的染色体。循环•一百次产生100个随机数来选择100个染色体作为下次迭代的父代。6、主函数先初始化种群，计算适值，选这一代中适值最好的，交叉变异选择，产生新的父代voidmainO{staticintmap[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,17
7、1,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,
8、0}G?ga;ga.initializePopO;//产生初始种群
