Back to search

University of Sheffield

A Computational View on Natural Evolution: On the Rigorous Analysis of the Speed of Adaptation

Abstract

dc:description.abstract

Inspired by Darwin’s ideas, Turing (1948) proposed an evolutionary search as an automated problem solving approach. Mimicking natural evolution, evolutionary algorithms evolve a set of solutions through the repeated application of the evolutionary operators (mutation, recombination and selection). Evolutionary algorithms belong to the family of black box algorithms which are general purpose optimisation tools. They are typically used when no good specific algorithm is known for the problem at hand and they have been reported to be surprisingly effective (Eiben and Smith, 2015; Sarker et al., 2002). Interestingly, although evolutionary algorithms are heavily inspired by natural evolution, their study has deviated from the study of evolution by the population genetics community. We believe that this is a missed opportunity and that both fields can benefit from an interdisciplinary collaboration. The question of how long it takes for a natural population to evolve complex adaptations has fascinated researchers for decades. We will argue that this is an equivalent research question to the runtime analysis of algorithms. By making use of the methods and techniques used in both fields, we will derive plenty of meaningful results for both communities, proving that this interdisciplinary approach is effective and relevant. We will apply the tools used in the theoretical analysis of evolutionary algorithms to quantify the complexity of adaptive walks on many landscapes, illustrating how the structure of the fitness landscape and the parameter conditions can impose limits to adaptation. Furthermore, as geneticists use diffusion theory to track the change in the allele frequencies of a population, we will develop a brand new model to analyse the dynamics of evolutionary algorithms. Our model, based on stochastic differential equations, will allow to describe not only the expected behaviour, but also to measure how much the process might deviate from that expectation.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Sheffield
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pérez Heredia, Jorge
Advisors dc:contributor.advisor
  • Sudholt, Dirk
  • Oliveto, Pietro S.

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.731555

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Pérez Heredia, Jorge. A Computational View on Natural Evolution: On the Rigorous Analysis of the Speed of Adaptation. doctoral thesis, University of Sheffield, 2017.