EAAI Submission: Introduction to genetic algorithms

Chris Brooks, University of San Francisco

Summary In this project, students learn to use genetic algorithms to solve three different sets of problems. They develop techniques for selecting and crossing over populations, and learn how the mixin design pattern can be used to easily evaluate a variety of different crossover, selection, and elitism choices.
Topics Genetic Algorithms, search, constraints
Audience Intro AI
Difficulty Medium. I give students two weeks to complete this.
Strengths. Gives students a chance to easily apply GAs to non-trivial problems and easily experiment with the wide variety of design choices. Encourages them to develop a scientific approach to parameter selection and algorithm evaluation. Illustrates the use of mixins to easily modify an application.
Weaknesses Students must use Python.
Dependencies Students should be familiar with search. I give this assignment about one month into the course. Students must be comfortable with Python and OO programming.
Variants The code is constructed so that it is very easy to add other problems, such as N-queens or map coloring. Interested students can also further explore selection, mutation and crossover operators and perform experiments to evaluate their effectiveness. Depending on the time available and skill sets of the students, instructors might want to focus on a subset of this assignment.