遗传算法解TSP问题

利用遗传算法解决TSP问题遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，对解决TSP问题有比较好的效果。TSP问题（旅行商问题）：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。此次设计考虑了N=10的情况，假设10个城市的位置坐标如表1所示，其中1-10表示10个城市的编号。为了便于对比，与之前用Hopfield神经网络解决TSP问题的初始化城市坐标相同。表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}};doubleCost_table[10][10];typedefstructunit{intpath[num_C];//个体的路径信息intcost;//个体代价值};structunitgroup[N];//种群变量groupintnum_gen=0;//记录当前达到第几代for(i=0;i10;i++)for(j=0;j10;j++){Cost_table[i][j]=0;}for(i=0;i10;i++){for(k=0;k10;k++){Cost_table[i][k]=sqrt((a[0][k]-a[0][i])*(a[0][k]-a[0][i])+(a[1][k]-a[1][i])*(a[1][k]-a[1][i]));printf(%f\t,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-path[j]=RandomInteger(0,num_C-1);else{p-path[j]=RandomInteger(0,num_C-1);while(kj){if(p-path[j]==p-path[k]){p-path[j]=RandomInteger(0,num_C-1);k=0;}elsek++;}//endwhile}}Calculate_cost(p);//计算该路径的代价值}}（3）种群进化，杂交，变异简单遗传算法的遗传操作主要有三种：选择，杂交和变异。选择即根据个体的适应度函数值所度量的优劣程度决定在下一代是被遗传还是淘汰。对于杂交操作，在顺序编码后，用简单的一点杂交或者多点杂交，不能确保一代比一代优，而且会导致未能完全遍历所有城市的非法路径，可选用两交换启发交叉(HGA)、三交换启发交叉(THGA)将生成的子代按适应度由小到大排序，将它赋给父代，同时将该代的适应度最优，即距离最短的个体与父代的最优比较，存储两者最优的。重新循环。这样就能将一代中最优的个体保存下来。voidEvolution(structunitgroup[N]){inti,j;inttemp1,temp2,temp3,temp4,temp5;temp1=N*pc/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,i);}Sort(group);Print_optimum(group,i-1);}/*交叉*/voidCross(structunit*p1,structunit*p2){inti,j,cross_point;intson1[num_C],son2[num_C];for(i=0;i=num_C-1;i++){son1[i]=-1;son2[i]=-1;}cross_point=RandomInteger(1,num_C-1);//交叉位随机生成for(i=0;i=cross_point-1;i++)son1[i]=p1-path[i];for(i=cross_point;i=num_C-1;i++){for(j=0;j=num_C-1;j++){if(search_son(son1,p2-path[j])==1){son1[i]=p2-path[j];break;}else;}}for(i=cross_point;i=num_C-1;i++)son2[i]=p2-path[i];for(i=0;i=cross_point-1;i++){for(j=0;j=num_C-1;j++){if(search_son(son2,p1-path[j])==1){son2[i]=p1-path[j];break;}else;}}//交叉for(i=0;i=num_C-1;i++){p1-path[i]=son1[i];p2-path[i]=son2[i];}Calculate_cost(p1);Calculate_cost(p2);}voidVaration(structunitgroup[N],intflag_v){intflag,i,j,k,temp;structunit*p;flag=RandomInteger(1,100);if(flag=(flag_v100)?(5*100*pm):(100*pm)){i=RandomInteger(0,N-1);//确定发生变异的个体j=RandomInteger(0,num_C-1);k=RandomInteger(0,num_C-1);p=&group[i];//变异temp=p-path[j];p-path[j]=p-path[k];p-path[k]=temp;Calculate_cost(p);//重新计算变异后路径的代价}}intsearch_son(intson[num_C],intk){inti;for(i=0;i=num_C-1;i++){if(son[i]==k)return-1;else;}return1;}/*将种群中个体按代价从小到大排序*/voidSort(structunitgroup[N]){inti,j;structunittemp,*p1,*p2;for(j=1;j=N-1;j++){for(i=1;i=N-1;i++){p1=&group[i-1];p2=&group[i];if(p1-costp2-cost){Copy_unit(p1,&temp);Copy_unit(p2,p1);Copy_unit(&temp,p2);}}}}/*计算某个路径的代价值*/voidCalculate_cost(structunit*p){intj;p-cost=0;for(j=1;j=num_C-1;j++){p-cost+=Cost_table[p-path[j-1]][p-path[j]];}p-cost+=Cost_table[p-path[num_C-1]][p-path[0]];}voidCopy_unit(structunit*p1,structunit*p2){inti;for(i=0;i=num_C-1;i++)p2-path[i]=p1-path[i];p2-cost=p1-cost;}intRandomInteger(intlow,inthigh){intk;doubled;k=rand();k=(k!=RAND_MAX)?k:(k-1);d=(double)k/((double)(RAND_MAX));k=(int)(d*(high-low+1));return(low+k);}voidPrint_optimum(structunitgroup[N],intk){inti,j;structunit*p;printf(当前第%d代：\n,k);for(i=0;i=N-1;i++){printf(第%d代，个体%d：,k,i);p=&group[i];for(j=0;j=num_C-1;j++)printf(%d,p-path[j]);printf(代价值为：%d\n,p-cost);}}（4）进化结果程序设置的迭代次数为200代，在实际操作中发现，当迭代到第90代时已经收敛，可见遗传算法的搜索的快速性。利用本遗传算法，最终得到的路径为1-2-3-4-5-6-9-10-8-7-1；路径代价为：3.054。在前次作业用Hopfield神经网络解决TSP问题中，通过多次试验得到最短的路径代价为2.9137。与之前Hopfield神经网络的结果相比，本次的代价比较大，可见本遗传算法需要一定的改进。在文献查阅中了解到在用遗传算法解题时，需要考虑出现各代适应函数值收敛过快导致过早成熟，以致找不到最优解。另外群体数目越大，越能获得最优解，但是机器耗时会变大。总之，本次作业使我对于理解遗传算法有了较深的理解，对以后智能算法的学习有很大的帮助。