Mutation, Sexual Reproduction and Survival in Dynamic Environments
Mutation, Sexual Reproduction and Survival in Dynamic Environments
复制标题
动态环境中的突变、有性生殖和生存
DOI：
10.4230/lipics.itcs.2017.16
复制
发表时间：
2015
期刊：
影响因子：
19.7
通讯作者：
V. Vazirani
中科院分区：
文献类型：
--
作者：
R. Mehta;Ioannis Panageas;G. Piliouras;P. Tetali;V. Vazirani
一种了解进化的新方法[Val09]，即通过计算的镜头观察它，已经开始产生新的见解，例如，在性重现下的自然选择可以解释为在协调游戏中玩过的乘量重量更新（MWU）算法，基因[CLPV14]。使用这种机械，我们研究了在有性繁殖存在下突变在不断变化的环境中的作用。在[WVA05]之后，我们通过Markov链对环境进行建模，其状态代表环境，每个环境都有自己的健身矩阵。在这种情况下，我们表明，在没有突变的情况下，人口灭绝，但是在存在突变的情况下，人口以积极的概率生存。在证明上述定理的路上，我们需要建立一些有关游戏中动态的事实。据我们所知，我们在协调游戏中为嘈杂的MWU提供了第一个融合。最后，我们还表明，在静态环境中，对于任何级别的突变，都会有性进化。
A new approach to understanding evolution [Val09], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [CLPV14]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [WVA05], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.