Evolutionary Algorithms:

Genetic Algorithms, Evolutionary Programming and Genetic Programming


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
  	  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.

Application Domains

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:

The recombination operation used by EAs requires that the problem can be represented in a manner that makes combinations of two solutions likely to generate interesting solutions. Consequently selecting an appropriate representation is a challenging aspect of applying these methods.

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.


At Sandia, a variety of EAs are included in SGOPT, a C++ class library of stochastic global optimization methods. It can be obtained from Bill Hart or accessed through the DAKOTA toolkit.

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.

Miscellaneous Links

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