EPSRC logo

Details of Grant 

EPSRC Reference: EP/V025562/1
Title: Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms
Principal Investigator: Lehre, Professor P
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Ecole Polytechnique Honda Massachusetts Institute of Technology
Meta (Previously Facebook) Technical University of Denmark
Department: School of Computer Science
Organisation: University of Birmingham
Scheme: EPSRC Fellowship - NHFP
Starts: 01 January 2021 Ends: 31 December 2025 Value (£): 1,254,385
EPSRC Research Topic Classifications:
Artificial Intelligence Fundamentals of Computing
Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
06 Oct 2020 Turing AI Acceleration Fellowship Interview Panel A Announced
Summary on Grant Application Form
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.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bham.ac.uk