Rigorous Runtime Analysis of Bio-Inspired Computing

生物启发搜索启发式算法是一种通用的随机搜索启发式算法。最著名的是进化算法、蚁群优化和人工免疫系统。它们已成功地应用于许多领域的组合优化。然而，它们的计算复杂性还远远没有被深入了解。在这个项目中，将开发数学方法，以揭示与传统问题特定算法相比，BISHs的真正力量在哪里。该项目在几个方面影响了bis领域。将BISHs与大多数其他算法区分开来的一个特征是它们同时探索搜索空间的个体数量。第一个目标是通过运行时分析来解释众所周知的组合优化问题的实际bish的性能，突出解决方案质量与群体探索能力之间的关系。第二个目标是从理论上解释BISHs如何利用新技术固有的并行性来实现所需的人口多样性，从而在更短的时间内产生更高质量的解决方案。该项目的第三个目标是创建一个数学基础来解释遗传规划（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.