Contents

• Anders Christensen
• Giovanni Pini

• Marco Dorigo
• Hugues Bersini
• Mauro Birattari
• Elio Tuci
• Tom Lenaerts
• Thomas Stützle

Evolutionary computation (EC) algorithms are inspired by nature's capability to evolve living beings well adapted to their environment that cooperate or compete with other members of the population. EC algorithms can be characterized as computational models of the evolutionary process that take inspiration from the natural genetic variety and natural selection.

At each iteration of the EC algorithm a number or operators is applied to the individuals of the current population to generate the individuals of the population of the next generation (iteration). Usually, EC algorithms use operators called recombination or crossover to recombine two or more individuals to produce new ones. They also use mutation or modification operators which cause a self-adaptation of individuals. The driving force in EC algorithms is the selection of individuals based on their fitness (which can be based on the objective function or some other kind of quality measure). Individuals with a higher fitness have a higher probability to be chosen as members of the population of the next iteration (or as parents for the generation of new individuals). This corresponds to the principle of survival of the fittest in natural evolution.

There has been a variety of different EC algorithms proposed over the years. Basically, they fall into three different categories which have been developed independently of each other. These are evolutionary programming (Fogel [1]; Fogel et al. [2]), evolution strategies (Rechenberg [3]; Schwefel [10]), and genetic algorithms (Holland [4]; Goldberg [11]; Mitchell [12]).

Over the years there have been quite a few overviews and surveys about EC methods. Among these are the ones by Bäck [5], by Fogel [6], by Spears et al. [7] and by Michlewicz and Michalewicz [8]. In Calegari et al. [9] a taxonomy of EC algorithm is proposed.

Despite their superficial differences, the three main approaches to EC share the same basic template. A general outline of an EC algorithm is shown here:

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
end-while

[1] L. J. Fogel. Toward inductive inference automata. In Proceedings of the International Federation for Information Processing Congress, pages 395-399, Munich, Germany, 1962.

[2] L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. John Wiley & Sons, New York, NY, 1966.

[3] I. Rechenberg. Evolution strategy: Optimization of technical systems by means of biological evolution. Fromman-Holzboog, Stuttgart, Germany, 1973.

[4] J. H. Holland. Adaptation in natural artificial systems. University of Michigan Press, Ann Arbor, MI, 1975.

[5] T. Bäck. Evolutionary Algorithms in Theory and Practice: Evolutionary Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York, NY, 1996.

[6] D. B. Fogel. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks, 5(1):3-14, Jan 1994.

[7] W. M. Spears, K. A. De Jong, T. Bäck, D. B. Fogel, and H. de Garis. An overview of evolutionary computation. In P. B. Brazdil, editor, Proceedings of the European Conference on Machine Learning (ECML-93), volume 667 of Lecture Notes in Artificial Intelligence, pages 442-459, Berlin, Germany, 1993. Springer-Verlag.

[8] Z. Michlewicz and M. Michalewicz. Evolutionary computation techniques and their applications. In Proceedings of the IEEE International Conference on Intelligent Processing Systems, pages 14-24, Piscataway, NJ, 1997. IEEE Publications.

[9] P. Calegari, G. Coray, A. Hertz, D. Kobler, and P. Kuonen. A taxonomy of evolutionary algorithms in combinatorial optimization. Journal of Heuristics , 5:145-158, 1999.

[10] H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, Chichester, UK, 1981.

[11] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.

[12] M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 1996.

• The Evonet (European Network of Excellence in Evolutionary Computing) website