ga.c

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

/********************************************************************\
***                                                                ***
***                      GENETIC ALGORITHM                         ***
***                                                                ***
***               Developed By : Prof. Kalyanmoy Deb               ***
***               with assistance from his Students                ***
***                                                                ***
*** Last Edited : 15.11.2001                                       ***
***................................................................***
This is a GA implementation using binary and real coded 
variables. Mixed variables can be used. Constraints can also be
handled. All constraints must be greater-than-equal-to type (g >= 0)
and normalized (see the sample problem in prob1 in objective()). 

There are three sample input file (inp-r for real-coded variables only, 
inp-b for binary-coded variables only, and inp-rb for a mixed real and binary
variables) which can be used to run this code. The template file for
each input data file is also included (input-real, input-binary, and
input-real+binary). 

Code your objective function and constraints at the end of the code 
(in objective())

Variable boundaries for real-coded variables can be fixed or flexible.

Following selection opeartor is coded:
Tournament selection: Set MINM=1 for minimization and -1 for maximization
in objective().

For binary strings, single-point crossover and for real parameters
 simulated binary crossover (SBX) are used.

Mutation: bit-wise for Binary coded GAs and polynomial mutation (with eta) for
          Real coded GAs

Constraints are handled using Deb's paramater-less 
approach (see CMAME, 2000 paper)

Niching allows restricted tournament selection. Recommended for 
complex and disconnected feasible regions. (Niching parameter of 0.1 is
recommended.) 

The execution creates a file `result.out' which contains the input
data and best solution obtained by the GA. The feasiblilty of the best
solution and constraint values are also marked. 
The report.out contains population record of each generation.
The file 'plot.out' contains a gnuplot-compatibale data file for
plotting best, avg, and worst population fitness versus generation number.

Send Comments to De. K. Deb ([e-mail])    
**************************************************************************/

#include<stdio.h>
#include<math.h>
#define BITS_PER_BYTE 8
#define UINTSIZE (BITS_PER_BYTE*sizeof(unsigned))
#define INFINITY 1e7
#define EPSILON  1e-6
#define PI 3.1415927
#define MAXVECSIZE 30
#define MAXPOPSIZE 500
#define MAXCONSTR  10
#define TRUE 1
#define FALSE 0
#define square(x)  ((x)*(x))
/***** Current Objective Function ******/
#define prob1  /* define your problem at the end in objfunc() */

/*=================
TYPE DEFINTIONS :
=================*/
struct indiv
{ double xreal[MAXVECSIZE];   /* real-coded variables */ 
  double  xbin[MAXVECSIZE];          /* binary-coded variables */
  double obj,penalty; /* objective fn. etc. */
  double cons[MAXCONSTR];
  unsigned *chrom;           /* chrosome string      */
  int parent1;
  int parent2;             /* s.no. of parents     */
  int cross_var;         /* cross over variable  */
};
typedef struct indiv INDIVIDUAL ;
typedef INDIVIDUAL *POPULATION ;        /* array of individuals */

/*====================
FUNCTION PROTOTYPES :
====================*/
void     objective();
double   randomperc();
double   get_beta();
double   get_delta();

/*==================
GLOBAL VARIABLES  :
==================*/
int     pop_size,               /* Population Size                      */
  gen_no,                 /* Current generation number            */
  max_gen,                /* Maximum no. of generations           */
  no_xover,               /* No. of cross overs done              */
  no_mutation,binmut,            /* No. of mutations done                */
  best_ever_gen,          /* Generation no. of best ever indiv.   */
  nvar_bin,                /* Number of total design variables     */
  nvar_real,
  lchrom,                 /* Length of chromosome                 */
  chromsize,              /* Number of bytes needed to store
			     lchrom strings          */
  maxrun,                 /* Maxm no. of GA runs for each set of
			     parameter values          */
  run,                    /* Actual run no.                       */
  SHARING,                /* Flag for Sharing ( True / False)     */
  REPORT,                 /* Flag for Full reports (True/False)   */
  RIGID,                  /* Flag for rigid boundaries (T/F)      */
  tourneylist[MAXPOPSIZE],/* List of indices of individuals for
			     tournament selection routine    */
  tourneypos,             /* Current position of tournament       */
  tourneysize,            /* Tournament size ( = 2 for binary )   */
  MINM,                   
  nc,                     /* Number of constraints */
  critical_size;          /* subpopulation size used in TS (0.25*N)  */

int chr_len[MAXVECSIZE];   /* chrom length for each variable */

