Intransitivity in coevolution

Abstract. We review and investigate the current status of intransitivity as a potential obstacle in coevolution. Pareto-Coevolution avoids intransitivity by translating any standard superiority relation into a transitive Pareto-dominance relation. Even for transitive problems though, cycling is possible. Recently however, algorithms that provide monotonic progress for Pareto-Coevolution have become available. The use of such algorithms avoids cycling, whether caused by intransitivity or not. We investigate this in experiments with two intransitive test problems, and find that the IPCA and LAPCA archive methods establish monotonic progress on both test problems, thereby substantially outperforming the same method without an archive. Coevolution offers algorithms for problems where the performance of individuals can be evaluated using tests [1–7]. Since evaluation in coevolution is based on evolving individuals, coevolution setups can suffer from inaccurate evaluation, leading to problems such as over-specialization, Red Queen dynamics, an