Rigorous Runtime Analysis of Bio-Inspired Computing

生物启发搜索启发式(BISH)是通用随机搜索启发式(RSHS)。众所周知的BISH是进化算法、蚁群优化和人工免疫系统。它们已成功地应用于许多领域的组合优化中。然而，人们还远未深入了解它们的计算复杂性。在这个项目中，将开发数学方法，以揭示与传统的特定问题算法相比，BISH的真正能力在哪里。该项目对BISH领域产生了多方面的影响。BISH与大多数其他算法的一个不同之处在于，它们的个体群体同时探索搜索空间。第一个目标是通过运行时分析来解释现实BISH对众所周知的组合优化问题的性能，强调解质量和种群的探索能力之间的关系。第二个目标是从理论上解释BISH如何利用新技术固有的并行性，实现在较短时间内产生更高质量解决方案所需的种群多样性。这个项目的第三个目标是建立一个数学基础来解释遗传编程(GP)的工作原理，并允许计算机程序有效和高效地自我进化。第四个目标是设计一个适用于BISH问题分类的计算复杂性模型。用BISH复杂性类扩大已建立的计算复杂性图，将有助于理解传统问题特定算法与BISH之间的关系。通过行业合作者，最终目标是直接利用与本项目所研究的组合优化问题相关的理论结果在现实世界中的应用。

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.