CMA-ES with Margin for Single-and Multi-Objective Mixed-Integer Black-Box Optimization

Ryoki Hamano, Shota Saito, Masahiro Nomura, Shinichi Shirakawa

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, a population-based stochastic search method, shows excellent performance in continuous BBO. However, when applied to MI-BBO with straightforward discretization, the variance corresponding to integer variables often becomes much smaller than the discretization granularity before reaching the optimal solution, leading to stagnation. This is particularly prevalent with binary variables. We propose a simple extension of the CMA-ES based on lower-bounding the marginal probabilities associated with the generation of integer variables. Numerical experiments demonstrate the efficiency and robustness of the proposed method in both single- and multi-objective cases.

Introduction: The Stagnation Problem in MI-BBO

The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a premier method for continuous black-box optimization. However, real-world applications often involve Mixed-Integer Black-Box Optimization (MI-BBO), requiring simultaneous handling of continuous and discrete variables.

When standard CMA-ES is applied to these problems via simple rounding, it frequently suffers from stagnation. As the algorithm converges, its step-size ($\sigma$) and variance shrink. If they become significantly smaller than the integer granularity (e.g., the distance between 0 and 1), the algorithm stops exploring different discrete values. It becomes trapped on a "plateau" where small changes in continuous parameters do not affect the discretized output. This "bit fixation" is especially problematic for binary variables.

Visualizing the stagnation problem: Standard CMA-ES-IM (top) exhibits mean drift and premature convergence compared to a constrained approach (bottom).

As shown in the figure above, the failure in binary optimization is often driven by the mean vector ($m$) drifting far from the discretization threshold while the variance is small, making mutations to alternative states statistically impossible.

Proposed Method: CMA-ES with Margin

To overcome these limitations, we introduce CMA-ES with Margin. Inspired by Estimation of Distribution Algorithms (EDAs), the "margin" ensures that the probability of sampling any alternative integer value never drops below a threshold $\alpha$. This prevents the distribution from collapsing onto a single point.

Technical Innovations

  1. Marginal Probability Lower-Bounding: If the probability of sampling a different integer value falls below $\alpha$, the algorithm shifts the mean closer to the discretization threshold and increases coordinate-wise variance to satisfy the margin.
  2. Affine Transformation Correction: Instead of modifying rounding logic, the authors adjust the sampling distribution itself by modifying the mean vector and a diagonal transformation matrix before generating candidates.
  3. Automated Hyperparameters: The paper suggests a robust default margin: $\alpha = (N\lambda)^{-1}$, where $N$ is the dimension and $\lambda$ is the population size.
Standard parameter configurations for the CMA-ES framework.

The method preserves the core CMA-ES logic (parameters shown in the table above), ensuring that covariance matrix updates and step-size adaptation remain functional while preventing distribution collapse.

Multi-Objective Extension

The margin logic was successfully integrated into MO-CMA-ES. The authors proved that this correction preserves the "elitist" properties of multi-objective search, ensuring it does not disrupt the ranking of successful individuals.

Experimental Results

The proposed method was evaluated on synthetic MI-BBO benchmarks, including combinations of Sphere/Ellipsoid functions with OneMax/LeadingOnes.

  • Robustness: In single-objective tests, CMA-ES with Margin maintained a 100% success rate up to 60D, whereas the baseline CMA-ES-IM success rate dropped to 8% on binary problems.
  • Efficiency: On integer problems like SphereInt, the proposed method reached the optimum with significantly fewer evaluations.
  • Multi-Objective Performance: On the DSLOTZ benchmark, the margin-corrected version achieved significantly higher Hypervolume than vanilla MO-CMA-ES and NSGA-II, both of which suffered from bit fixation.

Conclusion and Future Work

CMA-ES with Margin provides a simple, principled solution to stagnation in mixed-integer optimization. While highly effective, the current coordinate-wise margin correction may struggle with highly non-separable, ill-conditioned functions. Future research will explore moving beyond coordinate-wise margins to consider joint distributions and validating the method on complex real-world engineering black boxes.

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{hamano2024cma,
  author = {Ryoki Hamano and Shota Saito and Masahiro Nomura and Shinichi Shirakawa},
  title = {{CMA-ES with Margin for Single-and Multi-Objective Mixed-Integer Black-Box Optimization}},
  journal = {ACM Trans. Evol. Learn. Optim.},
  year = {2024},
  doi = {10.1145/3632962},
}
Figure