double   seed,                   /* Random seed number                   */
  basic_seed,             /* Basic seed number                    */
  n_distribution_c, n_distribution_m,
  p_xover,                /* Cross over probability               */
  p_mutation_bin,p_mutation_real, /* Mutation probability                 */
  sum_obj,                /* Sum of objective fn. values          */
  avg_obj,                /* Average of objective fn. values      */
  max_obj,                /* Maximum objective fn. value          */
  min_obj,                /* Minimum objective fn. value          */
  minx_bin[MAXVECSIZE],       /* Minimum and maximum values of design */
  maxx_bin[MAXVECSIZE],       /*        variables in a population     */
  minx_real[MAXVECSIZE],       /* Minimum and maximum values of design */
  maxx_real[MAXVECSIZE],       /*        variables in a population     */
  xbin_lower[MAXVECSIZE],    /* Lower and Upper bounds on each       */
  xbin_upper[MAXVECSIZE],    /*        design variable               */
  xreal_lower[MAXVECSIZE],    /* Lower and Upper bounds on each       */
  xreal_upper[MAXVECSIZE],    /*        design variable               */
  sigma_share;            /* Sharing distance                     */

POPULATION oldpop, newpop;      /* Old and New populations              */
INDIVIDUAL best_ever,current_best;           /* Best fit individual till current gen.*/

/*====================================================================
SUBROUTINE FOR INPUTTING GLOBAL PARAMETERS :
====================================================================*/
input_parameters()
{
   int k;
   char ans;

   printf("       ");
   puts("::::::::::::::::::::::::::::::::::::::::::::::::::::::::::");
   printf("       ");
   puts("::::::::       REAL-CODED GENETIC ALGORITHM        :::::::");
   printf("       ");
   puts("::::::::       ============================        :::::::");
   printf("       ");
   puts("::::::::  Kalyanmoy Deb and his students at KanGAL :::::::");
   printf("       ");
   puts("::::::::            All rights reserved.           :::::::");
   printf("       ");
   puts("::::::::::::::::::::::::::::::::::::::::::::::::::::::::::");

   printf("\nHow many generations ? ------------- : ");
   scanf("%d",&max_gen);
   printf("\nPopulation Size ? ------------------ : ");
   scanf("%d", &pop_size );
   if (pop_size > MAXPOPSIZE)
   {
        printf("\n Increase the value of MAXPOPSIZE in program");
        printf("  and re-run the program");
        exit(-1);
   }
   printf("\nNumber of binary-coded variables (Maximum %d) ---- : ",MAXVECSIZE);
   scanf("%d",&nvar_bin);
   printf("\nNumber of real-coded variables (Maximum %d) ---- : ",MAXVECSIZE);
   scanf("%d",&nvar_real);
   if (nvar_bin > 0)
     for (k=0, lchrom = 0; k < nvar_bin; k++)
       {
	 printf("\nString length and Lower and Upper bounds of xbin[%d] ----- : ",k+1);
	 scanf("%d %lf %lf",&chr_len[k],&xbin_lower[k],&xbin_upper[k]);
	 lchrom += chr_len[k];
       }
   if (nvar_real > 0)
     for (k=0; k < nvar_real; k++)
       {
	 printf("\nLower and Upper bounds of xreal[%d] ----- : ",k+1);
	 scanf("%lf %lf",&xreal_lower[k],&xreal_upper[k]);
       }
   if (nvar_real > 0) {
     printf("\n Are the real-parameter bounds rigid ? (y/n) ");
     do { ans = getchar(); } while (ans!= 'y' && ans !='n');
     if (ans == 'y')      RIGID = TRUE;
     else  RIGID = FALSE;
   } 
   printf("\nparameter-space niching to be done ? (y/n) --------- : ");
   do { ans = getchar(); } while (ans!= 'y' && ans !='n');
   if (ans == 'y')
   { SHARING = TRUE;
     printf("\nNiching parameter value  ? --------------- : ");
     scanf("%lf",&sigma_share);
   }
   else  SHARING = FALSE;
   printf ("\n Reports to be printed ? (y/n) ");
   do { ans = getchar(); } while (ans!= 'y' && ans !='n');
   if (ans == 'y') REPORT = TRUE;
   else            REPORT = FALSE;
   printf("\n How many runs ? ");
   scanf("%d",&maxrun);
   tourneysize=2;
   printf("\nCross Over Probability? (0 to 1): ");
   scanf("%lf",&p_xover);
   if (nvar_bin > 0) 
     {
       printf("\nMutation Probability for binary strings? (0 to 1) : ");
       scanf("%lf",&p_mutation_bin);
     }
   if (nvar_real > 0) 
     {
       printf("\nMutation Probability for real variables? (0 to 1) : ");
       scanf("%lf",&p_mutation_real);
     }
   if (nvar_real > 0)
     {
       printf("\n Give distr. index for SBX and mutation? ");
       scanf("%lf %lf",&n_distribution_c,&n_distribution_m);
     }
   printf("\n Give random seed (0 to 1.0) ");
   scanf("%lf",&basic_seed);

   critical_size = pop_size/4;
   input_app_parameters();
}

