Terminating the evolution

By default, GAUL terminates a simulation when a specified number of generations have occured. You might wish to stop optimisation once the population has converged or when a particular fitness threshold has been exceeded.

Here we further adapt the earlier example program struggle.c to demonstrate the use of user-defined stopping criteria. We also take this opportunity to collate some basic statistics about the optimisation.

For reference, the full source code for this section is struggle3.c.

Off-line statistics

The off-line performance of function optimisation depends upon some final measure of the best solution or set of solutions, irrespective of intermediate values. For example, the off-line performance might be defined as the average fitness of the final population, or might just be the fitness of the single best solution located.

On-line statistics

The on-line performance is dependent on every trial, or fitness evaluation, during the optimisation (or evolution). For example, it might be the proportion of all solutions generated in all generations with fitness scores above some threshold value, or it might be the average fitness of every solution from every generation.

Example implementation

Again, we reuse the same objective function from struggle.c. In this example we only apply the Lamarkian GA.

An additional function that GAUL calls at the beginning of each generation is defined. If at any point this function gives a return value of "FALSE" then the GA routine will be terminated. This is useful for preventing further calculations once a predetermined level of convergence has been obtained, or if your perfect solution has been found.

It is typically up to the programmer to collect the relevent statistics for a given problem, but GAUL does provide some utility functions for the most commonly required statistics.

Although not demonstrated in this example, an additional and very powerful feature is that the programmer is able to change the GA parameters within this routine. For example, using "ga_population_set_parameters()" the mutation ratio may be increased if the population begins to converge. In one of the author's applications, it was found to be highly advantageous to drastically reduce the population size after the first few generations.

Our additional function is:

boolean struggle_generation_hook(int generation, population *pop)
  {
  static double total_best_fitnesses=0.0;       /* Sum of best fitness score at each generation. */
  double        average, stddev;        /* Simple stats. */

  total_best_fitnesses += ga_get_entity_from_rank(pop,0)->fitness;

/*
 * Display statistics every 20th generation.
 */
  if (generation%20 == 0)
    {
    printf("Generation = %d\n", generation);
    printf("Number of evaluations = %ld\n", evaluation_count);
    printf("Best fitness = %f\n", ga_get_entity_from_rank(pop,0)->fitness);
    ga_fitness_mean_stddev(pop, &average, &stddev);
    printf("Mean fitness = %f, with standard deviation = %f\n", average, stddev);
    if (generation>0)
    printf("Average best fitness for entire run = %f\n", total_best_fitnesses/generation);
    }

/*
 * Stop if we have the exact solution.
 */
  if (!strncmp(target_text,
          (char *)ga_get_entity_from_rank(pop,0)->chromosome[0],
             strlen(target_text)))
    {
    printf("Exact solution has been found!\n");
    return FALSE;
    }

/*
 * Stop if the population has converged.
 */
    if (!strncmp((char *)ga_get_entity_from_rank(pop,0)->chromosome[0],
            (char *)ga_get_entity_from_rank(pop,pop->size-1)->chromosome[0],
               strlen(target_text)))
    {
    printf("Solutions have converged!\n");
    return FALSE;
    }

  return TRUE;  /* TRUE indicates that evolution should continue. */
  }

In the above code fragment, two stopping criteria are defined; the exact location of the correct solution, and premature convergence of the set of solutions (which is highly unlikely in this actual example). Some simple statistics about the current population are also written every 20th generation.

Our new "main()" function is:

int main(int argc, char **argv)
  {
  population    *pop=NULL;               /* Population structure. */
  char          *beststring=NULL;        /* Human readable form of best solution. */
  size_t        beststrlen=0;            /* Length of beststring. */

  random_seed(23091975);

  pop = ga_genesis_char(
     80,                                 /* const int              population_size */
     1,                                  /* const int              num_chromo */
     strlen(target_text),                /* const int              len_chromo */
     NULL,                               /* GAgeneration_hook      generation_hook */
     NULL,                               /* GAiteration_hook       iteration_hook */
     NULL,                               /* GAdata_destructor      data_destructor */
     NULL,                               /* GAdata_ref_incrementor data_ref_incrementor */
     struggle_score,                     /* GAevaluate             evaluate */
     ga_seed_printable_random,           /* GAseed                 seed */
     struggle_adaptation,                /* GAadapt                adapt */
     ga_select_one_roulette,             /* GAselect_one           select_one */
     ga_select_two_roulette,             /* GAselect_two           select_two */
     ga_mutate_printable_singlepoint_drift, /* GAmutate            mutate */
     ga_crossover_char_allele_mixing,    /* GAcrossover            crossover */
     NULL,                               /* GAreplace              replace */
     NULL                                /* void *                 userdata */
           );

  ga_population_set_parameters(
      pop,                               /* population             *pop */
      GA_SCHEME_LAMARCK_CHILDREN,        /* const ga_scheme_type   scheme */
      GA_ELITISM_PARENTS_SURVIVE,        /* const ga_elitism_type  elitism */
      0.8,                               /* const double           crossover */
      0.05,                              /* const double           mutation */
      0.0                                /* const double           migration */
           );

  if ( ga_evolution( pop, 1000 )<1000 )
    {
    printf( "The evolution was stopped because the termination criteria were met.\n" );
    }
  else
    {
    printf( "The evolution was stopped because the maximum number of generations were performed.\n" );
    }

  printf( "The final solution with score %f was:\n",
          ga_get_entity_from_rank(pop,0)->fitness );
  beststring = ga_chromosome_char_to_string(pop, ga_get_entity_from_rank(pop,0), beststring, &beststrlen);
  printf( "%s\n", beststring );
  printf( "Total number of fitness evaluations: %ld\n", evaluation_count );

  ga_extinction(pop);

  s_free(beststring);

  exit(EXIT_SUCCESS);
  }