inria-00452791, version 1
Lower Bounds for Comparison Based Evolution Strategies using VC-dimension and Sign Patterns
Hervé Fournier
1Olivier Teytaud 2, 3
Algorithmica (2010)
Résumé : 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.
- 1 : Parallélisme, Réseaux, Systèmes d'information, Modélisation (PRISM)
- CNRS : UMR8144 – Université de Versailles Saint-Quentin-en-Yvelines
- 2 : Laboratoire de Recherche en Informatique (LRI)
- CNRS : UMR8623 – Université Paris XI - Paris Sud
- 3 : TAO (INRIA Saclay - Ile de France)
- INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
- Domaine : Mathématiques/Optimisation et contrôle
- Mots-clés : Evolutionary Algorithms – Parallel Optimization – Comparison-based algorithms – VC-dimension – Sign patterns – Complexity
- inria-00452791, version 1
- http://hal.inria.fr/inria-00452791
- oai:hal.inria.fr:inria-00452791
- Contributeur : Olivier Teytaud
- Soumis le : Mercredi 3 Février 2010, 09:46:06
- Dernière modification le : Mercredi 3 Février 2010, 10:57:08
Documents associés
Exporter