Evolutionary computation is an emerging field that seeks to
solve difficult problems by using analogies to natural processes
such as mutation, crossover, and natural selection. Evolutionary
approaches maintain a population of proposed or partial solutions,
modifying them from generation to generation using evolutionary
operators and evaluating them using a fitness function. If the members
of the population are executable programs, this approach is known
as genetic programming. If the members of the population
are better viewed as strings of parameters, this approach is known
as genetic algorithms.
These approaches can be viewed as performing a randomized
beam search, ie. a search that always keeps its best k hypotheses.
The Genetic Algorithm
- Initialize the population to contain s individuals
- while (stopping condition not satisfied)
- Select (1-r)s individuals at random from the current generation
according to fitness
- Select another rs/2 pairs of individuals at random from the current
generation. Each pair participates in crossover, producing two offspring.
- The next generation consists of the (1-r)s individuals selected in
the first step plus the rs offspring from the second step
- Mutate the next generation at rate m
Reference:
Machine Learning
Tom M. Mitchell
McGraw-Hill, 1997