 
 


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 CoevolutionCoevolution 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 problemdependent. 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 Algorithms^{1}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 swapcomparisons (compare a and b, and if b is less than a swap them), and swapcomparisions 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 biologicalinspired 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 hostparasite 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.


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