详细介绍如何利用各种语言(C++,C,JAV等)实现遗传算法.doc

%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序1一个C+的程序：3C语言程序：7改进后用来求解VRP问题的Delphi程序：20%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序%D是距离矩阵，n为种群个数,建议取为城市个数的12倍，%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大%alpha为淘汰保护指数,可取为01之间任意小数,取1时关闭保护功能,最好取为0.81.0%R为最短路径,Rlength为路径长度function R,Rlength=geneticTSP(D,n,C,m,alpha)N,NN=size(D);farm=zeros(n,N);%用于存储种群for i=1:nfarm(i,:)=randperm(N);%随机生成初始种群endR=farm(1,:);%存储最优种群len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储归一化适应值counter=0;while counter=alpha*randnn=nn+1;FARM(nn,:)=farm(i,:);endendFARM=FARM(1:nn,:);aa,bb=size(FARM);%交叉和变异while aanif nnnFARM=FARM(1:n,:);%保持种群规模为nendfarm=FARM;clear FARMcounter=counter+1endRlength=myLength(D,R);function a,b=intercross(a,b)L=length(a);if L=rand&L10W=ceil(L/10);else W=floor(L/10);endp=unidrnd(L-W+1);%随机选择交叉范围，从p到p+Wfor i=1:W%交叉x=find(a=b(1,p+i-1);y=find(b=a(1,p+i-1);a(1,p+i-1),b(1,p+i-1)=exchange(a(1,p+i-1),b(1,p+i-1);a(1,x),b(1,y)=exchange(a(1,x),b(1,y); endfunction x,y=exchange(x,y)temp=x;x=y;y=temp;% 计算路径的子程序function len=myLength(D,p)N,NN=size(D);len=D(p(1,N),p(1,1);for i=1:(N-1)len=len+D(p(1,i),p(1,i+1);end%计算归一化适应值子程序function fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.000001).m;end 一个C+的程序：/c+的程序#include#includetemplateclass Graphpublic:Graph(int vertices=10)n=vertices;e=0;Graph()virtual bool Add(int u,int v,const T& w)=0;virtual bool Delete(int u,int v)=0;virtual bool Exist(int u,int v)const=0;int Vertices()constreturn n;int Edges()constreturn e;protected:int n;int e;templateclass MGraph:public Graphpublic:MGraph(int Vertices=10,T noEdge=0);MGraph();bool Add(int u,int v,const T& w);bool Delete(int u,int v);bool Exist(int u,int v)const;void Floyd(T*& d,int*& path);void print(int Vertices);private:T NoEdge;T* a;templateMGraph:MGraph(int Vertices,T noEdge)n=Vertices;NoEdge=noEdge;a=new T* n;for(int i=0;in;i+)ai=new Tn;aii=0;for(int j=0;jn;j+)if(i!=j)aij=NoEdge;templateMGraph:MGraph()for(int i=0;in;i+)deleteai;deletea;templatebool MGraph:Exist(int u,int v)constif(u0|vn-1|vn-1|u=v|auv=NoEdge)return false;return true;templatebool MGraph:Add(int u,int v,const T& w)if(u0|vn-1|vn-1|u=v|auv!=NoEdge)cerrBadInput!endl;return false;auv=w;e+;return true;templatebool MGraph:delete(int u,int v)if(u0|vn-1|vn-1|u=v|auv=NoEdge)cerrBadInput!endl;return false;auv=NoEdge;e-;return true;templatevoid MGraph:Floyd(T*& d,int*& path)d=new T* n;path=new int* n;for(int i=0;in;i+)di=new Tn;pathi=new intn;for(int j=0;jn;j+)dij=aij;if(i!=j&aijNoEdge)pathij=i;else pathij=-1;for(int k=0;kn;k+)for(i=0;in;i+)for(int j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;templatevoid MGraph:print(int Vertices)for(int i=0;iVertices;i+)for(int j=0;jVertices;j+)coutaij ;if(j=Vertices-1)coutendl;#define noEdge 10000#includevoid main()cout请输入该图的节点数：vertices;MGraph b(vertices,noEdge);cout请输入u,v,w:uvw;while(w!=noEdge)/u=u-1;b.Add(u-1,v-1,w);b.Add(v-1,u-1,w);cout请输入u,v,w:uvw;b.print(vertices);int* Path;int*& path=Path;float* D;float*& d=D;b.Floyd(d,path);for(int i=0;ivertices;i+)for(int j=0;jvertices;j+)coutPathij ;if(j=vertices-1)coutendl;int *V;V=new intvertices+1;cout请输入任意一个初始H-圈：endl;for(int n=0;nVn;for(n=0;n55;n+)for(i=0;in-1;i+)for(int j=0;j0&ji+1&jn-1)if(DViVj+DVi+1Vj+1DViVi+1+DVjVj+1)int l;l=Vi+1;Vi+1=Vj;Vj=l;float total=0;cout最小回路：endl;for(i=0;i=vertices;i+)coutVi+1 ;coutendl;for(i=0;ivertices;i+)total+=DViVi+1;cout最短路径长度：endl;couttotal; C语言程序：#include#include#include#include#include#include#include#include#include#define maxpop 100#define maxstring 100struct ppunsigned char chrommaxstring;float x,fitness;unsigned int parent1,parent2,xsite;struct pp *oldpop,*newpop,*p1;unsigned int popsize,lchrom,gem,maxgen,co_min,jrand;unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;float pcross,pmutation,sumfitness,avg,max,min,seed,maxold,oldrandmaxstring;unsigned char xmaxstring,ymaxstring ;float *dd,ff,maxdd,refpd,fm201;FILE *fp,*fp1;float objfunc(float);void statistics();int select();int flip(float);int crossover();void generation();void initialize();void report();float decode();void crtinit();void inversion();float random1();void randomize1();main()unsigned int gen,k,j,tt;char fname10;float ttt;clrscr();co_min=0;if(oldpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)=NULL)printf(memory requst fail!n);exit(0);if(dd=(float *)farmalloc(maxstring*maxstring*sizeof(float)=NULL)printf(memory requst fail!n);exit(0);if(newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp)=NULL)printf(memory requst fail!n);exit(0);if(p1=(struct pp *)farmalloc(sizeof(struct pp)=NULL)printf(memory requst fail!n);exit(0);for(k=0;kmaxpop;k+) oldpopk.chrom0=0;for(k=0;kmaxpop;k+) newpopk.chrom0=0;printf(Enter Result Data Filename:);gets(fname);if(fp=fopen(fname,w+)=NULL)printf(cannot open filen);exit(0);gen=0;randomize();initialize();fputs(this is result of the TSP problem:,fp);fprintf(fp,city: %2d psize: %3d Ref.TSP_path: %fn,lchrom,popsize,refpd);fprintf(fp,Pc: %f Pm: %f Seed: %fn,pcross,pmutation,seed);fprintf(fp,X site:n);for(k=0;klchrom;k+)if(k%16)=0) fprintf(fp,n);fprintf(fp,%5d,xk);fprintf(fp,n Y site:n);for(k=0;kmaxold)maxold=max;co_min=0;fmgen%200=100.0*oldpopmaxpp.x/ff;report(gen,oldpop);gotoxy(30,25);ttt=clock()/18.2;tt=ttt/60;printf(Run Clock: %2d: %2d: %4.2f,tt/60,tt%60,ttt-tt*60.0);printf(Min=%6.4f Nm:%dn,min,co_min);while(genmaxold)maxold=max;co_min=0;fmgen%200=100.0*oldpopmaxpp.x/ff;report(gen,oldpop);if(gen%100)=0)report(gen,oldpop);gotoxy(30,25);ttt=clock()/18.2;tt=ttt/60;printf(Run Clock: %2d: %2d: %4.2f,tt/60,tt%60,ttt-tt*60.0);printf(Min=%6.4f Nm:%dn,min,co_min);while(genmaxgen)&!bioskey(1);getch();for(k=0;klchrom;k+)if(k%16)=0)fprintf(fp,n);fprintf(fp,%5d,oldpopmaxpp.chromk );fprintf(fp,n);fclose(fp);farfree(dd);farfree(p1);farfree(oldpop);farfree(newpop);restorecrtmode();exit(0);/*%*/float objfunc(float x1)float y;y=100.0*ff/x1;return y;/*&*/void statistics(pop)struct pp *pop;int j;sumfitness=pop0.fitness;min=pop0.fitness;max=pop0.fitness;maxpp=0;minpp=0;for(j=1;jmax)max=popj.fitness;maxpp=j;if(popj.fitnessmin)for(k=0;kmin)for(k=0;klchrom;k+)oldpopminpp.chromk=newpopj+1.chromk;oldpopminpp.x=newpopj+1.x;oldpopminpp.fitness=newpopj+1.fitness;co_min+;return;j=j+2;while(jpopsize);/*%*/void initdata()unsigned int ch,j;clrscr();printf(-n);printf(A SGAn);printf(-n);/*pause();*/clrscr();printf(*SGA DATA ENTRY AND INITILIZATION *n);printf(n);printf(input pop size);scanf(%d,&popsize);printf(input chrom length);scanf(%d,&lchrom);printf(input max generations);scanf(%d,&maxgen);printf(input crossover probability);scanf(%f,&pcross);printf(input mutation prob);scanf(%f,&pmutation);randomize1();clrscr();nmutation=0;ncross=0;/*%*/void initreport()int j,k;printf(pop size=%dn,popsize);printf(chromosome length=%dn,lchrom);printf(maxgen=%dn,maxgen);printf(pmutation=%fn,pmutation);printf(pcross=%fn,pcross);printf(initial generation statisticsn);printf(ini pop max fitness=%fn,max);printf(ini pop avr fitness=%fn,avg);printf(ini pop min fitness=%fn,min);printf(ini pop sum fit=%fn,sumfitness);void initpop( )unsigned char j1;unsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5maxstring;float f1,f2;j=0;for(k=0;klchrom;k+)oldpopj.chromk=k;for(k=0;klchrom;k+)p5k=oldpopj.chromk;randomize();for(;jpopsize;j+)j2=random(lchrom);for(k=0;kj2+20;k+)j3=random(lchrom);j4=random(lchrom);j1=p5j3;p5j3=p5j4;p5j4=j1;for(k=0;klchrom;k+)oldpopj.chromk=p5k;for(k=0;klchrom;k+)for(j=0;jlchrom;j+)ddk*lchrom+j=hypot(xk-xj,yk-yj);for(j=0;jpopsize;j+)oldpopj.x=(float)decode(oldpopj.chrom);oldpopj.fitness=objfunc(oldpopj.x);oldpopj.parent1=0;oldpopj.parent2=0;oldpopj.xsite=0;/*&*/void initialize()int k,j,minx,miny,maxx,maxy;initdata();minx=0;miny=0;maxx=0;maxy=0;for(k=0;kmaxx)maxx=xk;if(xkmaxy)maxy=yk;if(yk(maxy-miny)maxxy=maxx-minx;else maxxy=maxy-miny;maxdd=0.0;for(k=0;klchrom;k+)for(j=0;jlchrom;j+)ddk*lchrom+j=hypot(xk-xj,yk-yj);if(maxddddk*lchrom+j)maxdd=ddk*lchrom+j;refpd=ddlchrom-1;for(k=0;klchrom;k+)refpd=refpd+ddk*lchrom+k+2;for(j=0;jlchrom;j+)ddj*lchrom+j=4.0*maxdd;ff=(0.765*maxxy*pow(lchrom,0.5);minpp=0;min=ddlchrom-1;for(j=0;jlchrom-1;j+)if(ddlchrom*j+lchrom-1min)min=ddlchrom*j+lchrom-1;minpp=j;initpop();statistics(oldpop);initreport();/*&*/void report(int l,struct pp *pop)int k,ix,iy,jx,jy;unsigned int tt;float ttt;cleardevice();gotoxy(1,1);printf(city:%4d para_size:%4d maxgen:%4d ref_tour:%fn,lchrom,popsize,maxgen,refpd);printf(ncross:%4d Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4fnn,ncross,nmutation,l,avg,min);printf(Rinpath:%6.4f Minpath length:%10.4f Ref_co_tour:%fn,popmaxpp.x/maxxy,popmaxpp.x,ff);printf(Co_minpath:%6.4f Maxfit:%10.8f,100.0*popmaxpp.x/ff,popmaxpp.fitness);ttt=clock()/18.2;tt=ttt/60;printf(Run clock:%2d:%2d:%4d.2fn,tt/60,tt%60,ttt-tt*60.0);setcolor(1%15+1);for(k=0;klchrom-1;k+)ix=xpopmaxpp.chromk;iy=ypopmaxpp.chromk+110;jx=xpopmaxpp.chromk+1;jy=ypopmaxpp.chromk+1+110;line(ix,iy,jx,jy);putpixel(ix,iy,RED);ix=xpopmaxpp.chrom0;iy=ypopmaxpp.chrom0+110;jx=xpopmaxpp.chromlchrom-1;jy=ypopmaxpp.chromlchrom-1+110;line(ix,iy,jx,jy);putpixel(jx,jy,RED);setcolor(11);outtextxy(ix,iy,*);setcolor(12);for(k=0;k1%200;k+)ix=k+280;iy=366-fmk/3;jx=ix+1;jy=366-fmk+1/3;line(ix,iy,jx,jy);putpixel(ix,iy,RED);printf(GEN:%3d,l);printf(Minpath:%f Maxfit:%f,popmaxpp.x,popmaxpp.fitness);printf(Clock:%2d:%2d:%4.2fn,tt/60,tt%60,ttt-tt*60.0);/*#*/float decode(unsigned char *pp)int j,k,l;float tt;tt=ddpp0*lchrom+pplchrom-1;for(j=0;jlchrom-1;j+)tt=tt+ddppj*lchrom+ppj+1;l=0;for(k=0;klchrom-1;k+)for(j=k+1;jlchrom;j+)if(ppj=ppk)l+;return tt+4*l*maxdd;/*%*/void crtinit()int driver,mode;struct palettetype p;driver=DETECT;mode=0;initgraph(&driver,&mode,);cleardevice();/*$*/int select()double rand1,partsum;float r1;int j;partsum=0.0;j=0;rand1=random1()*sumfitness;dopartsum=partsum+oldpopj.fitness;j=j+1;while(partsumrand1)&(jj5)k=jcross;jcross=j5;j5=k;else jcross=lchrom;if(jcross!=lchrom)s0=1;k=0;for(j=jcross;jj5;j+)ts1k=parent1j;ts2k=parent2j;k+;j3=k;for(j=0;jlchrom;j+)j2=0;while(parent2j!=ts1j2)&(j2k)j2+;if(j2=k)ts1j3=parent2j;j3+;j3=k;for(j=0;jlchrom;j+)j2=0;while(parent1j!=ts2j2)&(j2k)j2+;if(j2=k)ts2j3=parent1j;j3+;for(j=0;jlchrom;j+)newpopk5.chromj=ts1j;newpopk5+1.chromj=ts2j;elsefor(j=0;jlchrom;j+)newpopk5.chromj=parent1j;newpopk5+1.chromj=parent2j;mutate=flip(pmutation);if(mutate)s1=1;nmutation=nmutation+1;for(j3=0;j3200;j3+)j1=random(lchrom);j=random(lchrom);jj=newpopk5.chromj;newpopk5.chromj=newpopk5.chromj1;newpopk5.chromj1=jj;mutate=flip(pmutation);if(mutate)s2=1;nmutation=nmutation+1;for(j3=0;j3100;j3+)j1=random(lchrom);j=random(lchrom);jj=newpopk5+1.chromj;newpopk5+1.chromj=newpopk5+1.chromj1;newpopk5+1.chromj1=jj;j2=random(2*lchrom/3);for(j=j2;jj2+lchrom/3-1;j+)for(k=0;kj)i2=k;i1=j;elsei1=k;i2=j;f1=ddlchrom*newpopk5.chromi1+newpopk5.chromi2;f1=f1+ddlchrom*newpopk5.chrom(i1+1)%lchrom+newpopk5.chrom(i2+1)%lchrom;f2=ddlchrom*newpopk5.chromi1+newpopk5.chrom(i1+1)%lchrom;f2=f2+ddlchrom*newpopk5.chromi2+newpopk5.chrom(i2+1)%lchrom;if(f1f2)inversion(i1,i2,newpopk5.chrom);j2=random(2*lchrom/3);for(j=j2;jj2+lchrom/3-1;j+)for(k=0;kj)i2=k;i1=j;elsei1=k;i2=j;f1=ddlchrom*newpopk5+1.chromi1+newpopk5+1.chromi2;f1=f1+ddlchrom*newpopk5+1.chrom(i1+1)%lchrom+newpopk5+1.chrom(i2+1)%lchrom;f2=ddlchrom*newpopk5+1.chromi1+newpopk5+1.chrom(i1+1)%lchrom;f2=f2+ddlchrom*newpopk5+1.chromi2+newpopk5+1.chrom(i2+1)%lchrom;if(f1f2)inversion(i1,i2,newpopk5+1.chrom);return 1;/*$*/void inversion(unsigned int k,unsigned int j,unsigned char *ss)unsigned int l1,i;unsigned char tt;l1=(j-k)/2;for(i=0;il1;i+)tt=ssk+i+1;ssk+i+1=ssj-i;ssj-i=tt;/*%*/void randomize1()int i;randomize();for(i=0;i=lchrom)jrand=0;randomize1();return oldrandjrand;/*%*/int flip(float probability)float ppp;ppp=random(20001)/20000.0;if(ppp=probability)return 1;return 0;改进后用来求解VRP问题的Delphi程序：unit uEA;interfaceusesuUtilsEA, uIEA, uITSP, Classes, GaPara, windows, SysUtils, fEA_TSP;typeTIndividual = class(TInterfacedObject, IIndividual)private/ The internally stored fitness valuefFitness: TFloat;fWeConstrain: integer;fBackConstrain: integer;fTimeConstrain: integer;procedure SetFitness(const Value: TFloat);function GetFitness: TFloat;function GetWeConstrain: integer;procedure SetWeConstrain(const Value: integer);procedure SetBackConstrain(const Value: integer);function GetBackConstrain: integer;function GetTimeConstrain: integer;procedure SetTimeConstrain(const Value: integer);publicproperty Fitness : TFloat read GetFitness write SetFitness;property WeConstrain :integer read GetWeConstrain write SetWeConstrain;property BackConstrain :integer read GetBackConstrain write SetBackConstrain;property TimeConstrain :integer read GetTimeConstrain write SetTimeConstrain;end;TTSPIndividual = class(TIndividual, ITSPIndivid