A Simple Yet Efficient Evolution Strategy for Large-Scale Black-Box Optimization

We propose an evolution strategy algorithm using a sparse plus low rank model for large scale optimization in this paper. We first develop a rank one evolution strategy (R1-ES) using a single principal search direction. It is of linear complexity. Then we extend it to multiple search directions, and develop a rank-m evolution strategy (Rm-ES). We illustrate that the principal search direction accumulates the natural gradients with respect to the distribution mean, and acts as a momentum term. Further, we analyze the optimal low rank approximation to the covariance matrix, and experimentally show that the principal search direction can effectively learn the long valley of the function with predominant search direction. Then we investigate the effects of Hessian on the algorithm performance. We conduct experiments on a class of test problems and the CEC’2010 LSGO benchmarks. The experimental results validate the effectiveness of our proposed algorithms.