pith. sign in

arxiv: 2606.15830 · v2 · pith:RMF4X4TXnew · submitted 2026-06-14 · 💻 cs.NE · math.OC

MSC-CMA-ES: Structure-Aware Restarts for CMA-ES via Cyclic Nearest-Better Basin Discovery

Dimitar Nedanovski , Svetoslav Nenov , Dimitar Pilev This is my paper

Pith reviewed 2026-06-30 11:11 UTC · model grok-4.3

classification 💻 cs.NE math.OC
keywords CMA-ESrestart strategiesnearest-better clusteringbasin of attractionmultimodal optimizationCEC benchmarksevolutionary algorithms
0
0 comments X

The pith

MSC-CMA-ES makes CMA-ES restarts structure-aware by seeding one per basin discovered via nearest-better clustering on Sobol pre-samples.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces MSC-CMA-ES to replace uniform random restarts in standard CMA-ES with structure-aware ones that reuse information from prior evaluations. It alternates cycles of drawing a Sobol pre-sample, partitioning it into approximate basins of attraction through nearest-better clustering, and launching one restart per basin with locally scaled step and population sizes while skipping redundant basins. Remaining budget goes to unbounded local refinement of the best-so-far point. On CEC composition functions across four suites and dimensions 5-30, this produces the best scores on all aggregate measures and 2.7 times the target coverage of BIPOP-CMA-ES. The method shows a trade-off on basic functions where median error improves but deep-target coverage drops due to budget spent on discovery.

Core claim

MSC-CMA-ES discovers approximate basins of attraction from a Sobol pre-sample using nearest-better clustering in alternating cycles, then seeds one restart per basin with locally scaled step and population sizes, excludes redundant basin visits, and spends remaining budget on unbounded local refinement of the best-so-far solution, resulting in higher target coverage on composition functions than uniform restart strategies like BIPOP-CMA-ES.

What carries the argument

Nearest-better clustering applied to a Sobol pre-sample to partition the search space into approximate basins of attraction that guide non-redundant, basin-specific restarts.

If this is right

  • On composition functions, MSC-CMA-ES attains the best value on all four aggregate measures.
  • It achieves 2.7x the fixed-budget target coverage of BIPOP-CMA-ES, the highest among all algorithms evaluated.
  • On basic functions, it achieves the best median error but exhibits lower deep-target coverage because budget is spent on landscape discovery.
  • On hybrid functions both CMA variants trail the leading differential-evolution algorithms, so the deficit belongs to the CMA family rather than the restart mechanism.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The cyclic discovery pattern could reduce the need for hand-tuned restart frequencies in other multimodal evolutionary algorithms.
  • Public release of all results and scripts allows direct comparison of basin partitions against known ground-truth basins on standard test functions.
  • The method's budget split between discovery and refinement may need rebalancing when moving from 30D CEC problems to real-world black-box tasks with different basin densities.

Load-bearing premise

Nearest-better clustering applied to a Sobol pre-sample produces a sufficiently accurate partition into basins of attraction to guide effective restarts without excessive overhead or missed important basins.

What would settle it

On a multimodal test function whose true basins of attraction are known in advance, measure whether the partitions from nearest-better clustering on Sobol samples match those basins closely enough that basin-seeded restarts produce measurably higher success rates than uniform restarts at the same budget.

Figures

Figures reproduced from arXiv: 2606.15830 by Dimitar Nedanovski, Dimitar Pilev, Svetoslav Nenov.

