nsgaorig.c

原始非支配多目标遗传算法

/********************************************************************\
***                      NON-DOMINATED SORTING                     ***
***                             using                              ***
***                       GENETIC ALGORITHM                        ***
***                              for                               ***
***                  MULTI OBJECTIVE OPTIMIZATION                  ***
***                                                                ***
***        Developed by : Kalyanmoy Deb and Mayank Goyal           ***
***           The Department of Mechanical Engineering             ***
***            Indian Institute of Technology, Kanpur              ***
***                  Kanpur, PIN 208 016, INDIA                    ***
***................................................................***
*** This is a GA implementation for multi-objective optimization.  ***
*** For multi-objective optimization, non-domonated sorting has    ***
*** been used.  The design variables can be Binary, Integer, Real  ***
*** or Enumerated data type.  Moreover a design vector can have    ***
*** design variables where each variable can be any of the above   ***
*** mentioned types.  The order in which the design variables      ***
*** are needed is also maintained in the code.  For multi-objective***
*** optimization, sharing is done using either of two ways :       ***
*** Sharing on Fitness Space or Sharing on Parameter Space. After  ***
*** completion, results are stored in a 'result.out' and for       ***
*** detailed inspection in a file 'report'. For a detail discussion***
*** please refer to Journal paper:                                 ***
*** Srinivas, N. and Deb, K. (1994). Multiobjective optimization   ***
***  using nondominated sorting genetic algorithms. Evolutionary   ***
***  Computation. Vol. 2, No. 3. Pages 221--248.                   ***
***                                                                ***
*** Please send your comments or bug information at                ***
*** [e-mail] or [e-mail]       ***
***                                                                ***
*** All rights reserved. Not to be used for commercial purposes.   ***
*** In case of a publication resulted by use of this code,         ***
*** an acknowledgement will be appreciated.                        ***
***                                                                ***
*** Last update 15 June 1998       Kalyanmoy Deb                   ***
\********************************************************************/

#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 MAXENUMDATA   100
#define MAXOBJ        5
#define MINSCHEME     1   /* do not change */
#define TRUE          1   /*     ,,        */
#define FALSE         0   /*     ,,        */
#define ONESITE       1   /*     ,,        */
#define UNIF          2   /*     ,,        */
#define BIN           1   /*     ,,        */
#define INT           2   /*     ,,        */
#define ENUM          3   /*     ,,        */
#define CONT          4   /*     ,,        */
#define square(x)  ((x)*(x)) 
#define cube(x)  ((x)*(x)*(x)) 
#define PENALTY_COEFF 1.0e3

/*=============================
  Choose your problem here (put your problem at the end of code) 
  ===========================*/
#define book

/*=================
  TYPE DEFINTIONS :
  =================*/
struct indiv      
{  
  unsigned *chrom;		/* chrosome string 	*/
  float fitness[MAXOBJ];	/* fitness functions    */
  float x[MAXVECSIZE];	        /* variables  		*/
  float dumfitness;	        /* modified objective   */ 
  int   flag;                   /* flag as follows
			            0 => untouched
			            1 => dominated
		                    2 => non-dominated
		        	    3 => exhausted   */
  int   front;                  /* Front of the indiv.  */
  int   parent1;                /* two parents */
  int   parent2;	
};
typedef struct indiv INDIVIDUAL ;
typedef INDIVIDUAL *POPULATION ;	/* array of individuals */

/*====================
  FUNCTION PROTOTYPES :
  ====================*/
float 	randomperc(); 
float 	get_beta();
float	get_delta();
float   get_beta_rigid();
double  noise();
float 	rndreal();
int   	small(float);

/*==================
  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 	 */
  num_var,		/* Number of total design variables */
  num_bin_var,            /* Number of binary variables    */
  num_int_var,            /* Number of integer variables   */
  num_enum_var,           /* Number of enumerated variables */
  num_cont_var,           /* Number of continuous variables */
  num_obj,                /* Number of objectives           */
  lchrom[MAXVECSIZE], /* Length of chromosome		  */
  chromsize,          /* Number of bytes needed to store 
			 lchrom strings */
  x_strategy, 	    /* Crossover strategy UNIF,ONESITE etc. */
  REPORT,		    /* Flag for Full reports (True/False) */
  var_RIGID[MAXVECSIZE],  /* Flag for rigid boundaries (T/F) */
  BINGA,			/* Flag for binary GA (T/F)	*/
  REALGA,			/* Flag for real-GA (T/F)	  */
  FITNESS,                /* Flag for sharing strategy (T/F)  */
  PARAM,
  minmax[MAXOBJ],          /* min or max flag */
  tourneylist[MAXPOPSIZE],/* List of indices of individuals for
			     tournament selection routine */
  tourneypos, 		/* Current position of tournament   */
  tourneysize,		/* Tournament size ( = 2 for binary )*/
  var_type[MAXVECSIZE],   /* Temp. variable type            */
  TotalChromLength,       /* Total Chromosome Length       */
  num_enum_data[MAXVECSIZE];/* Number of Enumerated Data for
			       each enumerated variable    */

