Fitness landscapes in evolutionary optimization
Apart from the field of evolutionary biology, the concept of a fitness landscape has also gained importance in evolutionary optimization methods such as genetic algorithms or evolutionary strategies. In evolutionary optimization, one tries to solve real-world problems (e.g., engineering or logistics problems) by imitating the dynamics of biological evolution. For example, a delivery truck with a number of destination addresses can take a large variety of different routes, but only very few will result in a short driving time. In order to use evolutionary optimization, one has to define for every possible solution s to the problem of interest (i.e., every possible route in the case of the delivery truck) how 'good' it is. This is done by introducing a scalar-valued function f(s) (Scalar valued means that f(s) is a simple number, such as 0.3, while s can be a more complicated object, for example a list of destination addresses in the case of the delivery truck.), which is called the fitness function or fitness landscape. A high f(s) implies that s is a good solution. In the case of the delivery truck, f(s) could be the number of deliveries per hour on route s. The best, or at least a very good, solution is then found in the following way. Initially, a population of random solutions is created. Then, the solutions are mutated and selected for those with higher fitness, until a satisfying solution has been found.
Evolutionary optimization techniques are particularly useful in situations in which it easy to determine the quality of a single solution, but hard to go through all possible solutions one by one (it is easy to determine the driving time for a particular route of the delivery truck, but it is almost impossible to check all possible routes once the number of destinations grows to more than a handful).
The concept of a scalar valued fitness function f(s) also corresponds to the concept of a potential or energy function in physics. The two concepts only differ in so far that physicists traditionally think in terms of minimizing the potential function, while biologists prefer the notion that fitness is being maximized. Therefore, multiplying a potential function by -1 turns it into a fitness function, and vice versa.
Figure 1: Sketch of a fitness landscape. The arrows indicate the preferred flow of a population on the landscape, and the points A, B, and C are local optima. The red ball indicates a population that moves from a very low fitness value to the top of a peak. Illustration by C.O. Wilke, 2001.
For further reading
- Sewall Wright. "The roles of mutation, inbreeding, crossbreeding, and selection in evolution". In Proceedings of the Sixth International Congress on Genetics, pp. 355-366, 1932.
- Richard Dawkins. Climbing Mount Improbable. New York: Norton, 1996.
- Stuart Kauffman. At Home in the Universe: The Search for Laws of Self-Organization and Complexity. New York: Oxford University Press, 1995.
- Melanie Mitchell. An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press, 1996.
See also:
An earlier version of the above article was in review as of 6 June 2001 on Nupedia. It was written by Claus Wilke. It was not officially approved in Nupedia, but was at the "open review" step by the Biology group: lead reviewer, Gaytha Langlois ; with the assistance of other area(s): Computers.
