Evolutionary Computing

edited by Ben Paechter, Napier Univerity

The information of this page is taken from the EvoNet Web-site EvoWeb. This is an important resource for all researchers in Evolutionary Computing

Contents

• About Evolutionary Computing
• Readings
• Links

About Evolutionary Computing

The term evolutionary computating refers to the study of the foundations and applications of certain heuristic techniques based on the principles of natural evolution. In spite of the fact that these techniques can be classified into three main categories (we call it "The Evolutionary Equation", see Figure 1), this classification is based in some details and historical development facts rather than in major functioning differences. In fact, their biological basis is essentially the same.

Figure 1. The Evolutionary Equation.

Figure 2. The Soft Computing Equation.

Biological Basis

The origin of evolutionary algorithms was an attempt to mimic some of the processes taking place in natural evolution. Although the details of biological evolution are not completely understood (even nowadays), there exist some points supported by a strong experimental evidence:

• Evolution is a process operating over chromosomes rather than over organisms. The former are organic tools encoding the structure of a living being, i.e, a creature is "built" decoding a set of chromosomes.
• Natural selection is the mechanism that relates chromosomes with the efficiency of the entity they represent, thus allowing those efficient organism which are well-adapted to the environment to reproduce more often than those which are not.
• The evolutionary process takes place during the reproduction stage. There exists a large number of reproductive mechanisms in Nature. Most common ones are mutation (that causes the chromosomes of offspring to be different to those of the parents) and recombination (that combines the chromosomes of the parents to produce the offspring).

Based upon the features above, the three mentioned models of evolutionary computing were independently (and almost simultaneously) developed.

The Skeleton of an Evolutionary Algorithm

An Evolutionary Algorithm (EA) is an iterative and stochastic process that operates on a set of individuals (population). Each individual represents a potential solution to the problem being solved. This solution is obtained by means of a encoding/decoding mechanism. Initially, the population is randomly generated (perhaps with the help of a construction heuristic). Every individual in the population is assigned, by means of a fitness function, a measure of its goodness with respect to the problem under consideration. This value is the quantitative information the algorithm uses to guide the search. The whole process is sketched in Figure 3.

Generate initial population P(0)
t <- 0
WHILE termination conditions not met DO
  Evaluate(P(t))
  P'(t) <- Select(P(t))
  P''(t) <- ApplyReproductionOperators(P'(t))
  P(t+1) <- Replace(P(t),P''(t))
  t <- t+1
ENDWHILE
Return best solution found

It can be seen that the algorithm comprises three major stages: selection, reproduction and replacement. During the selection stage, a temporary population is created in which the fittest individuals (those corresponding to the best solutions contained in the population) have a higher number of instances than those less fit (natural selection). The reproductive operators are applied to the individuals in this population yielding a new population. Finally, individuals of the original population are substituted by the new created individuals. This replacement usually tries to keep the best individuals deleting the worst ones. The whole process is repeated until a certain termination criterion is achieved (usually after a given number of iterations).

Notice that the algorithm establishes a trade-off between the exploitation of good solutions (selection stage) and the exploration of new zones of the search space (reproduction stage), based on the fact that the replacement policy allows the acceptation of new solutions that not necessarily improve the existing ones.

EAs are heuristics and thus they do not ensure an optimal solution. The behaviour of these algorithms is stochastic so they may potentially present different solutions in different runs of the same algorithm. That's why it is very common to need averaged results when studying some problem and why probabilities of success (or failure), percentages of search extension, etc... are normally used for describing their properties and work.

Full Tutorial

Readings

The following textbooks (listed in no particlular order) give an introduction to the field. Other evolutionary compuitng publications can be searched here.

An Introduction to Genetic Algorithms

An Introduction to Genetic Algorithms for Scientists and Engineers

Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms

Authors: T Baeck
Publisher: Oxford University Press
Publication date: 1996
ISBN: 0195099710

Evolutionary Computation 1: Basic Algorithms and Operators

Editors: T Baeck, D Fogel, Z Michalewicz
Publisher: Institute of Physics
Publication date: 2000
ISBN: 0750306645

Evolutionary Computation 2 : Advanced Algorithms and Operators

Editors: T Baeck, D Fogel, Z Michalewicz
Publisher: Institute of Physics
Publication date: 2000
ISBN: 0750306653

Authors: Z Michalewicz
Publisher: Springer-Verlag
Publication date: 1996 3rd Rev edition
ISBN: 3540606769

Genetic Algorithms in Search, Optimization and Machine Learning

Authors: D Goldberg
Publisher: Addison-Wesley
Publication date: 1989
ISBN: 0201157675

Links

• The EvoNet website