Evolutionary algorithms (EAs) are search methods that take their inspiration from natural selection and survival of the fittest in the biological world. EAs differ from more traditional optimization techniques in that they involve a search from a "population" of solutions, not from a single point. Each iteration of an EA involves a competitive selection that weeds out poor solutions. The solutions with high "fitness" are "recombined" with other solutions by swaping parts of a solution with another. Solutions are also "mutated" by making a small change to a single element of the solution. Recombination and mutation are used to generate new solutions that are biased towards regions of the space for which good solutions have already been seen. Pseudo-code for a genetic algorithm is as follows:

Initialize the population Evaluate initial population Repeat Perform competitive selection Apply genetic operators to generate new solutions Evaluate solutions in the population Until some convergence criteria is satisfied

An extended discussion of issues involved with the implementation and use of evolutionary algorithms is included here. Several different types of evoluationary search methods were developed independently. These include (a) genetic programming (GP), which evolve programs, (b) evolutionary programming (EP), which focuses on optimizing continuous functions without recombination, (c) evolutionary strategies (ES), which focuses on optimizing continuous functions with recombination, and (d) genetic algorithms (GAs), which focuses on optimizing general combinatorial problems.

EAs are often viewed as a global optimization method although convergence to a global optimum is only guaranteed in a weak probabilistic sense. However, one of the strengths of EAs is that they perform well on "noisy" functions where there may be multiple local optima. EAs tend not to get "stuck" on a local minima and can often find a globally optimal solutions. EAs are well suited for a wide range of combinatorial and continuous problems, though the different variations are tailored towards specific domains:

- GPs are well suited for problems that require the determination of a function that can be simply expressed in a function form
- ES and EPs are well suited for optimizing continuous functions
- GAs are well suited for optimizing combinatorial problems (though they have occasionally been applied to continuous problems)

EAs have been successfully applied to a variety of optimization problems such as wire routing, scheduling, traveling salesman, image processing, engineering design, parameter fitting, computer game playing, knapsack problems, and transportation problems. The initial formulations of GP, ES, EP and GAs considered their application to unconstrained problems. Although most research on EAs continuous to consider unconstrained problems, a variety of methods have been proposed for handling constraints.

Many GA implementations can be obtained from the Web. http://www.aic.nrl.navy.mil/galist/src/ has a good listing of source code, including Fortran, C, C++ and parallel codes. John Koza's genetic programming code is given, as well as Michalewicz' GENOCOP (GEnetic algorithm for Numerical Optimization for COnstrained Problems) which allows any function with any number of linear constraints (equalities and inequalities). Finally, some PC versions are available. One system called "Evolver" is an Excel add-in.

John Holland was one of the first developers of artificial reproduction
schemes. A good introduction to the topic is found in his book
*Adaptation in Natural and Artificial Systems *[1975]. Goldberg
[1989] has written an excellent survey text on genetic algorithms
which is highly recommended. A good survey article is found in
Forrest [1993]. Michalewicz' text on evolutionary programming
is an excellent introduction to the field.

Booker, L. (1987). "Improving Search in Genetic Algorithms,"
Chapter 5 in *Genetic Algorithms and Simulated Annealing,*
Davis, L., Ed. Pitman, London, and Morgan Kaufman: Los Altos.

Bramlette, M. F. (1991). "Initialization, Mutation, and
Selection Methods in Genetic Algorithms for Function Optimization,"
*Proceedings of the Fourth International Conference on Genetic
Algorithms. *R. K. Belew and L. B. Booker, eds. Morgan Kaufman:
Los Altos, CA.

Davis, L. editor (1991). *Handbook of Genetic Algorithms.*
Van Nostrand Reinhold.

Forrest, S. (1993). "Genetic Algorithms: Principles of
Natural Selection Applied to Computation," *Science*,
**261,** 872-878.

Goldberg, D. E. (1989). *Genetic Algorithms in Search, Optimization,
and Machine Learning. *Addison-Wesley: Reading, MA.

Greffenstette, J. J. (1986). "Optimization of Control Parameters
for Genetic Algorithms," *IEEE Transactions on Systems,
Man, and Cybernetics SMC-16*, **1**, 122-128.

Holland, J. H. (1975). *Adaptation in Natural and Artificial
Systems. *Univ. of Michigan Press: Ann Arbor. Reprinted
in 1992 by MIT Press, Cambridge MA.

Koza, J. R. (1992). * Genetic Programming*. MIT Press:
Cambridge, MA.

Michalewicz, Z. (1996). *Genetic Algorithm +Data Structures
= Evolution Programs*. Third ed. Springer-Verlag: New York.

Schaffer, J.D., R. A. Caruana, L.J. Eshelman, and R. Das (1989).
"A Study of Control Parameters Affecting Online Performance
of Genetic Algorithms for Function Optimization," *Proceedings
of the Third International Conference on Genetic Algorithms*.
J. D. Schaffer, ed. Morgan Kaufman: Los Altos, CA.

http://www.aic.nrl.navy.mil/galist/ Genetic Algorithm Archive. A repository for information related to research in genetic algorithms. This is the best place to start - a very comprehensive listing.

http://www.aracnet.com/~wwir/NovaGenetica/ A site with GA and Genetic Programming (GP) Links

http://www.cs.cmu.edu/Groups/AI/html/faqs/ai/genetic/top.html Frequently Asked Questions. This also provides useful background information if you start at the beginning.

USENET newsgroup: comp.ai.genetic

Global Optimization Survey - Main Page

Sandia National Laboratories

This page maintained by wehart@cs.sandia.gov Last modified: March 10, 1997