---
_id: '1336'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
author:
- first_name: Tiago
  full_name: Paixao, Tiago
  id: 2C5658E6-F248-11E8-B48F-1D18A9856A87
  last_name: Paixao
  orcid: 0000-0003-2361-3953
- first_name: Jorge
  full_name: Pérez Heredia, Jorge
  last_name: Pérez Heredia
- first_name: Dirk
  full_name: Sudholt, Dirk
  last_name: Sudholt
- first_name: Barbora
  full_name: Trubenova, Barbora
  id: 42302D54-F248-11E8-B48F-1D18A9856A87
  last_name: Trubenova
  orcid: 0000-0002-6873-2967
citation:
  ama: Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. Towards a runtime comparison
    of natural and artificial evolution. <i>Algorithmica</i>. 2017;78(2):681-713.
    doi:<a href="https://doi.org/10.1007/s00453-016-0212-1">10.1007/s00453-016-0212-1</a>
  apa: Paixao, T., Pérez Heredia, J., Sudholt, D., &#38; Trubenova, B. (2017). Towards
    a runtime comparison of natural and artificial evolution. <i>Algorithmica</i>.
    Springer. <a href="https://doi.org/10.1007/s00453-016-0212-1">https://doi.org/10.1007/s00453-016-0212-1</a>
  chicago: Paixao, Tiago, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova.
    “Towards a Runtime Comparison of Natural and Artificial Evolution.” <i>Algorithmica</i>.
    Springer, 2017. <a href="https://doi.org/10.1007/s00453-016-0212-1">https://doi.org/10.1007/s00453-016-0212-1</a>.
  ieee: T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “Towards a runtime
    comparison of natural and artificial evolution,” <i>Algorithmica</i>, vol. 78,
    no. 2. Springer, pp. 681–713, 2017.
  ista: Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2017. Towards a runtime
    comparison of natural and artificial evolution. Algorithmica. 78(2), 681–713.
  mla: Paixao, Tiago, et al. “Towards a Runtime Comparison of Natural and Artificial
    Evolution.” <i>Algorithmica</i>, vol. 78, no. 2, Springer, 2017, pp. 681–713,
    doi:<a href="https://doi.org/10.1007/s00453-016-0212-1">10.1007/s00453-016-0212-1</a>.
  short: T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 78 (2017)
    681–713.
date_created: 2018-12-11T11:51:27Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T11:14:42Z
day: '01'
ddc:
- '576'
department:
- _id: NiBa
- _id: CaGu
doi: 10.1007/s00453-016-0212-1
ec_funded: 1
external_id:
  isi:
  - '000400379500013'
file:
- access_level: open_access
  checksum: 7873f665a0c598ac747c908f34cb14b9
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:19Z
  date_updated: 2020-07-14T12:44:44Z
  file_id: '4805'
  file_name: IST-2016-658-v1+1_s00453-016-0212-1.pdf
  file_size: 710206
  relation: main_file
file_date_updated: 2020-07-14T12:44:44Z
has_accepted_license: '1'
intvolume: '        78'
isi: 1
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 681 - 713
project:
- _id: 25B1EC9E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '618091'
  name: Speed of Adaptation in Population Genetics and Evolutionary Computation
publication: Algorithmica
publication_identifier:
  issn:
  - '01784617'
publication_status: published
publisher: Springer
publist_id: '5931'
pubrep_id: '658'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Towards a runtime comparison of natural and artificial evolution
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 78
year: '2017'
...