next up previous contents
Next: Multi-Resolution Methods and Up: Global Optimization Previous: Simulated Annealing

Genetic Algorithms

Genetic Algorithms attempt to minimize functions using an approach analogous with evolution and natural selection. The key features are

Usually a chromosome is a string of bits formed by concatenation of the bit strings representing each of the n parameters . The number of bits used to encode each parameter will depend on the desired tolerance.

Two chromosomes are combined by crossover. Two parent chromosomes are each cut at a random location and the opposing sections rejoined to form two children:

In addition a small amount of mutation is introduced, randomly changing bits in the chromosomes.

The algorithm starts by creating a first generation of N chromosomes scattered randomly about the search space. Each new generation is produced as follows

The assumption is made that the optima can be formed by combining small sub-sections of the chromosomes, each of which will tend to improve the function evaluation of any full chromosome containing them. Thus these good building blocks will tend to be reproduced and will propagate through the population. Eventually all the current generation of individuals should end up in the global optimum.

For functions of the form where each is continuous with upper and lower bounds a straightforward bitstring encoding of a is sufficient for the chromosomes. However, permutation problems (such as the Travelling Salesman Problem) are much harder - Simulated Annealing algorithms are likely to give better results.

Under the right conditions Genetic Algorithms have been shown to converge to good solutions remarkably quickly and have the advantage that the rate of convergence varies in accordance with the complexity of the search space [4] [15] [17].



next up previous contents
Next: Multi-Resolution Methods and Up: Global Optimization Previous: Simulated Annealing



Bob Fisher
Fri Mar 28 14:12:50 GMT 1997