sga.c

由我收集或写出的GA源码

   printf("\n Program is halting .....");
   exit(-1);
}
/*====================================================================
Copys contents of one individual into another.
====================================================================*/
copy_individual(indiv1,indiv2)
INDIVIDUAL *indiv1, *indiv2;
{
   int k;

   if (indiv1==NULL) error_ptr_null("indiv1 in copy_individual");
   if (indiv2==NULL) error_ptr_null("indiv2 in copy_individual");
   for (k=0; k<= MAXVECSIZE-1; k++)
      indiv2->x[k] = indiv1->x[k];
   indiv2->mod_obj = indiv1->mod_obj;
   indiv2->obj = indiv1->obj;
   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;
   float f;
   double pow(),bitpow,coef,temp[MAXVECSIZE];

   for (k=0; k<=pop_size-1; k++)
   {
     decode_string(&oldpop[k]);
     oldpop[k].obj = objective(oldpop[k].x);

     if (SHARING)
        oldpop[k].mod_obj = degraded_value(oldpop[k].obj,oldpop[k].x,oldpop);
     else oldpop[k].mod_obj = oldpop[k].obj;
   }
   if ( gen == 0)
   {
     if (SHARING)
        best_ever.mod_obj = degraded_value(best_ever.obj,best_ever.x,oldpop);
     else best_ever.mod_obj = best_ever.obj;
   }

   current_best = oldpop[0];
   sum_obj = avg_obj = oldpop[0].obj;
   max_obj = min_obj = oldpop[0].obj;
   for (k=0;  k<= num_var-1 ; k++) maxx[k] = minx[k] = oldpop[0].x[k];

   for(k=1; k<= pop_size-1; k++)
   {
     if(MINM * current_best.obj  >  MINM * oldpop[k].obj)
                   current_best = oldpop[k];
     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<= num_var-1; j++)
     {
        if (MINM * maxx[j] < MINM * oldpop[k].x[j]) maxx[j] = oldpop[k].x[j];
        if (MINM * minx[j] > MINM * oldpop[k].x[j]) minx[j] = oldpop[k].x[j];
     }
   };
   avg_obj = sum_obj/pop_size;
   if (MINM * current_best.obj < MINM * best_ever.obj)
   { 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;
    double pow(), bitpow;

    if (BINGA == FALSE) return;
    if (chrom == NULL) error_ptr_null("chrom in decodevalue");

    bits_per_var = lchrom/num_discr_var;
    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++) {
            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)(bits_per_var- bitpos-1));
                value[position] += bitpow;
            }
            tp = tp>>1;
        }
    }
}
/*====================================================================
DEGRADED VALUE (DUE TO SHARING) OF ACUTAL OBJECTIVE FUNCTION VALUE :
====================================================================*/
float degraded_value(f,x,pop)
float f, x[];
POPULATION pop;
{
   int k,j;
   float summation,dist,dist_sq;

   if (pop == NULL) error_ptr_null("pop in degraded_value");
   if (x ==NULL) error_ptr_null("x in degraded_value");
   summation = 0;
   for (k=0; k<= pop_size-1; k++)
   {
      dist_sq = 0;
      for (j=0; j<= num_var-1; j++)
         dist_sq += (x[j] - pop[k].x[j]) * (x[j] - pop[k].x[j]) ;
      dist = sqrt(dist_sq);
      if (dist <= sigma_share) summation += 1.0 - dist/sigma_share;
   }
   if (summation < 1.0) summation = 1.0;
   return (f/summation);
}

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

   app_computation();
   switch (s_strategy)
     {
     case 1 : preselect_tour(); break;
     case 2 : preselect_rw(); break;
     case 3 : preselect_sr(); break;
     }
   for (k=0; k<= pop_size-1; k +=2)
   {
     switch (s_strategy)
     {
     case 1 :  mate1 = tour_select(); mate2 = tour_select(); break;
     case 2 :  mate1 = rw_select(); mate2 = rw_select(); break;
     case 3 :  mate1 = sr_select(); mate2 = sr_select(); break;
     }
     switch( x_strategy)
     {
       case ONESITE :  cross_over_1_site(mate1,mate2,k,k+1); break;
       case UNIF :  cross_over_unif(mate1,mate2,k,k+1); break;
       case ONLINE: cross_over_line(mate1,mate2,k,k+1); break;
     }
     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)
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 ,(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];
            }
    }
}
/*====================================================================
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)
float p1,p2,*c1,*c2,low,high,*rand_var;
{
    float difference,x_mean,beta;
    float 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;
    *c2 = x_mean + beta * 0.5 * difference;
    *c1 = x_mean - beta * 0.5 * difference;
    if (flag == 1) { temp = *c1; *c1 = *c2; *c2 = temp; }
}
/*====================================================================
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;
{
    int k,site;
    float u;

    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);
      if ( REALGA )
      {
        site = rnd(num_discr_var,num_var-1);
        for (k=0; k<=site-1; k++)
        {
          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++)
        {
          newpop[childno2].x[k] = oldpop[first].x[k];
          newpop[childno1].x[k] = oldpop[second].x[k];
        }
        create_children(oldpop[first].x[site],oldpop[second].x[site],
                      &(newpop[childno1].x[site]),&(newpop[childno2].x[site]),
                      x_lower[site],x_upper[site],&u);
        newpop[childno1].cross_var = newpop[childno2].cross_var = u;
      }

    }                 /* 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;
    float u = 0.0;
    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);
     if (REALGA)
     {
      for (site = num_discr_var; site<=num_var-1; site++)
      {
       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],&u);
       }
       else
       {
        newpop[childno1].x[site] = oldpop[first].x[site];
        newpop[childno2].x[site] = oldpop[second].x[site];
       }
      }               /* for loop */
     newpop[childno1].cross_var = newpop[childno2].cross_var = u;
     }                /* if REALGA      */
    }                 /* 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];
      }
    }
}
/*====================================================================
CROSS - OVER strategy  ON A STRAIGHT LINE
  A random beta is generated and used to decide all the design
  variables for children. The effect is that offsprings are generated
  on a straight line joining the parents.
====================================================================*/
cross_over_line(first,second,childno1,childno2)
int first,second,childno1,childno2;
{
    float difference,x_mean,beta;
    float u,distance,dist1,dist2,alpha,min_alpha,umax;
    float p1,p2,temp;
    int site,k;

    if (flip(p_xover))   /* Cross over has to be done */
    {
     if (RIGID)
     {
        min_alpha = INFINITY;
        for (site=0; site <= num_var-1; site++)
        {
                p1 = oldpop[first].x[site];
                p2 = oldpop[second].x[site];
                if ( p1 > p2) {  temp = p1; p1 = p2; p2 = temp; }
                difference = p2 -p1;
                dist1 = p1 - x_lower[site] ;
                dist2 = x_upper[site] - p2;
                if (dist1 < dist2) distance = dist1; else distance = dist2;
                if (distance < 0.0) distance = 0.0;
                if (difference > EPSILON)
                {
                        alpha = 1.0 + (2.0*distance/difference);
                        if (min_alpha > alpha) min_alpha = alpha;
                }
        }
        if ( min_alpha < 0.0) min_alpha = 0.0;
        umax = 1.0- (0.5/pow((double)min_alpha,(double)(n_distribution_c+1.0)));
        u = umax * randomperc();
     }
     else u = randomperc();
     beta = get_beta(u);
     no_xover++;
     if (BINGA)
     binary_xover(oldpop[first].chrom,oldpop[second].chrom,
                  newpop[childno1].chrom,newpop[childno2].chrom);
     newpop[childno1].cross_var = newpop[childno2].cross_var = u;
     if (REALGA)
     {
       for (site = 0; site<=num_var-1; site++)
       {
         x_mean = (oldpop[first].x[site] + oldpop[second].x[site]) * 0.5;
         difference = oldpop[second].x[site] - oldpop[first].x[site];
         if (fabs(difference*beta) > INFINITY) beta = INFINITY/difference;
         newpop[childno1].x[site] = x_mean + beta * 0.5 * difference;
         newpop[childno2].x[site] = x_mean - beta * 0.5 * difference;
       }              /* for loop */
     }                /* if REALGA*/
    }                 /* Cross over done */

    else              /* Passing x-values straight */
    {