ga.c

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

   indiv2->parent1 = indiv1->parent1;
   indiv2->parent2 = indiv1->parent2;
   indiv2->cross_var = indiv1->cross_var;
   for (k=0; k < chromsize; k++)
     indiv2->chrom[k] = indiv1->chrom[k];
}

/*====================================================================
Calculates statistics of current generation :
====================================================================*/
statistics(gen)
int gen;
{
  // INDIVIDUAL current_best;
   int k,j, change_flag;
   double f;
   double pow(),bitpow,coef,temp[MAXVECSIZE];

   for (k=0; k < pop_size; k++)
   {
     decode_string(&oldpop[k]);
     objective(&(oldpop[k]));
   }
   copy_individual(&oldpop[0], &current_best);
   sum_obj = avg_obj = oldpop[0].obj;
   max_obj = min_obj = oldpop[0].obj;
   for (k=0;  k < nvar_bin; k++) 
     maxx_bin[k] = minx_bin[k] = oldpop[0].xbin[k];
   for (k=0;  k < nvar_real; k++) 
     maxx_real[k] = minx_real[k] = oldpop[0].xreal[k];
   for(k=1; k < pop_size; k++)
     {
       if (current_best.penalty > oldpop[k].penalty) 
	 copy_individual(&oldpop[k], &current_best);
       else if ((current_best.penalty <= 0.0) && (oldpop[k].penalty <= 0.0))
	 if (MINM * current_best.obj  >  MINM * oldpop[k].obj)
	   copy_individual(&oldpop[k], &current_best);
     if(MINM * max_obj < MINM * oldpop[k].obj)
                   max_obj = oldpop[k].obj;
     if(MINM * min_obj > MINM * oldpop[k].obj)
                   min_obj = oldpop[k].obj;
     sum_obj += oldpop[k].obj;
     for (j=0; j < nvar_bin; j++)
     {
        if (MINM * maxx_bin[j] < MINM * oldpop[k].xbin[j]) maxx_bin[j] = oldpop[k].xbin[j];
        if (MINM * minx_bin[j] > MINM * oldpop[k].xbin[j]) minx_bin[j] = oldpop[k].xbin[j];
     }
     for (j=0; j < nvar_real; j++)
     {
        if (MINM * maxx_real[j] < MINM * oldpop[k].xreal[j]) maxx_real[j] = oldpop[k].xreal[j];
        if (MINM * minx_real[j] > MINM * oldpop[k].xreal[j]) minx_real[j] = oldpop[k].xreal[j];
     }
   }
   avg_obj = sum_obj/pop_size;
   change_flag = 0;
   if (best_ever.penalty > current_best.penalty) change_flag = 1;
   else if ((best_ever.penalty <= 0.0) && (current_best.penalty <= 0.0))
     if (MINM * best_ever.obj > MINM * current_best.obj)
       change_flag = 1;
   if (change_flag == 1)
     {
       copy_individual(&current_best, &best_ever);
       best_ever_gen = gen;
     }
   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 k,j,stop,tp,bitpos,mask=1,position,bits_per_var,count;
    double pow(), bitpow;

    if (nvar_bin <= 0) return;
    if (chrom == NULL) error_ptr_null("chrom in decodevalue");

    position = 0; count = 0;
    for(k = 0; k < chromsize; k++)
    {
        if(k == (chromsize-1))
            stop = lchrom-(k*UINTSIZE);
        else
            stop = UINTSIZE;
        /* loop thru bits in current byte */
        tp = chrom[k];
        for(j = 0; j < stop; j++) {
	  bits_per_var = chr_len[position];
	  bitpos = j + UINTSIZE*k;
            /* test for current bit 0 or 1 */
            if((tp&mask) == 1) {
	      // position = bitpos / bits_per_var;
              //  bitpos -= position * bits_per_var;
                bitpow = pow(2.0,(double)(count));
                value[position] += bitpow;
            }
            tp = tp>>1; count++;
	    if (count >= chr_len[position])
	      {
		position += 1;
		count = 0;
	      }
	    
	}
    }
}

/*====================================================================
GENERATION OF NEW POPULATION through SELECTION, XOVER & MUTATION :
====================================================================*/
generate_new_pop()
{
   int k,mate1,mate2;

   app_computation();

   preselect_tour();

   for (k=0; k < pop_size; k += 2)
   {
     // selection
     if (SHARING)
       {
	 mate1 = tour_select_constr(); 
	 mate2 = tour_select_constr();
       }
     else 
       {
	 mate1 = tour_select(); 
	 mate2 = tour_select();
       } 
     // crossover
     cross_over(mate1,mate2,k,k+1);
     // mutation
     mutation(&newpop[k]);
     mutation(&newpop[k+1]);
     newpop[k].parent1 = newpop[k+1].parent1 = mate1+1;
     newpop[k].parent2 = newpop[k+1].parent2 = mate2+1;
   }
}