float 	seed,			/* Random seed number	   	*/
  n_distribution_c, n_distribution_m, /* Distribution
					 index for SBX 	*/
  p_xover, 		/* Cross over probability	*/
  p_mutation, 		/* Mutation probability		*/
  closeness,		/* Closeness epsilon		*/
  minx[MAXVECSIZE],	/* Minimum value of design variables */
  maxx[MAXVECSIZE],   	/* Maximum value of design variables */
  x_lower[MAXVECSIZE], 	/* Lower and Upper bounds on each  */
  x_upper[MAXVECSIZE], 	/*        design variable	   */
  afmin[MAXOBJ],          /* approx min value of obj funs. */
  afmax[MAXOBJ],          /* approx max value of obj funs  */
  dshare,	                /* Sharing distance		   */
  max_spread, 		/* Maximum spread */
  maxf[MAXOBJ],           /* Maximum fitness values         */
  minf[MAXOBJ],           /* Minimum fitness values         */
  avgfitness[MAXOBJ],     /* Average fitness values         */
  dum_avg, min_dum,       /* Avg. and min. dummy fitness      */
  init_dum,delta_dum,     /* Initial and delta dummy fitness  */
  c1=0.0,c2=0.0,          /* Children                         */
  weightage[MAXOBJ],      /* Weightage assigned to fitness    */
  EnumData[MAXVECSIZE][MAXENUMDATA]; /* Enumerated Data       */

POPULATION oldpop, newpop;	/* Old and New populations   */

int *choices, nremain;
float *fraction;

/*====================================================================
  SUBROUTINE FOR INPUTTING GLOBAL PARAMETERS :
  ====================================================================*/
