Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES)
Abstract
This paper presents a novel evolutionary optimization strategy based on the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). This new approach is intended to reduce the number of generations required for convergence to the optimum. Reducing the number of generations, i.e., the time complexity of the algorithm, is important if a large population size is desired: (1) to reduce the effect of noise; (2) to improve global search properties; and (3) to implement the algorithm on (highly) parallel machines. Our method results in a highly parallel algorithm which scales favorably with large numbers of processors. This is accomplished by efficiently incorporating the available information from a large population, thus significantly reducing the number of generations needed to adapt the covariance matrix. The original version of the CMA-ES was designed to reliably adapt the covariance matrix in small populations but it cannot exploit large populations efficiently. Our modifications scale up the efficiency to population sizes of up to 10n, where n is the problem dimension. This method has been applied to a large number of test problems, demonstrating that in many cases the CMA-ES can be advanced from quadratic to linear time complexity.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
MoG-VQE combines NSGA-II, a multiobjective genetic algorithm, and CMA-ES to tune parameters and evaluate optimized energies for qubit topologies.
“The MoG-VQE algorithm combines two evolutionary strategies: i) NSGA-II (Deb et al. , 2000), a multiobjective genetic algorithm, to propose a circuit structure to minimize both the energy and CNOT count, and ii) CMA-ES (Hansen et al. , 2003) to tune parameters and evaluate optimized energies for the qubit topologies suggested by the NSGA-II algorithm.”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Hansen et al., 2003
Traditional stochastic optimization strategies for 2D/3D registration are numeric-based methods without derivatives, such as CMAES or BOBYQA.
“Thus, traditional stochastic optimization strategies are numeric-based methods without derivatives, such as Covariance Matrix Adaptation Evolution Strategy (CMAES) [26] or BOBYQA [27].”
From A Fully Differentiable Framework for 2D/3D Registration and the Projective Spatial Transformers (2024) · cites this paper as [26]
Cites
Completely Derandomized Self-Adaptation in Evolution Strategies
Hansen, N., & Ostermeier, A. (2001) · Evolutionary Computation · doi:10.1162/106365601750190398 · Cited by 4,397 · see citing works
Self-citationEvolutionary computation: Comments on the history and current state
Back, T., Hammel, U., & Schwefel, H.-P. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585888 · Cited by 1,536 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Deep learning in neural networks: an overview
Schmidhuber, J. (2015) · Neural Networks · doi:10.1016/j.neunet.2014.09.003 · Cited by 18,570 · see citing works
Machine Learning for Fluid Mechanics
Brunton, S. L., Noack, B. R., & Koumoutsakos, P. (2020) · Annual Review of Fluid Mechanics · doi:10.1146/annurev-fluid-010719-060214 · Cited by 3,063 · see citing works
Self-citationNoisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Review of numerical optimization techniques for meta-device design [Invited]
Campbell, S. D., Sell, D., Jenkins, R. P., Whiting, E. B., Fan, J. A., & Werner, D. H. (2019) · Optical Materials Express · doi:10.1364/ome.9.001842 · Cited by 322 · see citing works
Hughes, R. T., Zhu, L., & Bednarz, T. (2021) · Frontiers in Artificial Intelligence · doi:10.3389/frai.2021.604234 · Cited by 178 · see citing works
Chimera: enabling hierarchy based multi-objective optimization for self-driving laboratories
Häse, F., Roch, L. M., & Aspuru-Guzik, A. (2018) · Chemical Science · doi:10.1039/c8sc02239a · Cited by 161 · see citing works
Unberath, M., Gao, C., Hu, Y., Judish, M., Taylor, R. H., Armand, M., & Grupp, R. (2021) · Frontiers in Robotics and AI · doi:10.3389/frobt.2021.716007 · Cited by 102 · see citing works
“1 using gradient-based or gradient-free methods, such as BFGS [22, 23] or CMA-ES [24] and BOBYQA [25], respectively.”
MethodA curious formulation robot enables the discovery of a novel protocell behavior
Grizou, J., Points, L. J., Sharma, A., & Cronin, L. (2020) · Science Advances · doi:10.1126/sciadv.aay4237 · Cited by 77 · see citing works
Human-competitive lens system design with evolution strategies
Gagné, C., Beaulieu, J., Parizeau, M., & Thibault, S. (2008) · Applied Soft Computing · doi:10.1016/j.asoc.2007.10.018 · Cited by 37 · see citing works
Seventekidis, P., & Giagopoulos, D. (2023) · Mechanical Systems and Signal Processing · doi:10.1016/j.ymssp.2022.109741 · Cited by 37 · see citing works
A Fully Differentiable Framework for 2D/3D Registration and the Projective Spatial Transformers
Gao, C., Feng, A., Liu, X., Taylor, R. H., Armand, M., & Unberath, M. (2024) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2023.3299588 · Cited by 36 · see citing works
“1 Thus, traditional stochastic optimization strategies are numeric-based methods without derivatives, such as Covariance Matrix Adaptation Evolution Strategy (CMAES) [26] or BOBYQA [27].”
MethodPredictive simulations identify potential neuromuscular contributors to idiopathic toe walking
Veerkamp, K., van der Krogt, M. M., Waterval, N. F. J., Geijtenbeek, T., Walsh, H. P. J., Harlaar, J., Buizer, A. I., Lloyd, D. G., & Carty, C. P. (2024) · Clinical Biomechanics · doi:10.1016/j.clinbiomech.2023.106152 · Cited by 13 · see citing works
Ku, P.-C., Martin-Gomez, A., Gao, C., Grupp, R., Mears, S. C., & Armand, M. (2023) · Computer Methods in Biomechanics and Biomedical Engineering: Imaging & Visualization · doi:10.1080/21681163.2022.2152375 · Cited by 8 · see citing works
EvolKV: Evolutionary KV Cache Compression for LLM Inference
Yu, B., & Chai, Y. (2025) · Findings of the Association for Computational Linguistics: EMNLP 2025 · doi:10.18653/v1/2025.findings-emnlp.88
- Authors
- Hansen, N., Müller, S. D., & Koumoutsakos, P.
- Affiliations
- Technische Universität Berlin (DE)
- ETH Zurich (CH)
- Venue
- Evolutionary Computation
- Publisher
- MIT Press
- Published
- 2003-03
- Volume
- 11
- Issue
- 1
- Pages
- 1-18
- ISSN
- 1063-6560 (ISSN-L)
- 1530-9304
- OpenAlex
- W2138537392
- Cited by
- 2,601
- References
- 2
- Citations by year
- 2026: 158 · 2025: 198 · 2024: 212 · 2023: 225 · 2022: 220 · 2021: 194 · 2020: 213 · 2019: 158 · 2018: 171 · 2017: 99 · 2016: 111 · 2015: 81 · 2014: 104 · 2013: 68 · 2012: 80
- FWCI
- 17.04
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Evolutionary Computation (publishedVersion)
- PubMed (publishedVersion)
- Funders
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- CMA-ES, covariance matrix adaptation, time complexity, large population size, parallel evolutionary algorithms, convergence rate, global optimization
- MeSH terms
- Algorithms, Computer Simulation, Biological Evolution, Models, Genetic, Population Density, Time Factors, Models, Statistical
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
