9. Cellular Automata and other Generative Systems


We've discussed cellular automata and reaction-diffusion systems. This session we will concentrate on the Genetic Algorithm (GA). This turns out to be reasonably simple, in concept and in basic execution. The essential elements are:
  • A population of "creatures"
  • A population of genes, encoded as strings/numbers/bits, associated with each creature.
  • A "fitness function" to rate the viability of each creature.
  • A process of generation or breeding to create a new population of creatures. The process may involve mutation of the genes or exchange of genetic material and other selection processes. In general, the more viable a creature, the more likely it is to make it to the next generation or to pass on its genetic material.
There are many variations on this basic pattern.

Reading
Swarm Intelligence, an essay and photos in the National Geographic.

Assignment
Using the genetic algorithm, produce an image or text.
Write a final project proposal, due next week.

Code
GA Sample Code, Daniel Shiffman's code, with a few mods and cosmetic touches.

Resources
Mitchell Waldrop, Complexity: The Emerging Science at the Edge of Order and Chaos, Simon and Schuster, 1992. History of the Sante Fe Institute.

Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, 1998.

The Watchmaker Framework, an Open Source Java library for genetic/evolutionary programming that takes its name from Richard Dawkins' book The Blind Watchmaker.
The Traveling Salesman Problem, history, code, and theory of one of the most famous "difficult" problems. The GA has been used to solve the TSP, but it is only one approach.

3D Travelling Salesman using Genetic Algorithms, a video generating with Processing.

The TSP is typical of a class of computational problems known as "NP-complete." It is a particularity of these problems that if any one of them can be solved efficiently ("in polynomial time," to use the language of complexity theory and the analysis of computer algorithms), they can all be solved. Wikipedia is generally well-informed about computation, if you are curious, see its entry for NP-complete.

Though somewhat technical, especially at the end, this paper by Lance Fortnow from the Communications of the ACM, " The Status of the P versus NP Problem," explains some of the limits of computability.