sga.c

由我收集或写出的GA源码

/********************************************************************\
***                                                                ***
***                      GENETIC ALGORITHM                         ***
***                                                                ***
***               Developed By : Prof. Kalyanmoy Deb               ***
***               with assistance from his Students                ***
***                                                                ***
*** Last Edited : 06.10.2001                                       ***
***................................................................***
This is a GA implementation using binary and real coded 
variables. There is a sample input file (input) which can be used to run
this code. Default values are suggested in the input file.

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

Variable boundaries can be fixed or fleexible

Following selection opeartors are coded:
1. Tournament selection: Set MINM=1 for minimization and -1 for maximization
2 and 3. Roulette wheel or Stochastic remainder RW selection: 
        Only maximization is allows (ENSURE MINM = -1 and 
        the obj. func. is to be maximized). For minimizing f(x) use the
        following objective function for maximization:
                     Fitness = 1.0/(1.0+f(x))

Following crossover operators are allowed: 
Binary coded GAs : single-point crossover
Real-coded GAs: SBX-eta or BLX-0.5
1. All variables upto a site are crossed and rest swapped
2. 50% variables are swapped at random (preferred)
3. Crossover is performed on a line

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

Constraints are handled using simple penalty function approach

Fitness sharing in parameter space is also allowed (Stochastic rem RW 
     is default selection opeartor) 

The execution creates a file `realga.out' for inspection.

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 1000
#define TRUE 1
#define FALSE 0
#define BLX 0
#define SBX 1
#define ONESITE 1
#define UNIF 2
#define ONLINE 3
#define square(x)  ((x)*(x))
/***** Current Objective Function ******/
#define prob1  /* define your problem at the end in objfunc() */

/*=================
TYPE DEFINTIONS :
=================*/
struct indiv
            {  float x[MAXVECSIZE];     /* variables            */
               float obj;               /* objective fn. value  */
               float mod_obj;           /* modified objective   */
               unsigned *chrom;         /* chrosome string      */
               int parent1;
               int parent2;             /* s.no. of parents     */
               float cross_var;         /* cross over variable  */
            };
typedef struct indiv INDIVIDUAL ;
typedef INDIVIDUAL *POPULATION ;        /* array of individuals */

/*====================
FUNCTION PROTOTYPES :
====================*/
float   objective();
float   degraded_value();
float   randomperc();
float   get_beta();
float   get_delta();
double  noise();
float   rndreal();

/*==================
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,            /* No. of mutations done                */
        best_ever_gen,          /* Generation no. of best ever indiv.   */
        num_var,                /* Number of total design variables     */
        num_discr_var,          /* Number of discrete variables         */
        lchrom,                 /* Length of chromosome                 */
        chromsize,              /* Number of bytes needed to store
                                                lchrom strings          */
        cross_type,             /* Cross over type ( SBX / BLX )        */
        x_strategy,s_strategy,  /* Cross-over strategy UNIF,ONLINE etc. */
        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)      */
        BINGA,                  /* Flag for binary GA (T/F)             */
        REALGA,                 /* Flag for real-GA (T/F)               */
        READFILE,               /* Flag for reading input from file     */
        tourneylist[MAXPOPSIZE],/* List of indices of individuals for
                                        tournament selection routine    */
        tourneypos,             /* Current position of tournament       */
        tourneysize,            /* Tournament size ( = 2 for binary )   */
        MINM;
float   seed,                   /* Random seed number                   */
        basic_seed,             /* Basic seed number                    */
  n_distribution_c, n_distribution_m,
        p_xover,                /* Cross over probability               */
        p_mutation,             /* 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[MAXVECSIZE],       /* Minimum and maximum values of design */
        maxx[MAXVECSIZE],       /*        variables in a population     */
        x_lower[MAXVECSIZE],    /* Lower and Upper bounds on each       */
        x_upper[MAXVECSIZE],    /*        design variable               */
        sigma_share;            /* Sharing distance                     */

