New Methods for Competitive Coevolution

TLDR

Competitive coevolution pits two independently evolving populations of hosts and parasites against each other, driving reciprocal arms races that raise performance and complexity. The study uses Nim and 3‑D Tic‑Tac‑Toe to investigate three novel competitive coevolution techniques. The authors introduce competitive fitness sharing, shared sampling, and a hall‑of‑fame strategy to modify fitness evaluation, diversify parasite selection, and sustain arms races. The methods are motivated mathematically and experimentally validated, with analyses addressing testing issues, diversity, extinction, arms‑race progress, and drift.

Abstract

We consider “competitive coevolution,” in which fitness is based on direct competition among individuals selected from two independently evolving populations of “hosts” and “parasites.” Competitive coevolution can lead to an “arms race,” in which the two populations reciprocally drive one another to increasing levels of performance and complexity. We use the games of Nim and 3-D Tic-Tac-Toe as test problems to explore three new techniques in competitive coevolution. “Competitive fitness sharing” changes the way fitness is measured; “shared sampling” provides a method for selecting a strong, diverse set of parasites; and the “hall of fame” encourages arms races by saving good individuals from prior generations. We provide several different motivations for these methods and mathematical insights into their use. Experimental comparisons are done, and a detailed analysis of these experiments is presented in terms of testing issues, diversity, extinction, arms race progress measurements, and drift.