Probabilistic runtime analysis of (1 +<over>, λ),ES using isotropic mutations

ABSTRACT

We consider the (1+λ)ES and the (1+λ)ES, which are simple evolutionary algorithms for minimization in Rⁿ, using isotropic mutations. General lower bounds on the number of mutations that are necessary to reduce the approximation error in the search space, ie the distance from the optimum (or from any other fixed point in the search space), are proved. Therefore, we generalize a lower-bound method recently introduced by Witt in a runtime analysis of the (μ+1)EA for the search space {0,1}ⁿ, which was also already successfully applied in an analysis of a (μ+1)ES. Namely, we prove that both, the (1+λ)ES as well as the (1+λ)ES need Ω(n•λ/√lnλ) function evaluations with an overwhelming probability to halve the approximation error in the search space - independently of how the isotropic mutations are adapted and of the function to be optimized.On the other hand, for an upper bound we consider the following concrete scenario: the minimization of the well-known SPHERE-function using Gaussian mutation vectors adapted by the 1/5-rule. We prove that the (1+λ)ES needs Ω(n•λ/√lnλ). SPHERE-evaluations with an overwhelming probability to halve the approximation error. Moreover, by some kind of reduction, we show that this upper bound also holds for the (1,λ)ES.Finally, the gap of size O(√lnλ) between the lower bound and the upper bound is discussed.

REFERENCES

• 1: The theory of evolution strategies, Springer-Verlag New York, Inc., New York, NY, 2001
• 2: 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]
• 3: Ericson, T., Zinoviev, V. (2001): Codes on Euclidean Spheres. Elsevier, Amsterdam.
• 4: Oliver Giel , Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.415-426, February 27-March 01, 2003
• 5: 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.
• 6: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 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: Jägersküpper, J. (2005): Rigorous runtime analysis of the (1+1), ES: 1/5-rule and ellipsoidal fitness landscapes. In Foundations of Genetic Algorithms: 8th Int'l Workshop, Revised Selected Papers (FOGA), vol. 3469 of LNCS, 260--281, Springer.
• 9: Jens Jägersküpper , Carsten Witt, Rigorous runtime analysis of a (μ+1)ES for the sphere function, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068153]
• 10: Thomas Jansen , Kenneth A. De Jong, An Analysis Of The Role Of Offspring Population Size In EAs, Proceedings of the Genetic and Evolutionary Computation Conference, p.238-246, July 09-13, 2002
• 11: Neumann, F., Wegener, I. (2004): Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In Proc. Genetic and Evolutionary Computation Conference (GECCO), vol. 3102 of LNCS, 713--724, Springer.
• 12: Rechenberg, I. (1973): Evolutionsstrategie. Frommann-Holzboog, Stuttgart, Germany.
• 13: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 14: Storch, T., Wegener, I. (2003): Real royal road functions for constant population size. In Proc. Genetic and Evolutionary Computation Conference (GECCO '03), vol. 2724 of LNCS, 1406--17, Springer.
• 15: Witt, C. (2004): An analysis of the (μ+1)-EA on simple pseudo-boolean functions. In Proc. Genetic and Evolutionary Computation Conference (GECCO), vol. 3102 of LNCS, 761--773, Springer.
• 16: Witt, C. (2005): Worst-case and average-case approximations by simple randomized search heuristics. In Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 3404 of LNCS, 44--56, Springer.
• 17: Yao, X., Liu, Y., Lin, G. (1999): Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2):82--102.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Performance, Theory

Keywords:
evolution strategies, runtime analysis, sphere function