Towards a runtime comparison of natural and artificial evolution

T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 78 (2017) 681–713.

Download
OA IST-2016-658-v1+1_s00453-016-0212-1.pdf 710.21 KB

Journal Article | Published | English

Scopus indexed
Author
Paixao, TiagoIST Austria ; Pérez Heredia, Jorge; Sudholt, Dirk; Trubenova, BarboraIST 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 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.
Publishing Year
Date Published
2017-06-01
Journal Title
Algorithmica
Volume
78
Issue
2
Page
681 - 713
ISSN
IST-REx-ID

Cite this

Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. Towards a runtime comparison of natural and artificial evolution. Algorithmica. 2017;78(2):681-713. doi:10.1007/s00453-016-0212-1
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. https://doi.org/10.1007/s00453-016-0212-1
Paixao, Tiago, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “Towards a Runtime Comparison of Natural and Artificial Evolution.” Algorithmica 78, no. 2 (2017): 681–713. https://doi.org/10.1007/s00453-016-0212-1.
T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “Towards a runtime comparison of natural and artificial evolution,” Algorithmica, vol. 78, no. 2, pp. 681–713, 2017.
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.
Paixao, Tiago, et al. “Towards a Runtime Comparison of Natural and Artificial Evolution.” Algorithmica, vol. 78, no. 2, Springer, 2017, pp. 681–713, doi:10.1007/s00453-016-0212-1.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
7873f665a0c598ac747c908f34cb14b9


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar