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

被引：13

作者：

Fournier, Herve ^{[1
,2
]}

Teytaud, Olivier ^{[3
]}

机构：

[1] CNRS, Lab PRiSM, UMR 8144, F-78035 Versailles, France

[2] Univ Versailles St Quentin en Yvelines, F-78035 Versailles, France

[3] Univ Paris Sud, TAO Inria, LRI, UMR 8623,CNRS, F-91405 Orsay, France

来源：

ALGORITHMICA | 2011年 / 59卷 / 03期

关键词：

Evolution algorithms; Convergence speed; VC-dimension; Sign patterns; Sphere function; CONVERGENCE; ALGORITHMS;

D O I：

10.1007/s00453-010-9391-3

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：387 / 408

页数：22

共 30 条

[1]

[Anonymous], 2002, GRAD TEXT M, DOI 10.1007/978-1-4613-0039-7

[2]

Arnold DV, 2002, IEEE T EVOLUT COMPUT, V6, P30, DOI [10.1109/4235.985690, 10.1023/A:1015059928466]

[3]

ARNOLD DV, 2008, LECT NOTES COMPUTER, V3469, P215

[4] Convergence results for the (1,λ)-SA-ES using the theory of φ-irreducible Markov chains [J].

Auger, A .

THEORETICAL COMPUTER SCIENCE, 2005, 334 (1-3) :35-69

[5]

Auger A, 2005, GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, P857

[6]

Baker J. E., 1987, Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, P14

[7] Toward a Theory of Evolution Strategies: On the Benefits of Sex- the (mu/mu, lambda) Theory [J].

Beyer, Hans-Georg .

EVOLUTIONARY COMPUTATION, 1995, 3 (01) :81-111

[8]

Devroye L., 1997, A Probabilistic Theory of Pattern Recognition. Stochastic Modelling and Applied Probability

[9]

Droste S, 2005, GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, P679

[10] A Rigorous Complexity Analysis of the (1+1) Evolutionary Algorithm for Separable Functions with Boolean Inputs [J].

Droste, Stefan ;

Jansen, Thomas ;

Wegener, Ingo .

EVOLUTIONARY COMPUTATION, 1998, 6 (02) :185-196

← 1 2 3 →