ga_simplex.c

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

      {
      for (j=0; j<pop->len_chromosomes; j++)
        ((double *)putative[i]->chromosome[0])[j]
            = ((double *)putative[0]->chromosome[0])[j] +
              random_double_range(-pop->simplex_params->step,pop->simplex_params->step);

      pop->evaluate(pop, putative[i]);
      }
    }	/* End of parallel block. */

/*
 * Sort the initial solutions by fitness.
 * We use a bi-directional bubble sort algorithm (which is
 * called shuffle sort, apparently).
 */ 
  last = pop->len_chromosomes-1;
  while (done == FALSE && first < last)
    {
    for (j = last ; j > first ; j--)
      {
      if ( putative[j]->fitness > putative[j-1]->fitness )
        {	/* Swap! */
        tmpentity = putative[j];
        putative[j] = putative[j-1];
        putative[j-1] = tmpentity;
        }
      }
    first++;    /* The first one is definitely correct now. */

    done = TRUE;

    for (j = first ; j < last ; j++)
      {
      if ( putative[j]->fitness < putative[j+1]->fitness )
        {	/* Swap! */
        tmpentity = putative[j];
        putative[j] = putative[j+1];
        putative[j+1] = tmpentity;
        done = FALSE;
        }
      }
    last--;     /* The last one is definitely correct now. */
    }

  plog( LOG_VERBOSE,
        "Prior to the first iteration, the current solution has fitness score of %f",
         putative[0]->fitness );

