# First Steps Towards a Runtime Comparison of Natural and Artificial Evolution

arXiv: https://arxiv.org/abs/1504.06260 · HTML: https://mlsanity.com/paper/1504.06260/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2015.

## Built on by (most cited first, 6 of 6)

- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [Hyper-Heuristics Can Profit From Global Variation Operators](https://mlsanity.com/paper/2407.14237/) (2024)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [When Non-Elitism Meets Time-Linkage Problems](https://mlsanity.com/paper/2104.06831/) (2021)

## Abstract (arXiv)

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.