Ranking Diversity Benefits Coevolutionary Algorithms on an Intransitive Game

Competitive coevolutionary algorithms (CoEAs) often encounter so-called coevolutionary pathologies particularly cycling behavior, which becomes more pronounced for games where there is no clear hierarchy of superiority among the possible strategies (intransitive games). In order to avoid these pathologies and ensure an efficient optimisation, it has been suggested that it is critical to choose a good evaluation environment (set of solutions used for evaluation). In this paper, we use runtime analysis to increase our understanding of the essential characteristics that the evaluation environments should possess to ensure efficient runtime on the intransitive problem class \(\textsc {Bilinear}_{\alpha ,\beta }\) . For this problem class, we observe that it is beneficial to maintain a high diversity of rankings in the evaluation environment, that is, a set of individuals used for evaluation which are diverse in how they rank opponents. We propose and analyse two mechanisms that implement this idea. In the first approach, we ensure diversity of rankings through an archive. In the second approach, we introduce a CoEA without an archive, but with a ranking diversity mechanism. Both approaches optimise \(\textsc {Bilinear}_{\alpha ,\beta }\) in expected polynomial time.