How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems

Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains. Over the past decades, many ways to aggregate the outcomes of interactions have been considered. At the moment, it is unclear which of these is the best choice. Previous research is fragmented and most of the fitness aggregation methods (fitness measures) proposed have only been studied empirically. We argue that a proper understanding of the dynamics of CoEAs and their fitness measures can only be achieved through rigorous analysis of their behaviour. In this work we make a step towards this goal by using runtime analysis to study two commonly used fitness measures. We show a dichotomy in the behaviour of a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mi>λ</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> CoEA when optimising a Bilinear problem. The algorithm finds a solution near the Nash equilibrium in polynomial time with high probability if the worst interaction is used as a fitness measure but is inefficient if the average of all interactions is used instead.