Introduction

Millions of telephone calls are made every day and every call requires a connection, a route through countless cables and exchanges. Routing calls is known to be a computationally hard problem and no search algorithm can find the optimal solution in a reasonable period of time. Even so we expect connections to be made in seconds rather than hours. This and many related problems can be tackled by fast probabilistic techniques which produce good but not perfect results.

Genetic algorithms have proved competent for this challenge and have been applied to a variety of problems from job scheduling to image registration. 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. A genetic representation must be chosen for the problem so that random changes and combinations can be made, the biological equivalent of mutation and crossover. Crossover combines features from successful individuals whilst mutation ensures variation and prevents the stagnation that often leads to poor solutions.

Potential solutions to the routing problem might be encoded as a list of exchanges which define the path from source to destination for each connection:

Mutation could select an alternate exchange for the list and crossover combine two previous solutions:

Each generation these solutions are evaluated and parents are selected to produce the new population. At every repetition bad solutions are weeded out and desirable solutions are encouraged. After many generations the population will, with luck, converge on some near-optimal solution.

Different problems pose different requirements for the algorithm, maximum computation time, real-world deadlines, or solution quality. Genetic algorithms can vary greatly in these and other respects depending on the choice of components. For example, an alternate mutation operator for the routing problem could have been biased towards overworked exchanges swapping them with those under less pressure. Extra time would be spent examining the exchanges but fewer generation would be required to distribute the workload. Changing just one component of an algorithm may reveal markedly different behaviour, making the design of a suitable algorithm a time consuming art form.

Previous work on genetic algorithms has followed two main paths - classic and hybrid. Classic genetic algorithms use a binary vector representation and a few standard reproduction operators. Identical algorithms can solve separate problems by their particular interpretation of the vector. Unfortunately such universal algorithms are slow to find good solutions and slower to find optimal ones. Hybrid genetic algorithms have no standard representations or operators. Instead, characteristics of the problem at hand are encoded into the algorithm to produce faster and better results but at the expense of loss of generality and additional time in writing the algorithm. For typical real world problems hybrid genetic algorithms are proving to be more effective and the additional experimentation required is worthwhile.

Despite their variety of forms, separate genetic algorithms share many common components. A unified model which organised components into independent classes would simplify algorithm design and a toolkit supporting such a model would expedite experimentation with new components and encourage software reuse. Currently toolkits and other techniques which combine many components in a systematic manner are still in their infancy. This project develops MUTANTS, a fast-prototyping object-oriented toolkit defining a range of generic classes containing several predefined components. New problems, outside the normal range of the toolkit, can be solved by extending existing classes.

The main goals of this project are to create a unifying model for genetic algorithms, design a toolkit based on this model, and demonstrating its flexibility with three example algorithms.

When reading this report it is helpful to have some understanding of computationally hard problems which necessitate the use of probabilistic techniques. The basic principles of genetic algorithms are introduced by the report but more extensive knowledge is useful when considering some aspects of toolkit design. Object-oriented design techniques are used but not discussed within the report. These techniques allow both functionality and state information to be encapsulate together inside genetic algorithm components.

The remainder of this project introduces genetic algorithms, discusses the design issues behind the toolkit, and demonstrates its flexibility with some example algorithms.

• Chapter 2 - introduces genetic algorithms, the concepts and terminology
• Chapter 3 - follows the development of the toolkit's unifying model
• Chapter 4 - implements the classic Travelling Salesman Problem using toolkit components
• Chapter 5 - develops the experimental components required to solve an optimisation problem for violin music notation
• Chapter 6 - summaries the successes and failures of this project and describes further work that they suggest