First steps towards a runtime comparison of natural and artificial evolution Conference Paper


Author(s): Paixão, Tiago; Sudholt, Dirk; Heredia, Jorge P; Trubenová, Barbora
Title: First steps towards a runtime comparison of natural and artificial evolution
Affiliation IST Austria
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 their runtime 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 occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (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.
Keywords: theory; Population Genetics; Natural evolution; Runtime analysis; Strong selection weak mutation regime
Conference Title: GECCO: Genetic and evolutionary computation conference
Conference Dates: July, 11 - 15, 2015
Conference Location: Madrid, Spain
ISBN: 978-1-4503-1963-8
Publisher: ACM  
Date Published: 2015-07-11
Start Page: 1455
End Page: 1462
Sponsor: The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE).
URL:
DOI: 10.1145/2739480.2754758
Notes: The authors thank the anonymous GECCO reviewers for their many constructive comments.
Open access: yes (repository)