Towards a Runtime Comparison of Natural and Artificial Evolution
Towards a Runtime Comparison of Natural and Artificial Evolution
复制标题
自然进化和人工进化的运行时比较
作者：
T. Paixão;Jorge Pérez Heredia;Dirk Sudholt;Barbora Trubenová
进化算法（EAs）形成了一种受自然进化启发的流行优化范式。近年来，进化计算领域已经发展出一种严格的分析理论来分析ea在许多说明性问题上的运行时间。这里我们把这个理论应用到一个简单的自然进化模型中。在强选择弱突变（SSWM）进化机制中，新突变发生之间的时间间隔比突变基因型接管种群所需的时间要长得多。在这种情况下，种群只包含一种基因型的拷贝，进化可以被建模为一个随机过程，通过突变和居民与突变基因型之间的选择来进化一种基因型。接受突变基因型的可能性取决于适应度的变化。我们从算法的角度研究了这一过程，即SSWM，量化了其对各种参数的预期优化时间，并研究了与类似的进化算法（1+1）EA的差异。我们表明，SSWM在交叉适应度谷时比（1+1）EA具有适度的优势，并研究了一个SSWM通过利用适应度梯度信息优于（1+1）EA的例子。
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.