最新TSP问题-遗传算法源代码.docx
精品资料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 <iostream>#include "stdio.h"#include "stdlib.h"#include "math.h" #include "time.h"#define MAXC 8 /个体大小#define POPSIZE 10 /种群大小#define NL 10000 /终止规则大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,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,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(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("%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);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;m<MAXC;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-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;j<=POPSIZE;j+) if(fitfun(pop,i)>fitfun(pop,j)for(k=1;k<=MAXC;k+)temp=popik;popik=popjk,popjk=temp; void copypop(int pop1POPSIZE+1MAXC+1,int pop2POPSIZE+1MAXC+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,evalPOPSIZE+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;break; 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; 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(r<a) 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");
