Overview

Genetic algorithms explore the hypothesis space in search of a best hypothesis to solve a problem through the manipulation of a string representation of those hypotheses. Inspired by biological evolution, parts of good hypotheses are combined and used with limited exploration to evolve new hypotheses similar to how different genes could potentially be combined into better chromosomes making a better creature.


This project presents an interactive game environment where the player (student) has to evolve members of a tribe of creatures, Modabus, in order to have the correct genetic makeup to overcome an obstacle impacting their society. Through manipulation of crossover, mutation, and selection the player (student) will guide the genetic algorithm to find a solution (a Modabu citizen with the proper level of intelligence, strength, and speed to overcome each obstacle) over the course of three increasingly difficult levels.

Modabu artwork by John Beck

The goal of this project is to give the student a deeper understanding of the mechanisms behind how genetic algorithms function and the impact of varying crossover, mutation, and selection. Students will gain this experience through interactive play with a game environment.
After completion of a full play session completing the 3 different levels of the game the student should have gained the following knowledge:
  • An understanding of the impact of single, multiple, and uniform crossover on a genetic algorithm.
  • An understanding of the impact of mutation on the exploration of the hypothesis space.
  • How selection and fitness impact a genetic algorithm.
  • Program the fitness, selection, and attribute encoding elements of a genetic algorithm.
  • An understanding of the problems and complexities associated with genetic algorithms.
Students should have a familiarity with basic programming concepts. In-game programming will be in the Python language, so basic knowledge of Python would be helpful. In-game programming is guided, so a lack of knowledge or experience in Python will not prevent completion, but it may take longer for those students since they will have to learn strategic elements of Python.

Along with the project, the student should cover the recommended background reading below.
For a more detailed introduction to genetic algorithms, we recommend the parallel reading of a good AI textbook section on search and genetic algorithms. For example, one might assign section 4.3 ("Local Search Algorithms and Optimization Problems") of:
  • Stuart Russell and Peter Norvig. Artificial Intelligence: a modern approach, 2nd ed. Prentice Hall, Upper Saddle River, NJ, USA, 2003.
For more advanced and deeper coverage of genetic algorithms, we suggest Chapter 9 ("Genetic Algorithms") of:
  • Tom Mitchell. Machine Learning, McGraw-Hill, Boston, MA, USA, 1997.
The detailed project description is available in the PDF file Understanding Genetic Algorithms through Interactive Play.pdf. You will need the free Adobe Acrobat Reader to view this file.
A sample syllabus used at the University of North Carolina at Charlotte when this project was assigned is available at:
  • Syllabus for AI Course at the University of North Carolina at Charlotte
  • Syllabus for a Machine Learning Course at the University of North Carolina at Charlotte
  • Syllabus for the AI section of a Game Design & Development Course at the University of North Carolina at Charlotte

Additional readings are included in the Background section above.