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.

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).

*Figure
7: Crossover in Genetic Programming*