POPULATION oldpop, newpop;      /* Old and New populations              */
INDIVIDUAL best_ever;           /* 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("::::::::     (c) R.B.Agrawal and K.Deb, 1995;      :::::::");
   printf("       ");
   puts("::::::::            All rights reserved.           :::::::");
   printf("       ");
   puts("::::::::::::::::::::::::::::::::::::::::::::::::::::::::::");

   printf("\n ARE YOU READING IT THROUGH A COMMENTED FILE (y/n) ?");
   do { ans = getchar(); } while (ans!= 'y' && ans !='n');
   if (ans == 'y')      READFILE = TRUE;
   else                 READFILE = FALSE;

   if (READFILE) printf("\n Reading data from file ............");
   if (!READFILE) printf("\nHow many generations ? ------------- : ");
   ignore_comment();
   scanf("%d",&max_gen);
   if (!READFILE)  printf("\nPopulation Size ? ------------------ : ");
   ignore_comment();
   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);
   }
   if (!READFILE) printf("\nCross Over Probability ? ( 0 to 1 )  : ");
   ignore_comment();
   scanf("%f",&p_xover);
   if (!READFILE) printf("\nMutation Probability ? ( 0 to 1 ) -- : ");
   ignore_comment();
   scanf("%f",&p_mutation);
   if (!READFILE)
        printf("\nNumber of variables (Maximum %d) ---- : ",MAXVECSIZE);
   ignore_comment();
   scanf("%d",&num_var);
   BINGA = REALGA = FALSE;
   if (!READFILE) printf("\n Binary or Real-coded parameters? (b for binary, r for real-coded) ");
   ignore_comment();
   do { ans = getchar(); } while (ans!= 'b' && ans !='r');
   if (ans == 'b') BINGA = TRUE;
   else            REALGA = TRUE;
   if (BINGA) num_discr_var = num_var;
   ignore_comment(); 
   for (k=0; k<= num_var-1; k++)
     {
       if (!READFILE) printf("\nLower and Upper bounds of x[%d] ----- : ",k+1);
       scanf("%f %f",&x_lower[k],&x_upper[k]);
     }
   if (REALGA) {
     if (!READFILE) printf("\n Are these bounds rigid ? (y/n)");
     ignore_comment();
     do { ans = getchar(); } while (ans!= 'y' && ans !='n');
     if (ans == 'y')      RIGID = TRUE;
     else  RIGID = FALSE;
   } else {
     if (READFILE) {
       ignore_comment();
       ans = getchar();
       RIGID = TRUE;
     }
   }
   if (BINGA)
     {
       if (!READFILE) printf("\n Total string length (each variable has equal string length)?");
	 ignore_comment();
	 scanf("%d",&lchrom);
     }
   else 
     if (READFILE) {
       ignore_comment();
       scanf("%d",&lchrom);
       lchrom=0;
     }
   if (!READFILE) printf("\nSharing to be done ? (y/n) --------- :");
   ignore_comment();
   do { ans = getchar(); } while (ans!= 'y' && ans !='n');
   if (ans == 'y')
   { SHARING = TRUE;
     if (!READFILE) printf("\nSigma share value  ? --------------- :");
     scanf("%f",&sigma_share);
   }
   else  SHARING = FALSE;
   if (!READFILE) printf ("\n Reports to be printed ? (y/n) ");
   ignore_comment();
   do { ans = getchar(); } while (ans!= 'y' && ans !='n');
   if (ans == 'y') REPORT = TRUE;
   else            REPORT = FALSE;
   if (!READFILE) printf("\n How many runs ?");
   ignore_comment();
   scanf("%d",&maxrun);
   if (!READFILE) 
     {
       printf("\n Enter selection operator --> ");
       printf("\n  1 : Tournament selection (min or max set by MINM in the code)");
       printf("\n  2 : Roulette wheel selection (always max)");
       printf("\n  3 : Stochastic remainder roulette wheel selection (always max)");
       printf("\n  Give your choice :");
     }
   ignore_comment();
   scanf("%d",&s_strategy);
   if (s_strategy == 1) {
     if (!READFILE) printf("\n Enter tournament size ");
     ignore_comment();
     scanf("%d", &tourneysize);
   } else 
     if (READFILE) {
       ignore_comment();
       scanf("%d",&tourneysize);
       tourneysize=0;
     }
   if (SHARING) s_strategy = 3; /* Stoch. Rem. RW is default */
   printf("TTTTT  %d \n",tourneysize);
   if (REALGA)
     {
       if (!READFILE)
	 {
	   printf("\n  Give the strategy for X-over");
	   printf("\n  1 : Polynomial distribution in one variable");
	   printf("\n  2 : Polynomial distribution in all variables");
	   printf("\n  3 : Polynomial distribution on a straight line");
	   printf("\n  Give your choice :");
	 }
       ignore_comment();
       scanf("%d",&x_strategy);
       
       if (!READFILE) printf("\n Type of cross over ? ( s for SBX, b for BLX) ");
       ignore_comment();
       do { ans = getchar(); } while (ans!= 's' && ans !='b');
       if (ans == 's') cross_type = SBX;
       else            cross_type = BLX;
       if (cross_type == SBX)
	 {
	   if (!READFILE) printf("\n Give eta for SBX and mutation?");
	   ignore_comment();
	   scanf("%f %f",&n_distribution_c,&n_distribution_m);
	 }
     }
   else {
     ignore_comment();
     scanf("%d",&x_strategy);
     x_strategy = 1; /* binary crossover */
     ignore_comment();
     ans = getchar();
     ignore_comment();
     scanf("%f %f",&n_distribution_c,&n_distribution_m);
     n_distribution_c = 0; n_distribution_m = 0;
   }
   if (!READFILE) printf("\n Give random seed (0 to 1.0)");
   ignore_comment();
   scanf("%f",&basic_seed);

   input_app_parameters();
}
/*====================================================================
  Ignores the comment from input ( ended by a ':')
====================================================================*/
ignore_comment()
{
    if (READFILE == FALSE) return;

    do
    {}
    while (getchar() != ':');
}
/*====================================================================
Initialses zero'th generation and global parameters
====================================================================*/
initialize()
{
   float 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);
   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((best_ever.chrom = (unsigned *) malloc(nbytes)) == NULL)
      nomemory("best_ever chromosomes");

   for (k=0; k<= pop_size-1; k++)
   {
      oldpop[k].parent1 = oldpop[k].parent2 = 0;
      for (j=num_discr_var; j<=num_var-1; j++)
      {
         u = randomperc();
         oldpop[k].x[j] = x_lower[j] * (1-u) + x_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 = 0;
   copy_individual(&oldpop[0],&best_ever);
   decode_string(&best_ever);
   best_ever.obj = objective(best_ever.x);

}

/*====================================================================
Decodes the string of the individual (if any) and puts the values in
the array of floats.
====================================================================*/
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 (BINGA)
   {
     temp = (double *) malloc(num_discr_var * sizeof(double));
     for(j=0; j<=num_discr_var - 1; j++) temp[j] = 0.0;
     decodevalue(ptr_indiv->chrom,temp);
     coef = pow(2.0,(double)(lchrom/num_discr_var)) - 1.0;
     for(j=0; j<=num_discr_var - 1; j++)
     {
        temp[j] = temp[j]/coef;
        ptr_indiv->x[j] = temp[j]*x_upper[j] + (1.0 - temp[j])*x_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);