Rigorous Runtime Analysis of Nature Inspired Meta-heuristics

本项目将分析不同性质启发的元启发式算法的严格运行时分析，以便更深入地了解给定的元启发式算法何时以及为什么会执行得很好或很差。各种自然启发的元启发式算法已经成功地应用于许多科学领域的组合优化中，但其计算复杂性还远未被深入了解。进化算法(EAs)、蚁群优化算法(ACO)和人工免疫系统(AIS)算法在本项目中将被研究。由于它们的计算复杂性的知识水平处于非常不同的阶段，因此将产生两种不同类型的结果。一是实际EA的计算复杂性结果，而不是(1+1)-EA的计算复杂性结果。将建立一组复杂性类，揭示哪类问题对于哪种EA来说是困难的(或容易的)。另一类是系统地对ACO和AIS进行计算复杂性分析的第一基础的设置。该项目的预期结果不仅将提供坚实的基础，还将在理解对于给定问题和在设计更有效的变体时优先选择哪种元启发式方面提供洞察和指导。

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.