selfsga.c

函数的遗传算法优化程序

#include<float.h>
#include<time.h>
#include<math.h>
//#include<graphics.h>
#include<stdlib.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();

/*main programe of SGA*/
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);
	}

/*calculating the fitness of individuals*/
float objfunc(float x1)
{float y;
 y=3.1415926*x1;
 y=sin(2.0*y);
 return y*y;
	}

/*The statistic of the fitness of population*/
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;
	}
	
/*Updating the population*/
void generation()
{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);
	}
	
/*Input the contol parameters*/
void initdata()
{unsigned int ch,j;
 clrscr();
 printf("---------------------------------\n");
 printf("A Simple Genetic Algorithm-SGA\n");
 printf("(c)UPC ZHENG NOV 2004\n");
 printf("   All Rights Reserved\n");
 printf("---------------------------------\n");
 pause();//clrscr();
 printf("********SGA DATA ENTERY 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 crossover probability---->");scanf("%f",&pcross);
 printf("Enter mutation probability----->");scanf("%f",&pmutation);
 clrscr();
 randomize();
 randomize1();
 nmutation=0;
 ncross=0;
 }
 
/*Initialize the output of the information*/
void initreport()
{int j,k;
 printf("  ------------------\n");
 printf("  A Simple Genetic Algorithm-SGA\n");
 printf("  (c)UPC ZHENG NOV 2004\n");
 printf("  All Rights Reserved \n");
 printf("  ------------------\n");
 printf("SGA parameters\n");
 printf("  ------------\n");
 printf("\n");
 printf("Population size(popsize)       =%d\n",popsize);
 printf("Chromosom length(lchrom)       =%d\n",lchrom);
 printf("Maximum # of 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();
}

/*Generate the initial population*/
void initpop()
{int j,j1;
 randomize();
 for(j=0;j<popsize;j++)
    {for(j1=0;j1<lchrom;j++)
       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;
    }
}

/*Initializing*/
void initialize()
{
	initdata();
	coef=pow(2.00,lchrom)-1.0;
	initpop();
	statistics(oldpop);
	initreport();
}

/*Output Datum*/
void report(int gen)
{int k,j;
 for(j=0;j<79;j++) printf("*");
 printf("\n");
 printf("  Population Report\n");
 printf("  Generation %3d\n",gen);
 printf("# parents xsite string x fitness");
 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=1.0;
 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<=25;j++)
    {for(j1=1;j1<2;j1++) x1=x1+1;
    }
 return x1;
 }
 
/*Selection*/
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*/
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*/
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;
}

/*Restart the random number generator*/
void randomize1()
{int i;
 randomize();
 for(i=0;i<lchrom;i++)
     oldrand[i]=random(30001)/30000.0;
 jrand=0;
}

/*Random number Generator*/
float random1()
{jrand=jrand+1;
 if(jrand>=lchrom)
 {jrand=0;
  randomize1();
 }
 return oldrand[jrand];
}

/*Benuley Tesment*/
int flip(float probability)
{float ppp;
 ppp=random(20001)/20000.0;
 if(ppp<=probability) return 1;
 return 0;
}