Summary of “Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure” by W. Daniel Hillis
Summary by Chris Wood
CS 410, Winter 2005
Biological evolution by the way of natural selection is a theory that has changed the way scientists view the world. In his paper, “Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure,” W. Daniel Hillis shows how computer problems can besolved through the simulation of evolution. Evolutionary algorithms for computers are useful in that they can be done on parallel computers, thus increasing the speed of the whole process. Hundreds or even thousands of generations can be tested over the space of a few hours.
Data structures such as strings and arrays are used to keep track of the individuals that are evolving in the problem. Evolution is modeled using computer algorithms. Individuals from the population are selected by taking the data from a given individual and scoring it on certain criteria. The selection method is coded to take the best individuals from a given population. Reproduction is achieved by taking the individuals who have been selected and combining them to create new individuals who will go into the next generation. The data that holds the information for a new individual is an amalgamation of the data of the two parents, combined in a consistent fashion. The new individuals are put into the general population while some of the old data is removed to keep the population size constant.
Hillis chose to test simulated evolution on minimal sorting networks. A sorting network is a parallelizable device for sorting lists with a fixed number of elements, n (Mitchell, 1996). This can be represented graphically with a series of horizontal lines. The n inputs are on the left and outputs are on the right. An exchange occurs when a vertical line connects two horizontal lines, which is when comparisons and swaps are done to sort the lists. Scientists in the 1960s were able to slowly optimize sorting networks for n = 16, dropping the number of exchanges from 65 down over a number of years to 60 by Green (Green, 1973).
Hillis decided that the best way to find a minimal sorting network is to search for ones that sort best out of the space of short sequences of comparisons or exchanges (Hillis, 1991). This was done because doing only minor changes to the network gave more of a chance for the resulting network to work. The individuals consisted of 15 pairs of chromosomes, with each chromosome having 8 codons. Codons were represented with 4 bit numbers; thus the entire set of data for an individual was a set of 30 strings, each 32 bits long. An individual is able to represent the information for a sorting network with 60 to 120 exchanges.He also seeded the initial data by initializing the population with the first half of the best known exchange.
These individuals are put through the simulated evolution process and are scored due to how well they succeed in sorting a series of input cases. The ones that sort better contribute to the next generation, and the ones that don’t are culled. Mating is done by using spatial locality and mating individuals that are near each other. The entire population of individuals is arranged in a 2-D grid so that individuals can be considered to have spatial locality if they are within a couple spaces of each other. With this setup, Hillis performed the procedure on populations of 64,536 individuals for up to 5,000 generations (Hillis, 1991). With this procedure the best results he could get were networks with 65 exchanges, compared to the optimal result of 60.
Hillis had several problems with the results and methods of his evolution experiment. The first was that running into local optima in the system stalled the program out after finding a decent solution. Once it got to something optimal, the evolutionary procedure wasn’t able to make progress, since to make progress the networks would have to be made worse. The second issue was that the tests used to score how well the networks worked were quickly solved, thus leading to a case of overfitting the training data. There had to be some way to change the test cases so that a wider variety of solutions would be achieved.
His solution was to apply the idea of co-evolution to his computer simulation. In his original simulation, only the networks evolved over time. His way to solve this was at the same time to allow the test cases to evolve over time. The two would be competing in a parasite/host relationship, also known as predator/prey. Information for both is kept on the same grid, and networks are scored according to how they do on tests found at the same grid location. The tests are scored in the adversarial manner of how they find flaws in the networks.
The networks and the tests both evolve over time, allowing the best networks to evolve and the best tests to evolve. This method seems to solve the issue of getting stuck in local optima, because the adversarial method of the procedure encourages bringing in tests and networks from other locations that will challenge the networks and tests that are stuck in local optima. This method also increases the efficiency of testing by getting rid of the tests that are easily solved and removing them from the effective test set. Because more tests are removed, the computation time for each generation is decreased, and the overall problem is sped up. With this method Hillis was able to generate a sorting network of only 61 exchanges, one higher than the lowest optimal one found to this date. In his future work, Hillis wants to continue to apply these methods to other problems to see what else co-evolutionary algorithms can be used for.
References
M. Green (1973). Sorting and Searching, Volume 3: The Art of Computer Programming. D. Knuth
W. Daniel Hillis (1991). Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure. In Artificial Life II, SFI Studies in the Sciences of Complexity, vol. X313-324.
M. Mitchell (1996). Genetic Algorithms: An Overview. An Introduction to Genetic Algorithms, 21-27.