Modelling Evolutionary Algorithms

People

Adam Prugel-Bennett

Alex Rogers

Work

A desciption of our work including papers and a guide to some of the issues and terminology is given here

Description

As technology tackles ever more complex problems traditional design techniques have proved inadequate for finding good design solutions. To address this problem designers have turned to imitating natural selection. This has been carried out both on computers to find good engineering solutions and using modern biotechnology techniques to discover new drugs. As complexity increases blind imitation of natural selection is not sufficient for finding state of the art solutions. Instead, evolutionary algorithms have to be tailored to the problem to ensure maximum efficiency. To do this the intricacies of natural selection and optimisation must be understood. One section of the intelligent systems research group, led by Dr Adam Prügel-Bennett is involved in developing a mathematical formalism for describing evolving systems.

Mathematical modelling of evolution has a long history within biology involving some of the giants of 20th century mathematical biology, such as Ronald Fisher, Sewel Wright and John B. S. Haldane. However, the techniques they developed were specialised for understanding variations at a single locus. These had direct implications for many diseases such as sickle cell aneamia. However, they are less applicable to design problems where the state of the whole genome is important. For this a more holistic approach, that takes into account the interaction between different parts of the genome, is vital. Over the last few years, Dr Prügel-Bennett together with co-workers in Manchester and his research students have developed a formalism based on techniques of statistical mechanics for describing the dynamics of evolving populations. This has lead to new insights into how evolutionary algorithms work and how they can be optimised. In addition, this work has generated a new tool for understanding evolution in biological systems. Recent areas of research include:

• A detailed analysis and comparison of different selection strategies.
• Understanding symmetry breaking within optimisation problems and how this is reflected in an evolving population.
• Looking at model systems where recombination is essential for efficient search.
• Obtaining the asymptotic behaviour of an evolving population as a function of the population size and number of loci.

The use of evolutionary algorithms grows every year and the number of applications is now enormous. The mathematical analysis of these algorithms is only at the beginning of its development. Understanding the underlying principles as well as the unique behaviour of particular problems will continue to be an important challenge for many years.