









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 realworld problems and the kind of problems that students can be expected to attack in an undergraduate AI or machinelearning course. Once students are ready to move beyond the toy problems and easytocode algorithms from the introductory phase of the course, they are likely to be faced with an unappealing set of options: wade through and refactor a poorlydocumented 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 stateoftheart 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:
 Current multiobjective 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 NSGAII written by the faculty member, using benchmark problems from the GA literature.
 Current solutions to benchmark GA problems like the evolution of controllers for polebalancing (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 newlyreleased version 2.0 of the NERO (NeuroEvolving 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 NSGAII algorithm:
For a concise description of the polebalancing 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.













