nsgaorig.c

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

		{
		  for(k1=0;k1<num_enum_data[j]-1;k1++)
		    {
		      if (oldpop[k].x[j]<EnumData[j][0]) 
			{
			  oldpop[k].x[j]=EnumData[j][0]; 
			  continue;
			}
		      else if (oldpop[k].x[j]>EnumData[j][num_enum_data[j]-1]) 
			{
			  oldpop[k].x[j]=EnumData[j][num_enum_data[j]-1]; 
			  continue;
			}
		      else if ((EnumData[j][k1]<oldpop[k].x[j])&&
			       (EnumData[j][k1+1]>oldpop[k].x[j]))
                        oldpop[k].x[j]=( (EnumData[j][k1+1]-oldpop[k].x[j])>
					 (oldpop[k].x[j]-EnumData[j][k1]) ) ? 
			  EnumData[j][k1] : EnumData[j][k1+1];
		    }    /* End of for k1 */
		}       /* End of if (INT or ENUM) */
	    }             /* End of if (not BIN)  */
	}
      
      /* Initializing chromosomes
	 for binary variables     */
      for(k1 = 0; k1 < chromsize; k1++) 
	{
	  oldpop[k].chrom[k1] = 0; 
	  if(k1 == (chromsize-1)) 
            stop = TotalChromLength - (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; 
	    }                 /* End of for (j1) */ 
	}                    /* End of for (k1) */
    }                       /* End of for (k) */
  
  no_xover = no_mutation = 0;
  
  init_dum  = pop_size;             /* For Sharing */
  min_dum   = 0.0;
  delta_dum = 0.1*init_dum;
  
  /* Decoding binary strings and initializing 
     fitness values for each individual */
  for (k=0; k<= pop_size-1; k++)    
    {                                    
      decode_string(&(oldpop[k]));      
      objective(&(oldpop[k]));          
    } 
}

/*====================================================================
  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[MAXVECSIZE]; 
  int j;
  
  if (ptr_indiv == NULL) error_ptr_null("ptr_indiv in decode_string");
  if (BINGA)
    {
      temp = (double *) malloc(num_var * sizeof(double));
      
      for(j=0; j<num_var; j++) 
	temp[j] = 0.0;
      
      decodevalue(ptr_indiv->chrom,temp);
      
      for(j=0; j<num_var; j++) 
	if (var_type[j]==BIN)
	  {
	    coef[j] = pow(2.0,(double)(lchrom[j])) - 1.0;
	    temp[j] = temp[j]/coef[j];
	    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);
  printf("\n Program is halting .....");
  exit(-1);
}

/*====================================================================
  Calculates statistics of current generation :
  ====================================================================*/
statistics(pop,gen)
     POPULATION pop;
     int gen;
{
  int j,iobj;
  float dumsumfit = 0.0;
  float sumfitness[MAXOBJ];
  
  for (iobj=0; iobj<num_obj; iobj++)
    {
      minf[iobj] = maxf[iobj] = 1.0e8;
      sumfitness[iobj] = 0.0;
    }
  
  for (j=0; j<=pop_size-1; j++)
    {
      dumsumfit   += pop[j].dumfitness;
      for (iobj=0; iobj<num_obj; iobj++)
	{
	  sumfitness[iobj] += pop[j].fitness[iobj];
	  if (pop[j].fitness[iobj] > maxf[iobj]) maxf[iobj] = pop[j].fitness[iobj];
	  if (pop[j].fitness[iobj] < minf[iobj]) minf[iobj] = pop[j].fitness[iobj];
	}
    }
  
  dum_avg = dumsumfit/(double)pop_size;
  for (iobj=0; iobj<num_obj; iobj++)
    avgfitness[iobj] = sumfitness[iobj]/(double)pop_size;
  
  app_statistics();
}

/*====================================================================
  Decodes the value of a group of binary strings and puts the decoded
  values into an array 'value'.
  ====================================================================*/
