More Web Proxy on the site http://driver.im/

research-article

(1+1)-CMA-ES with Margin for Discrete and Mixed-Integer Problems

Authors:

Yohei Watanabe,

Masahiro Nomura,

Shinichi ShirakawaAuthors Info & Claims

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

Pages 882 - 890

https://doi.org/10.1145/3583131.3590516

Published: 12 July 2023 Publication History

Abstract

The covariance matrix adaptation evolution strategy (CMA-ES) is an efficient continuous black-box optimization method. The CMA-ES possesses many attractive features, including invariance properties and a well-tuned default hyperparameter setting. Moreover, several components to specialize the CMA-ES have been proposed, such as noise handling and constraint handling. To utilize these advantages in mixed-integer optimization problems, the CMA-ES with margin has been proposed. The CMA-ES with margin prevents the premature convergence of discrete variables by the margin correction, in which the distribution parameters are modified to leave the generation probability for changing the discrete variable. The margin correction has been applied to (μ/μ_w,Λ)-CMA-ES, while this paper introduces the margin correction into (1+1)-CMA-ES, an elitist version of CMA-ES. The (1+1)-CMA-ES is often advantageous for unimodal functions and can be computationally less expensive. To tackle the performance deterioration on mixed-integer optimization, we use the discretized elitist solution as the mean of the sampling distribution and modify the margin correction not to move the elitist solution. The numerical simulation using benchmark functions on mixed-integer, integer, and binary domains shows that (1+1)-CMA-ES with margin outperforms the CMA-ES with margin and is better than or comparable with several specialized methods to a particular search domain.

References

[1]

Dirk V. Arnold and Nikolaus Hansen. 2012. A (1+1)-CMA-ES for Constrained Optimisation. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, New York, NY, USA, 297--304.

Digital Library

[2]

Shummet Baluja. 1994. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. Technical Report. Carnegie Mellon University Pittsburgh.

[3]

Komla A. Folly and Ganesh K. Venayagamoorthy. 2009. Effects of learning rate on the performance of the population based incremental learning algorithm. In 2009 International Joint Conference on Neural Networks. 861--868.

[4]

Garuda Fujii, Masayuki Takahashi, and Youhei Akimoto. 2018. CMA-ES-based structural topology optimization using a level set boundary expression-Application to optical and carpet cloaks. Computer Methods in Applied Mechanics and Engineering 332 (2018), 624--643.

[5]

Ryoki Hamano, Shota Saito, Masahiro Nomura, and Shinichi Shirakawa. 2022. CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22). Association for Computing Machinery, New York, NY, USA, 639--647.

Digital Library

[6]

Nikolaus Hansen. 2016. The CMA Evolution Strategy:A Tutorial. arXiv:1604.00772 (2016). arXiv:1604.00772

[7]

Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). IEEE Transactions on Evolutionary Computation 11 (2003), 1--18.

Digital Library

[8]

Nikolaus Hansen, AndrÉ S. P. Niederberger, Lino Guzzella, and Petros Koumoutsakos. 2009. A Method for Handling Uncertainty in Evolutionary Optimization With an Application to Feedback Control of Combustion. IEEE Transactions on Evolutionary Computation 13, 1 (2009), 180--197.

Digital Library

[9]

Nikolaus Hansen and Andreas Ostermeier. 1996. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In Proceedings of IEEE International Conference on Evolutionary Computation. IEEE, 312--317.

[10]

G. R. Harik, F. G. Lobo, and D. E. Goldberg. 1999. The Compact Genetic Algorithm. IEEE Transactions on Evolutionary Computation 3 (1999), 287--297. Issue 4.

Digital Library

[11]

Elad Hazan, Adam Klivans, and Yang Yuan. 2018. Hyperparameter optimization: a spectral approach. In International Conference on Learning Representations (ICLR).

[12]

Michael Hellwig and Hans-Georg Beyer. 2020. On the steady state analysis of covariance matrix self-adaptation evolution strategies on the noisy ellipsoid model. Theoretical Computer Science 832 (2020), 98--122.

[13]

Christian Igel, Nikolaus Hansen, and Stefan Roth. 2007. Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation 15, 1 (03 2007), 1--28.

Digital Library

[14]

Christian Igel, Thorsten Suttorp, and Nikolaus Hansen. 2006. A Computational Efficient Covariance Matrix Update and a (1+1)-CMA for Evolution Strategies. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, New York, NY, USA, 453--460.

Digital Library

[15]

Jeffrey Larson, Matt Menickelly, and Stefan M. Wild. 2019. Derivative-free optimization methods. Acta Numerica 28 (2019), 287--404.

[16]

Christian Piermarini and Massimo Roma. 2021. A Simulation-Based Optimization approach for analyzing the ambulance diversion phenomenon in an Emergency Department network. arXiv:2108.04162 (2021).

[17]

Ingo. Rechenberg. 1973. Evolutionsstrategie; Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Mit einem Nachwort von Manfred Eigen. Frommann-Holzboog.

[18]

Luis Miguel Rios and Nikolaos V. Sahinidis. 2013. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization 56, 3 (2013), 1247--1293.

[19]

Naoki Sakamoto and Youhei Akimoto. 2022. Adaptive Ranking-Based Constraint Handling for Explicitly Constrained Black-Box Optimization. Evolutionary Computation 30, 4 (12 2022), 503--529.

[20]

Thorsten Suttorp, Nikolaus Hansen, and Christian Igel. 2009. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning 75, 2 (2009), 167--197.

Digital Library

[21]

Yichi Zhang, Daniel W. Apley, and Wei Chen. 2020. Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables. Scientific Reports 10, 1 (2020), 4924.

Cited By

Li XKötzing TLi XHandl J(2024)Algorithm Performance Comparison for Integer-Valued OneMaxProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654287(407-410)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654287
Marty THansen NAuger ASemet YHéron S(2024)LB+IC-CMA-ES: Two Simple Modifications of CMA-ES to Handle Mixed-Integer ProblemsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_18(284-299)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70068-2_18

Index Terms

(1+1)-CMA-ES with Margin for Discrete and Mixed-Integer Problems
1. Mathematics of computing
  1. Discrete mathematics
  2. Probability and statistics
    1. Probabilistic algorithms

Recommendations

Marginal Probability-Based Integer Handling for CMA-ES Tackling Single- and Multi-Objective Mixed-Integer Black-Box Optimization
This study targets the mixed-integer black-box optimization (MI-BBO) problem where continuous and integer variables should be optimized simultaneously. The covariance matrix adaptation evolution strategy (CMA-ES), our focus in this study, is a population-...
CMA-ES with margin: lower-bounding marginal probability for mixed-integer black-box optimization
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

This study targets the mixed-integer black-box optimization (MI-BBO) problem where continuous and integer variables should be optimized simultaneously. The CMA-ES, our focus in this study, is a population-based stochastic search method that samples ...
CMA-ES with Learning Rate Adaptation: Can CMA-ES with Default Population Size Solve Multimodal and Noisy Problems?
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the most successful methods for solving black-box continuous optimization problems. One practically useful aspect of the CMA-ES is that it can be used without hyperparameter tuning. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 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 the author(s) 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: 12 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NEDO
JST PRESTO
JSPS KAKENHI

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

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
60
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XKötzing TLi XHandl J(2024)Algorithm Performance Comparison for Integer-Valued OneMaxProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654287(407-410)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654287
Marty THansen NAuger ASemet YHéron S(2024)LB+IC-CMA-ES: Two Simple Modifications of CMA-ES to Handle Mixed-Integer ProblemsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_18(284-299)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70068-2_18

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.

Media

Figures

Other

Tables

View Table of Contents