#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 200
#define maxstring 200
struct pp{int chrom[maxstring];
double x,fitness;
unsigned int parent1,parent2,xsite;
};
struct pp *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gen,maxgen,co_min,jrand;
unsigned int nmutation,ncross,jcross,maxpp,minpp,maxxy;
float pcross,pmutation,sumfitness,avg,max,min,maxold,oldrand[maxstring];
double x[maxstring]={4.8000000e+001,5.2000000e+001,5.0000000e+001,5.5000000e+001,5.4000000e+001,5.0000000e+001,5.1000000e+001,5.5000000e+001,5.5000000e+001,
5.0000000e+001,4.1000000e+001,4.5000000e+001,4.5000000e+001,4.0000000e+001,3.8000000e+001,3.3000000e+001,2.9000000e+001,3.3000000e+001,3.5000000e+001,3.0000000e+001,
2.2000000e+001,2.1000000e+001,2.1000000e+001,2.1000000e+001, 2.0000000e+001, 2.6000000e+001,2.2000000e+001,2.7000000e+001, 3.0000000e+001, 3.5000000e+001, 3.6000000e+001,
2.6000000e+001,1.5000000e+001,1.5000000e+001,1.6000000e+001, 1.2000000e+001,6.0000000e+000, 1.1000000e+001, 1.2000000e+001,7.0000000e+000, 9.0000000e+000, 1.5000000e+001,
1.0000000e+001, 1.7000000e+001, 2.6000000e+001,3.0000000e+001,3.5000000e+001,4.0000000e+001,4.0000000e+001, 3.1000000e+001,4.7000000e+001,5.0000000e+001,5.7000000e+001,
5.5000000e+001, 5.5000000e+001,6.2000000e+001,7.0000000e+001,6.2000000e+001, 6.7000000e+001,6.2000000e+001, 6.5000000e+001, 6.2000000e+001,5.5000000e+001,6.0000000e+001,
6.6000000e+001,6.6000000e+001,6.4000000e+001,5.9000000e+001,5.0000000e+001,5.4000000e+001,5.0000000e+001,4.4000000e+001,4.0000000e+001,3.6000000e+001,4.3000000e+001
};
double y[maxstring]={ 2.1000000e+001, 2.6000000e+001, 3.0000000e+001, 3.4000000e+001, 3.8000000e+001,
4.0000000e+001, 4.2000000e+001, 4.5000000e+001, 5.0000000e+001, 5.0000000e+001, 4.6000000e+001,
4.2000000e+001, 3.5000000e+001, 3.7000000e+001, 3.3000000e+001, 3.4000000e+001, 3.9000000e+001,
4.4000000e+001, 5.1000000e+001, 5.0000000e+001, 5.3000000e+001, 4.8000000e+000, 4.5000000e+001,
3.6000000e+001, 3.0000000e+001, 2.9000000e+001, 2.2000000e+001, 2.4000000e+001, 2.0000000e+001,
1.6000000e+001, 6.0000000e+000, 1.3000000e+001, 5.0000000e+000, 1.4000000e+001, 1.9000000e+001,
1.7000000e+001, 2.5000000e+001, 2.8000000e+001, 3.8000000e+001, 4.3000000e+001, 5.6000000e+001,
5.6000000e+001, 7.0000000e+001, 6.4000000e+001, 5.9000000e+001, 6.0000000e+001, 6.0000000e+001,
6.0000000e+001, 6.6000000e+001, 7.6000000e+001, 6.6000000e+001, 7.0000000e+001, 7.2000000e+001,
6.5000000e+001, 5.7000000e+001, 5.7000000e+001, 6.4000000e+001, 4.8000000e+001, 4.1000000e+001,
3.5000000e+001, 2.7000000e+001, 2.4000000e+001, 2.0000000e+001, 1.5000000e+001, 1.4000000e+001,
8.0000000e+000, 4.0000000e+000, 5.0000000e+000, 4.0000000e+000, 1.0000000e+001, 1.5000000e+001,
1.3000000e+001, 2.0000000e+001, 2.6000000e+001, 2.6000000e+001
};
float *dd,ff,maxdd,refpd,fm[201];
FILE *fp,*fp1;
double objfunc(double);
void statistics();
int select();
int flip(float);
int crossover();
void generation();
void initialize();
void report();
double decode();
float random1();
void inversion(unsigned int k,unsigned int j,int *ss);
void crtinit();
/*主程序*/
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))))
{
printf("memory request failed !\n");
exit(0);
}
if(!(dd=(float *)farmalloc(maxstring*maxstring*sizeof(float))))
{
printf("memory request failed !\n");
exit(0);
}
if(!(newpop=(struct pp *)farmalloc(maxpop*sizeof(struct pp))))
{
printf("memory request failed !\n");
exit(0);
}
if(!(p1=(struct pp *)farmalloc(sizeof(struct pp))))
{
printf("memory request failed !\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+")))
{
printf("can't open file\n");
exit(1);
}
gen=0;
srand(time(0));
initialize();
fputs("This is result of the tsp problem:",fp);
fprintf(fp,"citis: %2d psize: %3d Ref.Tsp_path: %f\n",lchrom,popsize,refpd);
fprintf(fp,"Pc: %f pm: %f \n",pcross,pmutation);
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*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<100)&&(!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);
free(dd);
free(p1);
free(oldpop);
free(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;
printf("******SGA DATA