More Web Proxy on the site http://driver.im/

research-article

First Steps Towards a Runtime Comparison of Natural and Artificial Evolution

Authors:

Jorge Pérez Heredia,

Barbora TrubenovaAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1455 - 1462

https://doi.org/10.1145/2739480.2754758

Published: 11 July 2015 Publication History

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.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics -- Foundations and Recent Developments. Number 1 in Series on Theoretical Computer Science. World Scientific, 2011.

Digital Library

[2]

E. Chastain, A. Livnat, C. Papadimitriou, and U. Vazirani. Algorithms, games, and evolution. Proceedings of the National Academy of Sciences, 111(29):10620--10623, July 2014.

[3]

K. Chatterjee, A. Pavlogiannis, B. Adlam, and M. A. Nowak. The time scale of evolutionary innovation. PLoS Computational Biology, 10(9), Sept. 2014.

[4]

D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre. Level-based analysis of genetic algorithms and other search processes. In PPSN 2014, pages 912--921. Springer, 2014.

[5]

B. Doerr. Analyzing randomized search heuristics: Tools from probability theory. InciteAuger2011, pages 1--20. World Scientific, 2011.

[6]

J. H. Gillespie. Molecular evolution over the mutational landscape. Evolution, 38(5):1116--1129, 1984.

[7]

J. Jägersküpper and T. Storch. When the plus strategy outperforms the comma strategy and when not. In Proc.\ of IEEE FOCI 2007, pages 25--32. IEEE, 2007.

[8]

T. Jansen. Analyzing Evolutionary Algorithms. The Computer Science Perspective. Springer, 2013.

Digital Library

[9]

T. Jansen, P. S. Oliveto, and C. Zarges. On the analysis of the immune-inspired B-Cell algorithm for the Vertex Cover problem. In Proc.\ of ICARIS 2011, pages 117--131. Springer, 2011.

Digital Library

[10]

T. Jansen and I. Wegener. A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation. Theoretical Computer Science, 386(1--2):73--93, 2007.

Digital Library

[11]

D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universit\"at des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institut für Informatik, 2010.

[12]

M. Kimura. On the probability of fixation of mutant genes in a population. Genetics, 47(6):713--719, 1962.

[13]

P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623--642, 2012.

Digital Library

[14]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[15]

P. S. Oliveto and D. Sudholt. On the runtime analysis of stochastic ageing mechanisms. In Proc. of GECCO 2014, pages 113--120. ACM Press, 2014.

Digital Library

[16]

P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369--386, 2011.

Digital Library

[17]

P. S. Oliveto and C. Witt. On the runtime analysis of the simple genetic algorithm. Theoretical Computer Science, 545:2--19, 2014.

Digital Library

[18]

T. Paixão, J. Pérez Heredia, D. Sudholt, and B. Trubenová. First steps towards a runtime comparison of natural and artificial evolution. ArXiv e-prints, 2015. Available from http://arxiv.org/abs/1504.06260.

[19]

P. Rohlfshagen, P. K. Lehre, and X. Yao. Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change. In Proc. of GECCO '09, pages 1713--1720. ACM Press, 2009.

Digital Library

[20]

J. E. Rowe and D. Sudholt. The choice of the offspring population size in the (1,łambda) evolutionary algorithm. Theoretical Computer Science, 545:20--38, 2014.

Digital Library

[21]

D. Sudholt. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 17(3):418--435, 2013.

Digital Library

[22]

L. G. Valiant. Evolvability. J. ACM, 56(1):3:1--3:21, 2009.

Digital Library

Cited By

Li MZheng WXie WSun AYao X(2024)When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_18(280-294)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_18
Trubenová BKrejca MLehre PKötzing T(2019)Surfing on the seascape: Adaptation in a changing environmentEvolution10.1111/evo.13784Online publication date: 28-Jun-2019
https://doi.org/10.1111/evo.13784
Qian CYu YTang KJin YYao XZhou Z(2018)On the effectiveness of sampling for evolutionary optimization in noisy environmentsEvolutionary Computation10.1162/evco_a_0020126:2(237-267)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1162/evco_a_00201
Show More Cited By

Index Terms

First Steps Towards a Runtime Comparison of Natural and Artificial Evolution
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length l, influence the runtime of different strategies for crossing these ...
Towards a Runtime Comparison of Natural and Artificial Evolution

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 ...
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism

Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Commission

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
113
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li MZheng WXie WSun AYao X(2024)When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_18(280-294)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_18
Trubenová BKrejca MLehre PKötzing T(2019)Surfing on the seascape: Adaptation in a changing environmentEvolution10.1111/evo.13784Online publication date: 28-Jun-2019
https://doi.org/10.1111/evo.13784
Qian CYu YTang KJin YYao XZhou Z(2018)On the effectiveness of sampling for evolutionary optimization in noisy environmentsEvolutionary Computation10.1162/evco_a_0020126:2(237-267)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1162/evco_a_00201
Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Sudholt D(2017)How crossover speeds up building block assembly in genetic algorithmsEvolutionary Computation10.1162/EVCO_a_0017125:2(237-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00171
Corus DOliveto PYazdani DBosman P(2017)On the runtime analysis of the opt-IA artificial immune systemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3079194(83-90)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3079194
Doerr B(2017)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067713(389-412)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067713
Paixão TPérez Heredia JSudholt DTrubenová B(2017)Towards a Runtime Comparison of Natural and Artificial EvolutionAlgorithmica10.1007/s00453-016-0212-178:2(681-713)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s00453-016-0212-1
Heredia JTrubenová BSudholt DPaixão T(2016)Selection Limits to Adaptive Walks on Correlated LandscapesGenetics10.1534/genetics.116.189340205:2(803-825)Online publication date: 23-Nov-2016
https://doi.org/10.1534/genetics.116.189340
Doerr BDoerr CNeumann FSutton A(2016)Theory for Non-TheoreticiansProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926982(463-482)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926982
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten