Quantitative Performance Analysis of Stopping Criteria for CMA-ES

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.

Stopping criteria automatically determine when to stop an evolutionary algorithm, so as not to waste function evaluations on a stagnant population. Although stopping criteria play an important role in real-world applications, they have attracted little attention in the evolutionary multi-objective optimization (EMO) community. In fact, new stopping criteria for EMO have been rarely developed in recent years. One reason for the stagnation in developing stopping criteria for EMO is a lack of effective benchmarking methodologies. To address this issue, this paper proposes (i) a performance measure of stopping criteria for EMO and (ii) a file-based benchmarking approach. This paper also proposes (iii) a data representation method that effectively stores population states in text files. (i) The proposed measure represents the performance of stopping criteria as a single scalar value, making comparison easy. (ii) The proposed file-based approach not only simplifies the benchmarking process but also facilitates reproducibility. (iii) The proposed data representation method addresses the issue of file size in (ii). We demonstrate the effectiveness of our three contributions (i)--(iii) by benchmarking five representative stopping criteria for EMO.

This paper proposes RCMAES, a novel variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for CEC benchmark optimization. RCMAES integrates a dimension-dependent nonlinear population-size reduction strategy with an adaptive restart mechanism within a pure CMA-ES framework. RCMAES is evaluated on three benchmark suites (CEC2017, CEC2020, and CEC2022) and compared with state-of-the-art DE algorithms as well as its closely related counterpart, BIPOP-aCMAES. Experimental results show that RCMAES achieves competitive and robust performance across all benchmarks.