Marginal Probability-Based Integer Handling for CMA-ES Tackling Single- and Multi-Objective Mixed-Integer Black-Box Optimization

Ryoki Hamano, Shota Saito, Masahiro Nomura, Shinichi Shirakawa

TL;DR

This paper introduces a novel "margin" mechanism to improve the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for mixed-integer black-box optimization (MI-BBO). By ensuring that the probability of integer variables taking on specific values stays within a defined range, the method prevents premature convergence and stagnation, leading to more robust and efficient optimization for both single and multi-objective problems.

What Problem Does This Paper Address?

Many real-world optimization problems involve a mix of continuous and integer variables, known as mixed-integer black-box optimization (MI-BBO). These problems are challenging because objective functions are often not explicitly given, and standard optimization algorithms designed for continuous variables struggle with the discrete nature of integer variables. A common approach is to adapt continuous optimization methods, like the powerful CMA-ES, by discretizing integer variables. However, a significant issue arises when the variance of the CMA-ES's distribution for integer variables becomes smaller than the "granularity" of the discretization. This leads to the optimization getting stuck on a plateau, especially for binary variables, where small changes in the continuous representation don't alter the discrete outcome. Existing methods, like injecting mutations, have limitations and don't effectively handle binary variables. This paper aims to solve this stagnation problem by proposing a principled way to handle integer variables within CMA-ES.

Methods

The core contribution is the "CMA-ES with Margin" method. It builds upon the standard CMA-ES by introducing a "margin" that acts as a lower bound on the marginal probability of integer variables taking on specific values. This is achieved by modifying the mean vector and an affine transformation matrix related to the covariance matrix.

Here's a breakdown:

  • Standard CMA-ES: Samples candidate solutions from a multivariate Gaussian distribution (MGD), updates its mean and covariance based on evaluation results.
  • The Problem: For integer variables, the MGD's variance can shrink too much, causing the distribution to concentrate on a single integer value, leading to stagnation.
  • Proposed Solution (CMA-ES with Margin):
    • Margin Definition: A hyperparameter a defines the minimum acceptable probability for an integer variable to fall within certain ranges.
  • Correction Mechanism: The algorithm adjusts the mean vector and an affine transformation matrix (A) to ensure that the marginal probabilities of integer variables stay above a. This is done by calculating confidence intervals and correcting the mean to keep it away from discretization thresholds.
  • Affine Transformation Invariance: A key insight is that the proposed correction can be viewed as an affine transformation of the samples. Since CMA-ES is invariant to affine transformations, the core optimization properties are preserved.
  • Extension to Multi-Objective: The margin concept is further extended to the multi-objective CMA-ES (MO-CMA-ES), adapting the margin correction to handle multiple objectives and elitist selection strategies.

Datasets

The paper uses several benchmark functions for evaluation:

  • Single-Objective:
    • SPHEREONEMAX, SPHERELEADINGONES, ELLIPSOIDONEMAX, ELLIPSOIDLEADINGONES (continuous and binary variables)
    • SPHEREINT, ELLIPSOIDINT (continuous and integer variables)
  • Multi-Objective:
    • DSLOTZ (DOUBLESPHERELEADINGONESTAILINGZEROS)
    • DSINT (DOUBLESPHEREINT)

No new datasets were introduced; existing benchmark functions were utilized.

Key Insights and Ideas

  • Stagnation is due to probability concentration: The paper clearly demonstrates that the failure of standard CMA-ES variants in MI-BBO, particularly with binary variables, stems from the MGD's probability distribution collapsing onto a single discrete value.
  • Margin as a "safety net": The "margin" concept provides a principled way to prevent this collapse by enforcing a minimum probability for variables to explore different discrete outcomes. This is analogous to how Population-Based Incremental Learning (PBIL) uses bounds for binary domains.
  • Affine transformation invariance is crucial: The elegance of the proposed method lies in its ability to modify the sampling distribution without breaking CMA-ES's fundamental properties, thanks to its invariance to affine transformations.
  • Generality of the margin idea: The successful extension of the margin concept to multi-objective optimization highlights its broad applicability beyond single-objective problems.

Key Results

  • Improved Robustness and Efficiency: The proposed CMA-ES with Margin consistently achieved higher success rates and often required fewer evaluations compared to existing methods (CMA-ES-IM and CMA-ES-IM with box constraints) across various MI-BBO benchmark functions, especially as the dimensionality increased.
  • 100% Success Rate: For many functions, the proposed method maintained a 100% success rate even in high-dimensional settings where other methods struggled.
  • Effective for Binary Variables: The method showed significant improvement in handling binary variables, a known weakness of previous approaches.
  • Competitive Multi-Objective Performance: In multi-objective scenarios, MO-CMA-ES with Margin performed competitively or better than the vanilla MO-CMA-ES and NSGA-II, particularly in high-dimensional and small sample size settings.
  • Hyperparameter Sensitivity: The study identified that the hyperparameter a is sensitive, with extreme values leading to instability or stagnation. A recommended default value of a = (Nλ)⁻¹ was proposed, simplifying parameter tuning.

Limitations and Future Work

  • Hyperparameter a: While a default value is suggested, the paper acknowledges that the optimal a can depend on problem characteristics, and a deeper understanding of its effects is needed.
  • Non-separable and Ill-conditioned Functions: The paper notes that challenges remain for highly complex functions, such as non-separable and ill-conditioned convex-quadratic functions (e.g., rotated Ellipsoid).
  • Multiple Dimension Correlations: Future work should address how to incorporate correlations between multiple dimensions more effectively.
  • Alternative Distribution Approaches: Exploring the joint distribution of MGDs with discrete distributions (like Bernoulli) is suggested as a future avenue.
  • Real-World Applications: Evaluating the proposed method on real-world MI-BBO problems, including multi-objective ones, is a key future direction.

Summary updated

Abstract

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 solution candidates from a multivariate Gaussian distribution (MGD), which shows excellent performance in continuous BBO. The parameters of MGD, mean and (co)variance, are updated based on the evaluation value of candidate solutions in the CMA-ES. If the CMA-ES is applied to the MI-BBO with straightforward discretization, however, the variance corresponding to the integer variables becomes much smaller than the granularity of the discretization before reaching the optimal solution, which leads to the stagnation of the optimization. In particular, when binary variables are included in the problem, this stagnation more likely occurs because the granularity of the discretization becomes wider, and the existing modification to the CMA-ES does not address this stagnation. To overcome these limitations, we propose a simple extension of the CMA-ES based on lower-bounding the marginal probabilities associated with the generation of integer variables in the MGD. The numerical experiments on the MI-BBO benchmark problems demonstrate the efficiency and robustness of the proposed method. Furthermore, in order to demonstrate the generality of the idea of the proposed method, in addition to the single-objective optimization case, we incorporate it into multi-objective CMA-ES and verify its performance on bi-objective mixed-integer benchmark problems.
BibTeX
@article{hamano2024marginal,
  author = {Ryoki Hamano and Shota Saito and Masahiro Nomura and Shinichi Shirakawa},
  title = {{Marginal Probability-Based Integer Handling for CMA-ES Tackling Single- and Multi-Objective Mixed-Integer Black-Box Optimization}},
  journal = {ACM Trans. Evol. Learn. Optim.},
  year = {2024},
  doi = {10.1145/3632962},
}
Figure