Aiming for a theoretically tractable CSA variant by means of empirical investigations

ABSTRACT

Evolution Strategies (ES) for black-box optimization of a function f:Rⁿ->R are investigated. Namely, we consider the cumulative step-size adaptation (CSA) for the variance of multivariate zero-mean normal distributions, which are commonly used to sample new candidate solutions within Evolution Strategies (ES). Four simplifications of CSA are proposed and investigated empirically and evaluated statistically. The background for these four new CSA-derivatives, however, is NOT performance tuning, but our aim to accomplish a probabilistic/theoretical runtime analysis of an ES using some kind of a CSA in the near future, and a better understanding of this step-size control mechanisms. Therefore, we consider two test problems, namely the Sphere function without and with Gaussian noise.

REFERENCES

• 1: The theory of evolution strategies, Springer-Verlag New York, Inc., New York, NY, 2001
• 2: Dirk V. Arnold , Hans-Georg Beyer, A Comparison of Evolution Strategies with Other Direct Search Methods in the Presence of Noise, Computational Optimization and Applications, v.24 n.1, p.135-159, January 2003 [doi>10.1023/A:1021810301763]
• 3: Hans-Georg Beyer , Dirk V. Arnold, Qualms regarding the optimality of cumulative path length control in CSA/CMA-evolution strategies, Evolutionary Computation, v.11 n.1, p.19-28, Spring 2003 [doi>10.1162/106365603321828989]
• 4: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]
• 5: Hansen, N. (2008): List of references to various applications of CMA-ES. http://www.bionik.tu--berlin.de/user/niko/cmaapplications.pdf
• 6: Hansen, N., Ostermeier, A. (1996): Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Proc. IEEE Int'l Conference on Evolutionary Computation (ICEC), 312--317.
• 7: Jägersküpper, J. (2003): Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. In Proc. 30th Int'l Colloquium on Automata, Languages and Programming (ICALP), vol. 2719 of LNCS, 1068--79, Springer.
• 8: Jens Jägersküpper, How the (1 + 1) ES using isotropic mutations minimizes positive definite quadratic forms, Theoretical Computer Science, v.361 n.1, p.38-56, 28 August 2006 [doi>10.1016/j.tcs.2006.04.004]
• 9: Jens Jägersküpper, Algorithmic analysis of a basic evolutionary algorithm for continuous optimization, Theoretical Computer Science, v.379 n.3, p.329-347, June, 2007 [doi>10.1016/j.tcs.2007.02.042]
• 10: Kolda, T. G., Lewis, R. M., Torczon, V. (2004): Optimization by direct search: New perspectives on some classical and m odern methods. SIAM Review, 45(3):385--482.
• 11: Nocedal, J., Wright, S. J. (1999): Numerical Optimization. Springer.
• 12: Hans-Paul Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, Inc., New York, NY, 1981

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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
empirical analysis, evolution strategies, sphere function