Lower Bounds for Comparison Based Evolution Strategies Using VC-dimension and Sign Patterns

1. Arnold, D.V.: Optimal weighted recombination. In: Foundations of Genetic Algorithms 8. Lecture Notes in Computer Science, vol. 3469, pp. 215–237. Springer, Berlin (2005)

   Chapter  Google Scholar 

2. Auger, A.: Convergence results for (1,λ)-SA-ES using the theory of φ-irreducible Markov chains. Theor. Comput. Sci. 334(1–3), 35–69 (2005)

   Article  MATH  MathSciNet  Google Scholar 

3. Auger, A., Schoenauer, M., Teytaud, O.: Local and global order 3/2 convergence of a surrogate evolutionary algorithm. In: GECCO’05: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 857–864. ACM, New York (2005)

   Chapter  Google Scholar 

4. Bäck, T., Hoffmeister, F., Schwefel, H.-P.: Extended selection mechanisms in genetic algorithms. In: Belew, R.K., Booker, L.B. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 92–99. Morgan Kaufmann, San Mateo (1991)

   Google Scholar 

5. Baker, J.E.: Reducing bias and inefficiency in the selection algorithm. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, pp. 14–21. Lawrence Erlbaum Associates, Mahwah (1987)

   Google Scholar 

6. Beyer, H.-G.: Toward a theory of evolution strategies: On the benefit of sex—the (μ/μ,λ)-theory. Evol. Comput. 3(1), 81–111 (1995)

   Article  MathSciNet  Google Scholar 

7. Beyer, H.-G., Schwefel, H.-P.: Evolution strategies: a comprehensive introduction. Nat. Comput. 1(1), 3–52 (2002)

   Article  MATH  MathSciNet  Google Scholar 

8. Devroye, L., Györfi, L., Lugosi, G.: A probabilistic Theory of Pattern Recognition. Springer, Berlin (1997)

   Google Scholar 

9. Droste, S.: Not all linear functions are equally difficult for the compact genetic algorithm. In: Proc. of the Genetic and Evolutionary Computation COnference (GECCO 2005), pp. 679–686 (2005)

10. Droste, S., Jansen, T., Wegener, I.: A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with boolean inputs. Evol. Comput. 6(2), 185–196 (1998)

    Article  Google Scholar 

11. Gelly, S., Ruette, S., Teytaud, O.: Comparison-based algorithms are robust and randomized algorithms are anytime. Evol. Comput. J. 15(4), 411–434 (2007). Special issue on bridging Theory and Practice

    Article  Google Scholar 

12. Halperin, D.: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 529–562. CRC Press, Boca Raton (2004). Chap. 24

    Google Scholar 

13. Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159–195 (2001)

    Article  Google Scholar 

14. Hooke, R., Jeeves, T.A.: “Direct search” solution of numerical and statistical problems. J. ACM 8(2), 212–229 (1961)

    Article  MATH  Google Scholar 

15. Jägersküpper, J.: Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. In: 30th International Colloquium on Automata, Languages, and Programming (ICALP 2003). LNCS, vol. 2719, pp. 1068–1079. Springer, Berlin (2003)

    Chapter  Google Scholar 

16. Jägersküpper, J.: Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. Theor. Comput. Sci. 379(3), 329–347 (2007). Special issue on ICALP 2003

    Article  MATH  Google Scholar 

17. Jägersküpper, J., Witt, C.: Rigorous runtime analysis of a (μ+1)-ES for the sphere function. In: GECCO, pp. 849–856 (2005)

18. Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, Berlin (2002)

    MATH  Google Scholar 

19. Moraglio, A., Poli, R.: Topological crossover for the permutation representation. In: GECCO’05: Proceedings of the 2005 Workshops on Genetic and Evolutionary Computation, pp. 332–338. ACM, New York (2005)

    Chapter  Google Scholar 

20. Neumann, F.: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Computers & OR 35(9), 2750–2759 (2008)

    Article  MATH  Google Scholar 

21. Rechenberg, I.: Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Holzboog Verlag, Stuttgart (1973)

    Google Scholar 

22. Rónyai, L., Babai, L., Ganapathy, M.K.: On the number of zero-patterns of a sequence of polynomials. J. Am. Math. Soc. 14(3), 717–735 (2001)

    Article  MATH  Google Scholar 

23. Rudolph, G.: Convergence rates of evolutionary algorithms for a class of convex objective functions. Control Cybern. 26(3), 375–390 (1997)

    MATH  MathSciNet  Google Scholar 

24. Sauer, N.: On the density of families of sets. J. Comb. Theory, Ser. A 13(1), 145–147 (1972)

    Article  MATH  MathSciNet  Google Scholar 

25. Sudholt, D., Witt, C.: Runtime analysis of binary PSO. In: GECCO’08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 135–142. ACM, New York (2008)

    Chapter  Google Scholar 

26. Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Proceedings of PPSN, pp. 21–31 (2006)

27. Teytaud, O., Fournier, H.: Lower bounds for evolution strategies using vc-dimension. In: PPSN, pp. 102–111 (2008)

28. Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. XVI(2), 264–280 (1971)

    Article  MathSciNet  Google Scholar 

29. Whitley, D.: The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In: Schaffer, J.D. (ed.) Proceedings of the Third International Conference on Genetic Algorithms, pp. 116–121. Morgan Kaufman, San Mateo (1989)

    Google Scholar 

30. Witt, C.: Theory of randomised search heuristics in combinatorial optimisation: an algorithmic point of view. In: GECCO’09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 3551–3592. ACM, New York (2009)

    Chapter  Google Scholar 

Download references