James Marshall
| Summary | Students implement a simple genetic algorithm in Python to evolve binary strings of 0s and 1s. This assignment is essentially Computer Exercise #1 from Chapter 1 of Melanie Mitchell's book An Introduction to Genetic Algorithms. Because GAs are inherently probabilistic, debugging them can prove challenging and frustrating to students. Therefore the assignment includes a robust tester program that can be used by students and instructors alike to detect bugs in students' code, which increases the chances that students will implement their GA correctly. This assignment can serve as a prequel to the Model AI Assignment "A Genetic Algorithm for Robby the Robot". |
| Topics | Genetic algorithms, evolutionary computation |
| Audience | Undergraduate students in an introductory AI or Machine Learning course, with some prior programming experience in Python. Also suitable as a CS1 programming assignment. |
| Difficulty | Easy. Can be completed in 1 week. |
| Strengths | The conceptual pieces of a genetic algorithm are easy to understand, and can be implemented and tested in an incremental, modular fashion. This assignment provides significant structure by breaking the GA implementation into 8 building blocks, corresponding to 8 Python functions that can be written and tested separately. The required input/output behavior of each function is specified in the assignment description. Except for the main top-level GA function, each building block can be tested by a robust automated tester program that is capable of detecting many subtle problems in students' code, including: not performing crossover entirely correctly, performing mutation with a higher or lower probability than expected, selecting genomes from the population in a way that does not correspond to their fitness, etc. Students can use the tester to receive immediate feedback as they develop their code. The tester also makes grading the assignment considerably easier for the instructor. |
| Weaknesses | Students must use Python. The tester program is only available for Python 2, although porting it to Python 3 would be straightforward. |
| Dependencies | Students should have some prior programming experience in Python. No prior knowledge of GAs is needed. The tester program requires Python 2. |
| 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 such as tournament selection, and so on. |