decodevalue(chrom,value) 
     unsigned *chrom; 
     double value[];
{ 
  int temp,k,count,tp,mask=1,sumlengthstring,stop,j,PrevTrack;
  int bitpos,flag1,flag2;
  int CountTrack;
  double pow(), bitpow; 
  
  if (BINGA == FALSE) return;
  if (chrom == NULL) error_ptr_null("chrom in decodevalue");
  
  for(count=0;count<num_var;count++)
    value[count]=0; 
  
  for(k = 0; k < chromsize ; k++) 
    { 
      if (k == (chromsize-1))
	stop = TotalChromLength-(k*UINTSIZE);
      else
	stop = UINTSIZE;
      /* loop thru bits in the current byte */ 
      tp = chrom[k]; 
      for (j=0;j<stop;j++)
	{
	  bitpos=j+k*UINTSIZE;
          /* test for current bit 0 or 1 */ 
          if((tp&mask) == 1) 
	    {
	      sumlengthstring=0;
	      flag1=FALSE;
	      flag2=FALSE;   /* To keep track of the 
			        position of 'j' in the chromosome */
              for(count=0;count<num_var;count++)        
		{                                           
		  if ((var_type[count]==BIN)&&(!flag2))  
		    {                                     
		      if (bitpos>=sumlengthstring)     
			flag1=TRUE;
		      else
			flag1=FALSE;
		      sumlengthstring+=lchrom[count];
		      if ((bitpos<sumlengthstring)&&(flag1)) 
			{  
			  flag2=TRUE;
			  CountTrack=count;
			  PrevTrack=sumlengthstring-lchrom[count];
			}                     /* End of if (bitpos...)  */ 
		    }                        /* End of if (vartype...) */
		}                           /* End of for (count)     */
              
              bitpow = pow(2.0,(double)(bitpos-PrevTrack));
              value[CountTrack] += bitpow;
	    }                   /* End of if (tp&mask) */   
          tp = tp>>1; 
	}                      /* End of for (j) */ 
    }                         /* End of for (k) */ 
} 

/*====================================================================
  GENERATION OF NEW POPULATION through SELECTION, XOVER & MUTATION :
  ====================================================================*/
generate_new_pop()
{
  int j,k,k1,mate1,mate2;
  
  app_computation();
  preselect();
  for (k=0; k<= pop_size-1; k += 2)
    {
      mate1 = select();       /* Stoc. Rem. Roulette Wheel Selection */
      mate2 = select();
      
      switch( x_strategy )          /* Crossover */
	{
	case ONESITE :  cross_over_1_site(mate1,mate2,k,k+1); break;
	case UNIF    :  cross_over_unif(mate1,mate2,k,k+1)  ; break;
	}
      
      mutation(&newpop[k]);        /* Mutation */
      decode_string(&(newpop[k]));
      update_x_BIN_ENUM(&(newpop[k]));
      objective(&(newpop[k]));
      newpop[k].parent1 = mate1+1;
      newpop[k].parent2 = mate2+1;
      
      mutation(&newpop[k+1]);
      decode_string(&(newpop[k+1])); 
      update_x_BIN_ENUM(&(newpop[k+1]));
      objective(&(newpop[k+1]));
      newpop[k+1].parent1 = mate1+1;
      newpop[k+1].parent2 = mate2+1;
    }                          /* For whole population */
}

/***************************************************************
  For integer and enumerated data, a permissible solution is
  calculated here 
  **************************************************************/
update_x_BIN_ENUM(indv)
     INDIVIDUAL *indv;
{
  int j, k1;
  
  for(j=0;j<num_var;j++)
    if ((var_type[j]==INT)||(var_type[j]==ENUM))
      {
	for(k1=0;k1<num_enum_data[j]-1;k1++)
	  {
	    if (indv->x[j]<EnumData[j][0]) 
	      {
		indv->x[j]=EnumData[j][0]; 
		continue;
	      }
	    else if (indv->x[j]>EnumData[j][num_enum_data[j]-1]) 
	      {
		indv->x[j]=EnumData[j][num_enum_data[j]-1]; 
		continue;
	      }
	    else if ((EnumData[j][k1]< indv->x[j])&&
		     (EnumData[j][k1+1]> indv->x[j]))
	      indv->x[j]=( (EnumData[j][k1+1] - indv->x[j]) >
			   (indv->x[j]-EnumData[j][k1]) ) ? 
		EnumData[j][k1] : EnumData[j][k1+1];
	  }                  /* End of for (k1) */
      }
}

/*====================================================================
  Binary cross over routine.
  ====================================================================*/
