A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies

ABSTRACT

First, the covariance matrix adaptation (CMA) with rank-one update is introduced into the (1+1)-evolution strategy. An improved implementation of the 1/5-th success rule is proposed for step size adaptation, which replaces cumulative path length control. Second, an incremental Cholesky update for the covariance matrix is developed replacing the computational demanding and numerically involved decomposition of the covariance matrix. The Cholesky update can replace the decomposition only for the update without evolution path and reduces the computational effort from O(n³) to O(n²). The resulting (1+1)-Cholesky-CMA-ES is an elegant algorithm and the perhaps simplest evolution strategy with covariance matrix and step size adaptation. Simulations compare the introduced algorithms to previously published CMA versions.

REFERENCES

• 1: David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
• 2: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 3: Hans-Georg Beyer , Hans-Paul Schwefel, Evolution strategies –A comprehensive introduction, Natural Computing: an international journal, v.1 n.1, p.3-52, May 2002 [doi>10.1023/A:1015059928466]
• 4: Mohinder S. Grewal , Angus P. Andrews, Kalman filtering: theory and practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 5: N. Hansen. An analysis of mutative σ-self-adaptation on linear fitness functions. Evolutionary Computation, 14(3), 2006.
• 6: N. Hansen and S. Kern. Evaluating the CMA evolution strategy on multimodal test functions. In X. Yao, E. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervós, J. A. Bullinaria, J. Rowe, P. Tivño, A. Kabán, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature (PPSN VIII), volume 3242 of LNCS, pages 282--291. Springer-Verlag, 2004.
• 7: Nikolaus Hansen , Sibylle D. Müller , Petros Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, v.11 n.1, p.1-18, Spring 2003 [doi>10.1162/106365603321828970]
• 8: N. Hansen and A. Ostermeier. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Proceedings of the 1996 IEEE Conference on Evolutionary Computation (ICEC '96), pages 312--317, 1996.
• 9: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 10: Stefan Kern , Sibylle D. Müller , Nikolaus Hansen , Dirk Büche , Jiri Ocenasek , Petros Koumoutsakos, Learning probability distributions in continuous evolutionary algorithms– a comparative review, Natural Computing: an international journal, v.3 n.1, p.77-112, 2004 [doi>10.1023/B:NACO.0000023416.59689.4e]
• 11: H. Mühlenbein, D. Schomisch, and J. Born. The Parallel Genetic Algorithm as Function Optimizer. Parallel Computing, 17(6-7):619--632, 1991.
• 12: I. Rechenberg. Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. Frommann-Holzboog, 1973.
• 13: G. Rudolph. On correlated mutations in evolution strategies. In R. Männer and B. Manderick, editors, Parallel Problem Solving from Nature 2 (PPSN II), pages 105--114. Elsevier, 1992.
• 14: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 15: Aimo Torn , Antanas Zilinskas, Global optimization, Springer-Verlag New York, Inc., New York, NY, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
Cholesky factors, covariance matrix adaptation, evolution strategy, rank-one update