Coevolutionary search among adversaries

Abstract

Competitive coevolution is a biologically-inspired search technique that uses a genetic algorithm in two competing populations. During search, individuals in each population are evaluated by direct competition against members of the opposing population. A class of adversarial problems is defined, to which competitive coevolution can be applied. In such problems, it is important to actively choose difficult test cases to accurately evaluate candidate solutions. Competitive coevolution evaluates candidate solutions and test cases against one another while searching for both, so that each drives the improvement of the other. Tools from computational learning theory are used to obtain positive theoretical results on the efficiency of simplified coevolutionary algorithms. Lower bounds show the importance of several parameters for describing performance of these algorithms. This work gives insight into necessary and sufficient conditions for successful coevolutionary search. Experimental work uses competitive coevolution as a heuristic method for adversarial problems. Several measurement techniques are used to understand the behavior of coevolution. These allow identification of several flaws in simple forms of coevolution. Coevolution can be stalled by the loss of important niches, by coevolutionary cycles, or by a lack of balance between populations. New methods are described that overcome these Aaws and make coevolution more efficient. Competitive fitness sharing preserves important niches, the hall of fame encourages long-term progress, the phantom parasite maintains balance, and shared sampling allows efficient fitness testing. With these new methods, coevolution is able to solve several game learning test problems that cannot be efficiently solved without them. Several applications are discussed. The first uses a simulation of patient blood pressure during surgery to evaluate drug delivery controllers against patients; the goal is a controller that successfully controls all possible patients. The second application uses a sorting network design problem to explore the relationship between theoretical concepts of testability and experimental coevolutionary behavior. The third application is the design of strategies for the game of Go. Coevolution produces competitive players that push the strategy representation to its limits. Finally, preliminary work is presented on the design of drugs that are robust across possible drug resistance mutations.