Encyclopedia > Genetic algorithm

Article Content

Genetic algorithm

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.

Initially several such parameter lists are generated randomly, to form an initial pool of possible solutions. This is called the first generation pool.

All of the lists are evaluated, and effectively the pool is sorted with those having better fitness at the top, representing better solutions to the problem. Notice that better in this context is relative, as initial solutions are likely to be rather poor.

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.

The first step in the construction of the next generation is to select a pair of lists for crossover. Selection is biased towards elements of the initial generation which have better fitness, though it is not so biased that poorer elements have no chance to participate. This can be done using roulette wheel selection[?] or using a ranking method.

Then perform the crossover (or recombination) genetic operator. This results in a new pair of lists, which are added to the second generation pool. This can be repeated until there are an appropriate number of new lists in the second generation pool.

The next step is to mutate the newly developed pool, again by a process of selection, this time of individual lists, followed by application of the mutation genetic operator. This process results in a second generation pool of lists which 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 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.

GAs may have a tendency to converge towards local solutions[?] rather than global solutions[?] to the problem to be solved
as time goes on each generation will tend to have multiple copies of successful parameter lists, which require evaluation, and this can slow down the processing
the most important genetic operators are selection and crossover. Mutation is only necessary to ensure that potential solutions are not lost.

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.