权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Rigorous Runtime Analysis of Bio-Inspired Computing

仿生计算的严格运行时分析

基本信息

批准号：
EP/M004252/1
负责人：
Pietro Oliveto
金额：
$ 161.39万
依托单位：
University of Sheffield
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM004252%2F1
关键词：
Rigorous Runtime Analysis Bio Inspired

项目摘要

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.

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