Rigorous Runtime Analysis of Nature Inspired Meta-heuristics

Lead Research Organisation: University of Birmingham
Department Name: School of Computer Science

Abstract

A rigorous runtime analysis of different nature inspired meta-heuristics will be analysed in this projectin order to gain a deeper understanding of when and why a given meta-heuristic is expected to perform well or poorly. Various nature inspired meta-heuristics have been applied successfully to combinatorial optimisation in many scientific fields.However, their computational complexity is far from being understood in depth. It is still unclear how powerfulthey are for solving combinatorial optimisation problems, and where their real power is in comparison with the more traditional deterministic algorithms.Evolutionary Algorithms (EAs), Ant Colony Optimisation (ACO) and Artificial Immune System (AIS) algorithms will be studied in this project.Since the knowledge level of their computational complexity is at very different stages, two different types of results will be produced.One is the computational complexity results of realistic EAs, not (1+1)-EAs, on selected well-known combinatorial optimisation problems. A setup of complexity classes will be built revealing what classes of problems are hard (or easy) for which kind of EAs.The other is a setup of the first basis for a systematic computational complexity analysis of ACO and AIS other popular nature inspired meta-heuristics for which very few runtime results are available.The expected outcomes of this project will not only provide a solid foundation, but also insights and guidance in understandingwhich meta-heuristic should be preferred for a given problem and in the design of more efficient variants.

Planned Impact

Nature inspired meta-heuristics are used in numerous practical applications that involve an optimisation process. These are wide spread with numerous applications. Industrial beneficiaries include the supply chain and logistics sector, the manufacturing sector, engineering sector, the health sector, etc. Through runtime analyses on specific problems, we will gain a deep understanding of which kind of problems a given meta-heuristic will perform well on, and on which it will perform poorly. Furthermore, the reasons for the good or bad performance will be highlighted. These kind of results, will allow practitioners to choose the best algorithm for their problem and effectively exploit the known information about the problem when setting the parameters of the algorithms. As a consequence, the results will help in considerably reducing the amount of resources required for a practical application, especially in terms of money and time. Most importantly they can tell a practitioner about the scalability of the algorithm to large problem sizes. The gained insights and guidance will lead to the design and application of better variants of the algorithms and to more efficient solutions to the problems. Due to the enormous spread of applications, the benefits of theoretical guidance should not be underestimated. Considering the involved fields, improvement in the quality of results of major companies and government organisations will definitely foster economic competitiveness, increase the effectiveness of public services and increase the quality of life and health. We will regularly disseminate our results through top international journals in evolutionary computation (EC), artificial intelligence and classical computer science. Results will also be presented at the top EC international conferences (GECCO, CEC, PPSN, FOGA, ANTS and ICARIS). Focused special sessions, workshops and tutorials will also be organised at the international conferences to foster discussion and exploitation of the latest results. Direct exploitation of our results in UK, Europe and USA will happen through the ``Centre of Excellence for Research in Computational Intelligence and Applications'' (CERCIA), The Max Planck Institute (MPI) of Saarbruecken, Germany and AT&T Labs, New Jersey, USA. Results towards the better understanding of the studied algorithms will be immediately exploited in the practical applications involved in these research organisations. During these research visits, seminars and workshops will be also organised.
 
Description The methodology that has allowed the first time complexity analyses of standard genetic algorithms (i.e., the simple genetic algorithm) and of standard artificial immune systems (i.e., the B-Cell Algorithm).
Exploitation Route The presented methodologies may be used by researchers to identify optimisation problems for which genetic algorithms and artificial immune systems are effective and efficient versus problems where they are inefficient.
Sectors Aerospace, Defence and Marine,Digital/Communication/Information Technologies (including Software),Energy,Environment,Manufacturing, including Industrial Biotechology,Pharmaceuticals and Medical Biotechnology,Transport

 
Description Too early for concrete impact to be seen since the nature of the research is foundational.
Sector Other
 
