A rapidly growing interdisciplinary science area that is concerned with modeling aspects of natural evolution in order to solve real-world problems. Living organisms, as well as those long extinct, demonstrate optimized complex behavior at all levels: cells, organs, individuals, and populations. Charles Darwin wrote of “organs of extreme perfection” when describing the ability of evolution to craft ingenious solutions to complex problems such as vision. Evolution is the great unifying principle of biology, but it extends beyond biology and can be used as an engineering principle where individuals in a population of candidate solutions to some particular problem undergo random variation (mutation and recombination) and face competition and selection based on their appropriateness for the task at hand.
The common use of an evolutionary algorithm requires four elements: (1) an evaluation (fitness) function that describes the quality of any candidate solution in quantitative terms, (2) a representation or data structure that the computer uses to store solutions, (3) a random variation operator (or operators) that transform “parents” into “offspring,” and (4) a means for selecting which solutions will survive to the next generation and which will be eliminated. In addition, the process must be initialized with a population of candidate solutions to the task at hand. This is often accomplished by seeding the first population with completely random solutions; however, if domain-specific knowledge is available regarding which solutions may be better than others, these hints can be used to bias the initial population and may accelerate the evolutionary optimization procedure.
An evolutionary algorithm (see illustration) is executed over a series of generations of random variation and selection. The variation to the existing solutions can come in the form of single-parent or multiparent operators. Alternative choices offer different sampling distributions from the space of all possible solutions. Each of the individuals in the population is scored with respect to how well the individual accomplishes the task at hand (fitness), and selection is used to eliminate some subset of the population or to amplify the percentage of above-average solutions. The algorithm terminates when some extrinsic criterion has been satisfied, such as prescribed maximum number of generations, or a suitable error tolerance. Over time, by eliminating poor solutions and extending the evolutionary search around those that appear better, the population can discover superior solutions to complex problems.
Typical flowchart for an evolutionary algorithm.
In comparison to traditional problem-solving techniques, evolutionary algorithms are often much faster and more adaptable to changes in the environment because whatever knowledge has been learned about how to solve a problem is contained in the collection of individual solutions that has survived up to that point. In contrast with, say, dynamic programming, an evolutionary algorithm need not be restarted when facing new data. This feature promises to have a significant potential in future problem solving. As the spread of data and processing speeds continue to increase, it will be necessary to make decisions ever more quickly. The evolutionary approach of bootstrapping off the current basis set of knowledge may eventually become the standard approach to real-world, real-time problem solving. See also Algorithm; Concurrent processing; Distributed systems (computers); Genetic algorithms; Multiprocessing; Optimization; Organic evolution; Supercomputer.
