Towards a runtime comparison of natural and artificial evolution

Paixão, Tiago and Pérez Heredia, Jorge and Sudholt, Dirk and Trubenová, Barbora (2016) Towards a runtime comparison of natural and artificial evolution. Algorithmica. ISSN 1432-0541

[img] Text
s00453-016-0212-1.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2016-658-v1+1]
Download (693Kb)
Official URL: http://dx.doi.org/10.1007/s00453-016-0212-1

Abstract

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.

Item Type: Article
Uncontrolled Keywords: theory, Population Genetics, Natural evolution, Runtime analysis, Strong selection weak mutation regime, Evolutionary algorithms
Subjects: 500 Science > 570 Life sciences; biology > 576 Genetics and evolution
Research Group: Barton Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 09 Nov 2016 15:27
Last Modified: 30 Aug 2017 07:56
URI: https://repository.ist.ac.at/id/eprint/658

Actions (login required)

View Item View Item