TOPICS
Search

Genetic Algorithm


A genetic algorithm is a class of adaptive stochastic optimization algorithms involving search and optimization. Genetic algorithms were first used by Holland (1975).

The basic idea is to try to mimic a simple picture of natural selection in order to find a good algorithm. The first step is to mutate, or randomly vary, a given collection of sample programs. The second step is a selection step, which is often done through measuring against a fitness function. The process is repeated until a suitable solution is found.

There are a large number of different types of genetic algorithms. The step involving mutation depends on how the sample programs are represented, as well as whether the programmer includes various crossover techniques. The test for fitness is also up to the programmer.

Like a gradient flow optimization, it is possible for the process to get stuck in a local maximum of the fitness function. One advantage of a genetic algorithm is that it does not require the fitness function to be very smooth, since a random search is done instead of following the path of least resistance. But to be successful, there needs to be some nice relationship between the modifiable parameters to the fitness. In general, one runs into computational irreducibility.

Holland created an electronic organism as a binary string ("chromosome"), and then used genetic and evolutionary principles of fitness-proportionate selection for reproduction (including random crossover and mutation) to search enormous solution spaces efficiently. So-called genetic programming languages apply the same principles, using an expression tree instead of a bit string as the "chromosome."


See also

Cellular Automaton, Differential Evolution, Evolutionary Programming, Evolution Strategies, Genetic Programming, Optimization Theory, Stochastic Optimization

Portions of this entry contributed by Todd Rowland

Explore with Wolfram|Alpha

References

Bengtsson, M. "Genetic Algorithms Notebook." http://library.wolfram.com/infocenter/MathSource/569/.Corne, D.; Dorigo, M.; and Glover, F. New Ideas in Optimization. New York: McGraw-Hill, 1999.Cramer, N. L. "A Representation for the Adaptive Generation of Simple Sequential Programs." In Proceedings, International Conference on Genetic Algorithms and their Applications, July 1985 (Ed. J. J. Grefenstette). Hillsdale, NJ: L. Erlbaum Associates, pp. 183-187, 1985.Fernandez, J. "The GP Tutorial." http://www.geneticprogramming.com/Tutorial/.Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, MI: University of Michigan Press, 1975.Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, 2nd ed. Cambridge, MA: MIT Press, 1992.Jacob, C. Illustrating Evolutionary Computation with Mathematica. San Francisco, CA: Morgan Kaufmann, 2001.Koza, J. R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, 1992. Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1002, 2002.

Referenced on Wolfram|Alpha

Genetic Algorithm

Cite this as:

Rowland, Todd and Weisstein, Eric W. "Genetic Algorithm." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GeneticAlgorithm.html

Subject classifications