« 3.6 Neural Networks | HomePage | 3.7 Genetic Algorithms »
Friday, June 03, 20051117820100
3.7 Genetic Algorithms
Note: This is an excerpt from a draft of my thesis, A Computer Model of National Behavior. The introduction and table of contents
are also available
3.7 Genetic Algorithms
Genetic Algorithms (GAs) is a type of evolutionary algorithm (EA). Heitkotter describes EAs as “computer-based problem solving systems which use computational models of some aspects of known mechanisms of [evolution] as key elements in their design and implementation.” Like neural networks, EAs are based on biology. Indeed, a work from Brunel University states that the field was pioneered by John Holland who read a book on genetics while working on neural network research in the 1950s. EAs work by keeping a population of data structures. This population can change by deaths and reproduction.
There are two main differences between EAs in general and GAs in particular. First, GAs are always made up of chromosomes. Essentially, chromosomes are sets “of character strings that are analogous to the base-4 chromosomes that we see in our own DNA.” Like in DNA the pieces of data contained in chromosomes are called alleles. Thus chromosomes are no more than data structures, and GAs are simulations composed of data structures.
The second difference is that chromosomes are normally fixed-length in GAs. This allows for simple and mechanical manipulation of the alleles by basic operators. There are some GAs where the chromosomes are variable length, but Heitkötter and Beasley note that the majority off models are fixed. GA systems that do allow variables lengths are often “genetic programming” systems, which are discussed in the next section.
To visualize the genetic process for GAs, imagine two arrays of values. Say one had the values (1,2,3) and the other had (7,8,9). If they would breed, the children would inherit from both parents. So a possible child value is (1,2,9). Visually
Figure 7. Genetic Algorithms Demonstration
GAs are based on the idea of evolution by selection where changes in a population result from the elimination of unfit members and the proliferation of fit members. This selection can be natural and caused by the environment, or intentional as ranchers and botanists artificially select for specific traits.
Specifically, new generations are created either by asexual reproduction (like when one cell splits into two identical cells) or sexual reproduction (like when children are the result of mixing of genetic material from their parents). In both of these cases, mutations (which are random changes in the genetic code) allow children to be different from their parents. Most of the time these mutations will be neutral or harmful. However, sometimes they will give the child a competitive advantage, allowing it to survive longer and have more children. Less fit members of the population may be killed off, which decreases the competitive pressures on more fit members. Thus over time, the population will be more fit for their environment. “Fitness” is a relative term because a change in the environment can cause many formerly fit members to die out. In a changing environment whole populations can become extinct.
Selection is the termination of unfit members. This culling can be done in one of two ways. One way is to calculate the fitness value for each member and allow the members with the highest fitness value to live on and multiply. This may be probabilistic to keep up a level of diversity and allow for the vagaries of chance. Another way is “tournament selection.” Tournament selection is more realistic and relies on direct competition between members of the population. In reality in any model there has to be some abstraction, and every model is a combination of these.
This model relies on genetic algorithms for the following reasons.
Firstly, genetic algorithms do not distort the model. They do not suffer from the problem of neural networks, where cognition is assumed to occur somewhere. Instead, nations are treated as simple creatures that can behave complexly. Just as bacteria act and evolve without any cognition, Beer shows nations play on their stage with just the tools available to them. “Successful nations are selfish... There is an environment. Units must adapt to it.” Occam's Razor states that we should make no more assumptions than needed, and genetic algorithms allow us to do this.
Secondly, genetic algorithms provide all the functionality needed by the model. Nations have attributes which are their genetic code. New nations can splinter off from old nations (asexual reproduction) or as the result of mixing of many old nations (sexual reproduction). There is uncertainty when the attributes of the child are being formed, which is mutation. Some nations die off and some nations leave no descendants, so there is a selection mechanism at work. In short, necessary features of nations clearly exist in any genetic view of nations.
Lastly, genetic algorithms provide a population-environment feedback mechanism. As nations evolve and the population becomes more fit, the environment itself will change. Life as a nation among unfitnations is much safer than life as the same nation among morecompetitive nations. Fit nations would be more effective atgathering resources (places, magnitude, etc.),and so new strategies would be needed. A nation could merely keepoptimizing for the old environment, or could become a “predator”and attempt to gain by the loss of others by becoming moreaggressive. As nations optimize for this new environment, however,countermeasures will be developed and the situation will change again. Genetic algorithms provide a clean way to allow for this dynamic without adding new elements to the model. A cause of this fragility is the unscientific nature of GP development.
For these reasons, nondistortion, functionality, and feedback, GAs provide the best approach to modeling nations.
Computer Science Thesis Index
12:35 Posted by Dan tdaxp in Thesis | Permalink | Comments (0) | Email this