Reducing the Time Complexity of the Derandomized Evolution Strategy
with Covariance Matrix Adaptation (CMA-ES)
Nikolaus Hansen, Sibylle D. Mueller, and Petros Koumoutsakos
http://www.bionik.tu-berlin.de/user/niko
http://www.icos.ethz.ch/cse/research/publications/articles
This paper presents a novel evolutionary optimization strategy based
on the derandomized evolution strategy with covariance matrix
adaptation (CMA-ES). This new approach is intended to reduce the
number of generations required for convergence to the optimum.
Reducing the number of generations, i.e., the time complexity of the
algorithm, is important if a large population size is desired: (1)
to reduce the effect of noise; (2) to improve global search
properties; and (3) to implement the algorithm on (highly) parallel
machines. Our method results in a highly parallel algorithm which
scales favorably with large numbers of processors. This is
accomplished by efficiently incorporating the available information
from a large population, thus significantly reducing the number of
generations needed to adapt the covariance matrix. The original
version of the CMA-ES was designed to reliably adapt the covariance
matrix in small populations but it cannot exploit large populations
efficiently. Our modifications scale up the efficiency to
population sizes of up to 10n, where n is the problem
dimension. This method has been applied to a large number of test
problems, demonstrating that in many cases the CMA-ES can be
advanced from quadratic to linear time complexity.
In Evolutionary Computation, 11(1), (2003).
http://mitpress.mit.edu/EVCO
http://mitpress.mit.edu/journals/pdf/evco_11_1_1_0.pdf
ERRATA:
Section 5 Test Functions: The text "Except for f_diffpower and
f_rosen, the functions as shown in Table 1 are completely
separable." must read "Except for f_rosen, the functions as shown
in Table 1 are completely separable."
Table 1, f_twoax: The index of the second sum, i = |n/2|...n,
should be i = floor(n/2)+1...n. Using i = floor(n/2)...n instead
has insignificant effect on the experimental results shown in
the paper.