MSC-CMA-ES: Structure-Aware Restarts for CMA-ES via Cyclic Nearest-Better Basin Discovery
About
CMA-ES behaves, per restart, primarily as a local optimizer; multimodal search relies on restart strategies such as IPOP and BIPOP, which draw every restart uniformly and reuse no information from previous evaluations. Multi-Start Clustering CMA-ES (MSC-CMA-ES) makes restarts structure-aware: in alternating cycles, a Sobol pre-sample is partitioned into approximate basins of attraction by nearest-better clustering, restarts are seeded basin by basin with locally scaled step-sizes and population sizes, redundant basin visits are detected and excluded, and the remaining budget is spent on a budget-bounded, tolerance-disabled local refinement of the best-so-far solution. We evaluate the method on the four CEC suites (2014, 2017, 2020, and 2022) at their official budgets, across ten (suite, dimension) cells with dimensions 5--30, with 51 runs per function, and compare it with BIPOP-CMA-ES and five differential-evolution algorithms (ARRDE, jSO, j2020, NL-SHADE-RSP, and L-SRTDE). Read per function class over the $D\leq 20$ cells, the results split three ways. On composition functions MSC-CMA-ES attains the best value on all aggregate measures, with $2.7\times$ the fixed-budget target coverage of BIPOP-CMA-ES -- the highest composition coverage of any algorithm evaluated -- and leads in most suites, dimensions, and budgets. On unimodal and simple-multimodal functions it attains the best median error in aggregate but the lowest deep-target coverage, with orderings varying by suite and dimension. On hybrid functions both CMA algorithms trail the leading DE algorithms. All results and scripts are publicly available.