Graceful scaling on uniform versus steep-tailed noise

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

doi:10.1007/978-3-319-45823-6_71

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 proceeding › Conference contribution

5 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings
Editors	Emma Hart, Ben Paechter, Julia Handl, Manuel López-Ibáñez, Peter R. Lewis, Gabriela Ochoa
Publisher	Springer Verlag
Pages	761-770
Number of pages	10
ISBN (Print)	9783319458229
DOIs	https://doi.org/10.1007/978-3-319-45823-6_71
State	Published - 2016
Externally published	Yes
Event	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 - Edinburgh, United Kingdom Duration: Sep 17 2016 → Sep 21 2016

Publication series

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

Other

Other	14th International Conference on Parallel Problem Solving from Nature, PPSN 2016
Country/Territory	United Kingdom
City	Edinburgh
Period	9/17/16 → 9/21/16

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.

Keywords

Evolutionary algorithm
Noisy fitness
Theory

Access

10.1007/978-3-319-45823-6_71

OpenUrl availability

Full text

Cite this

Friedrich, T., Kötzing, T., Krejca, M. S., & Sutton, A. M. (2016). Graceful scaling on uniform versus steep-tailed noise. In E. Hart, B. Paechter, J. Handl, M. López-Ibáñez, P. R. Lewis, & G. Ochoa (Eds.), Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings (pp. 761-770). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9921 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-45823-6_71

Graceful scaling on uniform versus steep-tailed noise. / Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S. et al.
Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. ed. / Emma Hart; Ben Paechter; Julia Handl; Manuel López-Ibáñez; Peter R. Lewis; Gabriela Ochoa. Springer Verlag, 2016. p. 761-770 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9921 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Friedrich, T, Kötzing, T, Krejca, MS & Sutton, AM 2016, Graceful scaling on uniform versus steep-tailed noise. in E Hart, B Paechter, J Handl, M López-Ibáñez, PR Lewis & G Ochoa (eds), Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9921 LNCS, Springer Verlag, pp. 761-770, 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016, Edinburgh, United Kingdom, 9/17/16. https://doi.org/10.1007/978-3-319-45823-6_71

Friedrich T, Kötzing T, Krejca MS, Sutton AM. Graceful scaling on uniform versus steep-tailed noise. In Hart E, Paechter B, Handl J, López-Ibáñez M, Lewis PR, Ochoa G, editors, Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. Springer Verlag. 2016. p. 761-770. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-45823-6_71

Friedrich, Tobias ; Kötzing, Timo ; Krejca, Martin S. et al. / Graceful scaling on uniform versus steep-tailed noise. Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings. editor / Emma Hart ; Ben Paechter ; Julia Handl ; Manuel López-Ibáñez ; Peter R. Lewis ; Gabriela Ochoa. Springer Verlag, 2016. pp. 761-770 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{304a26a1cc5e48d19acd37deaba4aa17,

title = "Graceful scaling on uniform versus steep-tailed noise",

abstract = "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.",

keywords = "Evolutionary algorithm, Noisy fitness, Theory",

author = "Tobias Friedrich and Timo K{\"o}tzing and Krejca, {Martin S.} and Sutton, {Andrew M.}",

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: {\textcopyright} Springer International Publishing AG 2016.; 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 ; Conference date: 17-09-2016 Through 21-09-2016",

year = "2016",

doi = "10.1007/978-3-319-45823-6_71",

language = "English (US)",

isbn = "9783319458229",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "761--770",

editor = "Emma Hart and Ben Paechter and Julia Handl and Manuel L{\'o}pez-Ib{\'a}{\~n}ez and Lewis, {Peter R.} and Gabriela Ochoa",

booktitle = "Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings",

}

TY - GEN

T1 - Graceful scaling on uniform versus steep-tailed noise

AU - Friedrich, Tobias

AU - Kötzing, Timo

AU - Krejca, Martin S.

AU - Sutton, Andrew M.

N1 - 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.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Evolutionary algorithm

KW - Noisy fitness

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=84988527827&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988527827&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-45823-6_71

DO - 10.1007/978-3-319-45823-6_71

M3 - Conference contribution

AN - SCOPUS:84988527827

SN - 9783319458229

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 761

EP - 770

BT - Parallel Problem Solving from Nature - 14th International Conference, PPSN 2016, Proceedings

A2 - Hart, Emma

A2 - Paechter, Ben

A2 - Handl, Julia

A2 - López-Ibáñez, Manuel

A2 - Lewis, Peter R.

A2 - Ochoa, Gabriela

PB - Springer Verlag

T2 - 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016

Y2 - 17 September 2016 through 21 September 2016

ER -

Graceful scaling on uniform versus steep-tailed noise

Abstract

Publication series

Other

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this