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

Mario Hevia Fajardo; Per Kristian Lehre

doi:10.1145/3583131.3590506

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

Mario Hevia Fajardo, Per Kristian Lehre

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Downloads (Pure)

Abstract

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 (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.

Original language	English
Title of host publication	GECCO '23
Subtitle of host publication	Proceedings of the Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery (ACM)
Pages	1593-1601
Number of pages	9
ISBN (Electronic)	9798400701191
DOIs	https://doi.org/10.1145/3583131.3590506
Publication status	Published - 12 Jul 2023
Event	GECCO '23: Genetic and Evolutionary Computation Conference - Lisbon, Portugal Duration: 15 Jul 2023 → 19 Jul 2023 https://dl.acm.org/conference/gecco

Publication series

Name	GECCO: Genetic and Evolutionary Computation Conference

Conference

Conference	GECCO '23: Genetic and Evolutionary Computation Conference
Abbreviated title	GECCO '23
Country/Territory	Portugal
City	Lisbon
Period	15/07/23 → 19/07/23
Internet address	https://dl.acm.org/conference/gecco

Bibliographical note

Acknowledgments:
This research was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). The computations described in this paper were performed using the University of Birmingham’s BlueBEAR HPC service. See http://www.birmingham.ac.uk/bear for more details.

Keywords

Runtime analysis
Competitive coevolution
Maximin Optimisation

Access to Document

10.1145/3583131.3590506Licence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

FajardoM2023FitnessFinal published version, 653 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms
Lehre, P. K.
Engineering & Physical Science Research Council
1/01/21 → 31/12/25
Project: Research Councils

Cite this

Hevia Fajardo, M., & Lehre, P. K. (2023). How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems. In GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference (pp. 1593-1601). (GECCO: Genetic and Evolutionary Computation Conference). Association for Computing Machinery (ACM). https://doi.org/10.1145/3583131.3590506

@inproceedings{93de5247a25b45a39a88ff0a888ccb38,

title = "How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems",

abstract = "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 (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.",

keywords = "Runtime analysis, Competitive coevolution, Maximin Optimisation",

author = "{Hevia Fajardo}, Mario and Lehre, {Per Kristian}",

note = "Acknowledgments: This research was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). The computations described in this paper were performed using the University of Birmingham{\textquoteright}s BlueBEAR HPC service. See http://www.birmingham.ac.uk/bear for more details. ; GECCO '23: Genetic and Evolutionary Computation Conference, GECCO '23 ; Conference date: 15-07-2023 Through 19-07-2023",

year = "2023",

month = jul,

day = "12",

doi = "10.1145/3583131.3590506",

language = "English",

series = "GECCO: Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery (ACM)",

pages = "1593--1601",

booktitle = "GECCO '23",

address = "United States",

url = "https://dl.acm.org/conference/gecco",

}

Hevia Fajardo, M & Lehre, PK 2023, How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems. in GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO: Genetic and Evolutionary Computation Conference, Association for Computing Machinery (ACM), pp. 1593-1601, GECCO '23: Genetic and Evolutionary Computation Conference, Lisbon, Portugal, 15/07/23. https://doi.org/10.1145/3583131.3590506

How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems. / Hevia Fajardo, Mario ; Lehre, Per Kristian.
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), 2023. p. 1593-1601 (GECCO: Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Hevia Fajardo, Mario

AU - Lehre, Per Kristian

N1 - Acknowledgments: This research was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1). The computations described in this paper were performed using the University of Birmingham’s BlueBEAR HPC service. See http://www.birmingham.ac.uk/bear for more details.

PY - 2023/7/12

Y1 - 2023/7/12

N2 - 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 (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.

AB - 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 (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.

KW - Runtime analysis

KW - Competitive coevolution

KW - Maximin Optimisation

U2 - 10.1145/3583131.3590506

DO - 10.1145/3583131.3590506

M3 - Conference contribution

T3 - GECCO: Genetic and Evolutionary Computation Conference

SP - 1593

EP - 1601

BT - GECCO '23

PB - Association for Computing Machinery (ACM)

T2 - GECCO '23: Genetic and Evolutionary Computation Conference

Y2 - 15 July 2023 through 19 July 2023

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Projects

Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms

Cite this