/*====================================================================
Initialses zero'th generation and global parameters
====================================================================*/
initialize()
{
   double u;
   int k,k1,i,j,j1,stop;
   double temp[MAXVECSIZE],coef;
   unsigned mask=1,nbytes;

   randomize();
   app_initialize();
   oldpop = (INDIVIDUAL *)malloc(pop_size*sizeof(INDIVIDUAL));
   newpop = (INDIVIDUAL *)malloc(pop_size*sizeof(INDIVIDUAL));

   if (oldpop == NULL) nomemory("oldpop in initialize()");
   if (newpop == NULL) nomemory("newpop in initialize()");

   chromsize = (lchrom/UINTSIZE);
   if(lchrom%UINTSIZE) chromsize++;
   nbytes = chromsize*sizeof(unsigned);
   if (nvar_bin > 0)
     for(j = 0; j < pop_size; j++)
       {
	 if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
	   nomemory("oldpop chromosomes");
	 
	 if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
	   nomemory("newpop chromosomes");
       }
   if (nvar_bin > 0)
     {
       if((best_ever.chrom = (unsigned *) malloc(nbytes)) == NULL)
	 nomemory("best_ever chromosomes");
       if((current_best.chrom = (unsigned *) malloc(nbytes)) == NULL)
	 nomemory("current_best chromosomes");
     }

   for (k=0; k < pop_size; k++)
   {
     oldpop[k].obj = 0.0;
     oldpop[k].parent1 = oldpop[k].parent2 = 0;
     oldpop[k].penalty = 0.0; oldpop[k].cross_var = 0;
     for (j=0; j < nc; j++)
       oldpop[k].cons[j] = 0.0;
     
     for (j=0; j < nvar_real; j++)
       {
         u = randomperc();
         oldpop[k].xreal[j] = xreal_lower[j] * (1-u) + xreal_upper[j] * u;
      }
 
      for(k1 = 0; k1 < chromsize; k1++)
      {
            oldpop[k].chrom[k1] = 0;
            if(k1 == (chromsize-1))
                stop = lchrom - (k1*UINTSIZE);
            else
                stop = UINTSIZE;
            /* A fair coin toss */
 
           for(j1 = 1; j1 <= stop; j1++)
            {
               if(flip(0.5))
                  oldpop[k].chrom[k1] = oldpop[k].chrom[k1]|mask;
               if (j1 != stop) oldpop[k].chrom[k1] = oldpop[k].chrom[k1]<<1;
            }
      }
   }
   no_xover = no_mutation = binmut = 0;

   copy_individual(&oldpop[0],&best_ever);
   decode_string(&best_ever);
   objective(&best_ever);
}

/*====================================================================
Decodes the string of the individual (if any) and puts the values in
the array of doubles.
====================================================================*/
decode_string(ptr_indiv)
INDIVIDUAL *ptr_indiv;
{
   double *temp,coef;
   int j;

   if (ptr_indiv == NULL) error_ptr_null("ptr_indiv in decode_string");
   if (nvar_bin > 0)
   {
     temp = (double *) malloc(nvar_bin * sizeof(double));
     for(j=0; j < nvar_bin; j++) 
       temp[j] = 0.0;
     decodevalue(ptr_indiv->chrom,temp);
     for(j=0; j < nvar_bin; j++)
     {
       coef = pow(2.0,(double)(chr_len[j])) - 1.0;
       temp[j] = temp[j]/coef;
       ptr_indiv->xbin[j] = temp[j]*xbin_upper[j] + (1.0 - temp[j])*xbin_lower[j];
     }
     free(temp);
   }
}
/*====================================================================
Prints an error message and terminates the program
====================================================================*/
nomemory(string)
char *string;
{
   printf("\nmalloc: out of memory making %s!!\n",string);
   printf("\n Program is halting .....");
   exit(-1);
}
/*==============================================================
Gives error message of null pointer  and terminates the program.
==============================================================*/
error_ptr_null(string)
char *string;
{
   printf("\n Error !! Pointer %s found Null !",string);
   printf("\n Program is halting .....");
   exit(-1);
}
/*====================================================================
Copys contents of one individual into another.
====================================================================*/
copy_individual(indiv1,indiv2)
INDIVIDUAL *indiv1, *indiv2;
{
   int k;

   if (indiv1==NULL) error_ptr_null("indiv1 in copy_individual");
   if (indiv2==NULL) error_ptr_null("indiv2 in copy_individual");
  
   for (k=0; k < nvar_bin; k++)
      indiv2->xbin[k] = indiv1->xbin[k];
   for (k=0; k < nvar_real; k++)
      indiv2->xreal[k] = indiv1->xreal[k];
   for (k=0; k < nc; k++)
     indiv2->cons[k] = indiv1->cons[k];
   indiv2->obj = indiv1->obj;
   indiv2->penalty = indiv1->penalty;