Genetic Algorithms

Genetic Algorithms (GA)

The first model of adaptation-processes based on Genetic Algorithms was by J.H. Holland in his 1975 book: Adaptation in Natural and Artificial Systems. Adaptation is regarded a process of progressive variation of structures, leading to an improved performance for interaction with an environment.
Hollands motivation, defining the Genetic Algorithms, was to model and implement robust and adaptive systems simulating the evolution of genetic structures found in organisms.

The Genetics Algorithms propagated by Goldberg reduced the data-structure used for representing the genetic structure to bitstrings. Nowadays this is considered to be one of the main-characteristics of Genetic Algorithms. Goldberg used bitstrings as he could show that the number of schemata for a specific code gets maximal for binary codes.

datastructure - GA-Chromosome - genotype structure

The evolution-package provides three different datastructures to be used.

  1. m bitstring parameters each of length n bit 
    
example:
 5*10 bit
 [[0011100111][0001100010][0000110011][1101111110][1110001100]]
  2. single bitstring of length n bit
    This is a special-case of the chromosome type above with n bitstring parameters each of length 1. 
    
example:
 50 bit
 [10011010010100110101110011011001001101001111110100]
  3. m double parameters 
    
example:
 7 double values from [10..20]
 [15.2219,18.1083,15.1299,17.7626,15.6554,10.6092,14.2667]
A system of n parameters will be encoded using n bitvectors. All bitvectors have the same length l.
Let bi,l be the i.th bitvector and l its length. Then a GA-Chromosome with n parameters and parameter-length l (l bits per parameter) is defined by:

c=(b1,l,b2,l,...,bn-1,l,bn,l)

The bitstrings (or parts of a single bitstring) are usually interpreted to be Binary Coded Decimals (BCD) or Gray-encoded. However they may be interpreted in other ways. The evolution package provides coresponding methods.

Crossover (recombination)

One-Point-Crossover

For two chromosomes c1=(a1,l,a2,a,... ,an-1,l,an,l) , c2=(b1,l,b2,b,... ,bn-1,l,bn,l) with the same number of paramters n and parameter-length l, the One-Point-Crossover operator generates two new chromosomes c'1 and c'2 by performing the following steps: 


    1. get a random number r out of [1..l-1], the crossover-position 

    2. split c1 into (a1,l,a2,l,...,ar,l) and (ar+1,l,...,an-1,l,an,l) 

       split c2 into (b1,l,b2,l,...,br,l) and (br+1,l,...,bn-1,l,bn,l) 

    3. merge 

       c'1=(a1,l,a2,l,...,ar,l,br+1,l,...,bn-1,l,bn,l)

       c'2=(b1,l,b2,l,...,br,l,ar+1,l,...,an-1,l,an,l)
For example (using chromosomes e1 and e2 of the example above) let r out of [1..3] be 3, then e3 and e4 being the result of a one-point-crossover of e1 and e2 will be: 
    e1 = [ 01010,11011,10010|00010 ]
    e2 = [ 11111,11101,00101|01110 ]
    ------------------------------------
    e3 = [ 01010,11011,10010,01110 ]
    e4 = [ 11111,11101,00101,00010 ]

Multi-Point-Crossover

For two chromosomes c1=(a1,l,a2,a,... ,an-1,l,an,l) , c2=(b1,l,b2,b,... ,bn-1,l,bn,l) with the same number of paramters n and parameter-length l, the Multi-Point-Crossover operator generates two new chromosomes c'1 and c'2 by performing the following steps: 

    1. get m crossover-positions r_i (i=1..m) out of [1..l-1]
    2. split c1 into m+1 parts
              A1    = (a1,l,...,ar_1,l), 
              A2    = (ar_1+1,l,...,ar_2,l), 
                      ..., 
              A(i+1)= (ar_i+1,l,...,ar_(i+1),l), 
                      ..., 
              A(m+1)= (ar_m+1,l,...,an,l)
       split c2 into m+1 parts
              B1    = (b1,l,...,br_1,l), 
              B2    = (br_1+1,l,...,br_2,l), 
                      ..., 
              B(i+1)= (br_i+1,l,...,br_(i+1),l), 
                      ..., 
              B(m+1)= (br_m+1,l,...,bn,l)
    3. merge 

       c'1=(A1,B2,A3,B4,...);
       c'2=(B1,A2,B3,A4,...);
For example (using chromosomes e1 and e2 of the example above) with a 2 point crossover we get crossover_positions r_1=1 and r2=3. Then e3 and e4 being the result of a 2-point-crossover of e1 and e2 will be: 
    e1 = [ 01010|11011,10010|00010 ]
    e2 = [ 11111|11101,00101|01110 ]
    ------------------------------------
    e3 = [ 01010,11101,00101,00010 ]
    e4 = [ 11111,11011,10010,01110 ]
Note that there is a variety of 'more than one-point'-crossover operators and this is only one possible implementation.

Mutation - genotype-variation

Let mp_per_parameter be the mutation probability per parameter (100%: every parameter will be mutated, 0% no parameter will be mutated) and m_bits_per_parameter be the maximum number of bits that can be mutated in a single parameter. For a chromsome c1=(a1,l,a2,a,... ,an-1,l,an,l) we define a mutation operator: mutate(chromosome c , mp_per_parameter, m_bits_per_parameter) as follows: 

   for each parameter ai,l
     if 'equal distributed random variable' < mp_per_parameter
       for 1 to m_bits_per_parameter
         get a random value r out of [1..l]
         get a random value d out of [0..1]  
         if( d < 0.5 )
           if ai,l[r] is 1
              ai,l[r] = 0
           else
              ai,l[r] = 1
For example (using chromosome e1 of the example above), with a mp_per_parameter being 25% and m_bits_per_parameter being 2, a mutant e3 of e1 may look like: 
    e3= [01010,11011,11000,00010 ] = mutate([ 01010,11011,10010,00010 ], 0.25, 2);
Note that there is a variety of mutation-operators and this is only one possible implementation.

Evolution Process

There are basically two different types of evolution-processes used with Genetic Algorithms: canonical and elite. They differ in how the parents for the next generation are selected. Let p be the number of indivuals in generation i, and let c be the number children in generation i, i.e. the c descendants of the p parents.
  • canonical

    • The p parents 'produce' c children using crossover (and mutation). Each of the c children is then assigned a fitness value, depending on its quality considering the problem-specific environment. In a fitness-proportional selection process, p children are selected and become next generations parents.
  • elite

    • The p parents 'produce' c children using crossover (and mutation). Each of the c children is then assigned a fitness value, depending on its quality considering the problem-specific environment. In a fitness-proportional selection process, p individuals out of the parents and the children are selected and become next generations parents.

    The fitness-proportional selection process
    The probability for a chromosome to be selected shall be proportional to its fitness value. Usually this is done by simulating a roulette wheel with fields of different size (bigger fields: higher fitness, smaller fields: lower fitness).

  • the roulette wheel method
    •    let P be a population of 5 chromosomes c1,...,c5,
   let W be its vector of fitness values [ 17.3, 12.1, 1.8, 12.2, 1.7 ]  and
            (fitness value of chromosome:   1     2     3    4     5    )
   let S be the sum of the fitness values:  45.1

   then we simulate the roulette wheel selection by 

   r = random value from [0..S]
   t = 0 
   for ( i=1, t<r, i=i+1 )
     t = t + W[i]
   select ci-1

    literature