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.
Methodology: CMA-ES-SoP
The proposed CMA-ES-SoP algorithm introduces three key mechanisms to maintain search mobility and prevent premature convergence:
- 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.
- 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.
- 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.
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