Main Page | See live article | Alphabetical index

Genetic algorithm

A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems, inspired by and named after biological processes of inheritance, mutation, natural selection, and the genetic crossover that occurs when parents mate to produce offspring. Genetic algorithms are a particular class of evolutionary algorithms.

Genetic algorithms are typically implemented as a computer simulation in which a population of abstract representations of candidate solutions to an optimization problem are stochastically selected, recombined, mutated, and then either eliminated or retained, based on their relative fitnesses.

John Holland was the pioneering founder of much of today's work in genetic algorithms, which has moved on from a purely theoretical subject (though based on computer modelling), to provide methods which can be used to solve some difficult problems today. Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling and scheduling problems, and many scheduling software packages are based on GAs.

The problem to be solved is represented by a list of parameters which can be used to drive an evaluation procedure. Possible solutions to the problem (referred to as chromosomes or genomes) are also represented in this parameter list form. These chromosomes are evaluated, and a value of goodness or fitness is returned.

The next step of the algorithm is to generate a second generation pool of parameter lists, which is done using the genetic operators selection, crossover (or recombination), and mutation.

These processes result in a second generation pool of chromosomes that is different from the initial generation, which is then evaluated and the fitness values for each list is obtained. Generally the average degree of fitness will have increased by this procedure for the second generation pool.

A slight variant of this method of pool generation is to allow some of the better chromosomes from the first generation to carry over to the second. This form of genetic algorithm is known as an elite selection strategy.

The process continues by generating third, fourth, fifth,... (and so on) generations, until one of the generations contains solutions which are good enough.

There are several general observations to make about the generation of solutions.

It is also important to note that there are several different variants of the basic GA algorithm. The simplest algorithm represents each chromosome as a bit string. Typically numeric parameters can be represented by integers, though it is possible to use floating point representations. The basic algorithm performs crossover and mutation at the bit level. Other variants treat the parameter list as lists of numbers, and crossover and mutation are performed so as to respect number boundaries. For most data types specific variation operators can be designed.

Genetic algorithms are known to produce good results for some problems. Their major disadvantage is that they are relatively slow, compared to other methods, such as random optimisation. Recent speed improvements have focused on speciation, wherein cross-over can only occur if individuals are closely-enough related. Genetic algorithms have been successfully applied to the study of neurological evolution (see NeuroEvolution by Augmented Topologies).

Genetic programming is a related technique developed by John Koza, in which computer programs, rather than function parameters, are optimised. Genetic programming often uses tree-based internal data structures to represent the computer programs for adaptation instead of the list, or array, structures typical of genetic algorithms. Genetic programming algorithms typically require running time that is orders of magnitude greater than that for genetic algorithms, but they may be suitable for problems that are intractable with genetic algorithms.

See also: artificial life, eight queens puzzle, evolutionary computation, genetic programming, fitness landscape, automatic label placement, NEAT, bio-inspired computing

References

External links