CAREER: Algorithmic Models of Adaptation

该奖项的全部或部分资金来自《2021年美国救援计划法案》(公法117-2)。进化是一个内在的算法过程：生物体中复杂的适应来自复制、变异和选择的基本力量，这些基本力量共同作用于遗传物质的进化序列。在人工智能领域，这一过程在高水平上被用来开发进化算法：应用这个框架的计算机程序，以使解决方案适应计算困难的问题。尽管它们在广泛的实际应用中很受欢迎，但人们对它们的工作原理或问题结构可能如何影响它们的适用性了解相对较少。此外，在生物进化和算法的交汇处，有大量尚未开发的跨学科知识的潜力。该项目通过建立一个算法进化实验室来解决这个问题，该实验室作为科学思想的孵化器，探索算法进化和进化种群的数学模型之间的界限。算法进化实验室的主要目的是从计算复杂性的角度研究进化和适应。该项目的影响包括对自然和人工环境中不同力量如何影响适应速度的新见解。它还将为人工智能领域的优化启发式算法提供严格的性能保证。随着社会变得越来越依赖人工智能技术，对这些算法进行严格分析变得越来越关键。尤其是当人类生命和安全受到威胁时，或者算法过程可能在更广泛的系统内产生戏剧性和意想不到的影响时，情况尤其如此。该项目将有助于宣传和推动对这类算法的严格分析。这项研究也与该项目的教育和推广目标密切相关。算法进化实验室为学生建立了一个进行跨学科研究的环境。本科生研究研讨会和计算机科学领域杰出女性的客座讲座等活动将服务于改善计算机科学领域的性别平衡的目标，并为女性和代表性不足的少数民族创造通向STEM研究机会的途径。该项目将应用参数化复杂性理论中的工具来解释不同的进化搜索算子如何影响组合景观上的适应速度，以及景观结构如何影响这一速度。来自人工智能的进化算法和其他优化启发式算法是健壮的和通用的，但往往带有许多模块和设计选择。要找到合理的配置，需要一种成本高昂的临时试错方法。该项目将在问题结构和算法设计中确定参数，以隔离算法的指数复杂性来源，以提供对不同运算符对运行时间的影响的严格理解。这将导致在实践中设计和调整这些技术的原则性方法。该项目还将通过从新的算法角度解决一个旧问题，为进化生物学的传统理论工作提供一个新的视角。赖特的转移平衡理论认为，遗传漂移等随机过程是适应动力学中的关键力量。这与菲舍尔认为适应是一个简单的爬山过程的观点相冲突。通过应用进化算法运行时间分析的工具，该项目将从一个基于计算复杂性的新框架来解决这些问题，其中可以使适应的效率变得严格。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).Evolution is an inherently algorithmic process: complex adaptations in living organisms emerge from the basic forces of replication, variation and selection acting together on an evolving sequence of genetic material. In the field of artificial intelligence, this process has been leveraged at a high level to develop evolutionary algorithms: computer programs that apply this framework to adapt solutions to computationally hard problems. Despite their popularity on a wide range of practical applications, relatively little is understood about their working principles, or how the structure of problems might influence their applicability. Moreover, there is a rich potential of untapped interdisciplinary knowledge situated at the confluence of biological evolution and algorithms. This project addresses this by establishing an Algorithmic Evolution Lab to serve as an incubator of scientific ideas that explore the boundaries between algorithmic evolution and mathematical models of evolving populations. The principal aim of the Algorithmic Evolution Lab is to study evolution and adaptation from the lens of computational complexity. The impacts of this project include developing new insights into how different forces affect the speed of adaptation in both natural and artificial settings. It will also yield rigorous performance guarantees for optimization heuristics coming from the field of artificial intelligence. As society becomes more reliant on techniques from artificial intelligence, it is increasingly more critical that these algorithms are rigorously analyzed. This is especially the case when human life and safety is at stake, or when algorithmic processes can have dramatic and unintended effects within broader systems. This project will help to publicize and push forward the rigorous analysis of these kinds of algorithms. The research is also tightly coupled to the educational and outreach goals of the project. The Algorithmic Evolution Lab builds an environment for students to conduct interdisciplinary research. Activities such as undergraduate research workshops and guest lectures from prominent women in computer science will serve the goal of improving the gender balance in computer science, and creating pathways to STEM research opportunities for women and underrepresented minorities.The project will apply tools from the theory of parameterized complexity to explain how different evolutionary search operators influence the speed of adaptation on combinatorial landscapes, and how landscape structure in turn influences this speed. Evolutionary algorithms and other optimization heuristics from AI are robust and general-purpose, yet often come with many modules and design choices. Finding reasonable configurations requires a costly, ad-hoc trial-and-error approach. The project will identify parameters, both in problem structure and algorithm design, that isolate the source of exponential complexity for the algorithm to provide a rigorous understanding of the influence of different operators on running time. This will result in a principled approach to designing and tuning these techniques in practice. The project will also offer a fresh view on traditional theoretical work in evolutionary biology by tackling an old problem from a new algorithmic perspective. Wright's Shifting Balance Theory contends that stochastic processes such as genetic drift are critical forces in the dynamics of adaptation. This conflicts with the Fisherian view that adaptation is a simple hill-climbing process. By applying tools from the running time analysis of evolutionary algorithms, this project will attack these questions from a novel framework based on computational complexity in which efficiency of adaptation can be made rigorous.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.