CAREER: Algorithmic Models of Adaptation

点击翻译按钮获取中文摘要

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.