Top

Published in:

2020 | OriginalPaper | Chapter

On Averaging the Best Samples in Evolutionary Computation

Authors : Laurent Meunier, Yann Chevaleyre, Jeremy Rapin, Clément W. Royer, Olivier Teytaud

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Choosing the right selection rate is a long standing issue in evolutionary computation. In the continuous unconstrained case, we prove mathematically that a single parent \(\mu =1\) leads to a sub-optimal simple regret in the case of the sphere function. We provide a theoretically-based selection rate \(\mu /\lambda \) that leads to better progress rates. With our choice of selection rate, we get a provable regret of order \(O(\lambda ^{-1})\) which has to be compared with \(O(\lambda ^{-2/d})\) in the case where \(\mu =1\). We complete our study with experiments to confirm our theoretical claims.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Improved Fixed-Budget Results via Drift Analysis

next chapter Filter Sort Is in the Worst Case

Arnold, D.V.: Optimal weighted recombination. In: Wright, A.H., Vose, M.D., De Jong, K.A., Schmitt, L.M. (eds.) FOGA 2005. LNCS, vol. 3469, pp. 215–237. Springer, Heidelberg (2005). https://doi.org/10.1007/11513575_12CrossRef

Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. JMLR 13, 281–305 (2012)MathSciNetMATH

Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13, 281–305 (2012)MathSciNetMATH

Beyer, H.G., Schwefel, H.P.: Evolution strategies -a comprehensive introduction. Natural Comput. Int. J. 1(1), 3–52 (2002). https://doi.org/10.1023/A:1015059928466MathSciNetCrossRefMATH

Beyer, H.-G., Sendhoff, B.: Covariance matrix adaptation revisited – the CMSA evolution strategy –. In: Rudolph, G., Jansen, T., Beume, N., Lucas, S., Poloni, C. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 123–132. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87700-4_13CrossRef

Bousquet, O., Gelly, S., Karol, K., Teytaud, O., Vincent, D.: Critical hyper-parameters: No random, no cry (2017, preprint). https://arxiv.org/pdf/1706.03200.pdf

Bubeck, S., Munos, R., Stoltz, G.: Pure exploration in multi-armed bandits problems. In: Gavaldà, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS (LNAI), vol. 5809, pp. 23–37. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04414-4_7CrossRef

Escalante, H., Reyes, A.M.: Evolution strategies. CCC-INAOE tutorial (2013)

Fournier, H., Teytaud, O.: Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns. Algorithmica (2010)

10.

Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 11(1), 159–195 (2003)CrossRef

11.

Hansen, N., Arnold, D.V., Auger, A.: Evolution strategies. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 871–898. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-43505-2_44CrossRef

12.

Jebalia, M., Auger, A.: Log-linear convergence of the scale-invariant (\({\mu }/{\mu }_{w{\lambda }}\))-ES and optimal \({\mu }\) for intermediate recombination for large population sizes. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 52–62. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_6CrossRef

13.

McKay, M.D., Beckman, R.J., Conover, W.J.: A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21(2), 239–245 (1979)MathSciNetMATH

14.

Niederreiter, H.: Random Number Generation and quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1992)CrossRef

15.

Rapin, J., Teytaud, O.: Nevergrad - A gradient-free optimization platform. https://GitHub.com/FacebookResearch/Nevergrad (2018)

16.

Teytaud, F.: A new selection ratio for large population sizes. In: Di Chio, C., et al. (eds.) EvoApplications 2010. LNCS, vol. 6024, pp. 452–460. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12239-2_47CrossRef

17.

Teytaud, F., Teytaud, O.: Why one must use reweighting in estimation of distribution algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2009, Proceedings, Montreal, Québec, Canada, 8–12 July 2009, pp. 453–460 (2009)

Title: On Averaging the Best Samples in Evolutionary Computation
Authors: Laurent Meunier
Yann Chevaleyre
Jeremy Rapin
Clément W. Royer
Olivier Teytaud
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_46

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner