Rigorous Runtime Analysis of Bio-Inspired Computing

Lead Research Organisation: University of Sheffield
Department Name: Computer Science

Abstract

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.

Planned Impact

Although this project is theoretical in nature, it has significant benefits to practical applications of bio-inspired search heuristics (BISHs). Bio-Inspired Algorithms are applied to numerous real-world applications that involve an optimisation process.
These are wide spread. Industrial beneficiaries include the engineering sector, the manufacturing sector, supply chain and logistics sector, the health sector, etc. All of these sectors have optimisation problems that share significant similarities with the combinatorial optimisation problems studied in this proposal. Major companies in these sectors that apply the considered bio-inspired algorithms include Rolls Royce, Honda, BMW, Network Rail, ST-Microelectronics, BT, TGV trains etc.
Unfortunately, most of the claims about realistic EAs and any other bio-inspired algorithms are only justified by experimental work. Based on experimental results, it is difficult to understand whether a good performance of a bio-inspired heuristic
is due to the settings of the algorithms, the experimental setup or the inherent power of the bio-inspired heuristic itself. Hence, understanding where the real power of these algorithms lies is a key challenge towards future industrial development and economic success.

It is specifically noted in the 'Big Data Revolution and Energy-Efficient computing' section of the Eight Great Technologies document that "We also have a particular opportunity in energy efficient computing. IT is an increasingly heavy user of energy ... Energy-use is driven by the number of calculations. Poor quality software come with a high energy cost. Smart algorithms which get to a result with less effort need less energy". This project will contribute directly to this goal in the context of bio-inspired computing, since studying the number of calculations required to reach a solution of a given quality is the main measure of performance considered in our work. In fact, the gained insights and guidance will lead to the design and application of more efficient variants of the algorithms and to better solutions to the problems.

Through our industrial partners (i.e., AT&T, Network Rail, ACRC and CERCIA), the theoretical results obtained in this project will be directly exploited in real applications. This will allow faster dissemination rather than just relying on the scientific
publications of the highest quality that will be produced. Furthermore, the close collaboration with the industrial partners will allow the development of benchmark problems that capture characteristics present in real-world optimisation problems, thus feeding back into theory.

Publications

10 25 50
 
Description Cost Action
Amount € 1,000,000 (EUR)
Funding ID CA15140 
Organisation European Cooperation in Science and Technology (COST) 
Sector Public
Country European Union (EU)
Start 10/2015 
End 09/2020
 
Description Black-Box Discrete Optimization Benchmarking (BB-DOB@PPSN) Workshop - Coimbra, Portugal, 8 September 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Study participants or study members
Results and Impact Quantifying and comparing performance of optimization algorithms is one important aspect of research in search and optimization. However, this task turns out to be tedious and difficult to realize, at least, if one is willing to accomplish it in a scientifically rigorous way. The aim of our workshop is to set up a process that will allow to achieve a standard methodology for the benchmarking of black box optimisation algorithms in discrete and combinatorial search spaces.
Year(s) Of Engagement Activity 2018
URL http://iao.hfuu.edu.cn/bbdob-ppsn18
 
Description 7th Workshop on Theory of Randomized Search Heuristics (ThRaSH) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Type Of Presentation workshop facilitator
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Co-organiser of the workshop.

Spawned several work collaborations between people and ideas for future work.
Year(s) Of Engagement Activity 2015
URL http://www.dcs.shef.ac.uk/people/D.Sudholt/thrash2015/index.html
 
Description A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms - tutorial 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Type Of Presentation keynote/invited speaker
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Tutorial explaining how to perform runtime analyses of evolutionary algorithms at IEEE CEC and IEEE SSCI conferences.

Interest from students in PhD and postdoc positions in my research group
Year(s) Of Engagement Activity 2014,2015,2016,2017,2018
 
