Turing AI Fellowship: Rigorous time-complexity analysis of co-evolutionary algorithms

优化-在大量候选人中确定满意解决方案的问题-不仅是人工智能和计算机科学的基本问题，而且对英国企业的竞争力至关重要。现实世界中的优化问题通常使用进化算法来解决，进化算法是受达尔文自然选择原理启发的优化技术。这些算法依赖于用户提供的适应度函数来对候选解决方案进行排名。然而，对于真实的世界的问题，候选解决方案的质量往往取决于复杂的对抗效果，如竞争对手，这是用户难以预见的，因此很少反映在适应度函数。因此，当在复杂和对抗性的现实世界中部署时，使用理想化适应度函数的进化算法所获得的解决方案不一定会表现良好。所谓的协同进化算法可以潜在地解决这个问题。它们模拟了两个种群之间的竞争，“猎物”试图发现好的解决方案，而“捕食者”试图找到这些解决方案的缺陷。这个想法极大地避免了用户需要提供一个适应度函数，预见所有的解决方案可能会失败。然而，由于对其工作原理的有限理解，共同进化算法受到一些病态行为的困扰，包括梯度损失，相对过度泛化，以及平庸的目标停滞。这些病理行为的原因和潜在的补救措施知之甚少，目前限制了这些算法的实用性。该项目旨在为共同进化算法的理论理解带来突破。我们将开发第一个数学上严格的理论，可以预测何时共同进化算法有效地达到解决方案，以及何时发生病理行为。这一理论有可能使共同进化算法成为解决复杂现实问题的可靠优化方法。

Optimisation -- the problem of identifying a satisficing solution among a vast set of candidates -- is not only a fundamental problem in Artificial Intelligence and Computer Science, but essential to the competitiveness of UK businesses. Real-world optimisation problems are often tackled using evolutionary algorithms, which are optimisation techniques inspired by Darwin's principles of natural selection.Optimisation with classical evolutionary algorithms has a fundamental problem. These algorithms depend on a user-provided fitness function to rank candidate solutions. However, for real world problems, the quality of candidate solutions often depend on complex adversarial effects such as competitors which are difficult for the user to foresee, and thus rarely reflected in the fitness function. Solutions obtained by an evolutionary algorithm using an idealised fitness function, will therefore not necessarily perform well when deployed in a complex and adversarial real-world setting.So-called co-evolutionary algorithms can potentially solve this problem. They simulate a competition between two populations, the "prey" which attempt to discover good solutions, and the "predators" which attempt to find flaws in these. This idea greatly circumvents the need for the user to provide a fitness function which foresees all ways solutions can fail.However, due to limited understanding of their working principles, co-evolutionary algorithms are plagued by a number of pathological behaviours, including loss of gradient, relative over-generalisation, and mediocre objective stasis. The causes and potential remedies for these pathological behaviours are poorly understood, currently limiting the usefulness of these algorithms.The project has been designed to bring a break-through in the theoretical understanding of co-evolutionary algorithms. We will develop the first mathematically rigorous theory which can predict when a co-evolutionary algorithm reaches a solution efficiently, and when pathological behaviour occurs. This theory has the potential to make co-evolutionary algorithms a reliable optimisation method for complex real-world problems.