|
|
发表于 2004-10-25 00:00:00
|
显示全部楼层
【共享】解TSP问题的遗传算法C语言程序
转自“研学论坛”：
http://bbs.matwav.com/post/view? ... tpg=1&age=0
感谢 研学论坛 ouyang_ying 提供！
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<alloc.h>
#include<conio.h>
#include<float.h>
#include<time.h>
#include<graphics.h>
#include<bios.h>
#define maxpop 100
#define maxstring 100
struct pp{unsigned char chrom[maxstring];
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,oldrand[maxstring];
unsigned char x[maxstring],y[maxstring];
float *dd,ff,maxdd,refpd,fm[201];
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 fname[10];
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;k<maxpop;k++) oldpop[k].chrom[0]='\0';
for(k=0;k<maxpop;k++) newpop[k].chrom[0]='\0';
printf("Enter Result Data Filename:");
gets(fname);
if((fp=fopen(fname,"w+"))==NULL)
{printf("cannot open file\n");exit(0);}
gen=0;
randomize();
initialize();
fputs("this is result of the TSP problem:",fp);
fprintf(fp,"city: %2d psize: %3d Ref.TSP_path: %f\n",lchrom,popsize,refpd);
fprintf(fp,"Pc: %f Pm: %f Seed: %f\n",pcross,pmutation,seed);
fprintf(fp,"X site:\n");
for(k=0;k<lchrom;k++)
{if((k%16)==0) fprintf(fp,"\n");
fprintf(fp,"%5d",x[k]);
}
fprintf(fp,"\n Y site:\n");
for(k=0;k<lchrom;k++)
{if((k%16)==0) fprintf(fp,"\n");
fprintf(fp,"%5d",y[k]);
}
fprintf(fp,"\n");
crtinit();
statistics(oldpop);
report(gen,oldpop);
getch();
maxold=min;
fm[0]=100.0*oldpop[maxpp].x/ff;
do {
gen=gen+1;
generation();
statistics(oldpop);
if(max>maxold)
{maxold=max;
co_min=0;
}
fm[gen%200]=100.0*oldpop[maxpp].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:%d\n",min,co_min);
}while((gen<100)&&!bioskey(1));
printf("\n gen= %d",gen);
do{
gen=gen+1;
generation();
statistics(oldpop);
if(max>maxold)
{maxold=max;
co_min=0;
}
fm[gen%200]=100.0*oldpop[maxpp].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:%d\n",min,co_min);
}while((gen<maxgen)&&!bioskey(1));
getch();
for(k=0;k<lchrom;k++)
{if((k%16)==0)fprintf(fp,"\n");
fprintf(fp,"%5d",oldpop[maxpp].chrom[k]);
}
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=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
for(j=1;j<popsize;j++)
{sumfitness=sumfitness+pop[j].fitness;
if(pop[j].fitness>max)
{max=pop[j].fitness;
maxpp=j;
}
if(pop[j].fitness<min)
{min=pop[j].fitness;
minpp=j;
}
}
avg=sumfitness/(float)popsize;
}
/*%%%%%%%%%%%%%%%%%%%%*/
void generation()
{unsigned int k,j,j1,j2,i1,i2,mate1,mate2;
float f1,f2;
j=0;
do{
mate1=select();
pp:mate2=select();
if(mate1==mate2)goto pp;
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
newpop[j].x=(float)decode(newpop[j].chrom);
newpop[j].fitness=objfunc(newpop[j].x);
newpop[j].parent1=mate1;
newpop[j].parent2=mate2;
newpop[j].xsite=jcross;
newpop[j+1].x=(float)decode(newpop[j+1].chrom);
newpop[j+1].fitness=objfunc(newpop[j+1].x);
newpop[j+1].parent1=mate1;
newpop[j+1].parent2=mate2;
newpop[j+1].xsite=jcross;
if(newpop[j].fitness>min)
{for(k=0;k<lchrom;k++)
oldpop[minpp].chrom[k]=newpop[j].chrom[k];
oldpop[minpp].x=newpop[j].x;
oldpop[minpp].fitness=newpop[j].fitness;
co_min++;
return;
}
if(newpop[j+1].fitness>min)
{for(k=0;k<lchrom;k++)
oldpop[minpp].chrom[k]=newpop[j+1].chrom[k];
oldpop[minpp].x=newpop[j+1].x;
oldpop[minpp].fitness=newpop[j+1].fitness;
co_min++;
return;
}
j=j+2;
}while(j<popsize);
}
/*%%%%%%%%%%%%%%%%%*/
void initdata()
{unsigned int ch,j;
clrscr();
printf("-----------------------\n");
printf("A SGA\n");
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=%d\n",popsize);
printf("chromosome length=%d\n",lchrom);
printf("maxgen=%d\n",maxgen);
printf("pmutation=%f\n",pmutation);
printf("pcross=%f\n",pcross);
printf("initial generation statistics\n");
printf("ini pop max fitness=%f\n",max);
printf("ini pop avr fitness=%f\n",avg);
printf("ini pop min fitness=%f\n",min);
printf("ini pop sum fit=%f\n",sumfitness);
}
void initpop()
{unsigned char j1;
unsigned int k5,i1,i2,j,i,k,j2,j3,j4,p5[maxstring];
float f1,f2;
j=0;
for(k=0;k<lchrom;k++)
oldpop[j].chrom[k]=k;
for(k=0;k<lchrom;k++)
p5[k]=oldpop[j].chrom[k];
randomize();
for(;j<popsize;j++)
{j2=random(lchrom);
for(k=0;k<j2+20;k++)
{j3=random(lchrom);
j4=random(lchrom);
j1=p5[j3];
p5[j3]=p5[j4];
p5[j4]=j1;
}
for(k=0;k<lchrom;k++)
oldpop[j].chrom[k]=p5[k];
}
for(k=0;k<lchrom;k++)
for(j=0;j<lchrom;j++)
dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
for(j=0;j<popsize;j++)
{oldpop[j].x=(float)decode(oldpop[j].chrom);
oldpop[j].fitness=objfunc(oldpop[j].x);
oldpop[j].parent1=0;
oldpop[j].parent2=0;
oldpop[j].xsite=0;
}
}
/*&&&&&&&&&&&&&&&&&*/
void initialize()
{int k,j,minx,miny,maxx,maxy;
initdata();
minx=0;
miny=0;
maxx=0;maxy=0;
for(k=0;k<lchrom;k++)
{x[k]=rand();
if(x[k]>maxx)maxx=x[k];
if(x[k]<minx)minx=x[k];
y[k]=rand();
if(y[k]>maxy)maxy=y[k];
if(y[k]<miny)miny=y[k];
}
if((maxx-minx)>(maxy-miny))
{maxxy=maxx-minx;}
else {maxxy=maxy-miny;}
maxdd=0.0;
for(k=0;k<lchrom;k++)
for(j=0;j<lchrom;j++)
{dd[k*lchrom+j]=hypot(x[k]-x[j],y[k]-y[j]);
if(maxdd<dd[k*lchrom+j])maxdd=dd[k*lchrom+j];
}
refpd=dd[lchrom-1];
for(k=0;k<lchrom;k++)
refpd=refpd+dd[k*lchrom+k+2];
for(j=0;j<lchrom;j++)
dd[j*lchrom+j]=4.0*maxdd;
ff=(0.765*maxxy*pow(lchrom,0.5));
minpp=0;
min=dd[lchrom-1];
for(j=0;j<lchrom-1;j++)
{if(dd[lchrom*j+lchrom-1]<min)
{min=dd[lchrom*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:%f\n"
,lchrom,popsize,maxgen,refpd);
printf("ncross:%4d Nmutation:%4d Rungen:%4d AVG=%8.4f MIN=%8.4f\n\n"
,ncross,nmutation,l,avg,min);
printf("Ref.cominpath:%6.4f Minpath length:%10.4f Ref_co_tour:%f\n"
,pop[maxpp].x/maxxy,pop[maxpp].x,ff);
printf("Co_minpath:%6.4f Maxfit:%10.8f"
,100.0*pop[maxpp].x/ff,pop[maxpp].fitness);
ttt=clock()/18.2;
tt=ttt/60;
printf("Run clock:%2d:%2d:%4d.2f\n",tt/60,tt%60,ttt-tt*60.0);
setcolor(1%15+1);
for(k=0;k<lchrom-1;k++)
{ix=x[pop[maxpp].chrom[k]];
iy=y[pop[maxpp].chrom[k]]+110;
jx=x[pop[maxpp].chrom[k+1]];
jy=y[pop[maxpp].chrom[k+1]]+110;
line(ix,iy,jx,jy);
putpixel(ix,iy,RED);
}
ix=x[pop[maxpp].chrom[0]];
iy=y[pop[maxpp].chrom[0]]+110;
jx=x[pop[maxpp].chrom[lchrom-1]];
jy=y[pop[maxpp].chrom[lchrom-1]]+110;
line(ix,iy,jx,jy);
putpixel(jx,jy,RED);
setcolor(11);
outtextxy(ix,iy,"*");
setcolor(12);
for(k=0;k<1%200;k++)
{ix=k+280;
iy=366-fm[k]/3;
jx=ix+1;
jy=366-fm[k+1]/3;
line(ix,iy,jx,jy);
putpixel(ix,iy,RED);
}
printf("GEN:%3d",l);
printf("Minpath:%f Maxfit:%f",pop[maxpp].x,pop[maxpp].fitness);
printf("Clock:%2d:%2d:%4.2f\n",tt/60,tt%60,ttt-tt*60.0);
}
/*###############*/
float decode(unsigned char *pp)
{int j,k,l;
float tt;
tt=dd[pp[0]*lchrom+pp[lchrom-1]];
for(j=0;j<lchrom-1;j++)
{tt=tt+dd[pp[j]*lchrom+pp[j+1]];}
l=0;
for(k=0;k<lchrom-1;k++)
for(j=k+1;j<lchrom;j++)
{if(pp[j]==pp[k])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;
do{
partsum=partsum+oldpop[j].fitness;
j=j+1;
}while((partsum<rand1)&&(j<popsize));
return j-1;
}
/*$$$$$$$$$$$$$$$*/
int crossover(unsigned char *parent1,unsigned char *parent2,int k5)
{int k,j,mutate,i1,i2,j5;
int j1,j2,j3,s0,s1,s2;
unsigned char jj,ts1[maxstring],ts2[maxstring];
float f1,f2;
s0=0;s1=0;s2=0;
if(flip(pcross))
{jcross=random(lchrom-1);
j5=random(lchrom-1);
ncross=ncross+1;
if(jcross>j5){k=jcross;jcross=j5;j5=k;}
}
else jcross=lchrom;
if(jcross!=lchrom)
{s0=1;
k=0;
for(j=jcross;j<j5;j++)
{ts1[k]=parent1[j];
ts2[k]=parent2[j];
k++;
}
j3=k;
for(j=0;j<lchrom;j++)
{j2=0;
while((parent2[j]!=ts1[j2])&&(j2<k)){j2++;}
if(j2==k)
{ts1[j3]=parent2[j];
j3++;
}
}
j3=k;
for(j=0;j<lchrom;j++)
{j2=0;
while((parent1[j]!=ts2[j2])&&(j2<k)){j2++;}
if(j2==k)
{ts2[j3]=parent1[j];
j3++;
}
}
for(j=0;j<lchrom;j++)
{newpop[k5].chrom[j]=ts1[j];
newpop[k5+1].chrom[j]=ts2[j];
}
}
else
{for(j=0;j<lchrom;j++)
{newpop[k5].chrom[j]=parent1[j];
newpop[k5+1].chrom[j]=parent2[j];
}
mutate=flip(pmutation);
if(mutate)
{s1=1;
nmutation=nmutation+1;
for(j3=0;j3<200;j3++)
{j1=random(lchrom);
j=random(lchrom);
jj=newpop[k5].chrom[j];
newpop[k5].chrom[j]=newpop[k5].chrom[j1];
newpop[k5].chrom[j1]=jj;
}
}
mutate=flip(pmutation);
if(mutate)
{s2=1;
nmutation=nmutation+1;
for(j3=0;j3<100;j3++)
{j1=random(lchrom);
j=random(lchrom);
jj=newpop[k5+1].chrom[j];
newpop[k5+1].chrom[j]=newpop[k5+1].chrom[j1];
newpop[k5+1].chrom[j1]=jj;
}
}
}
j2=random(2*lchrom/3);
for(j=j2;j<j2+lchrom/3-1;j++)
for(k=0;k<lchrom;k++)
{if(k==j)continue;
if(k>j){i2=k;i1=j;}
else{i1=k;i2=j;}
f1=dd[lchrom*newpop[k5].chrom[i1]+newpop[k5].chrom[i2]];
f1=f1+dd[lchrom*newpop[k5].chrom[(i1+1)%lchrom]+
newpop[k5].chrom[(i2+1)%lchrom]];
f2=dd[lchrom*newpop[k5].chrom[i1]+
newpop[k5].chrom[(i1+1)%lchrom]];
f2=f2+dd[lchrom*newpop[k5].chrom[i2]+
newpop[k5].chrom[(i2+1)%lchrom]];
if(f1<f2){inversion(i1,i2,newpop[k5].chrom);}
}
j2=random(2*lchrom/3);
for(j=j2;j<j2+lchrom/3-1;j++)
for(k=0;k<lchrom;k++)
{if(k==j)continue;
if(k>j){i2=k;i1=j;}
else{i1=k;i2=j;}
f1=dd[lchrom*newpop[k5+1].chrom[i1]+newpop[k5+1].chrom[i2]];
f1=f1+dd[lchrom*newpop[k5+1].chrom[(i1+1)%lchrom]+
newpop[k5+1].chrom[(i2+1)%lchrom]];
f2=dd[lchrom*newpop[k5+1].chrom[i1]+
newpop[k5+1].chrom[(i1+1)%lchrom]];
f2=f2+dd[lchrom*newpop[k5+1].chrom[i2]+
newpop[k5+1].chrom[(i2+1)%lchrom]];
if(f1<f2){inversion(i1,i2,newpop[k5+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;i<l1;i++)
{tt=ss[k+i+1];
ss[k+i+1]=ss[j-i];
ss[j-i]=tt;
}
}
/*%%%%%%%%%%%%%%%*/
void randomize1()
{int i;
randomize();
for(i=0;i<lchrom;i++)
oldrand=random(30001)/30000.0;
jrand=0;
}
/*%%%%%%%%%%%*/
float random1()
{jrand=jrand+1;
if(jrand>=lchrom)
{jrand=0;
randomize1();
}
return oldrand[jrand];
}
/*%%%%%%%%%%*/
int flip(float probability)
{float ppp;
ppp=random(20001)/20000.0;
if(ppp<=probability)return 1;
return 0;
}
[ Last edited by 碧城仙 on 2004-11-21 at 06:07 PM ] |
|
发表于 2004-10-12 00:00:00