Rigorous Runtime Analysis of Bio-Inspired Computing

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.

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.