TSP问题-遗传算法源代码

本程序是涉及8个城市的TSP问题的关于遗传算法的源代码，在VisualC++2010上调试运行，输出结果如下截图所示。另：8个城市的地理位置坐标={{3,4},{1,2},{4,7},{5,3},{1,12},{13,2},{22,21},{30,40}}。如有另需，只要修改城市的绝对位置坐标和城市数量MAXC就行了。#includeiostream#includestdio.h#includestdlib.h#includemath.h#includetime.h#defineMAXC8//个体大小#definePOPSIZE10//种群大小#defineNL10000//终止规则大N，最大不优化次数intparent[POPSIZE+1][MAXC+1];//二维数组，父代intchild[POPSIZE+1][MAXC+1];//二维数组，子代structcity//坐标{intx,y;};structcitylocation[MAXC+1]={{3,4},{1,2},{4,7},{5,3},{1,12},{13,2},{22,21},{30,40}};floatrandom0_1();//产生0到1的随机函数intrandom_n(int,int);//产生n1到n2的随机函数voidinipop(intpop[POPSIZE+1][MAXC+1]);//初始化群体floatdistance(intp1,intp2);//计算两点之间的距离floatfitfun(intpop[POPSIZE+1][MAXC+1],introw);//计算适应函数voidsortpop(intpop[POPSIZE+1][MAXC+1]);//种群排序voidcopypop(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1]);//拷贝种群voidcopycode(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1],intk,intm);//拷贝个体voidrepop(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1]);//产生种群voidcross(intpop[POPSIZE+1][MAXC+1]);//种群交叉voidmutation(intpop[POPSIZE+1][MAXC+1]);//种群变异voidprintcode(intpo[1][MAXC+1]);//输出个体floatfitfun(intpop[MAXC+1]);//计算个体适应函数voidmain(){intr;//循环次数intg;//进化代数intnloop=0;//最大优化次数intcopt[1][MAXC+1];//最优解floatfopt=100000;//适应函数的比较值srand((unsigned)time(NULL));inipop(parent);//群体初始化g=1;r=1;while(r){sortpop(parent);//群体排序if(foptfitfun(parent,1)){fopt=fitfun(parent,1);//记录优化自适应值nloop=0;copycode(parent,copt,1,0);//优化个体代码拷贝}elsenloop++;if(nloopNL)break;repop(parent,child);//产生种群cross(child);//种群交叉mutation(child);//种群变异copypop(child,parent);//拷贝种群//printf(%f\n,fopt);//输出自适应值//printf(%d%f\n,g,fopt);//输出进化代数，自适应值printf(进化代数:%d,其适应函数值:%f\n,g,fopt);//输出进化代数，自适应值g++;//进化代数自增r++;//循环次数自增//if(r==801)break;//循环次数限制}printf(最优解编码:);printcode(copt);}floatrandom0_1()//产生0到1的随机函数{floatr;r=(float)(rand()%32768+1);r=r/32768;return(r);}intrandom_n(intn1,intn2)//产生n1到n2的随机函数{intr;r=rand()%(n2-n1+1);r+=n1;return(r);}voidinipop(intpop[POPSIZE+1][MAXC+1])//初始化群体{inti,j,k,n,m,p[MAXC+1];for(i=1;i=POPSIZE;i++){for(k=1;k=MAXC;k++)p[k]=k;//产生一个数组，放1、2、3、4、5、6、...、MAXfor(j=1;j=MAXC;j++)//个体随机化{n=random_n(1,MAXC+1-j);pop[i][j]=p[n];for(m=n;mMAXC;m++)p[m]=p[m+1];}}}floatfitfun(intpop[POPSIZE+1][MAXC+1],introw)//计算适应函数{floatadd=0;intj;for(j=1;j=MAXC-1;j++)add+=distance(pop[row][j],pop[row][j+1]);add+=distance(pop[row][1],pop[row][MAXC]);return(add);}floatdistance(intp1,intp2)//计算两点之间的距离{floatdis;dis=(float)sqrt((float)((location[p1].x-location[p2].x)*(location[p1].x-location[p2].x)+(location[p1].y-location[p2].y)*(location[p1].y-location[p2].y)));return(dis);}voidsortpop(intpop[POPSIZE+1][MAXC+1])//种群排序{inti,j,k,temp;for(i=1;i=POPSIZE-1;i++)for(j=i+1;j=POPSIZE;j++){if(fitfun(pop,i)fitfun(pop,j))for(k=1;k=MAXC;k++){temp=pop[i][k];pop[i][k]=pop[j][k],pop[j][k]=temp;}}}voidcopypop(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1])//拷贝种群{inti;for(i=1;i=POPSIZE;i++)copycode(pop1,pop2,i,i);}voidcopycode(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1],intk,intm)//拷贝个体{intj;for(j=1;j=MAXC;j++)pop2[m][j]=pop1[k][j];}voidrepop(intpop1[POPSIZE+1][MAXC+1],intpop2[POPSIZE+1][MAXC+1])//产生种群{inti,j,choose;doubleq=1,a=0.9,fadd=0,eval[POPSIZE+1],roulette[POPSIZE+1],r;for(i=1;i=POPSIZE;i++){q*=a;fadd+=q;}q=1;eval[0]=0;for(i=1;i=POPSIZE;i++){q*=a;eval[i]=q/fadd;}//样本频率（样本概率）for(i=0;i=POPSIZE;i++)//计算累加频率（概率分布）{roulette[i]=0;for(j=0;j=i;j++)roulette[i]+=eval[j];}for(i=1;i=POPSIZE;i++){r=(float)(random0_1());for(j=1;j=POPSIZE;j++)if(r=roulette[j]){choose=j;break;}copycode(pop1,pop2,choose,i);}}voidcross(intpop[POPSIZE+1][MAXC+1])//种群交叉{inti,j,cpos=MAXC-1,c1,c2;for(i=1;i=POPSIZE;i+=2){if(pop[i][cpos]==pop[i+1][cpos])continue;else{c1=pop[i][cpos];c2=pop[i+1][cpos];for(j=1;j=MAXC;j++)if(pop[i][j]==c2){pop[i][j]=c1;pop[i][cpos]=c2;break;}for(j=1;j=MAXC;j++)if(pop[i+1][j]==c1){pop[i+1][j]=c2;pop[i+1][cpos]=c1;break;}}}}voidmutation(intpop[POPSIZE+1][MAXC+1])//种群变异{intii,p1,p2,temp;doubler,a=0.1;for(ii=1;ii=POPSIZE;ii++){r=random0_1();if(ra){do{p1=random_n(1,MAXC);p2=random_n(1,MAXC);}while(p1==p2);temp=pop[ii][p1];pop[ii][p1]=pop[ii][p2];pop[ii][p2]=temp;}}}voidprintcode(intpo[1][MAXC+1])//输出个体{inti;for(i=1;i=MAXC;i++)printf(%d,po[0][i]);printf(其适应值为%f,fitfun(po,0));printf(\n);}