Graceful scaling on uniform versus steep-tailed noise

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


Recently, different evolutionary algorithms (EAs) have been analyzed in noisy environments. The most frequently used noise model for this was additive posterior noise (noise added after the fitness evaluation) taken from a Gaussian distribution. In particular, for this setting it was shown that the (μ + 1)-EA on OneMax does not scale gracefully (higher noise cannot efficiently be compensated by higher μ). In this paper we want to understand whether there is anything special about the Gaussian distribution which makes the (μ + 1)-EA not scale gracefully. We keep the setting of posterior noise, but we look at other distributions. We see that for exponential tails the (μ + 1)-EA on OneMax does also not scale gracefully, for similar reasons as in the case of Gaussian noise. On the other hand, for uniform distributions (as well as other, similar distributions) we see that the (μ + 1)-EA on OneMax does scale gracefully, indicating the importance of the noise model.

Original languageEnglish (US)
Title of host publicationParallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings
EditorsEmma Hart, Ben Paechter, Julia Handl, Manuel López-Ibáñez, Peter R. Lewis, Gabriela Ochoa
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783319458229
StatePublished - 2016
Externally publishedYes
Event14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom
Duration: Sep 17 2016Sep 21 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9921 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/TerritoryUnited Kingdom

Bibliographical note

Funding Information:
The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 618091 (SAGE) and the German Research Foundation (DFG) under grant agreement no. FR 2988 (TOSU).

Publisher Copyright:
© Springer International Publishing AG 2016.


  • Evolutionary algorithm
  • Noisy fitness
  • Theory


Dive into the research topics of 'Graceful scaling on uniform versus steep-tailed noise'. Together they form a unique fingerprint.

Cite this