Genetic algorithms (or GAs) form a class of algorithms 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.
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. The list is evaluated, and a value of goodness or fitness is returned.
A slight variant of this method of pool generation is to allow some of the better lists from the first generation to carry over to the second. This form of genetic algorithm is known as elite.
The process continues by generating 3rd, 4th, 5th ... generations, until one of the generations contains solutions which are good enough.
There are several 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 parameter list 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.
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 programming is a technique developed by John Koza, which is similar, but in which computer programs are modified, and evaluated in the optimisation process. Genetic programming algorithms typically require running time which is orders of magnitude greater than a GA algorithm, but may be able to solve some problems which GAs cannot do easily. Genetic programming also uses internal data structures which are based on the use of tree structures to represent the computer programs for adaptation, rather than list structures which are used in genetic algorithms.
Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning
Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA Addison-Wesley