《最新TSP问题-遗传算法源代码.docx》由会员分享，可在线阅读，更多相关《最新TSP问题-遗传算法源代码.docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品资料TSP问题-遗传算法源代码.本程序是涉及8个城市的TSP问题的关于遗传算法的源代码，在Visual C+ 2010上调试运行，输出结果如下截图所示。另：8个城市的地理位置坐标=3,4,1,2,4,7,5,3,1,12,13,2,22,21,30,40。如有另需，只要修改城市的绝对位置坐标和城市数量MAXC就行了。#include #include stdio.h#include stdlib.h#include math.h #include time.h#define MAXC 8 /个体大小#define POPSIZE 10 /种群大小#define NL 10000 /终止规则
2、大N，最大不优化次数int parentPOPSIZE+1MAXC+1; /二维数组，父代int childPOPSIZE+1MAXC+1; /二维数组，子代struct city /坐标 int x,y; ;struct city locationMAXC+1=3,4,1,2,4,7,5,3,1,12,13,2,22,21,30,40;float random0_1(); /产生0到1的随机函数int random_n(int,int); /产生n1到n2的随机函数void inipop(int popPOPSIZE+1MAXC+1); /初始化群体float distance(int p1
3、,int p2); /计算两点之间的距离float fitfun(int popPOPSIZE+1MAXC+1,int row); /计算适应函数void sortpop(int popPOPSIZE+1MAXC+1); /种群排序void copypop(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAXC+1); /拷贝种群void copycode(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAXC+1,int k,int m); /拷贝个体void repop(int pop1POPSIZE+1MAXC+1,
4、int pop2POPSIZE+1MAXC+1); /产生种群void cross(int popPOPSIZE+1MAXC+1); /种群交叉void mutation(int popPOPSIZE+1MAXC+1); /种群变异void printcode(int po1MAXC+1); /输出个体float fitfun(int popMAXC+1); /计算个体适应函数void main() int r; /循环次数int g; /进化代数int nloop=0; /最大优化次数int copt1MAXC+1; /最优解float fopt=100000; /适应函数的比较值srand
5、(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); /优化个体代码拷贝 else nloop+; if(nloopNL) break; repop(parent,child); /产生种群 cross(child); /种群交叉 mutation(child); /种群变异 copypop(
6、child,parent);/拷贝种群/ printf(%fn,fopt); /输出自适应值/ printf(%d %fn,g,fopt); /输出进化代数，自适应值 printf(进化代数:%d,其适应函数值:%fn,g,fopt); /输出进化代数，自适应值 g+; /进化代数自增 r+; /循环次数自增/ if(r=801) break; /循环次数限制 printf(最优解编码:); printcode(copt);float random0_1() /产生0到1的随机函数 float r; r=(float)(rand()%32768+1); r=r/32768; return(r)
7、;int random_n(int n1,int n2) /产生n1到n2的随机函数 int r; r=rand()%(n2-n1+1); r+=n1; return(r);void inipop(int popPOPSIZE+1MAXC+1) /初始化群体 int i,j,k,n,m,pMAXC+1; for(i=1;i=POPSIZE;i+) for(k=1;k=MAXC;k+) pk=k; /产生一个数组，放1、2、3、4、5、6、.、MAXfor(j=1;j=MAXC;j+) /个体随机化 n=random_n(1,MAXC+1-j); popij=pn; for(m=n;mMAXC;
8、m+) pm=pm+1; float fitfun(int popPOPSIZE+1MAXC+1,int row) /计算适应函数 float add=0; int j;for(j=1;j=MAXC-1;j+) add+=distance(poprowj,poprowj+1);add+=distance(poprow1,poprowMAXC);return(add);float distance(int p1,int p2) /计算两点之间的距离 float dis; dis=(float)sqrt(float)(locationp1.x-locationp2.x)*(locationp1.x
9、-locationp2.x)+(locationp1.y-locationp2.y)*(locationp1.y-locationp2.y);return(dis);void sortpop(int popPOPSIZE+1MAXC+1) /种群排序 int i,j,k,temp; for(i=1;i=POPSIZE-1;i+) for(j=i+1;jfitfun(pop,j)for(k=1;k=MAXC;k+)temp=popik;popik=popjk,popjk=temp; void copypop(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAX
10、C+1) /拷贝种群 int i; for(i=1;i=POPSIZE;i+) copycode(pop1,pop2,i,i);void copycode(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAXC+1,int k,int m) /拷贝个体 int j; for(j=1;j=MAXC;j+) pop2mj=pop1kj;void repop(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAXC+1) /产生种群 int i,j,choose; double q=1,a=0.9,fadd=0,evalPOPSI
11、ZE+1,roulettePOPSIZE+1,r; for(i=1;i=POPSIZE;i+)q*=a;fadd+=q; q=1;eval0=0; for(i=1;i=POPSIZE;i+)q*=a;evali=q/fadd; /样本频率（样本概率） for(i=0;i=POPSIZE;i+) /计算累加频率（概率分布） roulettei=0;for(j=0;j=i;j+)roulettei+=evalj; for(i=1;i=POPSIZE;i+) r=(float)(random0_1(); for(j=1;j=POPSIZE;j+)if(r=roulettej)choose=j;bre
12、ak; copycode(pop1,pop2,choose,i); void cross(int popPOPSIZE+1MAXC+1) /种群交叉 int i,j,cpos=MAXC-1,c1,c2; for(i=1;i=POPSIZE;i+=2) if(popicpos=popi+1cpos)continue; else c1=popicpos; c2=popi+1cpos; for(j=1;j=MAXC;j+) if(popij=c2) popij=c1; popicpos=c2; break; for(j=1;j=MAXC;j+) if(popi+1j=c1) popi+1j=c2;
13、popi+1cpos=c1; break; void mutation(int popPOPSIZE+1MAXC+1) /种群变异 int ii,p1,p2,temp; double r,a=0.1; for(ii=1;ii=POPSIZE;ii+) r=random0_1(); if(ra) dop1=random_n(1,MAXC);p2=random_n(1,MAXC); while(p1=p2); temp=popiip1; popiip1=popiip2; popiip2=temp; void printcode(int po1MAXC+1) /输出个体 int i; for(i=1;i=MAXC;i+)printf( %d ,po0i);printf( 其适应值为%f,fitfun(po,0);printf(n);