Abstract
Surrogate models are employed in evolutionary algorithms to replace expensive objective function evaluations with cheaper though usually inaccurate estimates based on information gained in past iterations. Implications of the trade-off between computational savings on the one hand and potentially poor steps due to the inaccurate assessment of candidate solutions on the other are generally not well understood. We study the trade-off in the context of a surrogate model assisted \((1+1)\)-ES by considering a simple model for single steps. Based on the insights gained, we propose a step size adaptation mechanism for the strategy and experimentally evaluate it using several test functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arnold, D.V.: Noisy Optimization with Evolution Strategies. Kluwer, Dordrecht (2002)
Arnold, D.V., Beyer, H.-G.: A general noise model and its effects on evolution strategy performance. IEEE Trans. Evol. Comput. 10(4), 380–391 (2006)
Auger, A., Hansen, N., Perez Zerpa, J.M., Ros, R., Schoenauer, M.: Experimental comparisons of derivative free optimization algorithms. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 3–15. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02011-7_3
Büche, D., Schraudolph, N.N., Koumoutsakos, P.: Accelerating evolutionary algorithms with Gaussian process fitness function models. IEEE Trans. Syst. Man Cybern. B Cybern. Part C 35(2), 183–194 (2005)
Chen, Y., Zou, X.: Performance analysis of a (1+1) surrogate-assisted evolutionary algorithm. In: Huang, D.-S., Bevilacqua, V., Premaratne, P. (eds.) ICIC 2014. LNCS, vol. 8588, pp. 32–40. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09333-8_4
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_44
Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159–195 (2001)
Jin, Y.: Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol. Comput. 1(2), 61–70 (2011)
Kern, S., Hansen, N., Koumoutsakos, P.: Local meta-models for optimization using evolution strategies. In: Runarsson, T.P., Beyer, H.-G., Burke, E., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 939–948. Springer, Heidelberg (2006). https://doi.org/10.1007/11844297_95
Kern, S., Müller, S.D., Hansen, N., Büche, D., Ocenasek, J., Koumoutsakos, P.: Learning probability distributions in continuous evolutionary algorithms – a comparative review. Nat. Comput. 3(1), 77–112 (2004)
Loshchilov, I.: Surrogate-Assisted Evolutionary Algorithms. PhD thesis, Université Paris Sud - Paris XI (2013)
Loshchilov, I., Schoenauer, M., Sebag, M.: Comparison-based optimizers need comparison-based surrogates. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 364–373. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15844-5_37
Loshchilov, I., Schoenauer, M., Sebag, M.: Intensive surrogate model exploitation in self-adaptive surrogate-assisted CMA-ES. In: Genetic and Evolutionary Computation Conference – GECCO 2013, pp. 439–446. ACM Press (2013)
Pitra, Z., Bajer, L., Repický, J., Holena, M.: Overview of surrogate-model versions of covariance matrix adaptation evolution strategy. In: Genetic and Evolutionary Computation Conference Companion, pp. 1622–1629. ACM Press (2017)
Rechenberg, I.: Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Friedrich Frommann Verlag, Stuttgart (1973)
Schwefel, H.-P.: Numerical Optimization of Computer Models. Wiley, Hoboken (1981)
Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Runarsson, T.P., Beyer, H.-G., Burke, E., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 21–31. Springer, Heidelberg (2006). https://doi.org/10.1007/11844297_3
Ulmer, H., Streichert, F., Zell, A.: Model-assisted steady-state evolution strategies. In: Cantú-Paz, E. (ed.) GECCO 2003. LNCS, vol. 2723, pp. 610–621. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45105-6_72
Acknowledgements
This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Kayhani, A., Arnold, D.V. (2018). Design of a Surrogate Model Assisted (1 + 1)-ES. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-99253-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99252-5
Online ISBN: 978-3-319-99253-2
eBook Packages: Computer ScienceComputer Science (R0)