Genetic Algorithms

This week we're going to look at something (seemingly) completely different. We're going to investigate genetic algorithms, the idea that brought John Holland a MacArthur Fellowship.

Readings and tasks

Some of these readings may be redundant, but they approach the problem from different perspectives; further, this can be a difficult topic to understand and a bit of redundancy might help you gain a bit more traction with the subject.

  1. Read "Finding decision rules with genetic algorithms"
  2. Read "Genetic algorithms: Principles of natural selection applied to computation" by Forrest
  3. Read "Complex adaptive systems" by Holland
  4. Read the Introduction to genetic algorithms.

Questions

Be prepared to answer and discuss the following questions:

  1. What is the purpose of a genetic algorithm?
  2. What does one particular gene represent?
  3. How does the population evolve?
  4. Is the genetic algorithm deterministic or stochastic?
  5. What purpose does evolution serve?
  6. Describe the four properties and three mechanisms that are common to all complex adaptive systems and, specifically, how they apply to genetic algorithms.
  7. How does adaptation come about? That is, how is it that later generations generally produce better-performing individuals than earlier generations?
  8. Think of a problem that a GA might help you solve. Set up the encoding.

Resources

These are some more resources that introduce genetic algorithms.

  1. Hidden order: How adaptation builds complexity, by John H. Holland. Helix Books 1995.
  2. Gentic algorithms in search, optimization, and machine learning, by David E. Goldberg. Addison Wesley Longman, 1989.
  3. GA Tutorial (the original version is somewhere on the Web but I can't find it anymore): This 74-page technical note from the National Center for Atmospheric Research explains genetic algorithms in the context of other optimization techniques. It is a great place to begin if you're interested in doing more in-depth work with GAs.
  4. Good books and articles on genetic algorithms:
  5. Center for the Study of Complex Systems (here at the University of Michigan) — Good set of related links
  6. GA Software
  7. Stanislaw Ulam
  8. BACH group
  9. If you are going to use genetic programming, then you need to look at the information on Learning LISP.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License