/*====================================================================
Binary cross over routine.
====================================================================*/
binary_xover (parent1, parent2, child1, child2, x_site)
unsigned *parent1, *parent2, *child1, *child2;
int *x_site;
/* Cross 2 parent strings, place in 2 child strings */
{
    int j, jcross, k;
    unsigned mask, temp;

    if (nvar_bin <= 0) 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 ,(lchrom - 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];
            }
    }
    *x_site = jcross;
}
/*====================================================================
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,rand_var)
double p1,p2,*c1,*c2,low,high,*rand_var;
{
    double difference,x_mean,beta,v2,v1;
    double u,distance,umax,temp,alpha;
    int flag;

    if (c1 == NULL) error_ptr_null("c1 in create_children");
    if (c2 == NULL) error_ptr_null("c2 in create_children");
    if (rand_var == NULL) error_ptr_null("rand_var 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 ( (p1-low) < (high-p2) ) distance = p1-low;
    else                        distance = high-p2;
    if (distance < 0.0) distance = 0.0;
    if (RIGID && (difference > EPSILON))
    {
      alpha = 1.0 + (2.0*distance/difference);
      umax = 1.0 - (0.5 / pow((double)alpha,(double)(n_distribution_c+1.0)));
      *rand_var = umax * randomperc();
    }
    else *rand_var = randomperc();
    beta = get_beta(*rand_var);
    if (fabs(difference*beta) > INFINITY) beta = INFINITY/difference;
    v2 = x_mean + beta * 0.5 * difference;
    v1 = x_mean - beta * 0.5 * difference;

    if (v2 < low) v2 = low;
    if (v2 > high) v2 = high;
    if (v1 < low) v2 = low;
    if (v1 > high) v2 = high;
    *c2 = v2; *c1 = v1;
    //  if (flag == 1) { temp = *c1; *c1 = *c2; *c2 = temp; }

}

/*====================================================================
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(first,second,childno1,childno2)
int first,second,childno1,childno2;
{
    double difference,x_mean,beta;
    double u = 0.0;
    int site,k,x_s;

    x_s = 0;
    if (flip(p_xover))   /* Cross over has to be done */
    {
     no_xover++;
     if (nvar_bin > 0)
       {
	 binary_xover(oldpop[first].chrom,oldpop[second].chrom,
		      newpop[childno1].chrom,newpop[childno2].chrom,&x_s);
	 newpop[childno1].cross_var = newpop[childno2].cross_var = x_s;
       }
     if (nvar_real > 0)
       {
	 for (site = 0; site < nvar_real; site++)
	   {
	     if(flip(0.5) || (nvar_real == 1))
	       {
		 create_children(oldpop[first].xreal[site],oldpop[second].xreal[site],
		    &(newpop[childno1].xreal[site]),&(newpop[childno2].xreal[site]),
		     xreal_lower[site],xreal_upper[site],&u);
	       }
	     else
	       {
		 newpop[childno1].xreal[site] = oldpop[first].xreal[site];
		 newpop[childno2].xreal[site] = oldpop[second].xreal[site];
	       }
	   }               /* for loop */
	 if (nvar_bin == 0)
	   newpop[childno1].cross_var = newpop[childno2].cross_var = 0;
       }                /* if REALGA      */
    }                 /* Cross over done */
    
    else              /* Passing x-values straight */
    {
      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 < nvar_real; site++)
	{
	  newpop[childno1].xreal[site] = oldpop[first].xreal[site];
	  newpop[childno2].xreal[site] = oldpop[second].xreal[site];
	}
      for (site=0; site < nvar_bin; site++)
	{
	  newpop[childno1].xbin[site] = oldpop[first].xbin[site];
	  newpop[childno2].xbin[site] = oldpop[second].xbin[site];
	}
      newpop[childno1].cross_var = newpop[childno2].cross_var = 0;
    }
}

/*===================================================================
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, this results in uniform distribution of beta values in case
of BLX , and Binary Probability distribution simulation in case of
SBX.
====================================================================*/
double get_beta(u)
double u;
{
   double 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;
}
/*==================================================================
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().
====================================================================*/
double get_delta(u, delta_l, delta_u) 
     double u, delta_l, delta_u; 
{ 
  double 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 = %lf\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 (nvar_bin <= 0) return;
    if (child== NULL) error_ptr_null(" child in binmutation");
    for(k = 0; k < chromsize; k++)
    {
        mask = 0;
        if(k == (chromsize-1))
	  stop = lchrom - (k*UINTSIZE); 
        else
            stop = UINTSIZE;
        for(j = 0; j < stop; j++)
        {
            if(flip(p_mutation_bin))
            {
                mask = mask|(temp<<j);
		binmut++;
            }
        }
        child[k] = child[k]^mask;
    }