myga0.c

本程序是一个基本的简单遗传算法示范程序

#include<float.h>
#include<time.h>
#include<math.h>
#include<graphics.h>
#include<stdlib.h>
#include<stdio.h>

#define maxpop 100
#define maxstring 64
struct pp {unsigned char chrom[maxstring];
	   float x,fitness;
	   unsigned int parent1,parent2,xsite;
	   };
struct pp *oldpop,*newpop,*p1;
unsigned int popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,
minpp,jrand;
float pcross,pmutation,sumfitness,avg,max,min,seed,rj[maxpop],oldrand[maxpop];
double coef;
float objfunc(float);
void statistics();
int select();
int flip(float);
int crossover();
int mutation();
void generation();
void initialize();
void report();
void initpop();
void initdata();
void initreport();
float decode();
float random1();
void randomize1();
/*SGA main program */
void main()
{
long int gen,k,j;
float oldmax;
int oldmaxpp;
if(!(oldpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
{printf("memory request failed!\n");exit(0);}
if(!(newpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
{printf("memory request failed!\n");exit(0);}
if(!(p1=(struct pp*)malloc(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';
gen=0;
initialize();
clrscr();
p1=newpop;
newpop=oldpop;
statistics(newpop);
report(gen);
newpop=p1;
getch();
do{
gen=gen+1;
randomize();
oldmax=max;
oldmaxpp=maxpp;
generation();
statistics(newpop);
if(max<oldmax)
   {for(j=0;j<lchrom;j++)
    newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
    newpop[minpp].x=oldpop[oldmaxpp].x;
    newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
    statistics(newpop);
    }
   report(gen);
   p1=oldpop;
   oldpop=newpop;
   newpop=p1;
   getch();
   }while(gen<maxgen);
   free(p1);
   free(oldpop);
   free(newpop);
   exit(0);
   }
/*fitness value*/
float objfunc(float x1)
{
float y;
y=3.1415926*x1;
y=sin(2.0*y);
return y*y;
}
/*total fitness*/
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;
}
/*pop renew*/
void generation(void)
{unsigned int j,mate1,mate2;
j=0;
do{mate1=select();
   mate2=select();
   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;
   j=j+2;
   }while(j<popsize);
}
/* control parameter*/
void initdata()
{unsigned int ch,j;
clrscr();
printf("--------------------------\n");
printf("A Simple Genetic Algorithm-SGA\n");
printf("done by mint.2006.09.14\n");
printf("All Rights Reserved\n");
printf("--------------------------\n");
pause();clrscr();
printf("******** SGA DATA ENTRY AND INITIALIZATION ********\n");
printf("\n");
printf("enter population size---------->");scanf("%d",&popsize);
printf("enter chromosome length-------->");scanf("%d",&lchrom);
printf("enter max.generations---------->");scanf("%d",&maxgen);
printf("enter crosserover probability-->");scanf("%d",&pcross);
printf("enter mutation probability----->");scanf("%d",&pmutation);
clrscr();
randomize();
randomize1();
nmutation=0;
ncross=0;
}
/* initialize data output*/
void initreport()
{int j,k;
 printf("Population size (popsize)=%d\n",popsize) ;
 printf("chromosome length (lchrom)=%d\n",lchrom);
 printf("maximum fo generation (maxgen)=%d\n",maxgen);
 printf("crossover probability (pcross)=%f\n",pcross);
 printf("mutation probability (pmutation=%f\n)",pmutation);
 printf("-------------------->\n");
 printf("\n");
 printf("initial population maximum fitness=%f\n",max);
 printf("initial population average fitness=%f\n",avg);
 printf("initial population minimum fitness=%f\n",min);
 printf("initial population sum of fitness=%f\n",sumfitness);
 pause();
 }
 /* born init pop*/
 void initpop()
 {int j,j1;
 randomize();
 for(j=0;j<popsize;j++)
  {for(j1=0;j1<lchrom;j1++)
    oldpop[j].chrom[j1]=random(2);
  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;
  }
  }
/*initialize*/
void initialize()
{
initdata();
coef=pow(2.00,lchrom)-1.0;
initpop();
statistics(oldpop);
initreport();
}
/* data output*/
void report(int gen)
{ int k,j;
for(j=0;j<79;j++)printf("*");
printf("\n");
printf("    popultion report\n");
printf("    generation %3d\n",gen);
printf("parents xsite  string  x  fitness");
printf("\n");
for(j=0;j<79;j++)printf("+");
printf("\n");
for(j=0;j<popsize;j++)
{printf("%2d)(%2d,",j,newpop[j].parent1);
 printf("%2d)%2d",newpop[j].parent2,newpop[j].xsite);
 for(k=0;k<lchrom;k++)
  printf("%d",newpop[j].chrom[k]);
 printf("%12.1f",newpop[j].x);
 printf("%6.4f-New.\n",newpop[j].fitness);
 }
 for(k=0;k<79;k++)printf("*");
 printf("\n");
 printf("result: gen: %3d",gen);
 printf("avg=%8.4f min=%8.4f max=%8.4f\n",avg,min,max);
 printf("ncross=%4d nmutation=%4d\n",ncross,nmutation);
 }
 /*decode*/
 float decode(unsigned char *pp)
 {int j;
 float tt,tt1;
 tt1=10.;
 tt=0.0;
 for(j=lchrom-1;j>-1;j--)
   {if(pp[j])tt=tt+tt1;
   tt1=2.0*tt1;
   }
 tt=tt/coef;
 return tt;
 }
 /*delay*/
 pause()
 {int j,j1;
 int x1;
 x1=0;
 for(j=1;j<26;j++)
  {for(j1=1;j1<2;j1++)x1=x1+1;
  }
  return x1;
 }
 /*selece operation*/
 int select()
 {double rand1,partsum;
 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;
 }
/* mutation operation*/
int mutation(ch)
unsigned char ch;
{
int mutate,j;
mutate=flip(pmutation);
if(mutate)
 {nmutation=nmutation+1;
  if(ch)ch=0;
   else ch=1;
  }
 if(ch) return 1;
   else return 0;
 }
/*crossover operation*/
int crossover(unsigned char *parent1,unsigned char *parent2,int k5)
{int i,j,j1;
 if(flip(pcross))
 {jcross=random(lchrom-1);
 ncross=ncross+1;
 }
 else jcross=lchrom;
 if(jcross!=lchrom)
  {for(j=0;j<jcross;j++)
   {newpop[k5].chrom[j]=mutation(parent1[j]);
   newpop[k5+1].chrom[j]=mutation(parent2[j]);
   }
  for(j=jcross;j<lchrom;j++)
  {newpop[k5].chrom[j]=mutation(parent2[j]);
   newpop[k5+1].chrom[j]=mutation(parent1[j]);
   }
  }
  else{ for(j=0;j<lchrom;j++)
	{newpop[k5].chrom[j]=mutation(parent1[j]);
   newpop[k5+1].chrom[j]=mutation(parent2[j]);
   }
  }
  return 1;
 }
 /*reset counter*/
 void randomize1()
 {
  int i;
  randomize();
  for(i=0;i<lchrom;i++)
    oldrand[i]=random(30001)/30000.0;
    jrand=0;
    }
  /*random counter*/
  float random1()
  {jrand=jrand+1;
   if(jrand>=lchrom)
   {jrand=0;
   randomize1();
   }
  return oldrand[jrand];
 }
 /*bnl test */
 int flip(float probability)
 {float ppp;
 ppp=random(20001)/20000.0;
 if(ppp<=probability)return 1;
 return 0 ;
 }