General lower bounds for evolutionary algorithms

Olivier Teytaud 1 Sylvain Gelly 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Evolutionary optimization, among which genetic optimization, is a general framework for optimization. It is known (i) easy to use (ii) robust (iii) derivative-free (iv) unfortunately slow. Recent work [8] in particular show that the convergence rate of some widely used evolution strategies (evolutionary optimization for continuous domains) can not be faster than linear (i.e. the logarithm of the distance to the optimum can not decrease faster than linearly), and that the constant in the linear convergence (i.e. the constant C such that the distance to the optimum after n steps is upp er b ounded by C n ) unfortunately converges quickly to 1 as the dimension increases to infinity. We here show a very wide generalization of this result: al l comparison-based algorithms have such a limitation. Note that our result also concerns methods like the Hooke & Jeeves algorithm, the simplex method, or any direct search method that only compares the values to previously seen values of the fitness. But it does not cover methods that use the value of the fitness (see [5] for cases in which the fitness-values are used), even if these methods do not use gradients. The former results deal with convergence with respect to the number of comparisons performed, and also include a very wide family of algorithms with resp ect to the number of function-evaluations. However, there is still place for faster convergence rates, for more original algorithms using the full ranking information of the population and not only selections among the population. We prove that, at least in some particular cases, using the full ranking information can improve these lower bounds, and ultimately provide sup erlinear convergence results.
Type de document :
Communication dans un congrès
Parallel Problem Solving from Nature, Sep 2006, Reykjavik, 2006
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00112820
Contributeur : Sylvain Gelly <>
Soumis le : jeudi 9 novembre 2006 - 17:21:30
Dernière modification le : jeudi 10 mai 2018 - 02:06:23
Document(s) archivé(s) le : mardi 6 avril 2010 - 22:04:12

Fichier

Identifiants

  • HAL Id : inria-00112820, version 1

Collections

Citation

Olivier Teytaud, Sylvain Gelly. General lower bounds for evolutionary algorithms. Parallel Problem Solving from Nature, Sep 2006, Reykjavik, 2006. 〈inria-00112820〉

Partager

Métriques

Consultations de la notice

409

Téléchargements de fichiers

449