To illustrate how a genetic algorithm works, Koza, et. al. use a process of building a mathematical function. The primordial ooze is generated with simple mathematical operations and a handful of numbers, all combined to randomly generate a population of mathematical expressions. The goal in this case is to match a curve on a graph.
The genetic algorithm repeatedly cycles through its loop to define successive generations of objects:
- Compare each expression with the final goal to evaluate fitness.
- Discard the expressions that least fit the goal.
- Use crossover to generate the next generation of expressions.
- Simply copy some expressions--as is--to the next generation.
- Add some expressions with random mutations into the next generation.
An example of crossover might be the combination of expressions
3x + 4 / (x - 5) and 4x^2 - 9x + 3
to create offspring that might look like
4x^2 + 3x + 4, or 9x + 3(x-5)
where a part or parts of one expression are mixed and matched with the other expression. The genetic algorithm would select those offspring that are closer to matching the goal for the next generation, and leave the rest for extinction.
Some objects are copied "as is" and sent to the next generation, and others are randomly mutated. An example of a mutation my involve "9x + 3" combined with a randomly chosen "+", "4", "^2" and maybe another "3", to create an abomination like (4 + 3) ^2 (9x + 3).
"These genetic operations progressively produce an improved population of mathematical functions."--Koza, et. al.
To expand upon the example from Koza, et. al., computer programs can be designed with the use of genetic algorithms. In this case, genetic programming algorithms might create or delete subroutines, iterations, loops, recursions, conditional branches, variable comparisons, and various other commands in the evolving population of programs. "The evolutionary process itself determines the character and content of the computer program needed to solve the problem."
The constraints of the goal might be what input to expect, and what output is expected.
One could create a genetic algorithm that takes a "primordial ooze" of variable definitions, a mass of code snippets and a propensity toward building routines, and use them to generate source code that could be repeatedly tested for "fitness" with a compiler. Depending on the error messages generated by the compiler, the genetic algorithm would then know which combinations can be sent into the next generation, and which ones into extinction.
This, of course, would be easier said than done, but it's a good illustration of how just about any system can have genetic algorithms applied to its components to achieve a better fit system.
NASA has used genetic algorithms to successfully calculate low altitude satellite orbits and more recently to calculate the positioning of the Hubble space telescope.
The control mechanisms for the bots in Quake3 were developed using genetic algorithms. These control mechanisms required complicated optimization of several variables, a job well suited to genetic algorithms.
Genetic algorithms are the brain child of John Holland, who came up with the idea in the early 60s. Incredibly, he didn't feel the need to actually try them out on a computer and instead preferred to tinker about with a pen and paper! It was only when a student of his wrote a program that ran on a home personal computer that the world finally saw what could be achieved by implementing his ideas in software.