MUTANTS

A generic genetic algorithm toolkit for Ada 95

pdf, postscript

This is my senior honours project completed for 28th of April 1997. Little has been changed for this online with the exception of a dynamic Java demonstration applet to provide a demonstration of genetic algorithms. Printable version of the project are available, both complete and separately for report and appendices.

Many thanks to Bill Findlay for suggesting the topic in the first place and providing guidance throughout the project. Thanks to Cordelia Hall from whom I borrowed the violin music notation example and who provided me with test data. And finally to my father for accidentally getting me interested in the whole concept of artificial life and genetic algorithms.

There are many computationally hard problems to which no algorithm exist that can find an optimal solution in a reasonable time. Genetic algorithms offer a shortcut, able to produce good but not perfect results much faster. They are based on the principles of natural evolution and use selective breeding on a population of potential solutions to gradually derive more successful solutions. Designing the best algorithm for the job is difficult because of the wide variety of possible variations. This paper presents a genetic algorithm toolkit which provides a library of components which can be connected together to form many basic algorithms and then customised for any particular problem.

Contents

pdf, postscript

1. Introduction
2. Genetic Algorithms
   1. Nature's Genetics
   2. Computational Genetics
   3. Basic Algorithm
   4. Genetic Theory
   5. Vector Representation
   6. Messy Representation
   7. Improved Initialisation
   8. Competitive Fitness
   9. Breeding Techniques
3. Toolkit Design
   1. Information Flow
   2. Toolkit Components
   3. Breeding Model
   4. Fitness Function
   5. Parent Selector
   6. Individual Creator
4. Travelling Salesman Problem
   1. Salesman's Job
   2. Standard Decomposition
   3. Toolkit Performance
5. Violin Music Notation
   1. Violins and Bows
   2. Problem Analysis
   3. Algorithm Success
6. Conclusions
   1. Success and Failure
   2. Further Work
   3. Summary
7. Bibliography

Appendices

pdf, postscript

1. Problem Definition
2. Statement of Requirements
3. External Specification
4. Class Design
5. Maintenance Document
6. Status Report
7. Summary Log
8. Project Code

Here is some material which was not presented with the project:

• Frequently Asked Questions
• Genetic Algorithm Applications