Evolutionary computation
Alan Turing proposed a method of genetic search in 1948. His B-type u-machines resembled primitive neural networks where connections between neurons were learned via a sort of genetic algorithm. Turing's P-type u-machines resembled a method for reinforcement learning using pleasure and pain signals to direct machine behavior. However, his paper went unpublished until 1968, and he died in 1954. This early work had little to no effect on the field that was to develop. Evolutionary computing as a field began in earnest during the 1950s and 1960s. Several independent attempts used the process of evolution in computing at this time. These efforts developed separately for roughly 15 years before converging into distinct branches. Three branches emerged in different places to attain this goal: evolution strategies, evolutionary programming, and genetic algorithms. A fourth branch called genetic programming eventually emerged in the early 1990s.
In 1962, Lawrence J. Fogel initiated research into Evolutionary Programming within the United States. He considered it an artificial intelligence endeavor involving finite state machines solving prediction problems. These machines would be mutated by adding or deleting states or changing transition rules. The best of these mutated machines evolved further in future generations. In 1964, Ingo Rechenberg and Hans-Paul Schwefel introduced the paradigm of evolution strategies in Germany. They proposed random mutations applied to all parameters of some solution vector to escape local minima found by traditional gradient descent techniques. Child solutions were generated from parent solutions, keeping only the more successful ones for future generations. John Henry Holland introduced genetic algorithms in the 1960s while developing them further at the University of Michigan during the 1970s. Populations of chromosomes represented as bit strings transformed through artificial selection processes selecting specific allele bits. By the 1990s, a new approach called genetic programming emerged advocated for by John Koza among others. Programs written in high-level languages like Lisp S-expressions became subjects of evolution themselves.
Evolutionary computing techniques mostly involve metaheuristic optimization algorithms that rely on stochastic mutation and recombination. Changed pieces of information due to recombination and mutation are randomly chosen to create necessary diversity. On the other hand, selection operators can be either deterministic or stochastic depending on the method used. Individuals with higher fitness have a higher chance to be selected than those with lower fitness. Typically even weak individuals retain a chance to become parents or survive into the next generation. In biological terminology, a population of solutions is subjected to natural selection or artificial selection alongside mutation. As a result, the population gradually evolves to increase in fitness according to the chosen function. Many aspects of such an evolutionary process remain stochastic throughout repeated applications of these operators. Candidate solutions play the role of individuals within a population where cost functions determine their environment. Evolution of the population then takes place after applying reproduction, mutation, recombination, and natural selection repeatedly.
This technique was first used by Rechenberg and Schwefel to successfully solve optimization problems in fluid dynamics. Initially this optimization technique performed without computers relying instead on dice to determine random mutations. By 1965 calculations were performed wholly by machine allowing for greater precision and speed. The evolutionary programming method successfully applied itself to prediction problems system identification and automatic control tasks. It eventually extended to handle time series data and model the evolution of gaming strategies. Sequence induction pattern recognition and planning became successful applications of the genetic programming paradigm. Evolutionary algorithms now solve multi-dimensional problems more efficiently than software produced by human designers. They also optimize the design of systems ranging from antenna structures to complex engineering challenges. Many variants exist suited to specific families of problems and data structures found in modern computing environments.
Genetic algorithms deliver methods to model biological systems linked to theory of dynamical systems predicting future states. This view recognizes there is no central control of development as organisms develop through local interactions between cells. Biological systems resemble computational machines processing input information to compute next states rather than classical dynamical systems. Micro processes in biological organisms are fundamentally incomplete and undecidable implying deeper analogies beyond crude metaphors. Evolutionary automata generalize Evolutionary Turing machines investigating properties of biological and evolutionary computation precisely. These allow obtaining new results on expressiveness confirming initial findings about undecidability of natural evolution. Evolutionary finite automata working in terminal mode can accept arbitrary languages over given alphabets including non-recursively enumerable ones. The analogy extends to relationships between inheritance systems and biological structure revealing pressing problems explaining origins of life.
A network analysis of the community was published in 2007 listing active researchers like Kalyanmoy Deb and Kenneth A De Jong. Several journals dedicated to evolutionary computation emerged starting with Evolutionary Computation founded in 1993 by MIT Press. Artificial Life journal also launched that same year while IEEE Transactions began operations in 1997. Genetic Programming and Evolvable Machines started publication in 2000 followed by Swarm Intelligence in 2007. Main conferences include ACM Genetic and Evolutionary Computation Conference known as GECCO alongside IEEE Congress on Evolutionary Computation called CEC. EvoStar comprises four separate conferences covering EuroGP EvoApplications EvoCOP and EvoMUSART topics. Parallel Problem Solving from Nature abbreviated PPSN remains another major gathering point for researchers worldwide. Many dubious algorithms have been proposed recently often just copies of existing ones where only metaphor changed but algorithm itself remained identical.
Common questions
When did Alan Turing propose his method of genetic search?
Alan Turing proposed a method of genetic search in 1948. His paper remained unpublished until 1968, and he died in 1954.
Who initiated research into Evolutionary Programming within the United States?
Lawrence J. Fogel initiated research into Evolutionary Programming within the United States in 1962. He considered it an artificial intelligence endeavor involving finite state machines solving prediction problems.
What year was the journal Evolutionary Computation founded by MIT Press?
The journal Evolutionary Computation was founded by MIT Press in 1993. Several other journals dedicated to evolutionary computation emerged starting that same year or shortly after.
How did Rechenberg and Schwefel initially perform calculations for evolution strategies?
Initially this optimization technique performed without computers relying instead on dice to determine random mutations. By 1965 calculations were performed wholly by machine allowing for greater precision and speed.
Which three branches emerged from early efforts in evolutionary computing during the 1950s and 1960s?
Three branches emerged in different places to attain this goal: evolution strategies, evolutionary programming, and genetic algorithms. A fourth branch called genetic programming eventually emerged in the early 1990s.
All sources
22 references cited across the entry
- 1bookEvolutionary Computation: A Unified ApproachKenneth A. De Jong — MIT Press — 2006
- 2bookComputational Intelligence: A Methodological IntroductionRudolf Kruse — Springer International Publishing — 2022
- 3citationIntroduction to Soft ComputingDevenda K. Chaturvedi — Springer — 2008
- 4citationEvolutionary Computing: The OriginsA. E. Eiben et al. — Springer — 2015
- 5arxivEvolutionary Turing in the Context of Evolutionary MachinesMark Burgin et al. — 2013-04-12
- 6bookEvolutionary computation : the fossil recordIEEE Press — 1998
- 7citationKybernetische Systemanalyse Einer Tuchfabrik zur Einführung Eines Computergestützten Dispositionssystems der FertigungThomas Fischer — Springer Berlin Heidelberg — 1986
- 8bookAn Introduction to Genetic AlgorithmsMelanie Mitchell — The MIT Press — 1998
- 9journalEsempi Numerici di processi di evoluzioneNils Aall Barricelli — 1954
- 10journalMonte Carlo analyses of genetic modelsFraser AS — 1958
- 11bookGenetic Programming: On the Programming of Computers by Means of Natural SelectionJohn R. Koza — MIT Press — 1992
- 12bookNew Optimization Techniques in EngineeringGodfrey C. Onwubolu et al. — Springer — 2004-01-21
- 13journalTools for intelligent control: fuzzy controllers, neural networks and genetic algorithmsJamshidi M — 2003
- 14webEc Bestiary: A Bestiary Of Evolutionary, Swarm And Other Metaphor-Based AlgorithmsFelipe Campelo et al. — 2018-06-20
- 15journalA critical problem in benchmarking and analysis of evolutionary computation methodsJakub Kudela — 2022-12-12
- 16bookThe Stanford Encyclopedia of PhilosophyMetaphysics Research Lab, Stanford University — 2016
- 17journalElastic Multi-scale Mechanisms: Computation and Biological EvolutionJ.G. Diaz Ochoa — 2018
- 18journalBacteria as computers making computersA. Danchin — 2008
- 19arxivWho is the best connected EC researcher? Centrality analysis of the complex network of authors in evolutionary computationJ.J. Merelo and C. Cotta — 2007
- 20bookArtificial Intelligence, Evolutionary Computing and MetaheuristicsMark Burgin et al. — Springer-Verlag — 2013
- 21journalEvolutionary Automata: Expressiveness and Convergence of Evolutionary ComputationM. Burgin et al. — 2012
- 22book2009 IEEE Congress on Evolutionary ComputationEugene Eberbach et al. — IEEE — 2009