Overview

Reports on the industrial application of genetic algorithms (GAs) and related "biologically inspired" search methods appear frequently in the popular science and engineering press. At a superficial level, anyone familiar with the theory of natural selection can imagine how a difficult search problem might be attacked by combining the elements of reasonably good solutions and randomly mutating the resulting "offspring" to preserve variety. At a deeper level, there is often a disconnect between these real-world problems and the kind of problems that students can be expected to attack in an undergraduate AI or machine-learning course. Once students are ready to move beyond the toy problems and easy-to-code algorithms from the introductory phase of the course, they are likely to be faced with an unappealing set of options: wade through and re-factor a poorly-documented source code written for a different problem, purchase a commercial package, or start a lengthy and complicated project from scratch.

The primary aim of this project is to develop a set of tools to make state-of-the-art genetic algorithms available to undergraduate students with little or no AI background. The target audience includes both computer science majors and students in the natural sciences (biology, geology) and engineering interested in applying GAs to their own research areas. Because of its popularity in undergraduate teaching and professional applications, the Python programming language will be used. The project will focus on the following two themes:
  1. Current multi-objective optimization (MOO) approaches like the Nondominated Sorting GA II (NSGA II; Deb 2000), which will be provided to students as a simple application programming interface (API). Students will focus on implementing the Simple Genetic Algorithm (SGA; Mitchell 1998) in Python, and then comparing it to an implementation of NSGA-II written by the faculty member, using benchmark problems from the GA literature.


  2. Current solutions to benchmark GA problems like the evolution of controllers for pole-balancing (Geva & Sitte 1993). Students will learn the basics of the NEAT (NeuroEvolution of Augmenting Topologies) algorithm (Stanley & Miikkulainen 2001), and will then have the opportunity to see the algorithm at work by training teams of agents in the newly-released version 2.0 of the NERO (Neuro-Evolving Robotic Operatives) video game (Stanley et al. 2005).
The learning objectives of the project are:
  • Learning the basics of genetic algorithms and the problems associated with them (e.g., overspecialization, the No Free Lunch Theorem).
  • Appreciating (and overcoming) the difficulties associated with scaling up the basics to problems in the real world.
  • Better understanding of broader AI concepts such as reinforcement learning and search.
Students should have basic knowledge of algebra and should have some experience writing programs in Python.
For an introduction to genetic algorithms, students can read:
The material in this book provides sufficient background to understand the current GA literature, including this essential article on the NSGA-II algorithm: For a concise description of the pole-balancing task and how the NEAT algorithm solves it, students can read the following article:
The detailed project description is available in the PDF file GeneticAlgorithms.pdf. You will need the free Adobe Acrobat Reader to view this file.
This project is customizable to accommodate different approaches to teaching and different implementations. Additional exercises are also included for students seeking more extended challenges.
A sample syllabus used at Washington & Lee University when this project was assigned is available at:
Syllabus for AI Course at Washington & Lee University

Additional readings are included in the Background section above.