Figure 1
Figure 1. Figure 1: FBTC on the hybrid classes of CEC2020 D=5 and CEC2017 D=10, summed over the functions. 3.5 Budget scaling We evaluate the algorithms across multiple budgets to analyze how the final accuracy depends on the maximal number of function evaluations. The raw fixed-budget target coverage FBTC(b) defined in Section 3.1 is not necessarily a non-decreasing function of the budget b. Unlike the runtime perspective in… view at source ↗
Figure 2
Figure 2. Figure 2: Composition functions at D = 10 across the CEC2014, CEC2017, and CEC2022 suites. On composition functions at D = 10 across the three suites, MSC-CMA-ES attains the highest FBTC on the CEC2017 set, while NLSHADE-RSP and j2020 attain higher FBTC on the CEC2014 and CEC2022 suites. Across all dimensionalities of the CEC2020 composition class (D ∈ {5, 10, 15, 20}), MSC-CMA-ES attains the highest FBTC at every D… view at source ↗
Figure 3
Figure 3. Figure 3: FBTC on the composition class (f8–f10, class maximum 3) of CEC2020 at D ∈ {5, 10, 15, 20}. while MSC-CMA-ES continues to increase its coverage monotonically over the evaluated budgets. On the D = 20 composition class it rises from approximately 1.1 at 2 × 106 evaluations to 2.6 (out of a maximum of 3) at 4 × 107 . 4 Discussion Figures 4a and 4b track the seven algorithms on a composition class through four… view at source ↗
Figure 4
Figure 4. Figure 4: Algorithm rankings on the composition classes across four aggregate measures: worst-SUM, median-SUM, [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: CEC2017 D=30 composition-class stress test under two evaluation budgets. A focused D=30 budget-scaling diagnostic clarifies the scalability boundary of the basin-discovery mechanism. Fig￾ure 5 compares the CEC2017 D=30 composition class at the official CEC budget, 3 × 105 evaluations, and at an extended budget of 106 evaluations. This comparison is not part of the official-budget ranking; it is a diagnosti… view at source ↗
read the original abstract

CMA-ES is, per run, 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 an unbounded local refinement of the best-so-far solution. We evaluate the method on four CEC suites (CEC2014, CEC2017, CEC2020, CEC2022) at their official budgets, across ten (suite, dimension) cells with dimensions 5-30, 51 runs per function, against BIPOP-CMA-ES and five differential-evolution algorithms (ARRDE, jSO, j2020, NL-SHADE-RSP, LSRTDE). Read per function class, MSC-CMA-ES leads on one class, is mixed on a second, and trails on the third. On composition functions, MSC-CMA-ES attains the best value on all four aggregate measures, with 2.7x the fixed-budget target coverage of BIPOP-CMA-ES - the highest composition coverage of any algorithm evaluated. On basic functions, it achieves the best (lowest) median error but exhibits a lower deep-target coverage - the measured price of spending budget on landscape discovery. On hybrid functions both CMA variants trail the leading DE algorithms; the deficit belongs to the CMA family, not to the restart mechanism. All results and scripts are publicly available.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces MSC-CMA-ES, a restart strategy for CMA-ES that alternates Sobol pre-sampling with nearest-better clustering to partition the search space into approximate basins of attraction, seeds restarts basin-by-basin using locally scaled step-size and population-size parameters, detects and skips redundant basin visits, and allocates remaining budget to unbounded local refinement of the best-so-far solution. It reports results on CEC2014/2017/2020/2022 suites (dimensions 5–30, official budgets, 51 runs per function) against BIPOP-CMA-ES and five DE variants, claiming that on composition functions MSC-CMA-ES leads on all four aggregate measures with 2.7× the fixed-budget target coverage of BIPOP-CMA-ES.

Significance. If the reported performance differentials hold after verification of implementation details and statistical procedures, the work supplies a concrete, reproducible demonstration that nearest-better basin discovery can convert restart budget into higher coverage on composition landscapes without altering the underlying CMA-ES local search. Public release of all results and scripts is a clear strength that supports direct replication and extension.

major comments (1)
  1. [Method description / experimental setup] The central performance claim on composition functions rests on the assumption that nearest-better clustering of the Sobol pre-sample yields sufficiently accurate, non-redundant basin partitions; the manuscript should supply a quantitative validation (e.g., agreement with known basin counts on a subset of CEC composition functions or sensitivity analysis to the Sobol sample size) to confirm this step is load-bearing rather than incidental.
minor comments (2)
  1. [Algorithm description] Clarify whether the local scaling factors for step-size and population size are fixed a priori or adapted per basin; if the latter, state the adaptation rule explicitly.
  2. [Results] The abstract states that results are reported 'per function class'; include a supplementary table that breaks down the four aggregate measures by individual function within each class so readers can assess whether the composition-function advantage is uniform or driven by a few outliers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation of minor revision. The positive assessment of the method's significance and the emphasis on reproducibility are appreciated. We address the single major comment below.

read point-by-point responses

  1. Referee: [Method description / experimental setup] The central performance claim on composition functions rests on the assumption that nearest-better clustering of the Sobol pre-sample yields sufficiently accurate, non-redundant basin partitions; the manuscript should supply a quantitative validation (e.g., agreement with known basin counts on a subset of CEC composition functions or sensitivity analysis to the Sobol sample size) to confirm this step is load-bearing rather than incidental.

    Authors: We agree that the manuscript would benefit from explicit quantitative validation of the nearest-better basin partitioning step. In the revised version we will add a dedicated subsection containing (i) a sensitivity study of final performance and detected basin count with respect to Sobol pre-sample size and (ii) an agreement analysis against known or literature-reported basin counts on a representative subset of the CEC composition functions. All additional experiments will reuse the publicly released code base. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript describes an algorithmic restart strategy for CMA-ES that uses nearest-better clustering on a Sobol pre-sample to seed restarts, with all performance claims resting on direct empirical comparisons to independent external baselines (BIPOP-CMA-ES and multiple DE variants) across CEC suites. No equations, derivations, fitted parameters renamed as predictions, or self-citation chains appear in the provided text; the central claims are falsifiable via the publicly released code and results rather than being definitionally equivalent to the method's own inputs.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that nearest-better clustering on a modest Sobol pre-sample can discover usable basin structure; no new physical entities are postulated and no free parameters are numerically reported in the abstract.

free parameters (2)
  • Sobol pre-sample size
    Size of the initial sample used for basin discovery; choice affects clustering quality and overhead but is not quantified in the abstract.
  • local scaling factors for step-size and population size
    Per-basin adjustments mentioned in the method; exact functional form or fitting procedure not given.
axioms (1)
  • domain assumption Nearest-better clustering on a Sobol pre-sample yields an approximate partition into basins of attraction that is useful for guiding restarts.
    This premise is invoked when the abstract describes how restarts are seeded basin by basin.

pith-pipeline@v0.9.1-grok · 5857 in / 1429 out tokens · 59068 ms · 2026-06-30T11:11:49.362811+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 20 canonical work pages · 2 internal anchors

  1. [1]

    Akiba, S

    T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proc. ACM SIGKDD, pages 2623–2631, 2019. doi:10.1145/3292500.3330701

    work page doi:10.1145/3292500.3330701 2019

  2. [2]

    Auger and N

    A. Auger and N. Hansen. A restart CMA evolution strategy with increasing population size. In Proc. IEEE Congress on Evolutionary Computation (CEC), pages 1769–1776, 2005. doi:10.1109/CEC.2005.1554902

    work page doi:10.1109/cec.2005.1554902 2005

  3. [3]

    N. H. Awad, M. Z. Ali, J. J. Liang, B. Y . Qu, and P. N. Suganthan. Problem definitions and evaluation criteria for the CEC 2017 special session on single objective real-parameter numerical optimization. Technical report, Nanyang Technological University, 2017

    2017

  4. [4]

    Biedrzycki

    R. Biedrzycki. A version of IPOP-CMA-ES algorithm with midpoint for CEC 2017 single objective bound constrained problems. In Proc. IEEE CEC, pages 1489–1494, 2017. doi:10.1109/CEC.2017.7969479

    work page doi:10.1109/cec.2017.7969479 2017

  5. [5]

    Brest, M

    J. Brest, M. S. Mau ˇcec, and B. Boškoviˇc. Single objective real-parameter optimization: Algorithm jSO. In Proc. IEEE CEC, pages 1311–1318, 2017. doi:10.1109/CEC.2017.7969456

    work page doi:10.1109/cec.2017.7969456 2017

  6. [6]

    Brest, M

    J. Brest, M. S. Mau ˇcec, and B. Boškovi´c. Differential evolution algorithm for single objective bound-constrained optimization: Algorithm j2020. In Proc. IEEE CEC, pages 1–8, 2020. doi:10.1109/CEC48606.2020.9185551

    work page doi:10.1109/cec48606.2020.9185551 2020

  7. [7]

    Hansen and A

    N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2):159–195, 2001. doi:10.1162/106365601750190398

    work page doi:10.1162/106365601750190398 2001

  8. [8]

    N. Hansen. Benchmarking a BI-population CMA-ES on the BBOB-2009 function testbed. In Proc. GECCO Companion, pages 2389–2396, 2009. doi:10.1145/1570256.1570333

    work page doi:10.1145/1570256.1570333 2009

  9. [9]

    Hansen, Y

    N. Hansen, Y . Akimoto, and P. Baudis. CMA-ES/pycma on Github. Zenodo, 2019. https://github.com/ CMA-ES/pycma. doi:10.5281/zenodo.2559634. 11 MSC-CMA-ES A PREPRINT

    work page doi:10.5281/zenodo.2559634 2019

  10. [10]

    Hansen, A

    N. Hansen, A. Auger, R. Ros, O. Mersmann, T. Tušar, and D. Brockhoff. COCO: A platform for compar- ing continuous optimizers in a black-box setting. Optimization Methods and Software , 36(1):114–144, 2021. doi:10.1080/10556788.2020.1808977

    work page doi:10.1080/10556788.2020.1808977 2021

  11. [11]

    Hansen, A

    N. Hansen, A. Auger, D. Brockhoff, and T. Tušar. Anytime performance assessment in blackbox optimization benchmarking. IEEE Transactions on Evolutionary Computation , 26(6):1293–1305, 2022. doi:10.1109/TEVC.2022.3210897

    work page doi:10.1109/tevc.2022.3210897 2022

  12. [12]

    J. J. Liang, B. Y . Qu, and P. N. Suganthan. Problem definitions and evaluation criteria for the CEC 2014 special session on single objective real-parameter numerical optimization. Technical report, Zhengzhou University / Nanyang Technological University, 2013

    2014

  13. [13]

    M. A. Muñoz, M. Kirley, and K. Smith-Miles. Analyzing randomness effects on the reliability of landscape analysis. Natural Computing, 21:131–154, 2022. doi:10.1007/s11047-021-09847-1

    work page doi:10.1007/s11047-021-09847-1 2022

  14. [14]

    K. F. Muzakka, S. Möller, and M. Finsterbusch. Minion: a high-performance derivative-free optimization library. https://github.com/khoirulmuzakka/Minion, 2025

    2025

  15. [15]

    K. F. Muzakka, A. H. Shali, H. Suhendar, S. Möller, and M. Finsterbusch. Robust differential evolution via nonlinear population size reduction and adaptive restart: The ARRDE algorithm. arXiv:2511.18429, 2025. doi:10.48550/arXiv.2511.18429

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2511.18429 2025

  16. [16]

    M. Preuss. Niching the CMA-ES via nearest-better clustering. In Proceedings of the 12th annual conference companion on Genetic and evolutionary computation, pages 1711–1718, 2010. doi:10.1145/1830761.1830793

    work page doi:10.1145/1830761.1830793 2010

  17. [17]

    M. Preuss. Improved topological niching for real-valued global optimization. In European Conference on the Applications of Evolutionary Computation, pages 386–395. Springer, 2012. doi:10.1007/978-3-642-29178-4_39

    work page doi:10.1007/978-3-642-29178-4_39 2012

  18. [18]

    Renau, C

    Q. Renau, C. Doerr, J. Dreo, and B. Doerr. Exploratory landscape analysis is strongly sensitive to the sampling strategy. arXiv:2006.11135, 2020. doi:10.48550/arXiv.2006.11135

    work page doi:10.48550/arxiv.2006.11135 2006

  19. [19]

    Stanovov, S

    V . Stanovov, S. Akhmedova, and E. Semenkin. NL-SHADE-RSP algorithm with adaptive archive and selective pressure for CEC 2021 numerical optimization. In Proc. IEEE CEC , pages 809–816, 2021. doi:10.1109/CEC45853.2021.9504959

    work page doi:10.1109/cec45853.2021.9504959 2021

  20. [20]

    Critical current of a Josephson junction containing a conical magnet

    V . Stanovov and E. Semenkin. Success rate-based adaptive differential evolution L-SRTDE for CEC 2024 com- petition. In Proc. IEEE CEC, pages 1–8, 2024. doi:10.1109/CEC60901.2024.10611907

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/cec60901.2024.10611907 2024

  21. [21]

    Tanabe and A

    R. Tanabe and A. S. Fukunaga. Improving the search performance of SHADE using linear population size reduction. In Proc. IEEE CEC, pages 1658–1665, 2014. doi:10.1109/CEC.2014.6900380

    work page doi:10.1109/cec.2014.6900380 2014

  22. [22]

    R. Tanabe. Towards exploratory landscape analysis for large-scale optimization: a dimensionality reduction framework. In Proc. GECCO, pages 546–555, 2021. doi:10.1145/3449639.3459300

    work page doi:10.1145/3449639.3459300 2021

  23. [23]

    Törn and S

    A. Törn and S. Viitanen. Topographical global optimization. In Recent Advances in Global Optimization, pages 384–398. Princeton University Press, 1992

    1992

  24. [24]

    H. Wang, D. Vermetten, F. Ye, C. Doerr, and T. Bäck. IOHanalyzer: Detailed performance analyses for itera- tive optimization heuristics. ACM Transactions on Evolutionary Learning and Optimization , 2(3):1–29, 2022. doi:10.1145/3510426

    work page doi:10.1145/3510426 2022

  25. [25]

    C. T. Yue, K. V . Price, P. N. Suganthan, J. J. Liang, M. Z. Ali, B. Y . Qu, N. H. Awad, and P. P. Biswas. Prob- lem definitions and evaluation criteria for the CEC 2020 special session and competition on single objective bound constrained numerical optimization. Technical report, Zhengzhou University / Nanyang Technological University, 2019. 12

    2020