Sample Reuse in the Covariance Matrix Adaptation Evolution Strategy Based on Importance Sampling
Shinichi Shirakawa, Youhei Akimoto, Kazuki Ouchi, Kouzou Ohara · 2015
Recent studies reveal that the covariance matrix adaptation evolution strategy (CMA-ES) updates the parameters based on the natural gradient. The rank-based weight is considered the result of the quantile-based transformation of the objective value and the parameters are adjusted in the direction of the natural gradient estimated by Monte-Carlo with the samples drawn from the current distribution. In this paper, we propose a sample reuse mechanism for the CMA-ES. On the basis of the importance sampling, the past samples are reused to reduce the estimation variance of the quantile and the natural gradient. We derive the formula for the rank-¥mu update of the covariance matrix and the mean vector update using the past samples, then incorporate it into the CMA-ES without the step-size adaptation. From the numerical experiments, we observe that the proposed approach helps to reduce the number of function evaluations on many benchmark functions, especially when the number of samples at each iteration is relatively small.