comparison-based algorithms are robust and randomized algorithms are anytime.

Sylvain Gelly 1 Sylvie Ruette 2 Olivier Teytaud 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 : Randomized search heuristics (e.g., evolutionary algorithms, simulated annealing etc.) are very appealing to practitioners, they are easy to implement and usually provide good performance. The theoretical analysis of these algorithms usually focuses on convergence rates. This paper presents a mathematical study of randomized search heuristicswhich use comparison based selectionmechanism. The twomain results are: (i) comparison-based algorithms are the best algorithms for some robustness criteria, (ii) introducing randomness in the choice of offspring improves the anytime behavior of the algorithm. An original Estimation of Distribution Algorithm combining (i) and (ii) is proposed and successfully experimented.
Type de document :
Article dans une revue
Evolutionary Computation Journal, MIT Press, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00173221
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 19 septembre 2007 - 14:14:50
Dernière modification le : jeudi 10 mai 2018 - 02:06:29
Document(s) archivé(s) le : vendredi 9 avril 2010 - 02:28:54

Fichier

lb2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00173221, version 1

Collections

Citation

Sylvain Gelly, Sylvie Ruette, Olivier Teytaud. comparison-based algorithms are robust and randomized algorithms are anytime.. Evolutionary Computation Journal, MIT Press, 2007. 〈inria-00173221〉

Partager

Métriques

Consultations de la notice

484

Téléchargements de fichiers

167