» next  » last 

Jump to:

Evolutionary Algorithms

This article will show how we can use our ability to model a problem to breed solutions. We will use a method based on the laws which allowed us to crawl out of the primordial soup and struggle through millions of years to end up writing HTML in air-conditioned offices...

Update: Click here for the Powerpoint slides from my presentation at UK-BUG. (added October 2002)

Update: Dr Nikolai Shokhirev from the University of Arizona's Chemistry department has written an interface based implementation of the TSP demo code. This can be found here. Interfaces provide a much more usable framework for the GA than the components I developed. (added December 2002)

1. Introduction



This article is an introduction to Evolutionary Algorithms (EAs), which are an increasingly popular technique used in computer science. EAs are particularly useful for solving problems where we have very little knowledge of the solution but a good understanding of the problem.

A good example of this sort of problem is timetabling in schools and colleges: we understand, as the timetable designers, that we want to ensure that everyone can get to the right classes at the right times and we are able to judge whether this is the case. However, anyone with any experience of timetabling will immediately agree that it can be a mind numbingly complex task. In timetabling this is mainly due to multifarious interdependencies between the elements of the problem. One small change, say, moving art classes to a Wednesday afternoon, can cause a plethora of complications, rugby practice is on a Wednesday afternoon and the art room is used by photography...

Evolutionary algorithms provide us with an effective and uncomplicated approach to finding solutions to problems with high levels of complexity or interdependency. This article goes on to explain the basic principles of evolution and survival of the fittest in section 2, with a particular focus on evolution as a natural problem solving technique. Section 3 consolidates the main points from the previous section to give a simple algorithm and set of required building blocks for EAs. Section 4 introduces the Travelling Salesman problem, which will be used as an example problem for the remainder of the article. Sections 5 to 12 detail the components developed to implement the EA to solve the travelling salesman problem. Section 13 gives a tour of the Travelling Salesman application. In section 14 a checklist for solving a problem using the EA components is presented and finally, in section 15, there is a concluding discussion.

» next  » last 

Jump to: