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:
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.
Software
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.
References
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