Review: An Introduction to Genetic Algorithms

One of the pre-eminent reviewers on Slashdot, SEGV, has returned with a review of something a bit more esoteric than our normal book review fare. Melanie Mitchell's latest work, An Introduction to Genetic Algorithms, is the subject of today's review, and is well worth the reading for those interested in said subject. Click below to find out more.

An Introduction to Genetic Algorithms
author	Melanie Mitchell
pages	209
publisher	rating	8/10
reviewer	SEGV
ISBN
summary	An excellent, brief introduction to a fascinating field. ISBN 0-262-63185-7 (PB), 0-262-13316-4 (HB)

Background

It was in the early nineties when I became interested in these sorts of things. I was enrolled in a commerce program, but somehow got onto reading such popular science books as Levy's Artificial Life: A Report from the Frontier Where Computers Meet Biology and Waldrop's Complexity: The Emerging Science at the Edge of Order and Chaos.

Those books made me make my next degree a computer science degree.

Emergent Computation

I was fascinated by the idea of computation emerging from the bottom up: from simple rules acting together in simple ways. This is in marked contrast to the traditional artificial intelligence view that complex behaviour typically only arises from the top down: from the complex interactions of complex rules.

I could appreciate the uses of traditional AI techniques, but emergent computation seemed somehow right to me.

Genetic Algorithms

Notwithstanding my simplistic explanation, there's an obvious example right in front of us. Evolution is a relatively simple process (everyone's heard of Darwin, right?) that has produced very complex output (e.g. us). What if we could harness the power of this evolutionary computation?

John Holland had the idea of mimicking this process of evolution within the computer. He encoded potential solutions as strings of zeroes and ones (the language of the computer), much as human genotypes consist of DNA strands. He developed these strings into actual solutions and measured their success against a particular problem, much as we might measure our success in life. Then he bred another generation, selecting the best individuals to reproduce ("survival of the fittest"), and applying crossover ("sex") and mutation on the strings for good measure.

That's another simplistic explanation, but as time went on these strings got better and better at solving the problem. And it didn't matter which problem. The same process could be used on almost any problem. He called this process a genetic algorithm ("GA").

An Introduction

This book is a good introduction to that world. The first three chapters present an overview of the field, and illustrate how GAs can be applied both in practical problem solving and in more theoretical research environments.

The author explains some of the history and background of GAs, the biological terminology, and its equivalent GA terminology. She provides examples and uses figures effectively.

The entire book has an "overview" feel to it. It isn't very long, and aims for breadth rather than depth. Mitchell writes with clarity, and is great at explaining the subject matter. It's not a difficult book to read.

Theory and Practice

The next two chapters cover the theory and practice of genetic algorithms. Chapter 4 is the most difficult, as it covers Holland's Schema Theorem and other mathematical and statistical observations. Fortunately, you don't lose much if you gloss over the equations, and they're there if you're into that sort of thing.

Chapter 5 is the fun stuff. Mitchell doesn't provide code, but that's okay because the explanation is lucid and sufficiently detailed to implement in code. She discusses ways of encoding the problem, implementing selection methods and the various genetic operators, and setting the parameters of the GA.

To test this theory and practice, each chapter concludes with thought exercises and computer exercises.

Applicability

Dating from 1996, the book benefits from being relatively up-to-date. It borrows from papers and studies up until then, which you'll recognize if you've browsed through other literature (such as the Santa Fe Institute's Artificial Life Proceedings).

Mitchell does reserve a critical view. She's careful to point out where further study is required, and that's important as this remains a maturing area of computer science. She also points out promising avenues for future study.

Summary

I found this book to be an excellent introduction to the field, even though I'd read articles and papers on GAs beforehand. I'd recommend it to anyone interested in genetic algorithms and ready to go beyond the popular science descriptions, but not yet ready for the hardcore books and not willing to waste time on the poorer quality "GAs made E-Z" books.

Basically, this is an excellent quality "GAs in a Nutshell" book. When you've finished it, you might be interested in Goldberg's Genetic Algorithms in Search, Optimization, and Machine Learning.

The book's official site contains a more detailed table of contents, while Mitchell's book page contains solutions to selected thought exercises, an expanded index, and errata.

You can purchase this book at Amazon.

TABLE OF CONTENTS

Preface
Acknowledgements
1. Genetic Algorithms: An Overview
2. Genetic Algorithms in Problem Solving
3. Genetic Algorithms in Scientific Models
4. Theoretical Foundations of Genetic Algorithms
5. Implementing a Genetic Algorithm
6. Conclusions and Future Directions
Appendix A: Selected General References
Appendix B: Other Resources
Bibliography
Index