James Marshall
| Summary | Students implement a genetic algorithm in Python to evolve cleaning strategies for Robby the Robot, as described in Chapter 9 of Melanie Mitchell's book Complexity: A Guided Tour. Robby's task is to collect empty soda cans that lie scattered around his rectangular grid world, by following instructions encoded as 243-character genome strings. An easy-to-use graphical simulator written in Python is included with the assignment, which avoids the need for students to write one themselves, allowing them to focus on implementing the core ideas of the GA. This assignment can serve as a sequel to the Model AI Assignment "A Simple Genetic Algorithm". |
| Topics | Genetic algorithms, evolutionary computation |
| Audience | Undergraduate students in an introductory AI or Machine Learning course, with at least one semester of programming experience in Python. Also suitable as a late CS1 or early CS2 programming assignment. |
| Difficulty | Easy to medium difficulty. Can be completed in 1-2 weeks. |
| Strengths | The simulator makes it easy to watch Robby's behavior improve dramatically over time as the GA evolves, providing students with immediate and satisfying visual confirmation that simulated evolution really works. The conceptual pieces of a genetic algorithm are easy to understand, and can be implemented and tested in an incremental, modular fashion. |
| Weaknesses | The simulator only works with Python 2, although porting it to Python 3 would be straightforward. Python-based GAs tend to be slow, so evolving good strategies can take a long time. Because GAs are inherently probabilistic, debugging can be challenging and sometimes frustrating. |
| Dependencies | Students should have at least one semester of programming experience, preferably in Python. No prior knowledge of GAs is needed. The simulator requires Python 2, and John Zelle's Python graphics library (included in the simulator code). The assignment requires students to read Chapter 9 of Melanie Mitchell's book Complexity: A Guided Tour (a PDF is included in the assignment materials). |
| Variants | There are many potential avenues available for experimenting with or extending the GA, such as by varying crossover and mutation rates or population size, adding elitism, trying out different selection strategies, analyzing evolved strategies by observing the effect of changing certain "genes", monitoring the amount of "genetic drift" in the population over time for certain genes, and so on. |