appendices

Appendix I

The Genetic Algorithm

Algorithm:

1) Generate an initial, random population of chromosomes.
2) Test the fitness of each chromosome in the population.
3) Select parents as the most fit members of the population.
4) Reproduce from selected parents to produce a new population.
5) Mutate according to some probability.
6) Test the fitness of each chromosome in the new population.
7) Discard the old population.
8) Iterate steps 3 to 7 until termination criterion is met.

Note: Each iteration of this algorithm is a generation.
The initial, random generation is known as generation 0.

PseudoCode:

Begin GA.
    t 0;
    Generate_Population P;
    Test_Fitness P;
    while not DONE
    {
        t = t + 1;
        P^{~_{= Select_Parents P;}}
^{_{Crossover P}~_;}
^{_{Mutate P}~_;}
^{_{Test_Fitness P}~_;}
^{_{P Survive P, P}~_;}
^_}
^_End
GA.

^_where:
^{_{t
= time step;}}
^{_{P
= General Population;}}
^{_P~_{= Selected Breeders;}}
^{_{DONE
= Termination criterion.}}

Adapted From:Davis, L. (1991): Handbook of Genetic Algorithms. Van Nostrand Reinhold. New York, NY. p. 192.

Appendix II

Selection Algorithms

a) Roulette Wheel Selection

1.Sum the fitness of each member of the population.
2.Determine the relative fitness of each member of the population.
3.Generate a random number (SPIN) between zero and some predefined maximum value (MAX).
4.Select next individual.
5.From SPIN, subtract the individual’s relative proportion of MAX (i.e., relative fitness times MAX).
6.Repeat steps 4 and 5 until SPIN is less than or equal to zero.
7.Repeat steps 3 to 6 until mating pool is full.

b) Expected Value Model

1.Calculate the expected incidence of each member of the population (i.e., the e value).
2.Use Roulette Wheel (steps 1 to 6) to select an individual for reproduction or crossover.
3.If the expected incidence of the selected individual is not greater than zero repeat step 2.
4.Determine whether the individual is to be reproduced or mated.
5.If the individual is to be reproduced subtract one from expected incidence. Skip to step 8.
6.If the individual is to be mated select another individual using steps 2 and 3.
7.Subtract one-half from the expected incidence of each individual selected for mating.
8.Conduct reproduction or crossover operation into next generation.
9.Continue steps 2 to 8 until next generation is full.

c) Tournament Selection

1.Enter all individuals in the tournament.
2.Randomly select two individuals to compete.
3.Compare the fitness of the two individuals: the individual with the greatest fitness is considered the victor.
4.Add the victor to the mating pool.
5.Remove the loser from the tournament.
6.Repeat steps 2 to 6 until only one individual is left in the tournament.
7.Randomly select individuals from the mating pool for reproduction or crossover (without replacement).
8.Repeat step 7 until next generation is full (i.e., the mating pool is empty).

Appendix III
Crossover in Genetic Programming

Figure 7: Crossover in Genetic Programming

[Bibliography] [Appendix IV]
[Beer]