Evolutionary computation
From Wikipedia, the free encyclopedia
Evolutionary computation (EC) is a development in Computer Science. It contains building, applying and studying algorithms based on natural selection. EC is conducted with the help of evolutionary algorithms (EA).
Contents |
[edit] History
In the fifties, long before computers were used on a great scale, the idea to use Darwinian principles for automated problem solving originated.
In the sixties, three different interpretations of this idea have been developed at three different places.
Evolutionary programming was introduced by Fogel in the USA, while Holland called his method a genetic algorithm. In Germany Rechenberg and Schwefel introduced evolution strategies. These areas developed separately for about 15 years. From the early nineties they are seen as different representatives (“dialects”) of one technology, called evolutionary computing. In the early nineties, another fourth stream following the general ideas had emerged – genetic programming.
These terminologies denote the whole field by evolutionary computing and consider evolutionary programming, evolution strategies, genetic algorithms, and genetic programming as sub-areas.
[edit] What is an evolutionary algorithm?
All these concepts have the same underlying idea: A population which stands under natural selection due to environmental pressure, increases the fitness of the population. To measure this fitness, one can apply an objective function with candidate solutions. The individuals with the highest fitness will be chosen to provide the next generation by using recombination and/or mutation. Recombination acts on the two selected parents (candidates) and results in one or two children (new candidates). Mutation acts on one candidate and results in a new candidate. Recombination and mutation lead to the offspring (a set of new candidates). These new candidates will compete with old candidates for their place in the next generation. This process can be repeated until a candidate with sufficient quality (a solution) is found or a previously determined computational limit is reached. In this process, there are two main forces that form the basis of evolutionary systems.
- Recombination and mutation create the necessary diversity and thereby facilitate novelty, while - Selection acts as a force increasing quality.
Many aspects of such an evolutionary process are stochastic. Changed pieces of information due to recombination and mutation are randomly chosen.
On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness have a higher chance to be selected than individuals with a lower fitness, but typically even the weak individuals have a chance to become a parent or to survive.
[edit] References
- Th. Bäck and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, 1993. - W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. Genetic Programming — An Introduction. Morgan Kaufmann, 1998. - A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, 2003, ISBN 3-540-40184-9 - A.E. Eiben and M. Schoenauer, Evolutionary computing, Information Processing Letters, 82(1): 1-6, 2002. - D. B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. IEEE Press, Piscataway, NJ, 1995. - L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through Simulated Evolution. New York: John Wiley, 1966. - D. E. Goldberg. Genetic algorithms in search, optimization and machine learning. Addison Wesley, 1989. - J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975. - J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992. - I. Rechenberg. Evolutionstrategie: Optimierung Technisher Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Stuttgart, 1973. - H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, New-York, 1981. 1995 – 2nd edition.
[edit] See also
[edit] Major Conferences and Workshops
- The Genetic and Evolutionary Computation Conference (GECCO)
- IEEE Congress on Evolutionary Computation (CEC)
- Parallel Problem Solving from Nature (PPSN)
- The Foundations of Genetic Algorithms workshop (FOGA)
- The Workshop on Ant Colony optimization and Swarm Intellligence (ANTS)
- The Evo* and EuroGP workshops
[edit] Journals
- Evolutionary Computation
- IEEE Transactions on Evolutionary Computation
- Genetic Programming and Evolvable Machines
