Core Ideas of Genetic Algorithms
The original genetic algorithm suggested by John Holland was influenced by Ronald Fisher's classic book, 'The Genetical Theory of Natural Selection', which integrated genetics with Darwinian selection. Holland wanted to develop a general theory of adaptation with this philosophical background. He was also influenced by several other theories such as evolutionary biology, economics, game theory, and control theory. Some of them will be covered later in this blog in detail. After studying these theories, he focused on populations of agents. They should continually obtain information from changing environments and use it to improve the chance of survival.
John Holland's original genetic algorithm was started from following several core ideas.
Population, Sample and Implicit Parallelism
Holland interpreted evolution as a statistical phenomenon for population dynamics. In particular, he introduced the concept of search space. Basically, a population is an independent sample of many individuals. However, as the sample passes over time, it is biased to the high-fitness regions of the search space.
He also viewed the population as an implicit sample in a much larger space with the traits that individuals show. Holland described this implicit large-scale sampling of traits using the term "implicit parallelism".
Building Blocks and Recombination
As population undergoing adaptation, individuals construct a set of traits (evolutionary atoms) related to each individual's fitness or performance. Holland called these 'building blocks'. Successful individuals can be found at each stage. The first step is to find useful building blocks by stochastic sampling and recombine them over time to find higher-fitness individuals in more complex building blocks.
Exploitation vs. Exploration
Holland has defined 'exploitation' as propagation of successful building blocks within the population and defined 'exploration' as existing building blocks are recombined or mutated into new forms. It is at the heart of his argument that successful adaptation occurs in the balance between exploitation and exploration. To deal with this balance, he introduced "two-armed bandit problem" strategy. The multi-armed bandit problem first introduced by Herbert Robbins in 1952 and it is a very important theory in the probability theory.
Suppose there are slot machines with two arms. Each of these slot machines has an unknown payoff probability, and how you draw determines the total payoff you will take. Of course you try to maximize your payoff. There is a wide range of interpretations and attempts to address this problem. Holland suggests that the optimal strategy is to try observed best arm with a slightly higher probability than the worse arm than exponentially higher betting on it.
Further, he thought that the arms of the slot machine and building blocks in the population were similar. Evaluating each individual in the environment is analogous to pulling a selected arm in a multi-armed bandit. The problem here is how to optimally allocate trials for different arms. The information given here is the observed payoffs. It is same issue how to sample them in a large space of possible building blocks based on an estimated contribution of fitness.
In fact, this problem is still a statistical problem that can not be solved explicitly. Holland's core idea is that nearly optimal building-block sampling occurs implicitly, and this process is the emergent property of evolutionary population dynamics.
From these core ideas, Holland published several papers and influential 1975 book, "Adaptation in Natural and Artificial Systems". He tried to explain these ideas mathematically. And this led to invention of genetic algorithms that featured stochastic population-based search and inter-individual crossover as a critical operation on building blocks that can undergo recombination and testing under new contexts.
References
Adaptive Computation: The Multidisciplinary Legacy of John H. Holland
I'm a Bandit : Multi Arm Bandits and the Explore/Exploit trade-off
John Holland's original genetic algorithm was started from following several core ideas.
Population, Sample and Implicit Parallelism
Holland interpreted evolution as a statistical phenomenon for population dynamics. In particular, he introduced the concept of search space. Basically, a population is an independent sample of many individuals. However, as the sample passes over time, it is biased to the high-fitness regions of the search space.
Building Blocks and Recombination
As population undergoing adaptation, individuals construct a set of traits (evolutionary atoms) related to each individual's fitness or performance. Holland called these 'building blocks'. Successful individuals can be found at each stage. The first step is to find useful building blocks by stochastic sampling and recombine them over time to find higher-fitness individuals in more complex building blocks.
Exploitation vs. Exploration
Holland has defined 'exploitation' as propagation of successful building blocks within the population and defined 'exploration' as existing building blocks are recombined or mutated into new forms. It is at the heart of his argument that successful adaptation occurs in the balance between exploitation and exploration. To deal with this balance, he introduced "two-armed bandit problem" strategy. The multi-armed bandit problem first introduced by Herbert Robbins in 1952 and it is a very important theory in the probability theory.
Suppose there are slot machines with two arms. Each of these slot machines has an unknown payoff probability, and how you draw determines the total payoff you will take. Of course you try to maximize your payoff. There is a wide range of interpretations and attempts to address this problem. Holland suggests that the optimal strategy is to try observed best arm with a slightly higher probability than the worse arm than exponentially higher betting on it.
 |
| from primarydigit.com |
Further, he thought that the arms of the slot machine and building blocks in the population were similar. Evaluating each individual in the environment is analogous to pulling a selected arm in a multi-armed bandit. The problem here is how to optimally allocate trials for different arms. The information given here is the observed payoffs. It is same issue how to sample them in a large space of possible building blocks based on an estimated contribution of fitness.
In fact, this problem is still a statistical problem that can not be solved explicitly. Holland's core idea is that nearly optimal building-block sampling occurs implicitly, and this process is the emergent property of evolutionary population dynamics.
From these core ideas, Holland published several papers and influential 1975 book, "Adaptation in Natural and Artificial Systems". He tried to explain these ideas mathematically. And this led to invention of genetic algorithms that featured stochastic population-based search and inter-individual crossover as a critical operation on building blocks that can undergo recombination and testing under new contexts.
References
Adaptive Computation: The Multidisciplinary Legacy of John H. Holland
I'm a Bandit : Multi Arm Bandits and the Explore/Exploit trade-off
Comments
Post a Comment