sga.c

由我收集或写出的GA源码

      if (BINGA)
      for (k=0; k<=chromsize; k++)
      {
        newpop[childno1].chrom[k] = oldpop[first].chrom[k];
        newpop[childno2].chrom[k] = oldpop[second].chrom[k];
      }
      for (site=0; site<=num_var-1; site++)
      {
        newpop[childno1].x[site] = oldpop[first].x[site];
        newpop[childno2].x[site] = oldpop[second].x[site];
      }
    }
}
/*===================================================================
Calculates beta value for given random number u (from 0 to 1)
If input random numbers (u) are uniformly distributed for a set of
inputs, this results in uniform distribution of beta values in case
of BLX , and Binary Probability distribution simulation in case of
SBX.
====================================================================*/
float get_beta(u)
float u;
{
   float beta;

   if (cross_type == BLX) return(2.0*u);
   if (1.0-u < EPSILON ) u = 1.0 - EPSILON;
   if ( u < 0.0) u = 0.0;
   if (u < 0.5) beta = pow(2.0*u,(1.0/(n_distribution_c+1.0)));
   else beta = pow( (0.5/(1.0-u)),(1.0/(n_distribution_c+1.0)));
   return beta;
}
/*==================================================================
For given u value such that   -1 <= u <= 1, this routine returns a
value of delta from -1 to 1. Exact value of delta depends on specified
n_distribution. This is called by mutation().
====================================================================*/
float get_delta(u)
float u;
{
   float delta;
   int negative = FALSE;   /* Flag for negativeness of delta */

   if (cross_type == BLX) return(u);
   if(u <= -1.0) u = -1.0;
   if(u >1.0)  u =  1.0;
   if(u < 0.0)  {  u = -u;
                   negative = TRUE;
                }
   delta = 1.0 - pow((1.0 - u),(1.0 / (n_distribution_m + 1.0)));
   if(negative)  return (-delta);
   else          return delta;

}
/*==================================================================
Binary mutation routine ( borrowed from sga.c )
====================================================================*/
binmutation(child)
unsigned *child;
/* Mutate an allele w/ pmutation, count # of mutations */
{
    int j, k, stop;
    unsigned mask, temp = 1;

    if (BINGA == FALSE) return;
    if (child== NULL) error_ptr_null(" child in binmutation");
    for(k = 0; k < chromsize; k++)
    {
        mask = 0;
        if(k == (chromsize-1))
            stop = lchrom - ((k-1)*UINTSIZE);
        else
            stop = UINTSIZE;
        for(j = 0; j < stop; j++)
        {
            if(flip(p_mutation))
            {
                mask = mask|(temp<<j);
            }
        }
        child[k] = child[k]^mask;
    }
}
/*===================================================================
Mutation Using polynomial probability distribution. Picks up a random
site and generates a random number u between -1 to 1, ( or between
minu to maxu in case of rigid boudaries) and calls the routine
get_delta() to calculate the actual shift of the value.
====================================================================*/
mutation(indiv)
INDIVIDUAL  *indiv;
{
   float distance1,distance2,x,delta,minu,maxu,u;
   int k, site;

   if (indiv == NULL) error_ptr_null("indiv in mutation");
   if(flip (p_mutation) && REALGA)
   {
        site = rnd(num_discr_var,num_var - 1);
        no_mutation++;
        if(fabs(x_upper[site] -x_lower[site]) < EPSILON) return;

        /* calculation of bounds on delta */
        if(RIGID)
        { x = indiv->x[site];
          distance1 = x - x_lower[site];
          distance2 = x_upper[site] - x;

          delta = 2.0 * distance1 / (x_upper[site] - x_lower[site]);
          if (delta > 1.0)   delta = 1.0;
          minu = -1.0 + pow((1.0 - delta),(n_distribution_m + 1.0));

          delta = 2.0 * distance2 / (x_upper[site] - x_lower[site]);
          if (delta > 1.0)   delta = 1.0;
          maxu = 1.0 - pow((1.0 - delta),(n_distribution_m + 1.0));
          u = rndreal(minu,maxu);
        }
        else u = rndreal(-1.0,1.0);

        /* calculation of actual delta value */
        delta = get_delta(u) *  0.5 * (x_upper[site] - x_lower[site]);
        indiv->x[site] += delta;
  }    /* if flip() */
  if (BINGA) binmutation(indiv->chrom);
}
/*====================================================================
Reporting the user-specified parameters :
fp is the file pointer to output file.
====================================================================*/
initreport(fp)
FILE *fp;
{
   int k;

   if (fp == NULL) error_ptr_null(" File fp in initreport");
   fprintf(fp,"\n\n=============================================");
   fprintf(fp,"\n             INITIAL REPORT                  ");
   fprintf(fp,"\n=============================================");
   if (BINGA) fprintf(fp,"\n BINARY-CODED GA ");
   if (REALGA)
   {
      if (cross_type ==SBX) fprintf(fp,"\n REAL-CODED GA (SBX)");
      else                  fprintf(fp,"\n REAL-CODED GA (BLX)");
   }
   switch (s_strategy) 
     {
     case 1 : fprintf(fp,"\n Tournament Selection Used (Size = %d)",tourneysize); break;
     case 2 : fprintf(fp,"\n Roulette Wheel Selection Used"); break;
     case 3 : fprintf(fp,"\n Stochastic Remainder RW Selection Used"); break;
     }
   switch (x_strategy)
   {

    case ONESITE : fprintf(fp,"\n Crossover Strategy : 1 xsite with swapping"); break;
    case UNIF  : fprintf(fp,"\n Crossover Strategy : Uniformly all variables 50 \% ");
                 break;
    case ONLINE : fprintf(fp,"\n Crossover Strategy : On a straight line"); break;
    default   : fprintf(fp,"\n CROSSOVER NOT SET CORRECTLY "); break;
   }
   if (BINGA) 
     fprintf(fp,"\n Mutation Strategy: Bit-wise Mutation");
   else
     fprintf(fp,"\n Mutation Strategy: Polynomial Mutation");
   fprintf(fp,"\n Variable Boundaries : ");
   if (RIGID) fprintf(fp," Rigid");
   else       fprintf(fp," Flexible");
   fprintf(fp,"\n Population size            : %d",pop_size);
   fprintf(fp,"\n Total no. of generations   : %d",max_gen);
   fprintf(fp,"\n Cross over probability     : %6.4f",p_xover);
   fprintf(fp,"\n Mutation probability       : %6.4f",p_mutation);
   if (SHARING)
   {
        fprintf(fp,"\n Sharing to be done :");
        fprintf(fp,"\n Sigma-share value          : %6.4f",sigma_share);
   }
   if (BINGA)
      fprintf(fp,"\n String length              : %d",lchrom);
   fprintf(fp,"\n Number of variables        : %d",num_var);
   fprintf(fp,"\n Total Runs to be performed : %d",maxrun);
   if ((REALGA) && (cross_type == SBX)) {
     fprintf(fp,"\n Exponent (n for SBX)       : %7.2f",n_distribution_c);
     fprintf(fp,"\n Exponent (n for Mutation)  : %7.2f",n_distribution_m);
   }
   if (s_strategy == 1)
   fprintf(fp,"\n Lower and Upper bounds     :");
   for (k=0; k<=num_var-1; k++)
     fprintf(fp,"\n   %8.4f   <=   x%d   <= %8.4f",x_lower[k],k+1,x_upper[k]);
   fprintf(fp,"\n=================================================\n");
   app_initreport();
}
/*====================================================================
Writes a given string of 0's and 1's
puts a `-` between each substring (one substring for one variable)
Leftmost bit is most significant bit.
====================================================================*/
writechrom(chrom,fp)
unsigned *chrom;
FILE *fp;
{
    int j, k, stop,bits_per_var,count=0;
    unsigned mask = 1, tmp;

   if (fp == NULL) error_ptr_null(" File fp in initreport");
   if (BINGA == FALSE) return;
   if (chrom == NULL) error_ptr_null("chrom in writechrom");
    bits_per_var = lchrom/num_discr_var;
    for(k = 0; k < chromsize; k++)
    {
        tmp = chrom[k];
        if(k == (chromsize-1))
            stop = lchrom - (k*UINTSIZE);
        else
            stop = UINTSIZE;

        for(j = 0; j < stop; j++)
        {
            if(tmp&mask)
                fprintf(fp,"1");
            else
                fprintf(fp,"0");
            count++;
            if (( (count % bits_per_var) == 0) && (count < lchrom))
                     fprintf(fp,"-");
            tmp = tmp>>1;
        }
    }
}
/*====================================================================
Reporting the statistics of current population ( gen. no. 'num'):
  fp is file pointer to output file.
====================================================================*/
report(fp,num)
FILE *fp;
int num;
{
  int k,j;
  FILE *fp_x, *fp_y;
  char string[30];


  if (fp == NULL) error_ptr_null(" file fp in report()");
  if (REPORT)
    {
      /* ----------------------------------------- */
      /* WRITING IN THE OUTPUT FILE FOR INSPECTION */
      /* ----------------------------------------- */
      fprintf(fp,"\n========== Generation No. : %3d ===================",num);
      fprintf(fp,"\n  No.      x       Fitness     Parents     random  ");
      fprintf(fp,"\n===================================================");
      for (k=0; k<= pop_size-1; k++)
	{
	  fprintf(fp,"\n %3d. [%8.5f] ->",k+1,oldpop[k].x[0]);
	  for (j= 1; j<=num_var-1; j++)
	    fprintf(fp,"\n      [%8.5f] ->",oldpop[k].x[j]);
	  fprintf(fp,"  %8.5f  (%3d %3d)  %8.5f", oldpop[k].obj,
		  oldpop[k].parent1,oldpop[k].parent2,oldpop[k].cross_var);
	  if (num_discr_var >= 1)
	    {  fprintf(fp,"\n String = ");
	    writechrom(oldpop[k].chrom,fp); }
	}
    }
  if ((REPORT) || (num==max_gen))
    {
      fprintf(fp,"\n===================================================");
      fprintf(fp,"\nMax = %8.5f  Min = %8.5f   Avg = %8.5f",
	      max_obj,min_obj,avg_obj);
      fprintf(fp,"\nNo. of mutations = %d ;  No. of x-overs = %d",
	      no_mutation,no_xover);
      
      fprintf(fp,"\nBest ever = %f -> fitness: %f (from generation : %d)",
	      best_ever.x[0],best_ever.obj,best_ever_gen);
      for (j=1; j<=num_var-1; j++)
	fprintf(fp,"\n            %f",best_ever.x[j]);
      if (num_discr_var) { fprintf(fp,"\nBest_ever String = ");
      writechrom(best_ever.chrom,fp); }
      fprintf(fp,"\n===================================================");
      fprintf(fp,"\n\n");
    }
  
  app_report();
}
/*====================================================================
Releases the memory for all mallocs
====================================================================*/
free_all()
{
  int i;

  for(i = 0; i < pop_size; i++)
  {
      free(oldpop[i].chrom);
      free(newpop[i].chrom);
  }
  free(oldpop);
  free(newpop);
  free(best_ever.chrom);
  app_free();
}

/*==================================================================
Writes the results of GA run in the output file
===================================================================*/
write_in_file(fp,sno,x,obj,trials)
FILE *fp;
int sno, trials;
float *x,obj;
{
   int k;

   if (fp == NULL) error_ptr_null(" file fp in write_in_file");
   if (x == NULL) error_ptr_null(" x in write_in_file");

   fprintf(fp,"\n%3d.   %10.7f  %6d   %10.6f to %10.6f",
                             sno,x[0],trials,minx[0],maxx[0]);
   for (k =1; k<= num_var-1; k++)
       fprintf(fp,"\n       %10.7f           %10.6f to %10.6f",
                             x[k],minx[k],maxx[k]);
   if (num_discr_var) { fprintf(fp,"  ");
                        writechrom(best_ever.chrom,fp); }
   fprintf(fp,"\n          OBJECTIVE = %10.7f                ",obj);
   fprintf(fp,"\n       Random Seed Number : %6.4f                 ",seed);
   printf("  After %d Generations : ",trials/pop_size);
   printf("\n          OBJECTIVE = %10.7f                ",obj);
   printf("\n Random Seed Number : %6.4f                 ",seed);
}

/*====================================================================
MAIN PROGRAM ;
====================================================================*/
main()
{
   FILE *fp_out;                /* File pointer for output file         */
   int runno=0, k;
   POPULATION   temp;           /* A temporary pointer of population    */

/*---------------------------*/
/* Program starts here :     */
/*---------------------------*/
   input_parameters();
   fp_out = fopen("realga.out","w+");
   
   select_memory();
   select_memory_rw();
   select_memory_sr();
   initreport(fp_out);
   for (run = 1; run<= maxrun; run++)
     {
       printf("\nRun No. %d :  Wait Please .........",run);
       fprintf(fp_out,"\nRun No. %d ",run);
       seed = basic_seed + (1.0-basic_seed)*(float)(run-1)/(float)maxrun;
       if (seed > 1.0) printf("\n Warning !!! seed number exceeds 1.0");
       gen_no = 0;
       initialize();
       statistics(gen_no);
       report(fp_out,0);
       for(gen_no = 1; gen_no<=max_gen; gen_no++)
	 {
	   generate_new_pop();
	   
	   temp = oldpop;
	   oldpop = newpop;
	   newpop = temp;
	   
	   statistics(gen_no);
	   report(fp_out,gen_no);
	 };                        /* One GA run is over  */
       free_all();
     }                      /* for loop of run  */
   
   fclose(fp_out);
   app_closure();
   select_free_sr();
   select_free_rw();
   printf("\n Results are stored in file 'realga.out' ");
   puts("\n O.K Good bye !!!");
}

/**************** End of Main Program ***************************/

/*-------------------------------------------------------  */
/* random.c - contains random number generator and related */
/* utilities,                                              */
/* Source : sga.c  (c) E.Goldberg 1986
/*-------------------------------------------------------  */


/* variables are declared static so that they cannot       */
/* conflict with names of other global variables in other  */
/* files.  See K&R, p 80, for scope of static              */

static double oldrand[55];   /* Array of 55 random numbers */
static int jrand;                 /* current random number */
static double rndx1,rndx2;    /* used with random normal deviate */
static int rndcalcflag; /* used with random normal deviate */

initrandomnormaldeviate()
/* initialization routine for randomnormaldeviate */
{
    rndcalcflag = 1;
}

double noise(mu ,sigma)
/* normal noise with specified mean & std dev: mu & sigma */
double mu, sigma;
{
    double randomnormaldeviate();

    return((randomnormaldeviate()*sigma) + mu);
}

double randomnormaldeviate()
/* random normal deviate after ACM algorithm 267 / Box-Muller Method */
{
    double sqrt(), log(), sin(), cos();
    float randomperc();
    double t;

    if(rndcalcflag)
    {
        rndx1 = sqrt(- 2.0*log((double) randomperc()));
        t = 6.2831853072 * (double) randomperc();