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.