input_parameters()
{
  int   k,temp2,count;
  char  ans;
  float temp1, sumweight;
  
  printf("\nNumber of objective functions (2) --> ");
  scanf("%d",&num_obj);
  printf("\nSpecify minimization (1) or maximization (-1) for each function ");
 for (count=0; count<num_obj; count++)
    {
      printf("\n  Objective function #%2d (1 or -1)      --> ",count+1); 
      scanf("%d",&minmax[count]);
    }
  
  printf("\nNumber of variables (Maximum %2d) --- : ",MAXVECSIZE);
  scanf("%d",&num_var);
  
  BINGA = FALSE;
  REALGA = FALSE;
  TotalChromLength=0;
  
  num_bin_var=0; num_int_var=0; num_enum_var=0; num_cont_var=0;
  for (k=0; k<= num_var-1; k++)
    {
      printf("\nVariable Type for variable #%2d : \n",k+1);
      printf("\t\t 1 for Binary\n");
      printf("\t\t 2 for Integer\n");
      printf("\t\t 3 for Enumerated\n");
      printf("\t\t 4 for Continuous/Real");
      printf("\n  Give your choice (1/2/3/4) ------- : ");
      scanf("%d",&var_type[k]);
      
      if (var_type[k]!=ENUM)  /* If not ENUM, ask for bounds */
	{
	  printf("\nLower and Upper bounds of x[%d] ----- : ",k+1);
	  scanf("%f %f",&x_lower[k],&x_upper[k]);
	}
      
      if (var_type[k]!=CONT)
	var_RIGID[k] = TRUE;
      
      if (var_type[k]==BIN) /* If BIN Type ask for chromosome length */
	{
	  num_bin_var++;
	  BINGA = TRUE;
	  printf("\nChromosome Length ------------------ : ");
	  scanf("%d",&lchrom[k]);
	  TotalChromLength += lchrom[k];
	}
      else
	lchrom[k] = 0;       /* End of BIN */
      
      if (var_type[k]==ENUM)  /* If ENUM Type read the enumerated data */
	{
	  num_enum_var++;
	  REALGA=TRUE;
	  printf("\nEnter the data for variable [%d] in ASCENDING order.\n",k+1);
	  printf("End of data recognized by 999999: ");
	  temp2=0;
	  scanf("%f",&temp1);
	  EnumData[k][0] = temp1;
	  temp2++;
	  while (!small(temp1-999999.0))
	    {
	      scanf("%f",&temp1);
	      EnumData[k][temp2] = temp1;
	      temp2++;
	    }
	  num_enum_data[k]=temp2-1;
	  x_lower[k]=EnumData[k][0];
	  x_upper[k]=EnumData[k][num_enum_data[k]-1];
	}
      else
	num_enum_data[k]=0;  /* End of ENUM */
      
      if (var_type[k]==INT) /* If INT Type form the enumerated data */
	{
	  num_int_var++;
	  REALGA=TRUE;
	  num_enum_data[k] = x_upper[k]-x_lower[k]+1;
	  for (count=0;count<num_enum_data[k];count++)
	    EnumData[k][count]=x_lower[k]+count;
	}                       /* End of INT */
      
      if (var_type[k]==CONT)             /* If CONT Type */
	{
	  num_cont_var++;
	  REALGA=TRUE;
	  printf(" Are these bounds rigid ---- ? (y/n) : ");
	  do { ans = getchar(); } while (ans!= 'y' && ans !='n');
	  if (ans == 'y')  var_RIGID[k] = TRUE;
	  else             var_RIGID[k] = FALSE;
	}
    }  /* End of for loop for variable info. */
  printf("\n");
  
  for (count=0;count<num_var;count++)
    {
      printf("Variable (#%2d) Type : ",count+1);
      switch (var_type[count])
	{
	case BIN  : printf("BINARY\n");break;
	case INT  : printf("INTEGER\n");break;
	case ENUM : printf("ENUMERATED\n");break;
	case CONT : printf("CONTINUOUS\n");break;
	}
      printf("Lower Bound   : %f\n",x_lower[count]);
      printf("Upper Bound   : %f\n",x_upper[count]);
    }
  
  FITNESS=PARAM=FALSE;
  printf("\n Sharing Strategy :"); 
  printf("\n Sharing on Fitness Space   (f)");
  printf("\n Sharing on Parameter Space (p)");
  printf("\n Give your choice (f/p) p preferable : ");
  do { ans = getchar(); } while (ans!= 'f' && ans !='p');
  if (ans == 'f') 	FITNESS = TRUE;
  else                  PARAM   = TRUE;
  
  if (FITNESS)
    {
      printf("\nEqual weightage for all objectives (y or n)?: ");
      do { ans = getchar(); } while (ans!= 'y' && ans != 'n');
      if (ans == 'n') 
	{
	  for (count=0, sumweight=0.0; count<num_obj; count++)
	    {
	      printf("\n  Weight for objective #%2d (0.5) -> ",count+1);
	      scanf("%f", &weightage[count]);
	      sumweight += weightage[count];
	      printf("\n  Lower and Upper values of function #%2d (approx.) -> ",count+1);
	      scanf("%f %f", &afmin[count], &afmax[count]);
	    } 
	  for (count=0; count<num_obj; count++)
	    weightage[count] /= sumweight; 
	}
      else 
	for (count=0; count<num_obj; count++)
	  weightage[count] = 1.0/(double)num_obj;
   }
  /* give a suggestion of dshare */
  printf("\nSigma share value accordingly (%8.3f) -- : ",0.5*pow(0.1,1.0/num_var));
  scanf("%f",&dshare);
  
  printf("\nReports to be printed ----- ? (y/n)  : ");
  do { ans = getchar(); } while (ans!= 'y' && ans !='n');
  if (ans == 'y') REPORT = TRUE;
  else            REPORT = FALSE;
  
  printf("\nPopulation Size ? (~ 20 times N) ---- : ");
  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("\nCross Over Probability ? ( 0.7 to 1 )  : ");
  scanf("%f",&p_xover);
  
  printf("\nMutation Probability ? ( 0 to 0.2 ) -- : ");
  scanf("%f",&p_mutation);
  
  printf("\n Give the strategy for X-over");
  printf("\n 1 : Single-point crossover");
  printf("\n 2 : Uniform crossover"); 
  printf("\n Give your choice -------------(1/2) : ");
  scanf("%d",&x_strategy);
  
  if (REALGA)
    {
      printf("\nDistribution Index for crossover and mutation (30 50) : ");
      scanf("%f %f",&n_distribution_c, &n_distribution_m);
    }     
  
  printf("\nHow many generations (100) ? --------- : ");
  scanf("%d",&max_gen);
  
  printf("\nGive random seed (0 to 1.0)          : ");
  scanf("%f",&seed);
  
  input_app_parameters();
}

/*====================================================================
  Initialses zero'th generation and global parameters
  ====================================================================*/
initialize()
{
  float u;
  int tmp,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()");
  
  if (BINGA)    /* If Binary Variables, allocate memory for chromosomes */
    {
      chromsize = (TotalChromLength/UINTSIZE); 
      if (TotalChromLength%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"); 
	} 
    }             /* End of If (BINGA) */
  
  /* Initializing continuous, integer 
     and enumerated variables    */
  for (k=0; k<= pop_size-1; k++) 
    {  
      oldpop[k].flag = 0;
      oldpop[k].parent1 = oldpop[k].parent2 = 0;
      oldpop[k].dumfitness = 0.0;
      for (j=0; j<=num_var-1; j++)
	{ 
	  if (var_type[j]!=BIN)
	    {
	      u = randomperc();
	      oldpop[k].x[j] = x_lower[j] * (1-u) + x_upper[j] * u;   
	      
	      if ((var_type[j]==INT)||(var_type[j]==ENUM))