Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms
Lead Research Organisation:
University of Birmingham
Department Name: School of Computer Science
Abstract
Optimisation -- the problem of identifying a satisficing solution among a vast set of candidates -- is not only a fundamental problem in Artificial Intelligence and Computer Science, but essential to the competitiveness of UK businesses. Real-world optimisation problems are often tackled using evolutionary algorithms, which are optimisation techniques inspired by Darwin's principles of natural selection.
Optimisation with classical evolutionary algorithms has a fundamental problem. These algorithms depend on a user-provided fitness function to rank candidate solutions. However, for real world problems, the quality of candidate solutions often depend on complex adversarial effects such as competitors which are difficult for the user to foresee, and thus rarely reflected in the fitness function. Solutions obtained by an evolutionary algorithm using an idealised fitness function, will therefore not necessarily perform well when deployed in a complex and adversarial real-world setting.
So-called co-evolutionary algorithms can potentially solve this problem. They simulate a competition between two populations, the "prey" which attempt to discover good solutions, and the "predators" which attempt to find flaws in these. This idea greatly circumvents the need for the user to provide a fitness function which foresees all ways solutions can fail.
However, due to limited understanding of their working principles, co-evolutionary algorithms are plagued by a number of pathological behaviours, including loss of gradient, relative over-generalisation, and mediocre objective stasis. The causes and potential remedies for these pathological behaviours are poorly understood, currently limiting the usefulness of these algorithms.
The project has been designed to bring a break-through in the theoretical understanding of co-evolutionary algorithms. We will develop the first mathematically rigorous theory which can predict when a co-evolutionary algorithm reaches a solution efficiently, and when pathological behaviour occurs. This theory has the potential to make co-evolutionary algorithms a reliable optimisation method for complex real-world problems.
Optimisation with classical evolutionary algorithms has a fundamental problem. These algorithms depend on a user-provided fitness function to rank candidate solutions. However, for real world problems, the quality of candidate solutions often depend on complex adversarial effects such as competitors which are difficult for the user to foresee, and thus rarely reflected in the fitness function. Solutions obtained by an evolutionary algorithm using an idealised fitness function, will therefore not necessarily perform well when deployed in a complex and adversarial real-world setting.
So-called co-evolutionary algorithms can potentially solve this problem. They simulate a competition between two populations, the "prey" which attempt to discover good solutions, and the "predators" which attempt to find flaws in these. This idea greatly circumvents the need for the user to provide a fitness function which foresees all ways solutions can fail.
However, due to limited understanding of their working principles, co-evolutionary algorithms are plagued by a number of pathological behaviours, including loss of gradient, relative over-generalisation, and mediocre objective stasis. The causes and potential remedies for these pathological behaviours are poorly understood, currently limiting the usefulness of these algorithms.
The project has been designed to bring a break-through in the theoretical understanding of co-evolutionary algorithms. We will develop the first mathematically rigorous theory which can predict when a co-evolutionary algorithm reaches a solution efficiently, and when pathological behaviour occurs. This theory has the potential to make co-evolutionary algorithms a reliable optimisation method for complex real-world problems.
Organisations
People |
ORCID iD |
Per Kristian Lehre (Principal Investigator / Fellow) |
Publications
Dang D.-C.
(2021)
Escaping Local Optima with Non-Elitist Evolutionary Algorithms
in 35th AAAI Conference on Artificial Intelligence, AAAI 2021
Dang D.-C.
(2021)
Escaping Local Optima with Non-Elitist Evolutionary Algorithms
Lehre P
(2023)
Runtime Analysis with Variable Cost
Lehre P
(2022)
Runtime analysis of population-based evolutionary algorithms
Lehre P
(2022)
Self-adaptation via multi-objectivisation
Description | A mathematical tool ("level-based theorem") has been developed that facilitates performance analysis of co-evolutionary algorithms. When applicable, the tool gives a guarantee that the algorithm does not exceed a specific amount of time to obtain a solution with acceptable quality. Such results can reveal how the performance of an algorithm depends on its parameter settings, and on characteristics of the problem to be solved. This finding addresses WP1 and WP2: "What are relevant formal measures of time-complexity of co-evolution, and what probabilistic methods can be developed to estimate the time-complexity of co-evolutionary algorithms? How does the design of a co-evolutionary algorithm impact its time-complexity performance in discrete, maximin optimisation, and in identifying pure Nash equilibria in potential games?" |
Exploitation Route | The tool is generally applicable to a wide range of co-evolutionary processes. |
Sectors | Digital/Communication/Information Technologies (including Software),Financial Services, and Management Consultancy,Transport |
Description | MIT CSAIL |
Organisation | Massachusetts Institute of Technology |
Department | Computer Science and Artificial Intelligence Laboratory (CSAIL) |
Country | United States |
Sector | Academic/University |
PI Contribution | Co-authored paper on co-evolution. |
Collaborator Contribution | We have co-authored a paper about co-evolution. |
Impact | None so far. |
Start Year | 2022 |
Description | Conference talk |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Postgraduate students |
Results and Impact | Conference presentation, GECCO 2022. |
Year(s) Of Engagement Activity | 2022 |
Description | GECCO Tutorial |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Postgraduate students |
Results and Impact | Tutorial at the Genetic and Evolutionary Computation Conference (GECCO) in Boston, USA. |
Year(s) Of Engagement Activity | 2022 |
Description | Institute of Physics Talk |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | Regional |
Primary Audience | Public/other audiences |
Results and Impact | Popular science presentation about evolutionary computation. |
Year(s) Of Engagement Activity | 2022 |
Description | PPSN Tutorial |
Form Of Engagement Activity | A talk or presentation |
Part Of Official Scheme? | No |
Geographic Reach | International |
Primary Audience | Postgraduate students |
Results and Impact | Tutorial on runtime analysis of evolutionary algorithms presented at the PPSN conference in Dortmund. |
Year(s) Of Engagement Activity | 2022 |