dd-RCMA-ES: CMA-ES with Projection-Based Restricted Covariance Matrix Adaptation for High-Dimensional Problems

This paper addresses the computational challenges of the covariance matrix adaptation evolution strategy (CMA-ES) in high-dimensional optimization of an objective function \(f:\mathbb{R}^{n}\to\mathbb{R}\) where \(n\gg 100\) , particularly for problems exhibiting sparse-sensitivity structures where only a small number of directions are highly sensitive. To overcome the bottleneck associated with the covariance matrix, we propose a novel restricted covariance matrix model, reducing storage requirements from quadratic to linear in \(n\) . An efficient adaptation mechanism for this model is introduced, with linear time complexity per iteration, providing a substantial improvement over the standard CMA-ES. We also present two-point step-size adaptation (TPA) as an alternative to the cumulative step-size adaptation (CSA), particularly suitable for high-dimensional optimization. In contrast to CSA, TPA is not negatively affected by ineffective subspaces, prevalent in higher dimensions where non-relevant design variables may be introduced. The proposed algorithm, dd-RCMA-ES, determines its hyper-parameters based on the problem dimension \(n\) and the model complexity \(k\) , thereby maintaining the out-of-the-box usability of the standard CMA-ES, while offering the flexibility to upper bound the model complexity if desired. Experimental evaluations across 18 test problems in dimensions varying from 80 to 10240 demonstrate the efficiency of dd-RCMA-ES in terms of the number of function calls required to achieve a given target precision. In comparison with other CMA-ES variants, the dd-RCMA-ES excels on problems with sparse structures that comprise a small number of both, highly sensitive and insensitive directions.