Preface

This is the start of the GAUL tutorial. It will explain and demonstrate how to use GAUL to develop your own programs with genetic or evolutionary algorithms.

For the purpose of this tutorial, it is assumed that the reader has a reasonable understanding of the C programming language. When alternative language wrappers for the GAUL library are made available, additional versions of this tutorial will be written to cover those.

It is also assumed that the reader already understands the basic principles of genetic algorithms. Genetic algorithms are briefly described on this page.

During this tutorial several GA-based programs are developed to perform particular tasks. These programs are intended to demonstrate various features of the the GAUL library, so they are rarely optimal solutions to their tasks. Consequently, you are encouraged to tweak the examples and experiment to improve on the solutions and to see how the various parameters interact. You may wish to refer to the accompaning reference guide while working through this tutorial.

A minimal program using GAUL

Below is a guide to producing a really simple GA-based program. This example doesn't make use of any of GAUL's more advanced features, but is intended to demonstrate the ease with which a minimal application may be created.

For reference, slightly extended source code for this example is distributed in the gaul-examples package as source-code. It may be found as struggle.c. The only difference between these codes is that the distributed example runs the GA procedure fifty times instead of just once.

Annotated source code

The public header file for the GAUL library is "gaul.h" and this must be included by any code that will use GAUL:

#include <gaul.h>

This public header file defines all of the GAUL specific functions and datatypes. The two most important datatypes, "entity" and "population", contain all the data required to handle the individuals in a population and that population itself. In GAUL, each population has a set of GA parameters, such as mutation rates. These datastructures are described further below. The term "entity" is synonymous with "individual" or "potential solution". These terms will be used interchangably during this tutorial.

In this example, we define the target solution in a global string:

char *target_text="When we reflect on this struggle, we
 may console ourselves with the full belief, that the war
 of nature is not incessant, that no fear is felt, that
 death is generally prompt, and that the vigorous, the
 healthy, and the happy survive and multiply.";

The first thing that is needed is the objective function, the code for determining the "fitness" of each potential solution. Objective functions are used to define the fitness landscape on which the GA search will occur. The term "objective function" is synonymous with the term "fitness function". For this example program the most appropriate form of chromosome is a single array of chars (a string). The objective function simply has to compare each character in an individual's chromosome with the corresponding character in the target string to derive the fitness score:

boolean struggle_score(population *pop, entity *entity)
  {
  int           k;              /* Loop variable over all alleles. */

  entity->fitness = 0.0;

  /* Loop over alleles in chromosome. */
  for (k = 0; k < pop->len_chromosomes; k++)
    {
    if ( ((char *)entity->chromosome[0])[k] == target_text[k])
      entity->fitness+=1.0;
    /*
     * Component to smooth function, which helps a lot in this case:
     * Comment it out if you like.
     */
    entity->fitness += (127.0-fabs(((char *)entity->chromosome[0])[k]
                                -target_text[k]))/50.0;
    }

  return TRUE;
  }

The objective function must return "TRUE" upon successful evaluation of the fitness, and "FALSE" otherwise. Cases for the later would include the attempted scoring of an invalid chromosome. This example function assumes that the chromosome is always valid. You will notice that the chromosome must be cast to the correct type - this is because the core routines in GAUL are totally independant of the actual datatypes. You will notice that GAUL actually uses an array of chromosomes, thus enabling efficient support for multiple chromosome descriptions of any problem.

The "entity" datastructure is used to store details about individual solutions.

The calculated fitness score is placed into the "fitness" field of the "entity" structure.

The "population" datastructure is used to store the global information about the solutions, including the GA parameters and so on.

The "population" structure contains several useful fields. Some particular fields that are likely to be of use in most applications are "len_chromosomes" (the user-defined length of each chromosome), "num_chromosomes" (the user-defined number of chromosomes per individual), and "size" (the total number of individuals in the population).

GAUL uses its own random number generator which must be initialised, either by calling "random_init()" or by calling "random_seed()". This is generally done at the start of any application using GAUL. We also need to define at least one population structure. In this example, we perform both of those tasks in the code's main function.

int main(int argc, char **argv)
  {
  population *pop=NULL;	/* The population of solutions. */

  random_seed(2003);	/* Random seed requires any integer parameter. */

Now we need to define the population and specify the prefered variant of genetic algorithm. GAUL provides a selection of high-level convenience wrappers to generate populations with default parameters. These are named "ga_genesis_XXX()", where XXX is the chromosome datatype. In this example, we will use "ga_genesis_char()", because we are using the character-array chromosome type.

The majority of parameters to these genesis functions are pointers to callback functions which are used to perform various portions of the GA algorithm. In this way it is trivial to use you own code to, say, mutate the chromosome using a new, or problem specific, routine. In this example, however, only GAUL's built-in functions are utilised.

It is perfectly valid to specific a different set of callback functions for each population that you define. This makes GAUL usable in applications that perform multiple, different, search or optimisation tasks. The parameters for the genesis functions will be described and illustrated throughout this tutorial.

    pop = ga_genesis_char(
       250,                      /* 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 */
       NULL,                     /* GAadapt                adapt */
       ga_select_one_sus,        /* GAselect_one           select_one */
       ga_select_two_sus,        /* 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_DARWIN,        /* const ga_class_type     class */
       GA_ELITISM_PARENTS_DIE,  /* const ga_elitism_type   elitism */
       0.9,                     /* double                  crossover */
       0.2,                     /* double                  mutation */
       0.0                      /* double                  migration */
                              );

The second and third parameters to "ga_population_set_parameters()" specify the type of GA variant to apply. These parameters are described, in some detail, later in this tutorial. The specific parameters used here cause GAUL to use a standard Darwinian GA with no elitism.

The final three parameters to "ga_population_set_parameters()" specify the crossover, mutation and migration ratios, respectively. The migration ratio is ignored in the GA simulation performed here, but is required for island-model GAs. The exact meaning of these ratios depends upon the particular operator functions, from above, that are being used.

This call to "ga_population_set_parameters()" could even be skipped, if you are happy with the default GA parameters defined within GAUL.

Now we can invoke the actual GA evolution routines:

    ga_evolution(
       pop,                     /* population              *pop */
       500                      /* const int               max_generations */
              );

The function "ga_evolution()" performs a standard generation-based GA. An alternative is "ga_evolution_steady_state()" which performs a standard steady-state GA. This example is modified for use with this steady-state GA in struggle_ss.c.

And finally, we deallocate the population structure, and are finished:

  printf( "The final solution found was:\n", i);
  printf( "%s\n", ga_chromosome_char_to_staticstring(pop, ga_get_entity_from_rank(pop,0)));
  printf( "Fitness score = %f\n", ga_get_entity_from_rank(pop,0)->fitness);

  ga_extinction(pop);	/* Deallocates all memory associated with
			 * the population and it's entities.
			 */

  exit(EXIT_SUCCESS);
  }

The "ga_get_entity_from_rank()" function may be used to extract particular solutions from the population structure. The ranks run from 0 to N-1, inclusive, where N is the current population size.

The return value of "ga_evolution()" is the number of generations actually performed.