Contents
The process of artificial evolution can be improved with the use of artificial co-evolution. In artificial evolution the fitness landscape of a given problem is static - it is the same for each generation. But in artificial co-evolution the fitness of a given genotype will vary over time, due to the presence of other genotypes in the co-evolving population. This means that the fitness landscape is not static; it changes over time:
In artificial evolution some problems arise due to the presence of local optima. The fitness landscape of a typical evolutionary scenario will contain many peaks, and if the evolutionary process becomes caught in one of these peaks it can be difficult to move out of it. This makes it difficult to find the optimal solution. Artificial co-evolution can rectify this problem. When a large but imperfect sub-population evolves, it becomes an attractive target towards which the other population is likely to evolve. In other words, if one population becomes stuck in a local optima, the other population is likely to evolve to 'beat' that population, thus bringing it out of the local optima.
Biological evolution usually takes the form of an arms race. This is where two populations co-evolve so that any improvements made by one population will put pressure on the other population to adapt. This should result in each population improving over evolutionary time. Artificial co-evolution intends to simulate these arms races.
Arms races can be symmetric or asymmetric. Symmetric arms races are when both populations are trying to be good at the same thing. This is seen in nature when two animals from the same species fight each other - an improvement in one animal will put pressure on the other animal to adapt in some way. Asymmetric arms races are when each population is trying to beat the other population at some complementary behaviour. The classic example is Cheetahs chasing gazelles - the Cheetah is evolving towards greater speed, putting pressure on the Gazelle to adapt towards greater evasive abilities. Another example of an asymmetric arms race is the parasite-host scenario. Artificial co-evolution has been performed on both symmetric and asymmetric arms races. Karl Sims co-evolved "blockie creatures" to 'wrestle' each other, simulating a symmetric arms race. Other applications include animal-animat co-evolution, where game-playing programs learn from interaction with humans.
An example of the co-evolution of an asymmetric arms race is that of sorting networks. Hillis (1990) used a parasite-host scenario to evolve sorting networks. A sorting network is an algorithm to sort a given list of numbers. It works by selecting two numbers from the list and swapping them if they are out of order. A sorting network can be represented graphically:
The horizontal lines depict each number in the list, and the vertical lines show each comparison that is made between these numbers. A sorting network should successfully sort any list of numbers with the fewest number of comparisons possible. The smallest network previously discovered uses 60 comparisons to sort lists of 16 numbers. Hillis (1990) wanted to improve on this.
Hillis (1990) had the idea of co-evolving sorting networks (hosts) with lists of numbers (parasites), evolution selecting those sorting networks that sorted the lists of numbers in the least number of comparisons, and selecting those lists of numbers which were hardest to sort. The resultant sorting network used 61 comparisons - one short of the smallest network previously discovered.
Intransitive Dominance Hierarchy
Arms races will not in general lead to an improvement in fitness for each population. It is often the case that evolution will capitalize on some feature of a successful population, and adapt the other population accordingly. This situation can cycle indefinitely, with no great improvements made in either population. This is known as intransitive dominance hierarchy, and can be likened to a game of paper-scissors-rock. In artificial co-evolution we should therefore be careful that we do not get caught in such a situation, since progress would not be made, and no optimal solution would be found. However, it is possible to prevent such a situation by making the fitness of an individual dependent upon individuals from previous generations.
Measuring the Co-Evolutionary Process
The biggest problem when using artificial co-evolution is how to determine how much (if any) progress has been made. Co-evolution will not in general produce an increase in fitness over evolutionary time. This is because each population is trying only to beat the other population, it is not necessarily trying to find an optimal solution. Each population has to constantly adapt to keep up with the improvements made by the other population, resulting in an approximately constant fitness level. This is often referred to as the 'Red Queen effect' (the Red Queen was a character in "Through the Looking Glass" by Lewis Carroll, who constantly ran to keep up with the moving landscape, and did not appear to make any progress).
Cliff & Miller (1995) discussed these problems, and tried a number of methods for measuring the progress of a co-evolutionary process. They wanted to measure the progress of a pursuit and evasion co-evolutionary process. One method they used to do this was to compare current individuals with those from previous generations. Thus by competing a current pursuer against an evader from a previous generation, it would be possible to see how much improvement had been made by the pursuers (and similarly for evaders).
Vision-Based
Obstacle Avoidance: A Co-Evolutionary Approach
Co-Evolution
Evolutionary Computation
Co-Evolution
and Spatial Interaction
Biological
Evolution
Cliff,
D., and Miller, G. F. (1995) "Tracking the Red Queen:
Measurements of Adaptive Progress in Co-Evolutionary
Simulations". In: Moran, F., Moreno, A., Merelo, J. J.,
and Chacon, P. (eds.) Advances in Artificial Life.
Hillis, W. D. (1990) "Co-Evolving Parasites Improve
Simulated Evolution as an Optimization Procedure". In:
Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S.
(eds.) Artificial Life II.
Seth, A. Adaptive Behaviour in Animals and Robots Lecture Notes.
