Article : Evolutionary Algorithms

Evolutionary Algorithms

Evolutionary Algorithms have proved to be a powerful tool for solving complex optimization problems. Three main types of evolutionary algorithms have evolved during the last 30 years: Genetic Algorithms (GA), mainly developed by J.H. Holland [holland75adaption], Evolutionary Strategies (ES), developed by I. Rechenberg [rechenberg73evolution] and H.-P. Schwefel [schwefel81numerical] and Genetic Programming (GP) by J.R. Koza [koza92gp1]. Each of these uses different representations of the data and different operators working on them. They are, however, inspired by the same principles of natural evolution. Evolutionary Algorithms are a member of a family of stochastic search techniques that mimic the natural evolution as proposed by Charles Darwin of mutation and selection.

Evolutionary Algorithms are one of the research area of the Cognitive Systems group at the University of Tübingen (see Evolutionary Algorithms for more details).

Genetic Algorithms

Genetic Algorithms (GA) imitate the evolutionary processes with emphasis on genotype based operators (genotype/phenotype dualism). The GA works on a population of artificial chromosomes, referred to as individuals. Each individual is represented by a string of L bits. Each segment of this string corresponds to a variable of the optimizing problem in a binary encoded form.

The population is evolved in the optimization process mainly by crossover operations. This operation recombines the bit strings of individuals in the population with a certain probability Pc. Mutation is secondarily in most applications of a GA. It is responsible to ensure that some bits are changed, thus allowing the GA to explore the complete search space even if necessary alleles are temporarily lost due to convergence.

Evolution Strategy

The second type of Evolutionary Algorithms is the Evolution Strategy (ES). ES differ from GAs mainly in respect to the representation of solutions and the selection operators. They mainly rely on sophisticated mutation operators, smaller population sizes and an increased selection pressure.

The selection of the individuals forming a population is deterministic, as in contrast to GAs, where a stochastic method is used. In case of the (μ,λ)-ES selection strategy, the μ best individuals from a population of λ offsprings are selected to create the next population. An alternative implementation is the (μ + λ)-strategy, which selects the μ best individuals from the population of the λ offsprings joined with the old population of μ parents

The following listing describes the general principle of Evolution Strategies:

Genetic Programming

The idea of Genetic Programming (GP) is to introduce a new datatype to evolve and optimize computer programs. In the first experiments, the computer programming language LISP was used to encode problems. For example, the algebraic term (x-1) - x3 is represented in LISP as: ( - ( - x 1 ) (* x ( * x x ) ) ).

The GP representation for the problems that have to be encoded are trees. These tree structure use a driected acyclic graph with functions as nodes and terminals as leaves. The execution order is given by evaluating the left child before evaluating the right child.

Most commonly, GP programs use the following operators:

  • Arithmetic operators: +, -, *, /, sin, cos, exp, ....
  • Boolean operators: AND, OR, XOR, NOT, NAND
  • Problem specific operators: Max, Min, Variance,...

The following figure shows the encoding of a GP program tree:

With GP, Evolutionary Algorithms are able to model dynamic systems using arbitrary differential equations because with the presented encoding, any equation can be created.

Memetic Algorithm

The combination of an Evolutionary Algorithm with a local search heuristic is called Memetic Algorithm (MA) [moscato89evolution]. MAs are inspired by Dawkin's [dawkins76selfish] notion of a meme. A meme is a "cultural gene" and in contrast to genes, memes are usually adapted by the people who transmit them before they are passed to the next generation. From the optimization point of view, it is argued that the success of an MA is due to the tradeoff between the exploration abilities of the underlying EA and the exploitation abilities of the local searchers used. This means that during variation, the balance between disruption and information preservation is very important: on the one hand the escape of local optima must be guaranteed, but on the other hand disrupting too much may cause the loss of important information gained in the previous generation.

The following pseudocode describes the general principle of MA:

Memetic Algorithms combine the features of EA to explore the solution space of combinatorial problems and the abilitiy of exploiting of local search heuristics.