nsgaorig.c

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

{
    int j,k,site;
   
    if (flip(p_xover))   /* Cross over has to be done */
    {
       no_xover++;
       if (BINGA)
       binary_xover(oldpop[first].chrom   ,oldpop[second].chrom,
                    newpop[childno1].chrom,newpop[childno2].chrom); 

       site = rnd(0,num_var-1);
  
       for (k=0; k<=site-1; k++)   /* Passing the values straight
				      before the cross-site */ 
         if (var_type[site]!=BIN)  /* Only if variable type is not BINARY */
	 {
	    newpop[childno1].x[k] = oldpop[first].x[k]; 
            newpop[childno2].x[k] = oldpop[second].x[k]; 
 	 }

       for (k=site+1; k<=num_var-1; k++)  /* Swapping the values 
				             after the cross-site */ 
         if (var_type[site]!=BIN)
	 {
	    newpop[childno2].x[k] = oldpop[first].x[k]; 
            newpop[childno1].x[k] = oldpop[second].x[k]; 
	 }

                                     /* If variable != BINARY create children 
					at the cross site variable */ 
	if (var_type[site]!=BIN)
	      create_children(oldpop[first].x[site], oldpop[second].x[site], 
			    &(newpop[childno1].x[site]),
			    &(newpop[childno2].x[site]), 
			    x_lower[site],x_upper[site],var_RIGID[site]);
    }                 /* Cross over done */

    else              /* Passing x-values straight */
    {   
      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 (k=0; k<=num_var-1; k++)
      {
	newpop[childno1].x[k] = oldpop[first].x[k];
        newpop[childno2].x[k] = oldpop[second].x[k];
      }
    }
}

