At the forefront of Artificial Intelligence
  Home Articles Reviews Interviews JDK Glossary Features Discussion Search

An Introduction to Coevolution

Genetic algorithms are neat, but they do come with their own set of problems. One big problem is that genetic algorithms have a tendency to get stuck at local optima. In other words, they will find a reasonable solution, but not the best solution. There are several methods that have been devised to counter this problem, and the one we will look at is coevolution.

Overview of Coevolution

Coevolution is a term within the field of genetic algorithms that refers to evolving two or more interdependent sets of data. For example, if you are evolving a chess player, you would evolve both a white player and a black player together. So that each subsequent generation would (theoritically) be playing a more advanced opponent, forcing the GA to continuously evolve better players.

How do you go about coevolving two or more "species"? Well, as with genetic algorithms, the implementation is very problem-dependent. Coevolution is more of an idea than any specific technique. The easiest way to look at your problem is to try and create an analogy between your problem and the natural idea of parasite and host.

Let us keep with our chess problem - given a standard GA, we would pit each genetically evolved chess player against a set AI agent, rewarding each player according to how well they've done. Chances are, the GA would evolve a relatively good player, but it would take advantage of the various idiosyncrasies of the AI agent.

With coevolution, we would have two separately evolving populations: a population of black players and a population of white players. Having these two populations would ensure that neither of the populations would exploit certain traits of the other, because each population was constantly changing. Therefore, a generic, but good chess player would be evolved.

Example: Hillis and Sorting Algorithms1

Designing efficient algorithms to sort data is probably one of the most mundane but fundamentally important techniques in computer science. There was a lot of research done at one time at "n=16" sorting - an algorithm that sorted any list with 16 elements. Basically, each algorithm was a series of swap-comparisons (compare a and b, and if b is less than a swap them), and swap-comparisions that were independent of each other (they didn't compare the same elements, eg (1,2)(3,4)) could be performed in parallel to make the algorithm even faster.

In 1962, an algorithm requiring 65 comparisions was discovered, in 1964, 63 comparisons, 1969, 62 comparisions and then 60 comparisions. It was an exciting decade in the world of n=16 sorting algorithms! The problem was left alone until the 1980s when Daniel Hillis tried again to find an algorithm, except this time utilizing his massively parallel Connection Machine 2.

The details of how he encoded the problem are irrelevant here. In short, he used a rather complex and biological-inspired GA, but helped it along by setting the first 32 comparisions to known values that were common between all the manually discovered algorithms. Even with all of this, plus the huge populations (between 512 and 1 million!) that he could utilize using the Connection Machine, Hillis' GA only managed to create an algorithm that could sort lists in 65 comparisions.

Hillis persisted, and found that his GA was getting stuck in local optima. Therefore, he looked into the idea of coevolution using the host-parasite analogy. The host would be the sorting algorithm, and the parasites would be group of test cases for the algorithm to sort. The fitness of the host was the percentage of the test cases sorted, the fitness of the parasite was the percentage of test cases that stumped the algorithm. Therefore, when the GA was run, the parasites and hosts were locked into a spiraling arms race, with the sorting algorithms becoming more efficient, but the test cases becoming harder and harder to sort. With coevolution in place, the GA managed to find an algorithm that only required 61 comparisions - just one step away from the best so far discovered.

While Hillis' work never managed to create an algorithm that bettered any manually found one, it did prove the usefulness of coevolution as a viable GA technique.


1 Much of this section has been derived from Melanie Mitchell's excellent Introduction to Genetic Algorithms.

Submitted: 13/12/2000

Article content copyright © James Matthews, 2000.
 Article Toolbar
Print
BibTeX entry

Search

Latest News
- The Latest (03/04/2012)
- Generation5 10-year Anniversary (03/09/2008)
- New Generation5 Design! (09/04/2007)
- Happy New Year 2007 (02/01/2007)
- Where has Generation5 Gone?! (04/11/2005)

What's New?
- Back-propagation using the Generation5 JDK (07/04/2008)
- Hough Transforms (02/01/2008)
- Kohonen-based Image Analysis using the Generation5 JDK (11/12/2007)
- Modelling Bacterium using the JDK (19/03/2007)
- Modelling Bacterium using the JDK (19/03/2007)


All content copyright © 1998-2007, Generation5 unless otherwise noted.
- Privacy Policy - Legal - Terms of Use -