资源描述：
《遗传算法解TSP问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、利用遗传算法解决TSP问题遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，对解决TSP问题有比较好的效果。TSP问题（旅行商问题）：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。此次设计考虑了N=10的情况，假设10个城市的位置坐标如表1所示，其中1-10表示10个城市的编号。为了便于对比，与之前用Hopfield神经网络解决TSP问题的初始
2、化城市坐标相同。表1城市坐标城市12345678910X坐标0.10.20.40.50.70.80.20.50.70.9Y坐标0.60.30.10.50.20.40.80.90.60.8算法设计（1）初始化信息。根据城市坐标求出两两城市之间的距离。定群体规模为100，交叉概论0.9，变异概率0.1，最大迭代次数200。doublea[2][10]={{0.1,0.2,0.4,0.5,0.7,0.8,0.2,0.5,0.7,0.9},{0.6,0.3,0.1,0.5,0.2,0.4,0.8,0.9,0.6,0.8}};doubleC
3、ost_table[10][10];typedefstructunit{intpath[num_C];//个体的路径信息intcost;//个体代价值};structunitgroup[N];//种群变量groupintnum_gen=0;//记录当前达到第几代for(i=0;i<10;i++)for(j=0;j<10;j++){Cost_table[i][j]=0;}for(i=0;i<10;i++){for(k=0;k<10;k++){Cost_table[i][k]=sqrt((a[0][k]-a[0][i])*(a[0][
4、k]-a[0][i])+(a[1][k]-a[1][i])*(a[1][k]-a[1][i]));printf("%ft",Cost_table[i][k]);}}（2）初始化种群voidInitial_gen(structunitgroup[N]){inti,j,k;structunit*p;for(i=0;i<=N-1;i++)//初始化种群里的100个个体{p=&group[i];//p指向种群的第i个个体for(j=0;j<=num_C-1;j++)//生成10个城市间的一个随机路径{k=0;if(j==0)p->pat
5、h[j]=RandomInteger(0,num_C-1);else{p->path[j]=RandomInteger(0,num_C-1);while(kpath[j]==p->path[k]){p->path[j]=RandomInteger(0,num_C-1);k=0;}elsek++;}//endwhile}}Calculate_cost(p);//计算该路径的代价值}}（3）种群进化，杂交，变异简单遗传算法的遗传操作主要有三种：选择，杂交和变异。选择即根据个体的适应度函数值所度量的优劣程度决定在下一
6、代是被遗传还是淘汰。对于杂交操作，在顺序编码后，用简单的一点杂交或者多点杂交，不能确保一代比一代优，而且会导致未能完全遍历所有城市的非法路径，可选用两交换启发交叉(HGA)、三交换启发交叉(THGA)将生成的子代按适应度由小到大排序，将它赋给父代，同时将该代的适应度最优，即距离最短的个体与父代的最优比较，存储两者最优的。重新循环。这样就能将一代中最优的个体保存下来。voidEvolution(structunitgroup[N]){inti,j;inttemp1,temp2,temp3,temp4,temp5;temp1=N*pc
7、/2;temp2=N*(1-pc);temp3=N*(1-pc/2);temp4=N*(1-ps);temp5=N*ps;for(i=1;i<=genmax;i++){Sort(group);//选择Print_optimum(group,i-1);for(j=0;j<=temp4-1;j++){Copy_unit(&group[j],&group[j+temp5]);}for(j=0;j<=temp1-1;){Cross(&group[temp2+j],&group[temp3+j]);j+=2;}Varation(group,
8、i);}Sort(group);Print_optimum(group,i-1);}/*交叉*/voidCross(structunit*p1,structunit*p2){inti,j,cross_point;intson1[num_C],son
