caa a22 4500 44580484X CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-010-9391-3 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9391-3 Lower Bounds for Comparison Based Evolution Strategies Using VC-dimension and Sign Patterns [Elektronische Daten] [Hervé Fournier, Olivier Teytaud] We derive lower bounds on the convergence rate of comparison based or selection based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. This is achieved by considering the VC-dimension of the level sets of the fitness functions; results are then obtained through the use of the shatter function lemma. In the special case of optimization of the sphere function, improved lower bounds are obtained by an argument based on the number of sign patterns. Springer Science+Business Media, LLC, 2010 Evolution algorithms nationallicence Convergence speed nationallicence VC-dimension nationallicence Sign patterns nationallicence Sphere function nationallicence Fournier Hervé Laboratoire PRiSM, CNRS UMR 8144 and Univ. Versailles Saint-Quentin-en-Yvelines, 45 av. des États-Unis, 78035, Versailles, France aut Teytaud Olivier TAO (Inria), LRI, UMR 8623 (CNRS-Univ. Paris-Sud), Bât 490, Univ. Paris-Sud, 91405, Orsay, France aut Algorithmica Springer-Verlag 59/3(2011-03-01), 387-408 0178-4617 59:3<387 2011 59 453 https://doi.org/10.1007/s00453-010-9391-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9391-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fournier Hervé Laboratoire PRiSM, CNRS UMR 8144 and Univ. Versailles Saint-Quentin-en-Yvelines, 45 av. des États-Unis, 78035, Versailles, France aut NATIONALLICENCE 700 1- Teytaud Olivier TAO (Inria), LRI, UMR 8623 (CNRS-Univ. Paris-Sud), Bât 490, Univ. Paris-Sud, 91405, Orsay, France aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 387-408 0178-4617 59:3<387 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer