ga.c

This a GA implementation using binary and real coded variables. Mixed variables can be used. Constra

}

/*===================================================================
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;
{
   double distance1,x,delta_l,delta_u,delta,u;
   int k, site;

   if (indiv == NULL) error_ptr_null("indiv in mutation");
   
   if (nvar_real > 0) 
     for (site = 0; site < nvar_real; site++)
       {
	 if(flip(p_mutation_real))
	   {
	     no_mutation++;
	     if(RIGID)
	       { 
		 x = indiv->xreal[site]; 
		 distance1 = xreal_lower[site] - x; 
		 delta_l = distance1/(xreal_upper[site] - xreal_lower[site]); 
		 if (delta_l < -1.0)  delta_l = -1.0;
		 
		 distance1 = xreal_upper[site] - x;
		 delta_u = distance1/(xreal_upper[site] - xreal_lower[site]);
		 if (delta_u > 1.0)   delta_u = 1.0;
		 
		 if (-1.0*delta_l < delta_u) delta_u = -1.0 * delta_l;
		 else delta_l = -1.0 * delta_u;
	       }
	     else 
	       {
		 delta_l = -1.0;
		 delta_u =  1.0;
	       }
	     u = randomperc();
	     /* calculation of actual delta value */ 
	     delta = get_delta(u, delta_l, delta_u) 
	       * (xreal_upper[site] - xreal_lower[site]); 
	     indiv->xreal[site] += delta;
	     
	     if (indiv->xreal[site] < xreal_lower[site])
	       indiv->xreal[site] = xreal_lower[site];
	     if (indiv->xreal[site] > xreal_upper[site])
	       indiv->xreal[site] = xreal_upper[site];
	     
	   }    /* if flip() */
       }
   if (nvar_bin > 0) 
     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=============================================");

   fprintf(fp,"\n Variable Boundaries : ");
   if (nvar_real > 0)
     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);
   if (nvar_bin > 0)
     fprintf(fp,"\n Mutation probability (binary): %6.4f",p_mutation_bin);
   if (nvar_real > 0)
     fprintf(fp,"\n Mutation probability (real): %6.4f",p_mutation_real);
   if (SHARING)
   {
        fprintf(fp,"\n Niching to be done :");
        fprintf(fp,"\n Niching parameter value: %6.4f",sigma_share);
   }
   if (nvar_bin > 0)
     fprintf(fp,"\n Total String length              : %d",lchrom);
   if (nvar_bin > 0)
     fprintf(fp,"\n Number of binary-coded variables: %d",nvar_bin);
   if (nvar_real > 0)
     fprintf(fp,"\n Number of real-coded variables  : %d",nvar_real);
   fprintf(fp,"\n Total Runs to be performed : %d",maxrun);
   if (nvar_real > 0) 
     {
       fprintf(fp,"\n Exponent (n for SBX)       : %7.2f",n_distribution_c);
       fprintf(fp,"\n Exponent (n for Mutation)  : %7.2f",n_distribution_m);
     }
   fprintf(fp,"\n Lower and Upper bounds     :");
   for (k=0; k < nvar_bin; k++)
     fprintf(fp,"\n   %8.4f   <=   x_bin[%d]   <= %8.4f, string length = %d",xbin_lower[k],k+1,xbin_upper[k],chr_len[k]);
   for (k=0; k < nvar_real; k++)
     fprintf(fp,"\n   %8.4f   <=   x_real[%d]   <= %8.4f",xreal_lower[k],k+1,xreal_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, bitcount, position;
    unsigned mask = 1, tmp;

   if (fp == NULL) error_ptr_null(" File fp in initreport");
   
   if (nvar_bin <= 0) return;
   if (chrom == NULL) error_ptr_null("chrom in writechrom");
   
   position = 0;
   bitcount = 0;
    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++)
        {
	  bits_per_var = chr_len[position];
	  if(tmp&mask)
	    fprintf(fp,"1");
	  else
	    fprintf(fp,"0");
	  count++; bitcount++;
	  if (( (count % bits_per_var) == 0) && (count < lchrom))
	    fprintf(fp,"-");
	  tmp = tmp>>1;
	  if (bitcount >= chr_len[position])
	    {
	      bitcount = 0;
	      position += 1;
	    }
        }
    }
}

void writeindv(ind)
     INDIVIDUAL ind;
{
  int i;
  
  for (i=0; i<nvar_bin; i++)
    printf(" %lf",ind.xbin[i]);
  for (i=0; i<nvar_real; i++)
    printf(" %lf",ind.xreal[i]);
  printf("Obj=%lf penalty = %lf parent1 = %d parent2 = %d",ind.obj,ind.penalty,ind.parent1,ind.parent2);
  printf("cross_site = %lf ",ind.cross_var);
  for (i=0; i<chromsize; i++)
    printf(" %d",ind.chrom[i]);
}

/*====================================================================
Reporting the statistics of current population ( gen. no. 'num'):
  fp is file pointer to output file.
====================================================================*/
report(fr,fp,fl,num)
FILE *fr,*fp,*fl;
int num;
{
  int k,j;
  char string[30];


  if (fr == NULL) error_ptr_null(" file fr in report()");
  if (fp == NULL) error_ptr_null(" file fp in report()");
  if (num == 0)
    fprintf(fl,"\n# Generation Number  Best Fitness  Average Fitness  Worst Fitness");
  fprintf(fl,"\n %d  %lf  %lf  %lf",num,min_obj,avg_obj,max_obj);
  
  if (REPORT)
    {
      /* ----------------------------------------- */
      /* WRITING IN THE OUTPUT FILE FOR INSPECTION */
      /* ----------------------------------------- */
      fprintf(fr,"\n========== Generation No. : %3d ===================",num);
      fprintf(fr,"\n  No. Binary|Real x   Constr. violation    Fitness    Parents     Cross-site ");
      fprintf(fr,"\n===================================================");
      for (k=0; k < pop_size; k++)
	{
	  fprintf(fr,"\n%3d.  ",k+1);
	  if (nvar_bin > 0)
	    {
	      for (j=0; j < nvar_bin; j++)
		fprintf(fr," %8.5lf",oldpop[k].xbin[j]);
	    }
	  fprintf(fr,"|");
	  
	  if (nvar_real > 0)
	    {
	      for (j=0; j<nvar_real; j++)
		fprintf(fr," %8.5lf",oldpop[k].xreal[j]);
	    }
	  for (j=0; j<nc; j++)
	    fprintf(fr," %8.5lf",oldpop[k].cons[j]);
	  fprintf(fr," %8.5lf",oldpop[k].penalty);
	  fprintf(fr,"  %8.5lf (%3d %3d)", oldpop[k].obj,
		  oldpop[k].parent1,oldpop[k].parent2);
	  if (nvar_bin > 0) fprintf(fr,"  %d",oldpop[k].cross_var);
	  if (nvar_bin > 0)
	    {  
	      fprintf(fr,"\n String = ");
	      writechrom(oldpop[k].chrom,fr); 
	    }
	}
    }
  if (num==max_gen)
    {
      fprintf(fp,"\n===================================================");
      fprintf(fp,"\nMax = %8.5lf  Min = %8.5lf   Avg = %8.5lf",
	      max_obj,min_obj,avg_obj);
      fprintf(fp,"\nMutations (real)= %d ; Mutations (binary) = %d ; Crossovers = %d",
	      no_mutation,binmut,no_xover);
      fprintf(fl,"\n");

      if (best_ever.penalty <= 0.0) 
	{
	  fprintf(fp,"\nBest ever fitness: %lf (from generation : %d)\n",
		  best_ever.obj,best_ever_gen);
	  fprintf(fp,"Variable vector: Binary | Real -> ");
	  for (j=0; j < nvar_bin; j++)
	    fprintf(fp," %lf",best_ever.xbin[j]);
	  fprintf(fp,"|");
	  for (j=0; j < nvar_real; j++)
	    fprintf(fp," %lf",best_ever.xreal[j]);
	  if (nvar_bin > 0) 
	    { 
	      fprintf(fp,"\nBest_ever String = ");
	      writechrom(best_ever.chrom,fp); 
	    }
	  fprintf(fp,"\nConstraint value:");
	  for (j=0; j < nc; j++)
	    fprintf(fp," %lf",best_ever.cons[j]);
	  fprintf(fp,"| Overall penalty: %lf",best_ever.penalty);
	}
      else 
	fprintf(fp,"No feasible solution found!\n");
      fprintf(fp,"\n===================================================");
      fprintf(fp,"\n\n");
    }
  
  app_report();
}
/*====================================================================
Releases the memory for all mallocs
====================================================================*/
free_all()
{
  int i;

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

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

/*---------------------------*/
/* Program starts here :     */
/*---------------------------*/
   input_parameters();
   fp_out = fopen("result.out","w+");
   fp_rep = fopen("report.out","w");
   fp_plot= fopen("plot.out","w");

   select_memory();
   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)*(double)(run-1)/(double)maxrun;
       if (seed > 1.0) printf("\n Warning !!! seed number exceeds 1.0");
       gen_no = 0;  
       initialize();
       statistics(gen_no); 
       report(fp_rep,fp_out,fp_plot,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_rep,fp_out,fp_plot,gen_no);
	 };                   
     /* One GA run is over  */
       free_all();
     }                      /* for loop of run  */
   
   fclose(fp_out); fclose(fp_rep); fclose(fp_plot);
   app_closure();
   printf("\n Results are stored in file 'result.out', 'report.out', and 'plot.out'\n");
}

/**************** 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 */

advance_random()
/* Create next batch of 55 random numbers */
{
    int j1;
    double new_random;

    for(j1 = 0; j1 < 24; j1++)
    {
        new_random = oldrand[j1] - oldrand[j1+31];
        if(new_random < 0.0) new_random = new_random + 1.0;
        oldrand[j1] = new_random;
    }
    for(j1 = 24; j1 < 55; j1++)
    {
        new_random = oldrand [j1] - oldrand [j1-24];
        if(new_random < 0.0) new_random = new_random + 1.0;
        oldrand[j1] = new_random;
    }
}

int flip(prob)
/* Flip a biased coin - true if heads */
double prob;
{
    double randomperc();