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

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.