binary_xover (parent1, parent2, child1, child2) 
     unsigned *parent1, *parent2, *child1, *child2; 
     /* Cross 2 parent strings, place in 2 child strings */ 
{ 
  int j, jcross, k; 
  unsigned mask, temp; 
  
  if (BINGA == FALSE) return;
  if (parent1 == NULL) error_ptr_null("parent1 in binary_xover");
  if (parent2 == NULL) error_ptr_null("parent2 in binary_xover");
  if (child1== NULL) error_ptr_null("child1 in binary_xover");
  if (child2== NULL) error_ptr_null("child2 in binary_xover");
  
  jcross = rnd(1 ,(TotalChromLength - 1));/* Cross between 1 and l-1 */ 
  for(k = 1; k <= chromsize; k++) 
    { 
      if(jcross >= (k*UINTSIZE)) 
	{ 
                child1[k-1] = parent1[k-1]; 
                child2[k-1] = parent2[k-1]; 
	} 
            else if((jcross < (k*UINTSIZE)) && (jcross > ((k-1)*UINTSIZE))) 
            { 
	      mask = 1; 
	      for(j = 1; j <= (jcross-1-((k-1)*UINTSIZE)); j++) 
                { 
		  temp = 1; 
		  mask = mask<<1; 
		  mask = mask|temp; 
                } 
	      child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask)); 
	      child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask); 
            } 
      else 
	{ 
	  child1[k-1] = parent2[k-1]; 
	  child2[k-1] = parent1[k-1]; 
	} 
    } 
} 

/*====================================================================
  Creates two children from parents p1 and p2, stores them in addresses
  pointed by c1 and c2.  low and high are the limits for x values and
  rand_var is the random variable used to create children points.
  ====================================================================*/
create_children(p1,p2,c1,c2,low,high,RIGID)
     float p1,p2,*c1,*c2,low,high;
     int RIGID;
{
  float difference, x_mean, beta, temp;
  float u, u_l, u_u, beta_l=0.0, beta_u=0.0, beta1=0.0, beta2=0.0;
  int flag;
 
 
  if (c1 == NULL) error_ptr_null("c1 in create_children");
  if (c2 == NULL) error_ptr_null("c2 in create_children");
  flag = 0;
  if ( p1 > p2) { temp = p1; p1 = p2; p2 = temp; flag = 1; }
  x_mean = ( p1 + p2) * 0.5;
  difference = p2 - p1;
  if(difference <= 1.0e-9)
    {
      *c1 = p1;
      *c2 = p2;
    }
  else
    {
      if (RIGID)
        {
          beta_l = 1.0 + 2.0*(p1-low)/(p2-p1);
          beta_u = 1.0 + 2.0*(high-p2)/(p2-p1);
          if (MINSCHEME)
            {
              if(beta_l <= beta_u) beta_u = beta_l;
              else beta_l = beta_u;
              u = rndreal(0.0,1.0);
              beta1 = beta2 = get_beta_rigid(u,beta_l);
            }
          else
            {
              u_l = rndreal(0.0,1.0);
              beta1 = get_beta_rigid(u_l,beta_l);
 
              u_u = rndreal(0.0,1.0);
              beta2 = get_beta_rigid(u_u,beta_u);
            }
        }
      else
        {
          u = rndreal(0.0,1.0);
          beta1 = beta2 = get_beta(u);
        }
      *c1 = x_mean - beta1 * 0.5 * difference;
      *c2 = x_mean + beta2 * 0.5 * difference;
    }
  if (flag == 1)
    {
      temp = *c1; *c1 = *c2; *c2 = temp;
    }
  if (*c1 < low)  *c1 = low;
  if (*c2 > high) *c2 = high;
 
  if (*c1 < low || *c2 > high)
    {
      printf("Error!! p1 = %f, p2 = %f, c1 = %f, c2 = %f\n",p1,p2,*c1,*c2);
      exit(-1);
    }
}

/*====================================================================
cross over using strategy of 1 cross site with swapping .
  A random variable is chosen and crossed over. The variables on left
  side are passed as it is and those on right are swapped between the
  two parents.
====================================================================*/
cross_over_1_site(first,second,childno1,childno2)
int first,second,childno1,childno2;