Description ACM GECCO 2013 Conference
Amount $500 (USD)
Organisation Association for Computer Machinery Special Interest Group on Genetic and Evolutionary Computation (ACM SIGEVO) 
Sector Learned Society
Country Canada
Start 07/2013 
End 07/2013
 
Description ACM GECCO 2014 Conference
Amount $500 (USD)
Organisation Association for Computer Machinery Special Interest Group on Genetic and Evolutionary Computation (ACM SIGEVO) 
Sector Learned Society
Country Canada
Start 07/2014 
End 07/2014
 
Description CEC 2013 conference registration
Amount £500 (GBP)
Organisation IEEE Computational Intelligence Society 
Sector Charity/Non Profit
Country United States
Start 06/2013 
End 06/2013
 
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 EPSRC Early Career Fellowship
Amount £1,266,592 (GBP)
Funding ID EP/M004252/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Academic/University
Country United Kingdom
Start 03/2015 
End 02/2020
 
Description Runtime analysis of Greedy Randomized Adaptive Search Procedures 
Organisation AT&T Labs
Country United States 
Sector Private 
PI Contribution The first theoretical analysis of GRASP (i.e., greedy randomized adaptive search procedure)
Collaborator Contribution collaborative work (i.e., discussions and analysis)
Impact Paper under construction
Start Year 2010
 
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 
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 4 hour Tutorial at the 2013 IEEE Congress on Evolutionary Computation (CEC 2013).

Interest from students in undertaking research on runtime analysis of evolutionayr algorithms.
Year(s) Of Engagement Activity 2013
 
Description A Gentle Introduction to the Time Complexity Analysis of Evolutionary Algorithms 
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 Introductory tutorial on how to perform runtime analyses of evolutionary algorithms.
Presented at the 2012 IEEE World Conference on Computational Intelligence (4 hours).

Students came to ask if PhD and postdoc positions are available at my lab.
Year(s) Of Engagement Activity 2012
 
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 Chair of the IEEE Computational Intelligence Society (CIS) Task Force on 'Theoretical Foundations of Bio-inspired Computation' 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? Yes
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact The main goals of this task force are:



- to get theoretical research more propagated in the IEEE CIS community and to more people in general,

- to promote to non-theoreticians the importance of theoretically understanding the behavior and performance of the optimization algorithms they design,

- to bridge the gap between theory and practice.

Awarding Body - IEEE Computational Intelligence Society, Name of Scheme - IEEE CIS Technical Committee

More interest in theory from the IEEE Computational Intelligence Society
Year(s) Of Engagement Activity 2012
 
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 Midlands graduate school 
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 Introducing the theory of randomized search heuristics to students in other fields of theory of computation and maths of computing
Year(s) Of Engagement Activity 2014
URL http://www.cs.nott.ac.uk/~psztxa/mgs.2014/
 
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 
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 at ACM GECCO 2013, Amsterdam.

Increase in interest of attendees to perform research in similar directions.
Year(s) Of Engagement Activity 2013
URL http://dl.acm.org/citation.cfm?id=2482679&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 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 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 Runtime Analysis of Randomized Search Heuristics as Approximation Algorithms for the Vertex Cover Problem 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Type Of Presentation paper presentation
Geographic Reach Local
Primary Audience Postgraduate students
Results and Impact Invited Talk at national workshop.

People interested and asked about my research
Year(s) Of Engagement Activity 2012
 
Description Runtime Analysis of Randomized Search Heuristics as Approximation Algorithms for the Vertex Cover Problem 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Talk on the state of the art in the theoretical analysis of the performance of randomized search heuristics for the NP-hard vertex cover problem.

Further collaborations with the University of Nottingham
Year(s) Of Engagement Activity 2012
 
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/
 
Description time Complexity Analysis of Evolutionary Algorithms for Combinatorial Optimisation Problems 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Postgraduate students
Results and Impact Lecture on bio-inspired algorithms analysis at 2014 Midlands Graduate School in Nottingham

Advertising work to other community
Year(s) Of Engagement Activity 2014