Sampling in CMA-ES: Low Numbers of Low Discrepancy Points
Preprint
Abstract
The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is one of the most successful examples of a derandomized evolution strategy. However, it still relies on randomly sampling offspring, which can be done via a uniform distribution and subsequently transforming into the required Gaussian. Previous work has shown that replacing this uniform sampling with a low-discrepancy sampler, such as Halton or Sobol sequences, can improve performance over a wide set of problems. We show that iterating through small, fixed sets of low-discrepancy points can still perform better than the default uniform distribution. Moreover, using only 128 points throughout the search is sufficient to closely approximate the empirical performance of using the complete pseudorandom sequence up to dimensionality 40 on the BBOB benchmark. For lower dimensionalities (below 10), we find that using as little as 32 unique low discrepancy points performs similar or better than uniform sampling. In 2D, for which we have highly optimized low discrepancy samples available, we demonstrate that using these points yields the highest empirical performance and requires only 16 samples to improve over uniform sampling. Overall, we establish a clear relation between the $L_2$ discrepancy of the used point set and the empirical performance of the CMA-ES.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Constructing optimal star discrepancy setsProceedings of the American Mathematical Society, Series B, 2025
- Using the Empirical Attainment Function for Analyzing Single-Objective Black-Box Optimization AlgorithmsIEEE Transactions on Evolutionary Computation, 2024
- Heuristic approaches to obtain low-discrepancy point sets via subset selectionJournal of Complexity, 2024
- Tuning as a means of assessing the benefits of new ideas in interplay with existing algorithmic modules2021
- On the discrepancy of jittered samplingJournal of Complexity, 2016
- Completely Derandomized Self-Adaptation in Evolution StrategiesEvolutionary Computation, 2001
- The dispersion of the Hammersley Sequence in the unit squareMonatshefte für Mathematik, 1982
- An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integrationJournal of Computational Physics, 1979
- On the distribution of points in a cube and the approximate evaluation of integralsUSSR Computational Mathematics and Mathematical Physics, 1967
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integralsNumerische Mathematik, 1960