CAREER: Algorithmic Models of Adaptation

职业：适应的算法模型

• 批准号: 2144080
• 负责人: Andrew Sutton
• 金额: $ 53.03万
• 依托单位: University of Minnesota Duluth
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2027-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2144080&HistoricalAwards=false
• 关键词: CAREER; Algorithmic; Models; 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.

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

项目成果

Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

随机种植顶点覆盖的(1 1)进化算法的定参数易处理性

• 发表时间: 2023
• 期刊: Foundations of Genetic Algorithms
• 作者: Jack Kearney;F. Neumann;Andrew M. Sutton
• 通讯作者: Andrew M. Sutton

Finding Antimagic Labelings of Trees by Evolutionary Search

通过进化搜索寻找树木的反魔法标签

• 发表时间: 2023
• 期刊: Foundations of genetic algorithms
• 作者: Branson, Luke;Sutton, Andrew M.;Yan, Xiankun
• 通讯作者: Yan, Xiankun