Catalogue of Artificial Intelligence Techniques
Aliases: Evolutionary Algorithm
Author(s): Dave Corne
A Genetic Algorithm (GA) is a population-based optimisation strategy which finds use as a robust and often very effective technique for fast convergence to near-optima or optima of ill-understood fitness landscapes. Key concepts are the notion of a `chromosome' and its `fitness'. A chromosome is a (usually) fixed-length string of symbols which can be interpreted as a potential solution to the problem in hand; its fitness is a measure of how close this chromosome is to a perfect solution. A GA works via continual update of a collection (called a `population') of chromosomes, which are initially randomly generated. Updating comprises three steps: (i) One or more chromosomes are selected from the population; (ii) One of a set of genetic operators is applied to the selected chromosome(s), yielding one or more `offspring'; (iii) The offspring enter the population, replacing less fit members. The process iterates until some stopping criterion is met (e.g., a good enough or ideal solution is found), or all chromosomes in the population are the same. Variations on the GA theme range across a vast space of possible ways of doing steps (i), (ii), and (iii). Step (ii), in which genetic operators are applied, is particularly important in terms of how the search is conducted. The commonest operators are crossover, in which segments of each of two `parent' chromosomes are interchanged to produce one or more offspring, and mutation, in which a small part of a single parent is altered. Real-world applications of GAs usually benefit from the design of operators incorporating domain specific knowledge.
- Lawrence Davis, The Handbook of Genetic Algorithms
, Van Nostrand Reinhold, New York, 1991.