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.

Publications

10 25 50

publication icon
Dang D.-C. (2021) Escaping Local Optima with Non-Elitist Evolutionary Algorithms in 35th AAAI Conference on Artificial Intelligence, AAAI 2021

 
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?"

New co-evolutionary algorithms with better performance have been developed.

A co-evolutionary algorithm has been developed to improve the performance of energy controllers, taking into account average case and worst-case operating conditions.
Exploitation Route The tool is generally applicable to a wide range of co-evolutionary processes.

The co-evolutionary algorithm for energy controller has been developed in collaboration with Honda Research Institute.
Sectors Digital/Communication/Information Technologies (including Software)

Energy

Financial Services

and Management Consultancy

Transport

 
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 has been submitted to the IEEE CEC 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 We have submitted one paper to the CEC conference which is currently under review.
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 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 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 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