Genetic Algorithm: The Beginning
The discovery of the DNA double helix structure and the decoding of the genetic code was a tremendous event revealing the secrets of the mysterious phenomenon of evolution. So these discoveries directly or indirectly influenced various disciplines without affecting biology alone. Computer science was no exception.
The first case of computer simulation of evolution was Nils Aall Barricelli's 1954 work. He did this using a computer at the Institute for Advanced Study in Princeton and published a paper entitled "Symbiogenetic evolution processes realized by artificial methods." This paper did not attract much attention.
Computational simulation of evolution was well known to public since Alex Fraser, an Australian quantitative geneticist, published several papers since 1957. He has published series of simulation papers on artificial selection of living organisms with multiple loci controlling a measurable trait. Many of the simulation studies published by Fraser are considered to have almost all of the key elements in comparison with modern genetic algorithms. Fraser and many other biologists have begun to study computer simulation of evolution in the 1960s. I will briefly introduce some important researches from them.
Hans-Joachim Bremermann is one of the scholars who left a very important footprint in this period. He published various solutions including optimization problems, recombination, mutation, and selection in the 1960s. His work on genetic algorithms is well documented in "Optimization Through Evolution and Recombination," published in 1962 in Self-Organizing Systems. In this paper, he argues that evolution schemes can be applied to non-convex programming or even in machines that learn to play games or recognize patterns. The group that left another important milestone is the study of Ingo Rechenberg and Hans-Paul Schwefen in the 1960s and early 1970s. They used artificial evolution as a kind of optimization method and used it to solve complex engineering problems. These studies are better known as evolution strategies. Lawrence J. Fogel's evolutionary programming technique was also very important. He applied this technique as one of solutions for artificial intelligence, which is used for predicting environments, and used variation and selection to optimize the predictive logics. With this in mind, he published the book "Artificial Intelligence Through Simulated Evolution" in 1966 with Alvin J. Owens and Michael John Walsh. Due to his accomplishments, he is called "the father of evolutionary programming".
However, 'the beginning' that genetic algorithms have taken to a firm place as an important artificial intelligence technology is John Holland's 1970s researches. Holland considered adaptation the most important. Populations of agents that continuously acquire information from uncertainty and change the environment are crucial, and they can improve performance and ultimately increase the chances of survival. Holland also asserted that adaptation must be continuous and open ended. He believed that adaptive systems could not reach equilibrium and that there is no optimal configuration. His emphasis on open-ended, non-equilibrium dynamics has been in sharp contrast to the mainstream scientific goals which put emphasis on stable equilibrium dynamics. He thought the system in stable equilibrium was essentially dead. Holland’s influential 1975 book "Adaptation in Natural and Artificial Systems" showed these ideas could be expressed mathematically. His approaches including stochastic population-based search and crossover between individuals became the most important building blocks in genetic algorithms.
I will explain core ideas of John Holland's adaptation more in next post.
References
Optimization Through Evolution and Recombination
Adaptive Computation: The Multidisciplinary Legacy of John H. Holland
The first case of computer simulation of evolution was Nils Aall Barricelli's 1954 work. He did this using a computer at the Institute for Advanced Study in Princeton and published a paper entitled "Symbiogenetic evolution processes realized by artificial methods." This paper did not attract much attention.
Computational simulation of evolution was well known to public since Alex Fraser, an Australian quantitative geneticist, published several papers since 1957. He has published series of simulation papers on artificial selection of living organisms with multiple loci controlling a measurable trait. Many of the simulation studies published by Fraser are considered to have almost all of the key elements in comparison with modern genetic algorithms. Fraser and many other biologists have begun to study computer simulation of evolution in the 1960s. I will briefly introduce some important researches from them.
Hans-Joachim Bremermann is one of the scholars who left a very important footprint in this period. He published various solutions including optimization problems, recombination, mutation, and selection in the 1960s. His work on genetic algorithms is well documented in "Optimization Through Evolution and Recombination," published in 1962 in Self-Organizing Systems. In this paper, he argues that evolution schemes can be applied to non-convex programming or even in machines that learn to play games or recognize patterns. The group that left another important milestone is the study of Ingo Rechenberg and Hans-Paul Schwefen in the 1960s and early 1970s. They used artificial evolution as a kind of optimization method and used it to solve complex engineering problems. These studies are better known as evolution strategies. Lawrence J. Fogel's evolutionary programming technique was also very important. He applied this technique as one of solutions for artificial intelligence, which is used for predicting environments, and used variation and selection to optimize the predictive logics. With this in mind, he published the book "Artificial Intelligence Through Simulated Evolution" in 1966 with Alvin J. Owens and Michael John Walsh. Due to his accomplishments, he is called "the father of evolutionary programming".
However, 'the beginning' that genetic algorithms have taken to a firm place as an important artificial intelligence technology is John Holland's 1970s researches. Holland considered adaptation the most important. Populations of agents that continuously acquire information from uncertainty and change the environment are crucial, and they can improve performance and ultimately increase the chances of survival. Holland also asserted that adaptation must be continuous and open ended. He believed that adaptive systems could not reach equilibrium and that there is no optimal configuration. His emphasis on open-ended, non-equilibrium dynamics has been in sharp contrast to the mainstream scientific goals which put emphasis on stable equilibrium dynamics. He thought the system in stable equilibrium was essentially dead. Holland’s influential 1975 book "Adaptation in Natural and Artificial Systems" showed these ideas could be expressed mathematically. His approaches including stochastic population-based search and crossover between individuals became the most important building blocks in genetic algorithms.
I will explain core ideas of John Holland's adaptation more in next post.
References
Optimization Through Evolution and Recombination
Adaptive Computation: The Multidisciplinary Legacy of John H. Holland
Comments
Post a Comment