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.
People |
ORCID iD |
Pietro Oliveto (Principal Investigator) |
Publications
Chandra A
(2010)
Applications of Evolutionary Computation
Corus D
(2017)
On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation.
in Algorithmica
Dang D
(2018)
Escaping Local Optima Using Crossover With Emergent Diversity
in IEEE Transactions on Evolutionary Computation
Dang D
(2016)
Parallel Problem Solving from Nature - PPSN XIV
Jansen T
(2011)
Artificial Immune Systems
Jansen T
(2013)
Approximating vertex cover using edge-based representations
Kratsch S
(2010)
Parallel Problem Solving from Nature, PPSN XI
Kötzing T
(2010)
Ant colony optimization and the minimum cut problem
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 | Charity/Non Profit |
Country | Canada |
Start | 06/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 | Charity/Non Profit |
Country | Canada |
Start | 06/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 | 05/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 | Belgium |
Start | 09/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 | Public |
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 | 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 | 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 |
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 - 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 | 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 | 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 |
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 | 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 |