SSP 1998 Project Summary:
[EPCC home] [SSP home] [2001 projects] [2000 projects] [1999 projects] [1998 projects] [1997 projects] [1996 projects] [1995 projects] [1994 projects] [1993 projects]

VisualGA: Visualisation of a Genetic Algorithm

Student

Ruth Durie, University of Edinburgh

Supervisors

Kira Smyllie, EPCC

Roger Hare, EPCC

The project will involve designing and implementing a visual simulation of a genetic algorithm (GA). This will be used in the first instance as a teaching aid for tutorials on genetic algorithms to facilitate understanding of how and why GAs work.

GAs are a novel computing area used, for example, in optimisation. They have been applied in complex areas such as scheduling, bin packing, graph colouring, set covering and travelling salesman problems. The method is particularly relevant to high performance computing as GAs are highly suited to parallelisation. John Holland originated the idea of GAs in the 1970s with the "Simple GA" where a `population' of solutions is randomly generated, from which iteratively `parents' are selected and combined to form `children', in such a way that successive generations will contain better and better solutions to the problem under consideration. Since then, many variations on this have been suggested and used. The purpose of the project will be to produce a visualisation of a GA at work.

This will be particularly useful in explaining the key concepts of GAs and to help to show how the method works. (Currently a primitive example version of this exists - see Roger Hare for details.)

It is expected that the GA itself will be written in RPL2, a GA programming language available at EPCC, rather than have a student spend a lot of time writing genetic algorithm code from scratch. A Java server will be used to run the RPL2 program, and to receive data from it. The user interface will be through a Java applet, which will send queries to the server and receive data originating from the RPL2 program. This data will be used to update the simulation of the GA.

Clearly this project requires a good understanding of GAs and the methods used. The first stage of the project would therefore be for the student to become familiar with the theory behind genetic algorithms, using GA material available at EPCC. The next stage will be to decide on a problem and a representation which can be shown graphically in an easily understood manner. Based on this a simple GUI can also be designed. The GA can then be written : it is anticipated that initially this will follow the form of Holland's "Simple GA". Finally the interface for the simulation can be coded in Java and linked to the GA output. This forms the core of the project, however there is considerable scope for extending the project, for instance, specific simulation of the workings of crossover and selection; adding different types of genetic operators; including parallelisation.

The final report for this project is available here.
Webpage maintained by mario@epcc.ed.ac.uk