An Introduction To Genetic Algorithms

Keywords: Genetic algorithms, complexity theory, evolutionary computation

Title: An Introduction To Genetic Algorithms

Author: Melanie Mitchell

Publisher: MIT Press

ISBN: 0-262-63185-7

Media: Book

Level: Introductory, intermediate

Verdict: A good, solid introduction

Buy US
Buy UK

Evolution is an extraordinarily successful strategy in nature - with prime examples being disease-resistant bacteria that are evolving as fast we can through anti-biotics at them. It has it's failures too - just look at the BNP :)

Computer scientist John Holland, building on some earlier work, had the bright idea of applying evolutionary strategies to problem solving. He took random strings of 1's and 0's, which he used to encode solutions to mathematical problems, and evolved them using reproduction and mutation to mimic natural geentic processes. He would take these random strings, see which ones were closest to the answer and then cross-breed these with other random strings. Over time these strings got closer and closer to optimum solutions. This is the process called genetic algorithms.

It's useful to contrast this with the approach that says we have to work out what the best solutions are using pure brain-power and mathematics. For lost of problems this is ok because we understand how to do it. However there are classes of problem where the range of solutions are so great that we can't possibly find a best solution.

The classic problem of this type is the travelling salesman problem. Imagine you have to travel to five destinations, each in turn. What is the route that has the minimum distance? It's an easy problem to state but a hard one to solve. You can list all the possible journeys and see which is the best, but as the number of destinations rises the number of alternative routes rises even faster.

Genetic algorithms (GA) have been used to solve these kinds of problems, and very successful they are too.

This book is one of the best short introductions to this fascinating subject. It combines information about the biological processes which inspire GA, such as cross-over, mutation, sexual and asexual reproduction etc. It then looks at the history of GA, including John Holland's pioneering work.

Then, in more detail, it looks at the technique in practice, focusing on different applications and types of problems. Including such things as stock-market prediction, evolving computer programs and other areas.

The writing is clear and concise, but it's hard work unless you have some background in computer science or programming. It's nevertheless a model of clear exposition compared to some of the more advanced texts on the subject.

Anybody looking for example source code will be disappointed. This is an introductory text and does not aim to produce sample GA programs - though the explanations are at a level where a skilled programmer could probably start to code for him or herself.

In all, it's an interesting combination of biologically-inspired thinking and computer programming. I doubt there's a better introductory text than this one.

Hit the 'back' key in your browser to return to subject index page

Return to home page