Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Co-evolutionary algorithms have found several applications in game-theoretic applications and optimisation problems with an adversary, particularly where the strategy space is discrete and exponentially large, and where classical game-theoretic methods fail. However, the application of co-evolutionary algorithms is difficult because they often display pathological behaviour, such as cyclic behaviour and evolutionary forgetting. These challenges have prevented the broad application of co-evolutionary algorithms.

We derive, via rigorous mathematical methods, bounds on the expected time of a simple co-evolutionary algorithm until it discovers a Maximin-solution on the discrete Bilinear problem. Despite the intransitive nature of the problem leading to a cyclic behaviour of the algorithm, we prove that the algorithm obtains the Maximin-solution in expected O(n1.5) time. However, the algorithm quickly forgets the Maximin-solution and moves away from it. Along the way, we present new mathematical tools to compute the expected time for co-evolutionary algorithms to obtain a Maximin-solution. We are confident that these tools can help further advance runtime analysis in both co-evolutionary and evolutionary algorithms.
Original languageEnglish
Title of host publicationGECCO '23 Companion
Subtitle of host publicationProceedings of the Companion Conference on Genetic and Evolutionary Computation
PublisherAssociation for Computing Machinery (ACM)
Pages819–822
Number of pages4
ISBN (Electronic)9798400701207
DOIs
Publication statusPublished - 24 Jul 2023
EventGECCO '23: Genetic and Evolutionary Computation Conference - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023
https://dl.acm.org/conference/gecco

Publication series

NameGECCO: Genetic and Evolutionary Computation Conference

Conference

ConferenceGECCO '23: Genetic and Evolutionary Computation Conference
Abbreviated titleGECCO '23
Country/TerritoryPortugal
CityLisbon
Period15/07/2319/07/23
Internet address

Keywords

  • Runtime analysis
  • Competitive coevolution
  • Maximin Optimisation

Fingerprint

Dive into the research topics of 'Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation'. Together they form a unique fingerprint.

Cite this