Q1: What are Evolutionary Algorithms (EAs)?

Evolutionary algorithm is an umbrella term used to describe computer-based problem solving systems which use computational models of some of the known mechanisms of EVOLUTION as key elements in their design and implementation. A variety of EVOLUTIONARY ALGORITHMs have been proposed. The major ones are: GENETIC ALGORITHMs (see Q1.1), EVOLUTIONARY PROGRAMMING (see Q1.2), EVOLUTION STRATEGIEs (see Q1.3), CLASSIFIER SYSTEMs (see Q1.4), and GENETIC PROGRAMMING (see Q1.5). They all share a common conceptual base of simulating the evolution of INDIVIDUAL structures via processes of SELECTION, MUTATION, and REPRODUCTION. The processes depend on the perceived PERFORMANCE of the individual structures as defined by an ENVIRONMENT.

More precisely, EAs maintain a POPULATION of structures, that evolve according to rules of selection and other operators, that are referred to as "search operators", (or GENETIC OPERATORs), such as RECOMBINATION and mutation. Each individual in the population receives a measure of its FITNESS in the environment. Reproduction focuses attention on high fitness individuals, thus exploiting (cf. EXPLOITATION) the available fitness information. Recombination and mutation perturb those individuals, providing general heuristics for EXPLORATION. Although simplistic from a biologist's viewpoint, these algorithms are sufficiently complex to provide robust and powerful adaptive search mechanisms.

--- "An Overview of Evolutionary Computation" [ECML93], 442-459.

BIOLOGICAL BASIS

To understand EAs, it is necessary to have some appreciation of the biological processes on which they are based.

Firstly, we should note that EVOLUTION (in nature or anywhere else) is not a purposive or directed process. That is, there is no evidence to support the assertion that the goal of evolution is to produce Mankind. Indeed, the processes of nature seem to boil down to a haphazard GENERATION of biologically diverse organisms. Some of evolution is determined by natural SELECTION or different INDIVIDUALs competing for resources in the ENVIRONMENT. Some are better than others. Those that are better are more likely to survive and propagate their genetic material.

In nature, we see that the encoding for genetic information (GENOME) is done in a way that admits asexual REPRODUCTION. Asexual reproduction typically results in OFFSPRING that are genetically identical to the PARENT. (Large numbers of organisms reproduce asexually; this includes most bacteria which some biologists hold to be the most successful SPECIES known.)

Sexual reproduction allows some shuffing of CHROMOSOMEs, producing offspring that contain a combination of information from each parent. At the molecular level what occurs (wild oversimplification alert!) is that a pair of almost identical chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the RECOMBINATION operation, which is often referred to as CROSSOVER because of the way that biologists have observed strands of chromosomes crossing over during the exchange.

Recombination happens in an environment where the selection of who gets to mate is largely a function of the FITNESS of the individual, i.e. how good the individual is at competing in its environment. Some "luck" (random effect) is usually involved too. Some EAs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or asexual reproduction (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds.

Much EA research has assumed that the two processes that most contribute to evolution are crossover and fitness based selection/reproduction. Evolution, by definition, absolutely requires diversity in order to work. In nature, an important source of diversity is MUTATION. In an EA, a large amount of diversity is usually introduced at the start of the algorithm, by randomising the GENEs in the POPULATION. The importance of mutation, which introduces further diversity while the algorithm is running, therefore continues to be a matter of debate. Some refer to it as a background operator, simply replacing some of the original diversity which may have been lost, while others view it as playing the dominant role in the evolutionary process.

It cannot be stressed too strongly that an EVOLUTIONARY ALGORITHM (as a SIMULATION of a genetic process) is not a random search for a solution to a problem (highly fit individual). EAs use stochastic processes, but the result is distinctly non-random (better than random).

PSEUDO CODE


Algorithm EA is

// start with an initial time t := 0;

// initialize a usually random population of individuals initpopulation P (t);

// evaluate fitness of all initial individuals in population evaluate P (t);

// test for termination criterion (time, fitness, etc.) while not done do

// increase the time counter t := t + 1;

// select sub-population for offspring production P' := selectparents P (t);

// recombine the "genes" of selected parents recombine P' (t);

// perturb the mated population stochastically mutate P' (t);

// evaluate its new fitness evaluate P' (t);

// select the survivors from actual fitness P := survive P,P' (t); od end EA.


[Previous question] [Next question] [HHGTEC main contents page]

Mistakes in this page?
Hitch Hiker's Guide to Evolutionary Computation, Issue 9.1, released 12 April 2001
Copyright © 1993-2001 by J. Heitkötter and D. Beasley, all rights reserved.