Description Black Box Discrete Optimization Benchmarking (BB-DOB) Workshop 
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 Quantifying and comparing performance of optimization algorithms is one important aspect of research in search and optimization. However, this task turns out to be tedious and difficult to realize, at least, if one is willing to accomplish it in a scientifically rigorous way. The aim of our workshop is to set up a process that will allow to achieve a standard methodology for the benchmarking of black box optimisation algorithms in discrete and combinatorial search spaces.
Year(s) Of Engagement Activity 2017,2018
URL http://gecco-2018.sigevo.org/index.html/tiki-index.php?page=Workshops#id_Black%20Box%20Discrete%20Op...
 
Description COST ACTION ImAppNIO Working Group on Benchmarking 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Working Group 3 is tasked with the development of practice-driven theory-affine benchmarks. its task is to develop useful benchmark for nature-inspired search and optimisation heuristics with a strong focus on discrete search spaces and discrete optimisation problems making sure that the developed benchmarks are relevant from a practical perspective and accessible from a theoretical perspective.
Year(s) Of Engagement Activity 2017,2018
URL http://imappnio.dcs.aber.ac.uk/5-working-group-3-benchmarks
 
Description Cost Action ImAppNIO Industry panel, Coimbra, Portugal 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Study participants or study members
Results and Impact Invited to represent academics on the Industry Panel organised by Cost Action ImAppNIO for the Industry Workshop, held in Coimbra 5-7 September, 2018.
Year(s) Of Engagement Activity 2018
URL http://imappnio.dcs.aber.ac.uk/index.php/meetings
 
Description Invited talk at Computer Science Department, Aberystwyth, Wales 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Postgraduate students
Results and Impact Reporting about first steps towards analysing genetic programming techniques for the automatic evolution of computer programmes
Year(s) Of Engagement Activity 2016
 
Description Invited talk at the Algorithms and Computational Complexity Seminars, Department of Computer Science, University of Oxford 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Postgraduate students
Results and Impact Invited talk in the Algorithms and Computational Complexity group's regular seminar series. Dissemination of evolutionary computation results to the more general theoretical computer science community.
Year(s) Of Engagement Activity 2019
URL https://www.cs.ox.ac.uk/seminars/2169.html
 
Description Invited talk at the University of Exeter 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Postgraduate students
Results and Impact Invited talk entitled "Sexual Reproduction Can Speed Up Optimisation" which was very well received.
Year(s) Of Engagement Activity 2017
 
Description Rigorous Research Group Twitter Account 
Form Of Engagement Activity Engagement focused website, blog or social media channel
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Dissemination of results and research directions / debate
Year(s) Of Engagement Activity 2016,2017,2018
URL https://twitter.com/rigresearch
 
Description Rigorous Research group webpage 
Form Of Engagement Activity Engagement focused website, blog or social media channel
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Dissemination webpage
Year(s) Of Engagement Activity 2016,2017
URL https://www.dcs.shef.ac.uk/people/P.Oliveto/rig/
 
Description Runtime Analysis of Evolutionary Algorithms: Basic Introduction - Tutorial 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Type Of Presentation keynote/invited speaker
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Explaining how to use mathematical techniques to perform runtime analyses of evolutionary algorithms.

PhD and postdoc position enquiries
Year(s) Of Engagement Activity 2014
URL http://dl.acm.org/citation.cfm?id=2605345&CFID=736538457&CFTOKEN=12951715
 
Description Runtime Analysis of Evolutionary Algorithms: Basic Introduction - Tutorial 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact PPSN 2016 Tutorial
Year(s) Of Engagement Activity 2016
 
Description Runtime Analysis of Population-based Evolutionary Algorithms - tutorial 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact ACM GECCO Tutorial
Year(s) Of Engagement Activity 2016,2017,2018
URL http://dl.acm.org/citation.cfm?id=2926976&CFID=736538457&CFTOKEN=12951715
 
Description Time and Space Complexity of Genetic Programming Tutorial, Coimbra, Portugal 9/9/2018 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Tutorial on how to analyse the computational complexity of genetic programming techniques to evolve executable functions.
Year(s) Of Engagement Activity 2018
URL http://ppsn2018.dei.uc.pt/index.php/tutorials/