EPSRC logo

Details of Grant 

EPSRC Reference: EP/M004252/1
Title: Rigorous Runtime Analysis of Bio-Inspired Computing
Principal Investigator: Oliveto, Dr PS
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: University of Sheffield
Scheme: EPSRC Fellowship
Starts: 31 March 2015 Ends: 30 September 2020 Value (£): 1,266,592
EPSRC Research Topic Classifications:
Artificial Intelligence Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
17 Jul 2014 EPSRC ICT Prioritisation Panel - July 2014 Announced
04 Sep 2014 ICT Fellowships Interview Meeting - 4 Sept 2014 Announced
Summary on Grant Application Form
Bio-Inspired Search Heuristics (BISHs) are general purpose randomized search heuristics (RSHs). Well known BISHs are Evolutionary Algorithms, Ant Colony Optimisation and Artificial Immune Systems. They have been applied successfully to combinatorial optimization in many fields. However, their computational complexity is far from being understood in depth. In this project the mathematical methodology will be developed to reveal where the real power of BISHs is in comparison with the traditional problem-specific algorithms. The project impacts the field of BISHs in several ways. A feature that distinguishes BISHs from most other algorithms is their population of individuals that simultaneously explore the search space. The first objective is to explain the performance of realistic BISHs for well-known combinatorial optimization problems through runtime analyses, highlighting the relationships between the solution quality and the exploration capabilities of the population. The second objective is to theoretically explain how BISHs can take advantage of the parallelisation available inherently in new technologies to achieve the population diversity required to produce solutions of higher quality in shorter time. The third objective of this project is to create a mathematical basis to explain the working principles of Genetic Programming (GP) and allow the effective and efficient self-evolution of computer programs. The fourth objective is to devise a suitable computational complexity model for the problem classification of BISHs. The enlargement of the established computational complexity picture with BISH complexity classes will enable the understanding of the relationships between traditional problem-specific algorithms and BISHs. Through industrial collaborators, the final objective is the direct exploitation of the theoretical results in real-world applications related to the combinatorial optimization problems studied in this project.
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.shef.ac.uk