An Adaptive Re-evaluation Method for Evolution Strategy under Additive Noise

arXiv (Cornell University)

Abstract

The Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) is one of the most advanced algorithms in numerical black-box optimization. For noisy objective functions, several approaches were proposed to mitigate the noise, e.g., re-evaluations of the same solution or adapting the population size. In this paper, we devise a novel method to adaptively choose the optimal re-evaluation number for function values corrupted by additive Gaussian white noise. We derive a theoretical lower bound of the expected improvement achieved in one iteration of CMA-ES, given an estimation of the noise level and the Lipschitz constant of the function's gradient. Solving for the maximum of the lower bound, we obtain a simple expression of the optimal re-evaluation number. We experimentally compare our method to the state-of-the-art noise-handling methods for CMA-ES on a set of artificial test functions across various noise levels, optimization budgets, and dimensionality. Our method demonstrates significant advantages in terms of the probability of hitting near-optimal function values.

Authors 4

1. Catalin-Viorel Dinu Aachen

   Leiden University

   Affiliation as printed

   Leiden University Leiden , The Netherlands

2. Yash J. Patel Aachen applied Quantum algorithms (aQa)

   Leiden University · University of Applied Sciences Leiden

   Affiliation as printed

   applied Quantum algorithms , Leiden University LIACS , Leiden University Leiden , The Netherlands

3. Xavier Bonet-Monroig Aachen

   Leiden University

   Affiliation as printed

   Honda Research Institute Europe GmbH Frankfurt , Germany Instituut-Lorentz ,

   Leiden University Leiden , The Netherlands

4. Hao Wang Aachen applied Quantum algorithms (aQa)

   Leiden University · University of Applied Sciences Leiden

   Affiliation as printed

   applied Quantum algorithms , Leiden University LIACS , Leiden University Leiden , The Netherlands