CMA-ES for Discrete and Mixed-Variable Optimization on Sets of Points

Kento Uchida, Ryoki Hamano, Masahiro Nomura, Shota Saito, Shinichi Shirakawa

Introduction

Optimization in continuous spaces is a mature field, but many real-world engineering challenges require selecting variables from arbitrary, non-grid sets of points. Standard evolutionary strategies, such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), often struggle in these domains due to premature convergence. This paper introduces CMA-ES-SoP (Sets of Points), an extension designed to handle arbitrary discrete and mixed-variable landscapes through a novel adaptive margin correction technique.

The Challenge of Arbitrary Discrete Sets

Traditional mixed-integer optimization often assumes variables lie on a regular grid. However, practical problems frequently involve disjoint sets of coordinates, such as specific permitted locations for infrastructure or catalog-based component selection. In these scenarios, continuous optimizers often suffer from "distribution collapse": the search distribution shrinks so rapidly around a local optimum that the probability of sampling neighboring points becomes negligible, effectively trapping the algorithm in a sub-optimal state.

A search distribution before margin correction, illustrating how the probability of sampling a neighbor (pink dot) can become dangerously low as the distribution (purple dashed line) shrinks.

Methodology: CMA-ES-SoP

The proposed CMA-ES-SoP algorithm introduces three key mechanisms to maintain search mobility and prevent premature convergence:

  1. Voronoi-Based Sample Encoding: Continuous samples generated by the algorithm are projected to the nearest available point in the discrete set using a Voronoi diagram approach. This allows the optimizer to operate in a latent continuous space while evaluating valid discrete solutions.
  2. Margin Correction: To prevent the search distribution from becoming too narrow relative to the distance between discrete points, the algorithm identifies neighboring points in the set. It then modifies the covariance matrix to ensure a minimum probability (a "margin") of sampling these neighbors.
  3. Adaptive Margin Control: This is the primary innovation of the paper. Unlike previous static margin methods, CMA-ES-SoP adaptively updates the margin value during execution. This ensures the search remains aggressive when progress is being made but becomes more cautious—maintaining a wider reach—when it risks stagnation.
Evolution of the search distribution over discrete Voronoi cells at t=0, 2, and 5, showing how the algorithm navigates the discrete landscape.

Experimental Evaluation

The researchers benchmarked CMA-ES-SoP against standard CMA-ES using modified versions of classic optimization functions, including the Sphere, Ellipsoid, and Rosenbrock landscapes. In high-dimensional discrete tests (up to 30 dimensions), the standard CMA-ES frequently failed with a 0% success rate due to stagnation. In contrast, CMA-ES-SoP maintained a success rate between 96% and 100% across nearly all benchmarks.

The results demonstrate that while standard methods may be faster on low-dimensional, simple landscapes, CMA-ES-SoP provides the necessary robustness for complex, high-dimensional mixed-variable optimization where available points are scattered arbitrarily.

Conclusion and Future Directions

CMA-ES-SoP effectively bridges the gap between continuous and discrete optimization for arbitrary point sets. By preventing distribution collapse through adaptive margins, it enables reliable optimization in previously difficult engineering domains. Future work will focus on refining step-size adaptation specifically for discrete geometries and testing the algorithm on real-world datasets where point distributions may exhibit non-uniform structural patterns.

Summary updated

BibTeX
@inproceedings{uchida2024cma,
  author = {Kento Uchida and Ryoki Hamano and Masahiro Nomura and Shota Saito and Shinichi Shirakawa},
  title = {{CMA-ES for Discrete and Mixed-Variable Optimization on Sets of Points}},
  booktitle = {PPSN},
  year = {2024},
  doi = {10.1007/978-3-031-70068-2\_15},
}
Figure