TSP问题求解试验报告

1、TSP问题求解（一）实验目的熟悉和掌握遗传算法的原理，流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。（二）实验原理巡回旅行商问题给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提由的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。近年来，有很多解决该问题的较为有效的算法不断被推由，例如Hopfield神经网络方法，模

2、拟退火方法以及遗传算法方法等。TS限索空间随着城市数n的增加而增大，所有的旅程路线组合数为（n-1）!/2o在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。基本遗传算法可定义为一个8元组:(SGA=(C,E,P0,M，r,3，T)C个体的编码方法，SGA使用固定长度二进制符号串编码方法；E个体的适应度评价函数；P0初始群体；M群体大小,一般取20100;一一选择算子，SGA使用比例算子；r交叉算子，SGA使用单点交叉算子；里一一变异算子，SGA使用基本位变异算子；T算法终止条件，一田终止进化代数为10

3、0500;问题的表示对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP,一个旅程很自然的表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用。路径表示是表示旅程对应的基因编码的最自然，最简单的表示方法。它在编码，解码，存储过程中相对容易理解和实现。例如：旅程(5-1-7-8-9-4-6-2-3)可以直接表示为(517894623)(三)实验内容N>=8o随即生成N个城市间的连接矩阵。指定起始城市。给由每一代的最优路线和总路线长度O以代数T作为结束条件，T>=50o(四)实验代码#include"stdafx.h"

4、#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<time.h># definecities10/城市的个数# defineMAXXI00/迭代次数# definepc0.8/交配概率# definepm0.05/变异概率#definenum10/种群的大小intbestsolution;/最优染色体intdistancecitiescities;/城市之间的距离structgroup/染色体的结构intcitycities;/城

5、市的顺序intadapt;/适应度doublep;/在种群中的幸存概率groupnum,grouptempnum;/随机产生cities个城市之间的相互距离voidinit()inti,j;memset(distance,0,sizeof(distance);srand(unsigned)time(NULL);for(i=0;i<cities;i+)for(j=i+1;j<cities;j+)distanceij=rand()%100;distanceji=distanceij;/打印距离矩阵printf("城市的距离矩阵如下n");for(i=0;i<c

6、ities;i+)(for(j=0;j<cities;j+)printf("%4d",distanceij);printf("n");/随机产生初试群voidgroupproduce()inti,j,t,k,flag;for(i=0;i<num;i+)/初始化for(j=0;j<cities;j+)groupi.cityj=-1;srand(unsigned)time(NULL);for(i=0;i<numi+)(/产生10个不相同的数字for(j=0;j<cities;)(t=rand()%cities;flag=1;fo

7、r(k=0;k<j;k+)(if(groupi.cityk=t)(flag=0;break;if(flag)(groupi.cityj=t;j+;/打印种群基因printf("初始的种群n");for(i=0;i<numi+)(for(j=0;j<cities;j+)printf("%4d",groupi.cityj);printf("n");)/评价函数，找出最优染色体voidpingjia()inti,j;intn1,n2;intsumdistance,biggestsum=0;doublebiggestp=0;

8、for(i=0;i<numi+)(sumdistance=0;for(j=1;j<cities;j+)(n1=groupi.cityj-1;n2=groupi.cityj;sumdistance+=distancen1n2;)groupi.adapt=sumdistance;/每条染色体的路径总和biggestsum+=sumdistance;/种群的总路径)/计算染色体的幸存能力，路劲越短生存概率越大for(i=0;i<numi+)(groupi.p=1-(double)groupi.adapt/(double)biggestsum;biggestp+=groupi.p;)

9、for(i=0;i<numi+)groupi.p=groupi.p/biggestp;/在种群中的幸存概率，总和为1/求最佳路劲bestsolution=0;for(i=0;i<numi+)if(groupi.p>groupbestsolution.p)bestsolution=i;/打印适应度for(i=0;i<numi+)printf("染色体d的路径之和与生存概率分别为4d%.4fn",i,groupi.adapt,groupi.p);printf("当前种群的最优染色体是d#染色体n",bestsolution);)/选择

10、voidxuanze()(inti,j,temp;doublegradientnum；梯度概率doublexuanzenum；选择染色体的随机概率intxuannug;/选择了的染色体/初始化梯度概率for(i=0;i<numi+)gradienti=0.0;xuanzei=0.0;gradient0=group0.p;for(i=1;i<numi+)gradienti=gradienti-1+groupi.p;srand(unsigned)time(NULL);/随机产生染色体的存活概率for(i=0;i<numi+)xuanzei=(rand()%100);xuanzei

11、/=100;/选择能生存的染色体for(i=0;i<numi+)for(j=0;j<numj+)if(xuanzei<gradientj)xuani=j;/第i个位置存放第j个染色体break;/拷贝种群for(i=0;i<numi+)grouptempi.adapt=groupi.adapt;grouptempi.p=groupi.p;for(j=0;j<cities;j+)grouptempi.cityj=groupi.cityj;/数据更新for(i=0;i<numi+)temp=xuani;groupi.adapt=grouptemptemp.ada

12、pt;groupi.p=grouptemptemp.p;for(j=0;j<cities;j+)groupi.cityj=grouptemptemp.cityj;/用于测试printf("<>n");for(i=0;i<numi+)for(j=0;j<cities;j+)printf("%4d",groupi.cityj);printf("n");printf("染色体d的路径之和与生存概率分别为4d%.4fn",i,groupi.adapt,groupi.p);/交配，对每个染色体产

13、生交配概率，满足交配率的染色体进行交配voidjiaopei()inti,j,k,kk;intt;/参与交配的染色体的个数intpoint1,point2,temp;交配断点intpointnum;inttemp1,temp2;intmap1cities,map2cities;doublejiaopeipnum;染色体的交配概率intjiaopeiflagnum;染色体的可交配情况for(i=0;i<numi+)/初始化jiaopeiflagi=0;/随机产生交配概率srand(unsigned)time(NULL);for(i=0;i<numi+)jiaopeipi=(rand(

14、)%100);|jiaopeipi/=100;/确定可以交配的染色体t=0;for(i=0;i<numi+)if(jiaopeipi<pc)jiaopeiflagi=1;t+;)t=t/2*2;/t必须为偶数/产生t/2个0-9交配断点srand(unsigned)time(NULL);tempi=0;/temp1号染色体和temp2染色体交配for(i=0;i<t/2;i+)(pointi=rand()%cities;point2=rand()%cities;for(j=tempi;j<numj+)if(jiaopeiflagj=1)(tempi=j;break;)f

15、or(j=tempi+1;j<numj+)if(jiaopeiflagj=i)(temp2=j;break;)/进行基因交配if(pointi>point2)/保证pointi<=point2(temp=pointi;pointi=point2;_|point2=temp;)memset(mapi,-i,sizeof(mapi);memset(map2,-i,sizeof(map2);/断点之间的基因产生映射for(k=pointi;k<=point2;k+)|(mapigrouptempi.cityk=grouptemp2.cityk;map2grouptemp2.c

16、ityk=grouptempi.cityk;)/断点两边的基因互换for(k=0;k<pointi;k+)(temp=grouptempi.cityk;grouptempi.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;)for(k=point2+1;k<cities;k+)(temp=grouptemp1.cityk;grouptemp1.cityk=grouptemp2.cityk;grouptemp2.cityk=temp;)/处理产生的冲突基因for(k=0;k<point1;k+)(for(kk=point1;kk<

17、=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)(grouptemp1.cityk=map1grouptemp1.cityk;break;)for(k=point2+1;k<cities;k+)(for(kk=point1;kk<=point2;kk+)if(grouptemp1.cityk=grouptemp1.citykk)(grouptemp1.cityk=map1grouptemp1.cityk;break;)for(k=0;k<point1;k+)(for(kk=point1;kk<=point2;kk+)i

18、f(grouptemp2.cityk=grouptemp2.citykk)(grouptemp2.cityk=map2grouptemp2.cityk;break;)for(k=point2+1;k<cities;k+)(for(kk=point1;kk<=point2;kk+)if(grouptemp2.cityk=grouptemp2.citykk)(grouptemp2.cityk=map2grouptemp2.cityk;break;)tempi=temp2+1;)/变异voidbianyi()inti,j;intt;inttempi,temp2,point;doubleb

19、ianyipnum;染色体的变异概率intbianyiflagnum;染色体的变异情况for(i=0;i<numi+)/初始化bianyiflagi=0;/随机产生变异概率srand(unsigned)time(NULL);for(i=0;i<numi+)(bianyipi=(rand()%100);bianyipi/=100;)/确定可以变异的染色体t=0;for(i=0;i<numi+)(if(bianyipi<pm)/变异操作，即交换染色体的两个节点srand(unsigned)time(NULL);for(i=0;i<numi+)(if(bianyifla

20、gi=1)(temp1=rand()%10;temp2=rand()%10;point=groupi.citytemp1;groupi.citytemp1=groupi.citytemp2;groupi.citytemp2=point;)intmain()inti,j,t;init();groupproduce();/初始种群评价pingjia();t=0;while(t+<MAXX(xuanze();/jiaopei();bianyi();pingjia();)/最终种群的评价printf("n输出最终的种群评价n");for(i=0;i<numi+)()pr

21、intf("最优解为d#染色体n",bestsolution);system("Pause");)（五）实验结果截图污kt。晟硅文件夹A工智i疆累羸露漏昙为概率分别为?裳用遗传算法好TSP问豁Debug't09851929染色体1的路径之和与生存概率分别为19800245染色体2的路径之和与生存概率分别为10333345除色体3的路径之和与生存概率分别为110333345快色体4的路径之和与生存概率分别为46222351染色体5的路径之和与生存概率分别为染色体6的路径之和与生存概率分别为除色体?的路径之和与生存概率分别为3生生生生生生生与与与与与

22、与与口口口口口口C之之之之本之之0的的的的的的的9012345一伊&质tttt/律，峰1色色色色色色色存存存存存存不5为为为为为为为V另另另另另另另Su?赛加强瓠和既和70.095070.098570.103370.103370.099570.096770.096770.103370.10330.09940.09920.09620.10300.10300.1013TSP问蓄Debugt.46800251染色体1的路径之和与生存概率分别为染色体2的路径之和与生存概率分别为10333345染色体3的路径之和与生存概率分别为10333345染色体4的路径之和与生存概率分别为19396245染色体5的路径之和与生存概率分别为19222245染色体6的路径之和与生存概率分别