TSP问题-遗传算法源代码

精选优质文档-----倾情为你奉上精选优质文档-----倾情为你奉上专心---专注---专业专心---专注---专业精选优质文档-----倾情为你奉上专心---专注---专业本程序是涉及8个城市的TSP问题的关于遗传算法的源代码，在VisualC++2010上调试运行，输出结果如下截图所示。另：8个城市的地理位置坐标={{3,4},{1,2},{4,7},{5,3},{1,12},{13,2},{22,21},{30,40}}。如有另需，只要修改城市的绝对位置坐标和城市数量MAXC就行了。#include<iostream>#include"stdio.h"#include"stdlib.h"#include"math.h"#include"time.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=;//适应函数的比较值 srand((unsigned)time(NULL));inipop(parent);//群体初始化 g=1; r=1;while(r){ sortpop(parent);//群体排序 if(fopt>fitfun(parent,1)) { fopt=fitfun(parent,1);//记录优化自适应值 nloop=0; copycode(parent,copt,1,0);//优化个体代码拷贝 } else nloop++; if(nloop>NL) 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、...、MAX for(j=1;j<=MAXC;j++)//个体随机化 {n=random_n(1,MAXC+1-j); pop[i][j]=p[n]; for(m=n;m<MAXC;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(r<a) {do{p1=random_n(