遗传算法解决TSP问题(C++)

遗传算法解决TSP问题（C++版）遗传算法流程：交叉，编译，计算适应度，保存最优个体。其中交叉过程是选择最优的两个染色体进行交叉操作，本文采用的是轮盘赌算法。#includeiostream#includecstdlib#includectimeusingnamespacestd;#definepopulation200//种群数量#definepc0.9//交叉的概率#definepm0.1//变异的概率#definecount200//迭代的次数#definenum10//城市的数量int**city;//存放每个个体的访问顺序intpath[10][10]={//0,1,2,3,4,5,6,7,8,9{0,23,93,18,40,34,13,75,50,35},//0{23,0,75,4,72,74,36,57,36,22},//1{93,75,0,64,21,73,51,25,74,89},//2{18,4,64,0,55,52,8,10,67,1},//3{40,72,21,55,0,43,64,6,99,74},//4{34,74,73,52,43,0,43,66,52,39},//5{13,36,51,8,64,43,0,16,57,94},//6{75,57,25,10,6,66,16,0,23,11},//7{50,36,74,67,99,52,57,23,0,42},//8{35,22,89,1,74,39,94,11,42,0}//9};int*dis;//存放每个个体的访问顺序下的路径长度double*fitness;//存放灭个个体的适应度intmin_dis=1000000;intmin_index=-1;int*min_path;//初始化种群voidinit(){int*a=newint[num];for(inti=0;inum;i++){a[i]=i;}city=newint*[population];for(inti=0;ipopulation;i++){city[i]=newint[num];}for(inti=0;ipopulation;i++){for(intj=num-1;j=0;j--){intn=rand()%(j+1);//产出的数是0-j,保证交换的后面的数不会再被交换swap(a[j],a[n]);//保证a里面全是0-(num-1)的数，无重复的数，只是顺序颠倒city[i][j]=a[j];}}delete[]a;dis=newint[population];fitness=newdouble[population];min_path=newint[num];}//计算适应度voidcompute(){//coutdocomputenow.endl;doubletotal=0;for(inti=0;ipopulation;i++){//计算每种情况下，路径的长度dis[i]=0;inta=city[i][0],b;for(intj=1;jnum;j++){b=city[i][j];dis[i]+=path[a][b];a=b;}dis[i]+=path[b][city[i][0]];fitness[i]=1.0/dis[i];//以距离的倒数作为适应度函数值total+=fitness[i];}}//选择适应度高的物种，采用轮盘赌算法intselect(){doubletotal=0;for(inti=0;ipopulation;i++){total+=fitness[i];}doublesize=rand()/(double)RAND_MAX*total;//保证不产生0//coutsizesizeendl;doublesum=0;inti=0;while(sum=size&&ipopulation){sum+=fitness[++i];}return--i;//返回被选中的个体}intgetMinDis(){intresult=dis[0];intindex=0;for(inti=1;ipopulation;i++){if(resultdis[i]){result=dis[i];index=i;}}returnindex;}intgetMaxDis(){intresult=dis[0];intindex=0;for(inti=1;ipopulation;i++){if(resultdis[i]){result=dis[i];index=i;}}returnindex;}voidsave(){intcurrent_min_index=getMinDis();intcurrent_max_index=getMaxDis();if(dis[current_min_index]min_dis){min_dis=dis[current_min_index];for(inti=0;inum;i++){min_path[i]=city[current_min_index][i];}//coutcurrentmindisis:min_disendl;}else{for(inti=0;inum;i++){city[current_max_index][i]=min_path[i];}dis[current_max_index]=min_dis;fitness[current_max_index]=1.0/min_dis;}}//最优保存算法boolisExist(intvalue,int*array,intlen){for(inti=0;ilen;i++){if(value==array[i])returntrue;}returnfalse;}voidconvert(intp1,intp2,int*src,int*dst){intlen=p2-p1+1;int*temp=newint[len];for(inti=p1;i=p2;i++){temp[i-p1]=src[i];}intj=(p2+1)%num;for(inti=1;i=num;i++){intindex=(i+p2)%num;if(!isExist(dst[index],temp,len)){dst[j]=dst[index];j=(j+1)%num;}}for(inti=p1;i=p2;i++){dst[i]=src[i];}delete[]temp;}//交叉，采用次序交叉算法voidcross(){//coutdocrossnow.endl;for(intk=0;kpopulation;k+=2){inta=select();intb=select();while(a==b){b=select();//保证被选中的个体不是一样的//coutsamebendl;}//coutchoosepopuilationabendl;doublep=rand()/double(RAND_MAX);//coutcrossrateispendl;int*a1=newint[num];int*a2=newint[num];int*b1=newint[num];int*b2=newint[num];for(inti=0;inum;i++){a1[i]=city[a][i];a2[i]=city[b][i];b1[i]=a2[i];b2[i]=a1[i];}if(ppc)//满足交叉条件{//选择交叉的两点，并保证p1p2intp1=-1;intp2=-1;while(p1==p2){p1=rand()%num;p2=rand()%num;if(p1p2){swap(p1,p2);}}//coutchooseposp1p2endl;//开始交叉convert(p1,p2,a1,b1);convert(p1,p2,a2,b2);for(inti=0;inum;i++){city[k][i]=b1[i];city[k+1][i]=b2[i];}}else{for(inti=0;inum;i++){city[k][i]=a1[i];city[k+1][i]=a2[i];}}delete[]a1;delete[]a2;delete[]b1;delete[]b2;}}//变异,采用对换操作进行变异voidmorphis(){//coutdomorphisnow.endl;for(inti=0;ipopulation;i++){doublep=rand()/double(RAND_MAX);//coutmorphisrateispendl;if(ppm)//执行变异{inta=-1,b=-1;while(a==b){a=rand()%num;b=rand()%num;}swap(city[i][a],city[i][b]);}}}intgetdis(){//compute();intresult=dis[0];intindex=0;for(inti=1;ipopulation;i++){if(resultdis[i]){result=dis[i];index=i;}}returnresult;}//释放申请的数组的空间voiddispose(){for(inti=0;ipopulation;i++){delete[]city[i];}delete[]city;delete[]dis;delete[]fitness;}intmain(){init();//初始化种群inti=0;srand(time(0));compute();while(icount){cross();//交叉morphis();//变异compute();//计算适应度save();//保存当前最优的个体//coutcounti++endl;coutgetdis();//输出结果//coutmin_index;if(++i%10==0)coutendl;}compute();coutmindistanceis:min_disendl;for(inti=0;inum;i++)coutmin_path[i];coutendl;dispose();//释放空间return0;}