4. Cellular Automata and Fractal Evolution

4.D. Genetic Algorithms and Artificial Evolution

The best Artificial Intelligence results involve neural nets, computing modeled on the architcture of the brain.

Pursuing the biological paradigm further, John Holland developed genetic algorithms, computer programs that can be used to solve problems by evolution.

The basic genetic algorithm has seven steps. (Classifier system, fitness, crossover, and mutation will be described soon.)

1. Express solutions as a sequence of yes-no questions (a classifier system for the problem).

2. Start with a random initial distribution of proposed solutions, sequences of answers to the yes-no questions.

3. Try each proposed solution on test case problems.

4. The fitness of each proposed solution is how well it performs on the test cases.

5. Remove the least-fit members of the population.

6. Reward the most-fit by letting them reproduce by crossover, with occasional mutation.

7. Repeat steps 3-6 on the new population.

First, a classifier system is a way to encode possible solutions in a fashion similar to the storage architecture of genetic information.

Next, the fitness represents the success of a proposed solution with the test problems. Often this is thought of, at least metaphorically, as a landscape.

The first genetic operation we use is crossover.

In addition, we use mutation.

Here is an application of genetic algorithms to a problem involving cellular automata.

Genetic algorithms have been used to solve a variety of design and optimization problems. In addition to the walking robots mentioned earlier, here are two interesting recent variations.

Genetic algorithms applied to circuit design Can a few thousand generations of machine evolution discover design possibilities undetected by a few thousand electrical engineers?

Genetic algorithms applied to art Evolution, but is it art?.