TEACH GA
                                              Riccardo Poli Nov 1995


 How to use LIB GA - The simple library to run Genetic Algorithms
 (Note: this is a very preliminary, incomplete version.)

         CONTENTS - (Use <ENTER> g to access required sections)

 -- Introduction
 -- A simple genetic algorithm
 -- A simple problem
 -- Preparing to use genetic algorithms
 -- Using LIB GA to solve the problem
 -- Note
 -- Further reading


-- Introduction -----------------------------------------------------

Genetic   algorithms  (GAs)  are optimisation  and   search procedures
inspired by genetics and the process of natural selection.

In order  to do so in GAs  the following nature-to-computer mapping is
used:

  +-----------------------+--------------------------------------+
  !       Nature          !           Computer                   !
  +-----------------------+--------------------------------------+
  ! Individual            !    Solution to a problem             !
  !                       !                                      !
  ! Population            !    Set of solutions                  !
  !                       !                                      !
  ! Fitness               !    Quality of a solution             !
  !                       !                                      !
  ! Chromosome            !    Representation for a solution     !
  !                       !    (e.g. set of parameters)          !
  !                       !                                      !
  ! Gene                  !    Part of the representation of     !
  !                       !    a solution (e.g. parameter)       !
  !                       !                                      !
  ! Growth                !    Decoding of the representation of !
  !                       !    solutions                         !
  !                       !                                      !
  ! Crossover or          !    Main search operator              !
  ! recombination         !                                      !
  !                       !                                      !
  ! Mutation              !    Secondary search operator         !
  !                       !                                      !
  ! Natural Selection     !    Reuse of good (sub-)solutions     !
  +-----------------------+--------------------------------------+

In GAs there is  a strong distinction  between adult individuals (i.e.
solutions) and chromosomes (i.e.  representations for the solutions).

Chromosomes are strings of symbols (e.g.  0s and 1s).

Adult individuals can be  anything  as  long  as  there  is a way   of
encoding/decoding them   using  a  string of  symbols   (chromosomes).
Examples are vectors of parameters or lists of choices.

As  GAs (like nature) act   on genotypes only, a genotype-to-phenotype
decoding process is required ("generalised" growth).

-- A simple genetic algorithm ----------------------------------------

A typical GA includes the following steps:


 1.  Randomly generate a population of chromosomes

 2.  DECODE each  chromosome to get an individual

 3.  EVALUATE the fitness of each individual    

 4.  Generate a new population partly by CLONING (copying), partly by
     RECOMBINING and partly by MUTATING the chromosomes of the
     fittest individuals

 5.  Repeat steps 2, 3 and 4 until a stop condition is true.


Note: Cloning is  used to  simulate the  survival of  parents for more
than one generation.

-- A simple problem --------------------------------------------------

Let us   start with a  simple  example. 

The   problem is  to find the    number in {0,1,...,255}  whose binary
representation has  the maximum number    of 0-to-1 transitions.   

The solution to this problem  is quite easy to  find for us, it is  85
(01010101) which has  7 transitions. However, it  is not  easy to find
with a computer if not  by using brute  force (the domain is discrete,
so we cannot use most of the methods from numerical analysis).

-- Preparing to use genetic algorithms -------------------------------

There are some decisions to be made   before starting the GA.

REPRESENTATION: First  we need to decide how  many bits  to use in our
chromosomes.  We can use chromosomes with eight bits (byte), which are
are sufficient to represent any value in {0,1,...,255}.

DECODING: As we want the solution as a decimal  number, we will decode
our solutions by using the normal binary to decimal conversion.

FITNESS:  The  quality  of  our adult   individuals  (decimal numbers)
depends  on  the  the number   of  0/1  transitions  in their   binary
representation. Our  fitness function will have  to transform back the
adult individuals into   binary form and count  the  transitions.  (Of
course, for this   particular problem we  can   increase efficiency by
avoiding  to  convert the  chromosomes in  decimal  form  in the first
place.)

POPULATION: Given the extreme simplicity of  the problem we use a very
small population of 10 individuals.

SELECTION: We will select  individuals for reproduction and cloning on
with a probability proportional to their fitness.

CLONING: 30% of the selected  individuals will be just copied. 

RECOMBINATION: We  will  apply recombination to   70% of  the selected
strings. To recombine two strings we cut them at a random position and
swap their left hand sides.

MUTATION:  We flip   random bits  of  the  chromosome with a  very low
probability.

-- Using LIB GA to solve the problem ---------------------------------

In order to run this example we have to load the GA library with

   lib ga;

then we have to define an appropriate  fitness function which receives
as  argument  a  chromosome  and returns  the  fitness  of   the adult
individual  represented by   such chromosome (the   decoding phase, if
necessary, will have to take place inside the fitness function).

Here is a procedure that  evaluates the number  of 0/1 transitions  in
the bit string of a chromosome and stores it.

  define test_fitness_function( chrom );
      lvars chorm, bit_str = bit_string(chrom), fit = 0, counter;

      for counter from 2 to bit_number(chrom) do
          if ( bit_str(counter-1) /= bit_str(counter) ) then
             fit + 1 -> fit;
          endif;
      endfor;
      fit -> fitness(chrom);
  enddefine;


It  is possible to  check  whether the function  performs  the correct
computation by creating a chromosome using the procedure

   conschromosome( <fitness>, <bit vector>, <length> )

and then running test_fitness_function on it. E.g.

   vars c = conschromosome( undef, { 1 0 1 0 }, 4 );
   test_fitness_function( c );
   fitness(c) ==>

Once the fitness function is defined we can run the procedure

  genetic_algorithm( <fitness function name>, <population size>, <bits>,
                <generations>, <recombination probability>, 
                <mutation probability>,  0, false, 
                <print generation stats>, undef )

which will return the best individual found.   E.g. the following code
will  run  a GA with  the characteristics  outlined above,  print some
statistics  for each generation (average  fitness, best fitness, etc.)
and return the best individual in the variable "best".

   vars best = genetic_algorithm( "test_fitness_function", 30, 8, 50, 
                                0.7, 0.01, 0, false, true, undef );
   bit_string(best) ==>
   fitness(best) ==>


-- Note ----------------------------------------------------------------

Normally  genetic_algorithm() will save the  population on disk every
ten generations. You can prevent this by enclosing <population size>
inside a list before passing it to genetic_algorithm(). E.g. 

   genetic_algorithm( "test_fitness_function", [30], ....)

It is also  possible  to restart a run   saved on disk by passing  the
corresponding  filename (a string)  instead of a number  or a list (in
<population size>).

-- Further reading ---------------------------------------------------

 SHOWLIB * GA
    The source code of the library

 TEACH * GA_DEJONG.p
    The source code of a small set of more interesting examples
    on how to use LIB GA for function optimisation (minimisation or
    maximisation) 

--- $poplocal/local/teach/ga
--- The University of Birmingham 1995.  --------------------------------

