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
- University of Birmingham (Lead Research Organisation)
- Massachusetts Institute of Technology (Collaboration)
- Honda Research Institute Europe GmbH (Collaboration, Project Partner)
- Technical University of Denmark (Project Partner)
- Ecole Polytechnique (Project Partner)
- Massachusetts Institute of Technology (Project Partner)
- Meta (Previously Facebook) (Project Partner)
People |
ORCID iD |
| Per Kristian Lehre (Principal Investigator / Fellow) |
Publications
Dang D.-C.
(2021)
Escaping Local Optima with Non-Elitist Evolutionary Algorithms
Fajardo M
(2023)
Runtime Analysis of a Co-Evolutionary Algorithm
Hevia Fajardo M
(2024)
A Self-adaptive Coevolutionary Algorithm
Hevia Fajardo M
(2024)
Genetic Programming Theory and Practice XX
| 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. The theorem have been applied in several settings, including for games with binary payoffs with exponentially large strategy spaces, to bilinear games, and to aid in design of new algorithms. These 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?" In collaboration with MIT CSAIL, we have explored the application of co-evolutionary algorithms in DefendIT, which models a cyber-security scenario. This addresses WP3 (Games and Solution Concepts). Finally, to understand fundamental limitations with co-evolutionary algorithms, we have proved No Free Lunch theorems and defined and studied Black-Box Models of co-evolutionary algorithms. This addresses WP4 (Black Box Complexity). New co-evolutionary algorithms with better performance have been developed. |
| Exploitation Route | The level-based theorem is a general analytical tool that will facilitate time-complexity analysis (theoretical performance evaluation) of new co-evolutionary algorithms. Several new co-evolutionary algorithms have been developed (including the PDCoEA). These can be applied in finding Nash equilibria of large games, and in adversarial optimisation. |
| Sectors | Aerospace Defence and Marine Digital/Communication/Information Technologies (including Software) Energy Financial Services and Management Consultancy Manufacturing including Industrial Biotechology Pharmaceuticals and Medical Biotechnology Transport |
| Description | A co-evolutionary algorithm has been developed to improve the performance of energy controllers, taking into account average case and worst-case operating conditions. |
| First Year Of Impact | 2023 |
| Sector | Energy,Financial Services, and Management Consultancy,Transport |
| Impact Types | Economic |
| Description | Honda |
| Organisation | Honda Research Institute Europe GmbH |
| Country | Germany |
| Sector | Private |
| PI Contribution | We have collaborated with Honda RI in Frankfurt to develop a simulator and a co-evolutionary algorithm to develop energy controllers which minimise cost, both from the perspective of average case and worst case weather scenarios. One of the PDRAs on the project, Dr Alistair Benford travelled to Honda Research Institute Europe, located near Offenbach Germany on 4th - 28th September 2023. We co-authored a paper which was presented and published in the proceedings of IEEE Congress on Evolutionary Computation conference in Japan, 2024. |
| Collaborator Contribution | Honda RI have provided a supervisor in Frankfurt who assisted Dr Benford in developing an energy simulator. Honda has also contributed in producing a manuscript about the outcome of this project which has been submitted to IEEE CEC conference in Japan, 2024. |
| Impact | A. Benford, M. Olhofer, T. Rodemann and P. K. Lehre, "Bicriteria Optimisation of Average and Worst-Case Performance Using Coevolutionary Algorithms," 2024 IEEE Congress on Evolutionary Computation (CEC), Yokohama, Japan, 2024, pp. 1-8, doi: 10.1109/CEC60901.2024.10611909. https://ieeexplore.ieee.org/document/10611909 |
| Start Year | 2023 |
| 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 several papers on co-evolution. I had a longer research visit with MIT CSAIL in Boston/US June 19th - July 14th. |
| Collaborator Contribution | We have co-authored several papers about co-evolution. We have weekly meetings about ongoing research. |
| Impact | The following conference paper has been published: Per Kristian Lehre, Mario Hevia Fajardo, Erik Hemberg, Una-May O'Reilly, and Jamal Toutouh, Analysis of a Pairwise Dominance Coevolutionary Algorithm And DefendIt, To appear in Proceedings of Genetic and Evolutionary Computation Conference (GECCO '23) |
| Start Year | 2022 |
| Description | Breakout session at Dagstuhl Seminar on Theory of Randomised Search Heuristics |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | During a Dagstuhl seminar, we led a breakout group on theory of co-evolutionary algorithms. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://www.dagstuhl.de/seminars/seminar-calendar/seminar-details/17191 |
| Description | COST Workshop on Uncertainty |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Industry/Business |
| Results and Impact | Led COST action working group day on optimisation under uncertainty. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Conference talk |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | Conference/poster presentation at international conference. |
| Year(s) Of Engagement Activity | 2023 |
| 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 | Contributed talk at Dagstuhl Seminar - Competitive Coevolutionary Algorithms |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the potential benefits of conducting runtime analysis of competitive coevolutionary algorithms, along with an invitation for other researchers to explore future collaborations with our group. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Contributed talk at Dagstuhl Seminar -- EDAs: Theory and Applications |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the potential benefits of using coevolutionary estimation-of-distribution algorithms for learning optimal play in combinatorial games. Particular emphasis was made on how an EDA being stable as opposed to balanced can be used to prevent coevolutionary forgetting. |
| Year(s) Of Engagement Activity | 2025 |
| URL | https://www.dagstuhl.de/en/seminars/seminar-calendar/seminar-details/25092 |
| Description | Contributed talk at GECCO (Melbourne, Australia) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the paper "Runtime analysis of coevolutionary algorithms on a class of symmetric zero-sum games". |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://gecco-2024.sigevo.org/HomePage |
| Description | Contributed talk at IEEE Congress on Evolutionary Computation (Yokohama, Japan) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the paper "Bicriteria optimisation of average and worst-case performance using coevolutionary algorithms". The following audience discussion focused on how details of the relevant application (efficient management of an energy system) were accounted for in the coevolutionary process. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://2024.ieeewcci.org/ |
| Description | Facts & Snacks talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the time-complexity analysis of coevolutionary algorithms focusing on a resent analysis of the RLS-PD coevolutionary algorithm on the Bilinear function. |
| Year(s) Of Engagement Activity | 2023 |
| Description | Facts & Snacks talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the theory of coevolutionary algorithms and related results on coevolution for game-playing. |
| Year(s) Of Engagement Activity | 2024 |
| 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 |
| Description | Science at the Bar talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Other audiences |
| Results and Impact | Flash talk on fundamentals of coevolutionary algorithms and our group's research |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at Carnegie Mellon University (USA) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | A seminar giving an overview of the research undertaken by our group at the weekly "Meet & Think" at the Tepper School of Business, CMU. The audience was primarily interested in optimisation, but was largely unfamiliar with EAs and CoEAs, leading to in depth discussion of underlying principles. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at Manchester University |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | National |
| Primary Audience | Other audiences |
| Results and Impact | Presentation to the Alliance Manchester Business School about our research on co-evolutionary algorithms. We drafted ideas for a grant proposal. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at Nanjing University |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A presentation of our published research on co-evolutionary algorithms. The talk was hosted by Prof Chao Qian. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at New York University |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | Invited by Prof Julian Togelius to give a talk in the Game Innovation Lab. |
| Year(s) Of Engagement Activity | 2025 |
| Description | Talk at SUSTech |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A presentation of our published results on co-evolutionary algorithms. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at Tsinghua University |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | Summary of our previously published work on co-evolution. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at Tsukuba University (Japan) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A presentation of our current published results on co-evolutionary algorithms. The talk was hosted by Prof Yohei Akimoto. We discussed research collaboration. |
| Year(s) Of Engagement Activity | 2024 |
| Description | Talk at University of Adelaide |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | I presented our published research on co-evolutionary algorithms. |
| Year(s) Of Engagement Activity | 2024 |
| Description | ThRaSH seminar |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A seminar presenting proof aspects from the group's work on symmetric zero-sum games. Further (then ongoing) research on combinatorial games was presented at the end of the seminar. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://thrash-seminars.github.io/ |
| Description | ThRaSH seminar |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Other audiences |
| Results and Impact | A talk on the time-complexity analysis of coevolutionary algorithms focusing on a resent analysis of the RLS-PD coevolutionary algorithm on the Bilinear function. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://thrash-seminars.github.io/ |
| Description | Tutorial at GECCO (Melbourne, Australia) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | We presented a tutorial on runtime analysis of population-based evolutionary algorithms. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://gecco-2024.sigevo.org/Tutorials |
| Description | Tutorial on Co-Evolutionary Algorithms at IEEE Congress on Evolutionary Computation (CEC) in Japan |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | We gave a tutorial on co-evolutionary algorithms at the 2024 IEEE Congress on Evolutionary Computation. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://2024.ieeewcci.org/program/tutorials |
| Description | Tutorial on co-evolution at PPSN |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | We presented a tutorial on theory of co-evolutionary algorithms. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://ppsn2024.fh-ooe.at/ |
| Description | Tutorial on runtime analysis at PPSN |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Postgraduate students |
| Results and Impact | We presented a tutorial on runtime analysis of population-based evolutionary algorithms at the conference Parallel Problem Solving from Nature (PPSN). |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://ppsn2024.fh-ooe.at/ |
| Description | UK AI panel discussion on industry vs academia in AI |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | National |
| Primary Audience | Industry/Business |
| Results and Impact | Led panel discussion on interaction between academia and industry in AI. Participants included Dr Markus Olhofer, Honda Research Institute (Germany), Dr Timothy Lillicrap, Google Deepmind (UK), Prof Julian Togelius, New York University (USA), Dr Jacob Wood, Innovate UK UKRI (UK), and Prof Michel Valstar, BlueSkeye AI (UK). May 2023 |
| Year(s) Of Engagement Activity | 2023 |