Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function

Per Kristian Lehre

Introduction

Competitive co-evolutionary algorithms (CoEAs) are inspired by the biological concept of an "arms race," where two or more populations—such as predators and prey—evolve simultaneously. In these systems, the fitness of an individual in one population is determined by its interactions with individuals in the opposing population. This dynamic makes CoEAs uniquely suited for complex tasks like hardware design, game strategy evolution, and cyber security.

Despite their utility, CoEAs are notoriously difficult to analyze and often exhibit "pathological" behaviors. These include loss of gradient (where populations stop improving due to a lack of challenging opponents), relative over-generalisation, and mediocre objective stasis. While traditional Evolutionary Algorithms (EAs) benefit from a robust framework for "runtime analysis"—predicting the iterations required to find a solution—such a framework has been largely absent for competitive co-evolution. This paper bridges that gap by providing the first rigorous runtime analysis for population-based CoEAs.

Theoretical Framework and Methodology

To address the complexities of co-evolutionary dynamics, the research introduces several foundational theoretical components:

1. Co-evolutionary Level-based Theorem

The paper’s primary contribution is the generalization of the "level-based theorem" from standard EA theory to the co-evolutionary context. This theorem allows researchers to derive upper bounds on expected runtime by partitioning the search space into discrete "levels." By analyzing the probability of populations transitioning from one level to the next, the theorem provides a structured way to predict algorithmic progress.

2. Pairwise Dominance CoEA (PDCoEA)

The author proposes a new algorithm, PDCoEA, specifically designed for maximin optimization. PDCoEA utilizes a "pairwise dominance" selection mechanism. By sampling two pairs of individuals from the populations and retaining the pair that "dominates" the other based on the objective function, the algorithm maintains a stable selective pressure even in adversarial settings.

3. Cartesian Product State Tracking

A critical insight of this work is that co-evolution cannot be analyzed by tracking a single population in isolation. Instead, the "state" of the algorithm must be viewed as the relationship between the two populations, modeled as their Cartesian product. This perspective is essential for capturing the interdependent progress of the predator and prey populations.

The BILINEAR Benchmark

As a theoretical study, the paper utilizes a synthetic benchmark problem called BILINEAR. This is a maximin optimization problem where a "predator" attempts to maximize a function while a "prey" (adversary) attempts to minimize it. Much like the "OneMax" problem serves as a fundamental test for standard EAs, BILINEAR provides a clear, structured environment to test co-evolutionary dynamics and drift analysis.

Key Results and the Error Threshold

The paper establishes several landmark results regarding the efficiency and limits of co-evolutionary search:

  • Polynomial Runtime: The author proves that under specific settings for the BILINEAR problem, PDCoEA reaches an $\epsilon$-approximate solution in expected polynomial time: $O(r\lambda^3 n)$, where $\lambda$ is the population size and $n$ is the problem dimension. This success occurs with a high probability of $1 - (1/r)(1 + o(1))$ for any $r \in poly(n)$.
  • The Error Threshold: For the first time in a co-evolutionary context, the paper identifies a critical "error threshold." If the mutation rate $\chi$ exceeds a certain constant threshold, the "noise" introduced by mutation overwhelms the selective pressure. In such cases, the algorithm’s runtime jumps from polynomial to exponential, leading to a total failure to find the optimum.

Limitations and Future Directions

While this research provides a vital foundation, it notes several areas for further exploration:

  • Parameter Constraints: The current analysis focuses on a specific subset of the BILINEAR problem (constrained by parameters $\alpha$ and $\beta$) and does not yet cover the general case for all bilinear functions.
  • Approximation vs. Exactness: The proofs focus on reaching an $\epsilon$-approximation rather than the exact maximin-optimal point.
  • Algorithm and Problem Scope: The results are currently specific to PDCoEA and the BILINEAR benchmark. Future work is required to apply these level-based tools to other popular co-evolutionary architectures and more rugged, deceptive adversarial landscapes found in real-world applications.

By establishing these rigorous bounds, the paper moves CoEA research away from empirical trial-and-error and toward a more predictable, mathematically grounded engineering discipline.

Summary updated

BibTeX
@article{lehre2024runtime,
  author = {Per Kristian Lehre},
  title = {{Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function}},
  journal = {Algorithmica},
  year = {2024},
  doi = {10.1007/s00453-024-01218-3},
}
Figure