Abstract
Evolutionary computation is an old field of computer science that started in the end of the 1960s nearly simultaneously in different parts of the world. Each paradigm has evolved separately, apparently without knowledge of what was happening elsewhere, until people finally got together and shared their experience. This resulted in strong trends that still survive, even though it is now possible to outline a generic structure for an evolutionary algorithm that is described in this chapter.
Key Terms in this Chapter
Mutation: Function that can possibly alter the genotype of an individual. Mutation is usually seen as an exploration operator, allowing the escape from local optima. A good mutation function should be ergodic.
Phenotype: Expression of the genotype. The fitness of an individual is evaluated on its phenotype, not on its genotype. In some problems there is no simple correlation between phenotype and genotype. For instance, there is not a single gene coding for blue eyes. Blue eyes is a phenotype.
Unary Operator: Operator needing only one operand.
Individual: Potential solution to a problem.
N-ary Operator: Operator needing n operands.
Ergodicity: A function is ergodic if the probability to jump from any point a of the search space to any other point b is not null. A mutation operator randomly flipping a single bit of a bitstring is therefore not strictly ergodic. However, it is ergodic in a loose sense, in that it is possible to obtain any other individual in a finite number of mutations.
Elitism: Elitist algorithms make sure that the best individuals are not discarded, by transferring them directly into the next generation.
Genotype: Set of parameters allowing representation of a solution to a problem.
Representation: Structure of the genome of an individual (array of bits, integers, doubles, etc.).
Epistasis: Amount of correlation between different genes (or parameters).
Crossover: Function capable of recombining several potential solutions (parents) into new solutions (children). Crossover is usually seen as an exploitation operator, equivalent to a local search.
Replacement: Refers to the operator that will create a new generation out of a pool of children and/or parents. Only one instance of an individual can make it to the new generation.