First steps towards a runtime comparison of natural and artificial evolution

T. Paixao, D. Sudholt, J. Heredia, B. Trubenova, in:, Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, 2015, pp. 1455–1462.


Conference Paper | Published | English
Author
; ; ;
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.
Publishing Year
Date Published
2015-07-11
Proceedings Title
Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation
Page
1455 - 1462
Conference
GECCO: Genetic and evolutionary computation conference
Conference Location
Madrid, Spain
Conference Date
2015-07-11 – 2015-07-15
IST-REx-ID

Cite this

Paixao T, Sudholt D, Heredia J, Trubenova B. First steps towards a runtime comparison of natural and artificial evolution. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM; 2015:1455-1462. doi:10.1145/2739480.2754758
Paixao, T., Sudholt, D., Heredia, J., & Trubenova, B. (2015). First steps towards a runtime comparison of natural and artificial evolution. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp. 1455–1462). Madrid, Spain: ACM. https://doi.org/10.1145/2739480.2754758
Paixao, Tiago, Dirk Sudholt, Jorge Heredia, and Barbora Trubenova. “First Steps towards a Runtime Comparison of Natural and Artificial Evolution.” In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 1455–62. ACM, 2015. https://doi.org/10.1145/2739480.2754758.
T. Paixao, D. Sudholt, J. Heredia, and B. Trubenova, “First steps towards a runtime comparison of natural and artificial evolution,” in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain, 2015, pp. 1455–1462.
Paixao T, Sudholt D, Heredia J, Trubenova B. 2015. First steps towards a runtime comparison of natural and artificial evolution. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. GECCO: Genetic and evolutionary computation conference 1455–1462.
Paixao, Tiago, et al. “First Steps towards a Runtime Comparison of Natural and Artificial Evolution.” Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, 2015, pp. 1455–62, doi:10.1145/2739480.2754758.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar