Genetic Algorithms
Genetic Algorithms: What Is It?
Adaptation to a changing situation allows an organism to survive in an adverse environment. The organism has a distinguishable characteristic that has allowed it to thrive where the rest of its species cannot.
Reproduction will make future generations inherit this trait and hence survive.
Darwin suggested this Theory Of Evolution by Natural Selection
in 1869.
Gregor Mendel's work proved that traits are encoded into the organism's DNA as Genes, of which there are strings of chromosomes.
Since genes are generally passed to a generation if the trait has thrived in the environment, each consecutive generation will be insured to have this optimal characteristic.
Overview
This subset of AI
deals with understanding and imitating mother nature's process of biological evolution to solve complex problems
and is essentially a search for the most optimal solution.
Typical implementations are simulations requiring a:
- A population containing possible solutions to a problem.
In Nature: A generation containing traits that have been passed on from surviving parents. - Selecting which individual members are most applicable solutions. In Nature: Survival of the Fittest, the Natural Selection of the most advantageous trait.
- Recombination to create a generation with this solution. In Nature: Reproduction to produce offspring with this trait.
- Terminate when the most suitable individual is found.
Canonical Genetic Algorithm
Pioneered by John Holland (1975) and his students of the University of Michigan, this describes a strict interpretation of the model for Genetic Algorithms(GA).
GA traditionally uses a simple data structure of a Bit String to representing possible solutions to a problem where the 1 bit string is called an individual.
Decoding the Bit String into a meaningful context is a difficulty discussed here.
However Bit Strings of length N are able to represent any kind of possible data.
The next few pages provide a detailed insight into the world of Genetic Algorithms.