research-article

Effect of the mean vector learning rate in CMA-ES

Authors:

Hidekazu Miyazawa,

Youhei AkimotoAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 721 - 728

https://doi.org/10.1145/3071178.3071203

Published: 01 July 2017 Publication History

Abstract

We investigate the effect of the mean vector learning rate in variants of CMA-ES. The learning rate is set to one in the standard setting, but it is natural to set it to a lower value from the perspective of the CMA-ES as the natural gradient method. Our experiments show that decreasing the mean vector learning rate has an effect similar to increasing the population size in the rank-μ update CMA-ES, and well structured multimodal functions can be solved with the default population size by introducing a small learning rate. On the contrary, the CMA-ES with the cumulative step-size adaptation (CSA) fails to locate the global optimum on well structured multimodal functions with the default population size even if a small learning rate is introduced. The results are discussed from the viewpoint of KL-divergence in relation with the optimal step-size. A parameter setting for the CMA-ES with CSA is reconsidered and evaluated on test problems. The results show the CMA-ES with CSA can solve well structured multimodal functions on dimension up to 80 with high probability with population size of ten if the mean vector learning rate is set small enough.

References

[1]

Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2017. Quality Gain Analysis of the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions. In Foundations of Genetic Algorithms, FOGA XIV. ACM, 111--126.

Digital Library

[2]

Youhei Akimoto, Yuichi Nagata, Isao Ono, and Shigenobu Kobayashi. 2010. Bidirectional Relation between CMA Evolution Strategies and Natural Evolution Strategies. In Parallel Problem Solving from Nature - PPSN XI (LNCS). Springer-Verlag, 154--163.

Digital Library

[3]

Dirk V. Arnold. 2005. Optimal weighted recombination. In Foundations of Genetic Algorithms. Springer, 215--237.

Digital Library

[4]

Dirk V. Arnold. 2006. Weighted multirecombination evolution strategies. Theoretical Computer Science 361 (2006), 18--37.

Digital Library

[5]

H.-G. Beyer. 1998. Mutate Large, But Inherit Small! On the Analysis of Rescaled Mutations in (1, λ)-ES with Noisy Fitness Data. In Parallel Problem Solving from Nature, 5, Springer, Heidelberg, 109--118.

Digital Library

[6]

Hans-Georg Beyer and Michael Hellwig. 2016. The Dynamics of Cumulative Step Size Adaptation on the Ellipsoid Model. Evolutionary Computation 24, 1 (2016), 25--57.

Digital Library

[7]

Benjamin Doerr, Nikolaus Hansen, Jonathan L. Shapiro, and L. Darrell Whitley. 2013. Theory of Evolutionary Algorithms (Dagstuhl Seminar 13271). Dagstuhl Reports 3, 7 (2013), 1--28.

[8]

Tobias Glasmachers, Tom Schaul, Sun Yi, Daan Wierstra, and Jürgen Schmidhuber. 2010. Exponential Natural Evolution Strategies. In Proceedings of Genetic and Evolutionary Computation Conference. ACM, 393--400.

Digital Library

[9]

Nikolaus Hansen and Anne Auger. 2014. Principled Design of Continuous Stochastic Search: From Theory to Practice. In Theory and Principled Methods for the Design of Metaheuristics, Y Borenstein and A Moraglio (Eds.). Springer.

[10]

Nikolaus Hansen, Anne Auger, Raymond Ros, Steffen Finck, and Petr Povsik. 2010. Comparing Results of 31 Algorithms from the Black-Box Optimization Benchmarking BBOB-2009. In Proceedings of Genetic and Evolutionary Computation Conference. 1689--1696.

Digital Library

[11]

Nikolaus Hansen and Stefan Kern. 2004. Evaluating the CMA Evolution Strategy on Multimodal Test Functions. In Parallel Problem Solving from Nature - PPSN VIII. Springer, 282--291.

[12]

Nikolaus Hansen, Sibylle D. Muller, and Petros Koumoutsakos. 2003. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation 11, 1 (2003), 1--18.

Digital Library

[13]

Nikolaus Hansen and Andreas Ostermeier. 2001. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9, 2 (2001), 159--195.

Digital Library

[14]

Kouhei Nishida and Youhei Akimoto. 2016. Population Size Adaptation for the CMA-ES Based On the Estimation Accuracy of the Natural Gradient. In Genetic and Evolutionary Computation Conference, GECCO. ACM, 237--244.

Digital Library

[15]

Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. 2011. Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles. (06 2011). arXiv:1106.3708

Digital Library

[16]

I. Rechenberg. 1994. Evolutionsstrategie '94. Frommann-Holzboog, Stuttgart-Bad Cannstatt.

[17]

Raymond Ros and Nikolaus Hansen. 2008. A simple modification in CMA-ES achieving linear time and space complexity. In Parallel Problem Solving from Nature - PPSN X. Springer, 296--305.

Cited By

Nomura MAkimoto YOno I(2024)CMA-ES with Learning Rate AdaptationACM Transactions on Evolutionary Learning and Optimization10.1145/3698203Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1145/3698203
Nomura MAkimoto YOno ISilva SPaquete L(2023)CMA-ES with Learning Rate Adaptation: Can CMA-ES with Default Population Size Solve Multimodal and Noisy Problems?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590358(839-847)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590358

Index Terms

Effect of the mean vector learning rate in CMA-ES
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Bio-inspired optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Bio-inspired optimization

Recommendations

PSA-CMA-ES: CMA-ES with population size adaptation
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

The population size, i.e., the number of candidate solutions generated at each iteration, is the most critical strategy parameter in the covariance matrix adaptation evolution strategy, CMA-ES, which is one of the state-of-the-art search algorithms for ...
Benchmarking a BI-population CMA-ES on the BBOB-2009 function testbed
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

We propose a multistart CMA-ES with equal budgets for two interlaced restart strategies, one with an increasing population size and one with varying small population sizes. This BI-population CMA-ES is benchmarked on the BBOB-2009 noiseless function ...
Benchmarking a BI-population CMA-ES on the BBOB-2009 noisy testbed
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

We benchmark the BI-population CMA-ES on the BBOB-2009 noisy functions testbed. BI-population refers to a multistart strategy with equal budgets for two interlaced restart strategies, one with an increasing population size and one with varying small ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

JSPS KAKENHI

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
132
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nomura MAkimoto YOno I(2024)CMA-ES with Learning Rate AdaptationACM Transactions on Evolutionary Learning and Optimization10.1145/3698203Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1145/3698203
Nomura MAkimoto YOno ISilva SPaquete L(2023)CMA-ES with Learning Rate Adaptation: Can CMA-ES with Default Population Size Solve Multimodal and Noisy Problems?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590358(839-847)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590358

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten