解TSP問題的遺傳算法C語言程序

1、解TSP問題的遺傳算法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;un

2、signed int nmutation,ncross,jcross,maxpp,minpp,maxxy;floatpcross,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 ge

3、neration();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(d

4、d=(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;kmaxpo

5、p;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,lchro

6、m,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()/

7、18.2;tt=ttt/60;printf(Run Clock: %2d: %2d: %4.2f,tt/60,tt%60,ttt-tt*60.0);printf(Min=%6.4fNm:%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

8、: %4.2f,tt/60,tt%60,ttt-tt*60.0);printf(Min=%6.4fNm:%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);/*%*/flo

9、at 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;

10、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)

11、; printf(input chromlength);scanf(%d,&lchrom); printf(input maxgenerations);scanf(%d,&maxgen); printf(input crossoverprobability);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)

12、;printf(chromosome length=%dn,lchrom);printf(maxgen=%dn,maxgen);printf(pmutation=%fn,pmutation); printf(pcross=%fn,pcross);printf(initial generation statisticsn); printf(ini pop maxfitness=%fn,max); printf(ini pop avr fitness=%fn,avg); printf(inipop min fitness=%fn,min); printf(ini pop sum fit=%fn,s

13、umfitness); 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

14、;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,

15、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;klchr

16、om;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;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 in

17、t 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,popmax

18、pp.x,ff); printf(Co_minpath:%6.4fMaxfit:%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

19、;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,j

20、x,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;klc

21、hrom-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

22、+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(p

23、arent1j!=ts2j2)&(j2k)j2+;if(j2=k)ts2j3=parent1j;j3+;for(j=0;jlchrom;j+)newpopk5.chromj=ts1j;newpopk5+1.chromj=ts2j; for(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(lchro

24、m);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;

25、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)inver

26、sion(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;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*ne

27、wpopk5+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();

28、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;%TSP題(又名：旅行商問題，貨郎擔(dān)問題)遺傳算法通用matlab程序D是距 離矩陣，n為種群個(gè)數(shù)，建議取為城市個(gè)數(shù)的12倍，C為停止代數(shù)，遺傳到第C 代時(shí)程序停止,C 的具體取值視問題的規(guī)模和耗費(fèi)的時(shí)間而定%nJ適應(yīng)值歸一化淘汰加速指數(shù),最好取為1,2,3,4 ,不宜太大alpha為淘汰保護(hù)指數(shù), 可取為 01 之間任意小數(shù), 取 1 時(shí)關(guān)閉保護(hù)功能, 最好取為 0.81.0%M最短路徑，Rlength為路徑長度function R,Rlength=geneticTSP(D,n,C,m,alp