> CS > AI > Sub-symbolic > CI > EC > AE > EA > Genetic Algorithms:
Genetic Algorithms provide a way to search a large space of possible solutions in a near-optimal way, using 4 Bio-Darwinian methods:
1. Natural Selection (find the members of the population with the best fitness)
2. Reproduction (replicate those members of the population identified to have the best fitness)
3. Crossover (cross-breed two parent chromosomes at a random point to produce new offspring)
4. Mutation (randomly change bits within a chromosome)
Koza's Genetic Programming, Figure 3.1
Natural selection and reproduction result in a definite performance improvement within the population, but just using these two methods limits the potential players in the realm of all possible solutions. Basically the existing best persist and reproduce and the not-so-good go extinct, but if the optimal solution was not in the population to begin with, it could never be found because there is no variation.
"Natural selection does not create variety. It merely selects from whatever variety is already present in the population in order to increase the average fitness of the population as a whole" (pg. 48).
Crossover and mutation are necessary evils in that they slightly degrade the overall optimization, while opening up the possibilities toward discovering better solutions that were not present in the original population.
"The genetic crossover operation serves the necessary function of creating promising new individuals in the search space" (GP, pg. 48).
So, by keeping relatively low levels of crossover and mutation within the GA architecture, new solutions can be discovered while still allowing natural selection and reproduction to keep the balance tilting toward an optimal solution.
"The allocation of future trials is most nearly optimal when [crossover and mutation rates] are both small. A schema with a relatively short defining length and a relatively few defined positions is a building block which will be propagated from generation to generation at close to the near-optimal rate. The genetic algorithm processes such schema most favorably. A problem whose solution can be incrementally built up from schemata of relatively short defining length and relatively few defined positions is handled by genetic algorithms in a near-optimal way" (pg. 49).
The interesting thing about the genetic algorithm is that it is a domain independent process and can find near-optimal solutions without even storing a memory of the solution's lineage. The only prerequisite is for the problem to be defined in terms the GA can "understand."
This prerequisite can be fulfilled by applying a simple 4-step process to any problem (pp. 53-54):
1. Select the representation scheme.
This often includes transitioning problem parameters to binary strings. This is an ideal way to present the problem to the GA as a "chromosome" ripe for reproduction, crossover and mutation.
2. Identify the fitness measure.
This step is crucial to defining what the problem is seeking to achieve.
3. Define control parameters and variables.
Here is where the population, bit string length, and generations to be run are defined.
4. Define when / how the run will be terminated and what will be designated as the best result.
References:
Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press.
Links:
Genetic Algorithms on Wikipedia