/*====================================================================
CROSS - OVER  USING strategy of uniform 50% variables 
  For one variable problem, it is crossed over as usual.
  For multivariables, each variable is crossed over with a probability
  of 50 % , each time generating a new random beta.
====================================================================*/
cross_over_unif(first,second,childno1,childno2)
int first,second,childno1,childno2;
{
    float difference,x_mean,beta;
    int site,k;
   
    if (flip(p_xover))   /* Cross over has to be done */
    {
     no_xover++;
     if (BINGA)
     binary_xover(oldpop[first].chrom,oldpop[second].chrom,
		  newpop[childno1].chrom,newpop[childno2].chrom); 
      for (site = 0; site<=num_var-1; site++)
      {
	if (var_type[site]!=BIN)
          if (flip(0.5) || (num_var==1))
          {
            create_children(oldpop[first].x[site],oldpop[second].x[site],
		      &(newpop[childno1].x[site]),&(newpop[childno2].x[site]),
		      x_lower[site],x_upper[site],var_RIGID[site]);
          }
          else 
          {
	    newpop[childno1].x[site] = oldpop[first].x[site];
            newpop[childno2].x[site] = oldpop[second].x[site];
          }
      }               /* for loop */
    }                 /* Cross over done */

    else              /* Passing x-values straight */
    {   
      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, Binary Probability distribution simulation
====================================================================*/
float get_beta(u)
     float u;
{
  float beta;
 
  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);
}

/*****************************************************************
  Calculates beta for rigid boundaries 
  ****************************************************************/
float get_beta_rigid(u,betaa)
     float u, betaa;
{
  float bet, beta;
 
  if (u <= 0.0+1.0e-9)      beta = 0.0;
  else if (u >= 1.0-1.0e-9) beta = betaa;
  else
    {
      bet = 1.0/betaa;
      bet = 2.0 - pow(bet, (n_distribution_c + 1.0));
      if (u <= 1.0/bet)
        beta = pow(bet * u, (1.0 / (n_distribution_c + 1.0)));
      else
        beta = pow(1.0/(2.0-u*bet), (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, delta_l, delta_u)
     float u, delta_l, delta_u;
{
  float delta, aa;
  
  if (u >= 1.0-1.0e-9)      delta = delta_u;
  else if (u <= 0.0+1.0e-9) delta = delta_l;
  else
    {
      if (u <= 0.5)
        {
          aa = 2.0*u + (1.0-2.0*u)*pow((1+delta_l),
				       (n_distribution_m + 1.0));
          delta = pow(aa, (1.0 / (n_distribution_m + 1.0))) - 1.0;
        }
      else
        {
          aa = 2.0*(1-u) + 2.0*(u-0.5)*pow((1-delta_u),
					   (n_distribution_m + 1.0));
          delta = 1.0 - pow(aa, (1.0 / (n_distribution_m + 1.0)));
        }
    }
  if (delta < -1.0 || delta > 1.0)
    {
      printf("Error in mutation!! delta = %f\n",delta);
      exit(-1);
    }
  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 = TotalChromLength - ((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 distance,x,delta,u,delta_l,delta_u;
   int k, site;

   if (indiv == NULL) error_ptr_null("indiv in mutation");

   if (flip(p_mutation))  no_mutation++;
   if(flip (p_mutation) && REALGA)
     {
       site = rnd(0,num_var - 1);
       
       if (var_type[site]!=BIN)
	 {
	   if(fabs(x_upper[site] -x_lower[site]) < EPSILON) return;
	   
	   /* calculation of bounds on delta */  
 	   if(var_RIGID[site])
	     { 
	       x = indiv->x[site];
	       distance = x_lower[site] - x;
	       delta_l = distance / (x_upper[site] - x_lower[site]);
	       if (delta_l < -1.0)  delta_l = -1.0;
	       
	       distance = x_upper[site] - x;
	       delta_u = distance / (x_upper[site] - x_lower[site]);
	       if (delta_u > 1.0)   delta_u = 1.0;
	       
	       if (MINSCHEME) 
		 {    
		   if (-1.0*delta_l < delta_u) delta_u = -1.0 * delta_l;
		   else delta_l = -1.0 * delta_u;
		 }
	     }
	   else  /* flexible */
	     {
	       delta_l = -1.0;
	       delta_u =  1.0;
	     }
	   u = rndreal(0.0, 1.0);
	   delta = get_delta(u, delta_l, delta_u)
	     * (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, iobj;

   if (fp == NULL) error_ptr_null(" File fp in initreport");
   fprintf(fp,"\n=============================================");
   fprintf(fp,"\n             INITIAL REPORT                  ");
   fprintf(fp,"\n=============================================");
   fprintf(fp,"\n");
   fprintf(fp,"\n Number of objective functions : %2d",num_obj);
   for (iobj=0; iobj<num_obj; iobj++) 
     {
       fprintf(fp,"\n   Objective function #%2d : ",iobj+1); 
       if (minmax[iobj] == 1) fprintf(fp,"Minimize");
       else if (minmax[iobj] == -1) fprintf(fp,"Maximize");
     }
   fprintf(fp,"\n\n CROSSOVER TYPE             : ");
   if (BINGA) fprintf(fp,"Binary GA (Single-pt)");
   fprintf(fp,"\n                              ");
   switch (x_strategy)
   {
    case ONESITE : fprintf(fp,"\n STRATEGY                   : 1 cross - site with swapping"); break;
    case UNIF    : fprintf(fp,"\n STRATEGY                   : Uniformly all variables 50 % "); break;
    default      : fprintf(fp,"\n CROSS OVER NOT SET CORRECTLY "); break;
   }
   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 (BINGA)
      fprintf(fp,"\n String length              : %d",TotalChromLength);
   fprintf(fp,"\n Number of variables");
   fprintf(fp,"\n                Binary      : %d",num_bin_var);
   fprintf(fp,"\n                Integer     : %d",num_int_var);
   fprintf(fp,"\n                Enumerated  : %d",num_enum_var);
   fprintf(fp,"\n                Continuous  : %d",num_cont_var);
   fprintf(fp,"\n                  TOTAL     : %d",num_var);
   fprintf(fp,"\n Epsilon for closeness      : %g",closeness);
   if (REALGA)
     {
       fprintf(fp,"\n Distribution Index (cross) : %g",n_distribution_c);
       fprintf(fp,"\n Distribution Index (mut)   : %g",n_distribution_m);
     }
   fprintf(fp,"\n Sigma-share value          : %6.4f",dshare);
   fprintf(fp,"\n Sharing Strategy           : ");
   if (PARAM) 
      fprintf(fp,"sharing on Parameter Space");
   else if (FITNESS) 
     {
       fprintf(fp,"sharing on Fitness Space");
       for (iobj=0; iobj<num_obj; iobj++)
	 fprintf(fp,"\n Weightage for Obj. Fun. #%2d : %6.4f",iobj+1,weightage[iobj]);
     }
   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; 
    int temp[100];

   for (j=0;j<100;j++)
    temp[j]=0;
   if (fp == NULL) error_ptr_null(" File fp in initreport");
   if (BINGA == FALSE) return;
   if (chrom == NULL) error_ptr_null("chrom in writechrom");
    for(k = 0; k < chromsize; k++) 
    { 
        tmp = chrom[k]; 
        if(k == (chromsize-1)) 
            stop = TotalChromLength - (k*UINTSIZE); 
        else 
            stop = UINTSIZE; 
        for(j = 0; j < stop; j++) 
        { 
            if(tmp&mask) 
	    {
                /*fprintf(fp,"1"); */
		temp[j+count*UINTSIZE]=1;
	    }
            else 
	    {
                /*fprintf(fp,"0"); */
		temp[j+count*UINTSIZE]=0;
	    }
            tmp = tmp>>1; 
        } 
	count++;
    } 

    count=0;
    for(j=0;j<num_var;j++)
    {
       for(k=count+lchrom[j]-1;k>=count;k--)
       {
	  fprintf(fp,"%d",temp[k]);
       }
       count+=lchrom[j];
       if (j!=num_var-1) fprintf(fp,"_");
    }
} 

/*====================================================================
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,iobj; 
  char string[30];

  if (fp == NULL) error_ptr_null(" file fp in report()");
   /* ----------------------------------------- */
   /* WRITING IN THE OUTPUT FILE FOR INSPECTION */
   /* ----------------------------------------- */