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