ga_de.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

            ((double *)tmpentity->chromosome[0])[n] =
              ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
              + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);

            for (L=1; L<pop->len_chromosomes; L++)
              {
              if ( random_boolean() )
                ((double *)tmpentity->chromosome[0])[n] =
                  ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                  + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                    + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                    - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                    - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              }

            }
          else if (pop->de_params->num_perturbed == 3)
            { /* DE/rand/3/bin */
            _gaul_pick_random_entities(permutation, 7, pop->orig_size, i);

            ((double *)tmpentity->chromosome[0])[n] =
              ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
              + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);

            for (L=1; L<pop->len_chromosomes; L++)
              {
              if ( random_boolean() )
                ((double *)tmpentity->chromosome[0])[n] =
                  ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                  + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                    + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                    + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                    - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
                                    - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
                                    - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              }

            }
          else
            {
            die("Invalid differential evolution selection number.");
            }
          }
        else if (pop->de_params->strategy == GA_DE_STRATEGY_RANDTOBEST)
          {
          if (pop->de_params->num_perturbed == 1)
            { /* DE/rand-to-best/1/bin */
            _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);

            ((double *)tmpentity->chromosome[0])[n] +=
              weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                              - ((double *)tmpentity->chromosome[0])[n]
                              + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                              - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);

            for (L=1; L<pop->len_chromosomes; L++)
              {
              if ( random_boolean() )
                ((double *)tmpentity->chromosome[0])[n] +=
                  weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                                  - ((double *)tmpentity->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              }

            }
          else if (pop->de_params->num_perturbed == 2)
            { /* DE/rand-to-best/2/bin */
            _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);

            ((double *)tmpentity->chromosome[0])[n] +=
              weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                              - ((double *)tmpentity->chromosome[0])[n]
                              + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                              + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                              - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                              - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);

            for (L=1; L<pop->len_chromosomes; L++)
              {
              if ( random_boolean() )
                ((double *)tmpentity->chromosome[0])[n] +=
                  weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                                  - ((double *)tmpentity->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              }

            }
          else
            {
            die("Invalid differential evolution selection number.");
            }
          }
        else
          {
          die("Unknown differential evolution strategy.");
          }
        
        }
      else
        { /* pop->de_params->crossover_method == GA_DE_CROSSOVER_EXPONENTIAL */
        if (pop->de_params->strategy == GA_DE_STRATEGY_BEST)
          {
          if (pop->de_params->num_perturbed == 1)
            { /* DE/best/1/exp */

            _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[best]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else if (pop->de_params->num_perturbed == 2)
            { /* DE/best/2/exp */

            _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[best]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
            }
          else if (pop->de_params->num_perturbed == 3)
            { /* DE/best/3/exp */

            _gaul_pick_random_entities(permutation, 6, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[best]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
            }
          else
            {
            die("Invalid differential evolution selection number.");
            }
          
          }
        else if (pop->de_params->strategy == GA_DE_STRATEGY_RAND)
          {
          if (pop->de_params->num_perturbed == 1)
            { /* DE/rand/1/exp (DE1) */

            _gaul_pick_random_entities(permutation, 3, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else if (pop->de_params->num_perturbed == 2)
            { /* DE/rand/2/exp */

            _gaul_pick_random_entities(permutation, 5, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else if (pop->de_params->num_perturbed == 3)
            { /* DE/rand/3/exp */

            _gaul_pick_random_entities(permutation, 7, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] =
                ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                  + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
                                  - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else
            {
            die("Invalid differential evolution selection number.");
            }

          }
        else if (pop->de_params->strategy == GA_DE_STRATEGY_RANDTOBEST)
          {
          if (pop->de_params->num_perturbed == 1)
            { /* DE/rand-to-best/1/exp */

            _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] +=
                weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                                - ((double *)tmpentity->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else if (pop->de_params->num_perturbed == 2)
            { /* DE/rand-to-best/2/exp */

            _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);

            L = 0;
            do
              {
              ((double *)tmpentity->chromosome[0])[n] +=
                weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
                                - ((double *)tmpentity->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
                                + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
                                - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);

              n = (n+1)%pop->len_chromosomes;
              L++;
              } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));

            }
          else
            {
            die("Invalid differential evolution selection number.");
            }

          }
        else
          {
          die("Unknown differential evolution strategy.");
          }

        }

/*
 * Evaluate new solution and restore the former chromosome values
 * if this new solution is not an improvement.
 */
      if ( !pop->evaluate(pop, tmpentity) ||
         ( pop->rank == ga_rank_fitness && pop->entity_iarray[i]->fitness > tmpentity->fitness ) ||
         ( pop->rank != ga_rank_fitness && pop->rank(pop, tmpentity, pop, pop->entity_iarray[i]) < 0 ) )
        {
/*printf("DEBUG: old = %f > new = %f\n", pop->entity_iarray[i]->fitness, tmpentity->fitness);*/
        ga_entity_blank(pop, tmpentity);
        ga_entity_copy(pop, tmpentity, pop->entity_iarray[i]);
        }

      }

/*
 * Eliminate the original population members.
 */
    while (pop->orig_size > 0)
      {
      pop->orig_size--;
      ga_entity_dereference_by_rank(pop, pop->orig_size);
      }

/*
 * End of generation.
 */
    plog(LOG_VERBOSE,
          "After generation %d, population has fitness scores between %f and %f",
          generation,
          pop->entity_iarray[0]->fitness,
          pop->entity_iarray[pop->size-1]->fitness );

    }	/* Generation loop. */

/*
 * Ensure final ordering of population is correct.
 */
  sort_population(pop);

  return generation;
  }