/*
 * Do all the iterations:
 *
 * Stop when (a) max_iterations reached, or
 *           (b) "pop->iteration_hook" returns FALSE.
 */
  while ( (pop->iteration_hook?pop->iteration_hook(iteration, putative[0]):TRUE) &&
           iteration<max_iterations )
    {
    iteration++;

/*
 * Compute the vector average of all solutions except the least fit.
 * Exploration will proceed along the vector from the least fit point
 * to that vector average.
 */
    for (j = 0; j < pop->len_chromosomes; j++)
      {
      average[j] = 0.0;

      for (i = 0; i < num_points-1; i++)
        average[j] += ((double *)putative[i]->chromosome[0])[j];

      average[j] /= num_points-1;
      }

/*
 * Check for convergence and restart if needed.
 * Reduce step, alpha, beta and gamma each time this happens.
 */
    restart_needed = TRUE;
/*printf("DEBUG: average = ");*/

    for (j = 0; j < pop->len_chromosomes; j++)
      {
      if ( average[j]-TINY > ((double *)putative[pop->len_chromosomes]->chromosome[0])[j] ||
           average[j]+TINY < ((double *)putative[pop->len_chromosomes]->chromosome[0])[j] )
        restart_needed = FALSE;
      
      /*printf("%f ", average[j]/pop->len_chromosomes);*/
      }
/*printf("\n");*/

  if (restart_needed != FALSE)
    {
/*printf("DEBUG: restarting search.\n");*/
    pop->simplex_params->step *= 0.50;
    pop->simplex_params->alpha *= 0.75;
    pop->simplex_params->beta *= 0.75;
    pop->simplex_params->gamma *= 0.75;

    for (i=1; i<num_points; i++)
      {
      for (j=0; j<pop->len_chromosomes; j++)
        ((double *)putative[i]->chromosome[0])[j]
           = ((double *)putative[0]->chromosome[0])[j] +
              random_double_range(-pop->simplex_params->step,pop->simplex_params->step);

      pop->evaluate(pop, putative[i]);
      }
    }

/*
 * Simplex reflection - Extrapolate by a factor alpha away from worst point.
 */
   for (j = 0; j < pop->len_chromosomes; j++)
     ((double *)new1->chromosome[0])[j]
         = (1.0 + pop->simplex_params->alpha) * average[j] -
           pop->simplex_params->alpha * ((double *)putative[num_points-1]->chromosome[0])[j];

/*
 * Evaluate the function at this reflected point.  
 */
    pop->evaluate(pop, new1);

    if (new1->fitness > putative[0]->fitness)
      {
/*
 * The new solution is fitter than the previously fittest solution, so attempt an 
 * additional extrapolation by a factor alpha.
 */
/*printf("DEBUG: new1 (%f) is fitter than p0 ( %f )\n", new1->fitness, putative[0]->fitness);*/

      for (j = 0; j < pop->len_chromosomes; j++)
        ((double *)new2->chromosome[0])[j]
            = (1.0 + pop->simplex_params->alpha) * ((double *)new1->chromosome[0])[j] -
              pop->simplex_params->alpha * ((double *)putative[num_points-1]->chromosome[0])[j];

      pop->evaluate(pop, new2);

      if (new2->fitness > putative[0]->fitness)
        {
/*
 * This additional extrapolation succeeded, so replace the least fit solution
 * by inserting new solution in correct position.
 */
/*printf("DEBUG: new2 (%f) is fitter than p0 ( %f )\n", new2->fitness, putative[0]->fitness);*/

        tmpentity = putative[pop->len_chromosomes];

        for (j = pop->len_chromosomes; j > 0; j--)
          putative[j]=putative[j-1];

        putative[0] = new2;

        new2 = tmpentity;
        }
      else
        {
/*
 * This additional extrapolation failed, so use the original
 * reflected solution.
 */
        tmpentity = putative[pop->len_chromosomes];

        for (j = pop->len_chromosomes; j > 0; j--)
          {
          putative[j]=putative[j-1];
          }

        putative[0] = new1;

        new1 = tmpentity;
        }
      }
    else if (new1->fitness < putative[pop->len_chromosomes-1]->fitness)
      {
/*
 * The reflected point is worse than the second-least fit.  
 */
/*printf("DEBUG: new1 (%f) is less fit than p(n-1) ( %f )\n", new1->fitness, putative[pop->len_chromosomes-1]->fitness);*/

      did_replace = FALSE;

      if (new1->fitness > putative[pop->len_chromosomes]->fitness)
        {
/*
 * It is better than the least fit, so use it to replace the
 * least fit.
 */
/*printf("DEBUG: but fitter than p(n) ( %f )\n", putative[pop->len_chromosomes]->fitness);*/

        did_replace = TRUE;

        tmpentity = putative[pop->len_chromosomes];

        putative[pop->len_chromosomes] = new1;

        new1 = tmpentity;
        }
/*
 * Perform a contraction of the simplex along one dimension, away from worst point.
 */
      for (j = 0; j < pop->len_chromosomes; j++)
        ((double *)new1->chromosome[0])[j]
                = (1.0 - pop->simplex_params->beta) * average[j] +
                  pop->simplex_params->beta * ((double *)putative[num_points-1]->chromosome[0])[j];

      pop->evaluate(pop, new1);

      if (new1->fitness > putative[pop->len_chromosomes]->fitness)
        {
/*
 * The contraction gave an improvement, so accept it by
 * inserting the new solution at the correct position.
 */
        did_replace = TRUE;

/*printf("DEBUG: contracted new1 (%f) is fitter than p(n) ( %f )\n", new1->fitness, putative[pop->len_chromosomes]->fitness);*/

        i = 0;
        while (putative[i]->fitness > new1->fitness) i++;

        tmpentity = putative[pop->len_chromosomes];

        for (j = pop->len_chromosomes; j > i; j--)
          putative[j]=putative[j-1];

        putative[i] = new1;

        new1 = tmpentity;
        }

      if (did_replace == FALSE)
        {
/*
 * The new solution is worse than the previous worse.  So, contract
 * toward the average point.
 */
/*printf("DEBUG: new1 (%f) is worse than all.\n", new1->fitness);*/

        for (i = 1; i < num_points; i++)
          {
          for (j = 0; j < pop->len_chromosomes; j++)
            ((double *)putative[i]->chromosome[0])[j]
                = average[j] +
                  pop->simplex_params->gamma
                    * (((double *)putative[i]->chromosome[0])[j] - average[j]);

          pop->evaluate(pop, putative[i]);
          }

/*
 * Alternative is to contact toward the most fit point.
        for (i = 1; i < num_points; i++)
          {
          for (j = 0; j < pop->len_chromosomes; j++)
            ((double *)putative[i]->chromosome[0])[j]
                = ((double *)putative[0]->chromosome[0])[j] +
                  pop->simplex_params->gamma
                    * (((double *)putative[i]->chromosome[0])[j] - ((double *)putative[0]->chromosome[0])[j]);

          pop->evaluate(pop, putative[i]);
          }
*/

        }

      }
    else
      {
/*
 * The reflection gave a solution which was better than the worst two
 * solutions, but worse than the best solution.
 * Replace the old worst solution by inserting the new solution at the
 * correct position.
 */
/*printf("DEBUG: new1 (%f) is fitter than worst 2\n", new1->fitness);
      for (j=0; j < pop->len_chromosomes; j++)
        printf("%d fitness = %f\n", j, putative[j]->fitness);
*/

      i = 0;
      while (putative[i]->fitness > new1->fitness) i++;

/*printf("DEBUG: new1 inserted at position %d\n", i);*/

      tmpentity = putative[pop->len_chromosomes];

      for (j = pop->len_chromosomes; j > i; j--)
        putative[j]=putative[j-1];

      putative[i] = new1;

      new1 = tmpentity;
      }

/*
 * Use the iteration callback.
 */
    plog( LOG_VERBOSE,
          "After iteration %d, the current solution has fitness score of %f",
          iteration,
          putative[0]->fitness );

    }	/* Iteration loop. */

/*
 * Store best solution.
 */
  ga_entity_copy(pop, initial, putative[0]);

/*
 * Cleanup.
 */
  ga_entity_dereference(pop, new1);
  ga_entity_dereference(pop, new2);

  for (i=0; i<num_points; i++)
    {
    ga_entity_dereference(pop, putative[i]);
    }

  s_free(putative);

  return iteration;
  }