Rigorous Runtime Analysis of Nature Inspired Meta-heuristics

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.

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.