Coevolution and Tartarus

Coevolution is the process of mutual adaptation of two populations. When a difficult optimization is performed with evolutionary computation, a population of adaptive test cases can strongly affect the progress of evolution. This study applies coevolution to the Tartarus task, a grid robot test problem. If the coevolving test cases are viewed as a form of parasite, then the question of virulence becomes an important feature of the algorithm. This study compares different types of parasites for the Tartarus problem. The impact of coevolution in this study is at odds with intuition and statistically significant. Analysis of the different types of coevolution suggests that disruptive crossover has a key effect. In the presence of disruptive crossover, coevolution may need to be modified to be effective. Examples of these modifications are presented. The key method of dealing with disruptive crossover is tracking the age of the Tartarus agents. The age of an agent is defined to be the number of selection steps the agent has survived. Using only older agents to drive coevolution of test cases substantially enhances the performance of one of the two type of coevolution studied.