A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize

Marc Schoenauer 1, 2 Fabien Teytaud 1, 3 Olivier Teytaud 1, 3
1 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Multi-Modal Optimization (MMO) is ubiquitous in engineer- ing, machine learning and artificial intelligence applications. Many algo- rithms have been proposed for multimodal optimization, and many of them are based on restart strategies. However, only few works address the issue of initialization in restarts. Furthermore, very few comparisons have been done, between different MMO algorithms, and against simple baseline methods. This paper proposes an analysis of restart strategies, and provides a restart strategy for any local search algorithm for which theoretical guarantees are derived. This restart strategy is to decrease some 'step-size', rather than to increase the population size, and it uses quasi-random initialization, that leads to a rigorous proof of improve- ment with respect to random restarts or restarts with constant initial step-size. Furthermore, when this strategy encapsulates a (1+1)-ES with 1/5th adaptation rule, the resulting algorithm outperforms state of the art MMO algorithms while being computationally faster.
Type de document :
Communication dans un congrès
Artificial Evolution, Oct 2011, Angers, France. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00625855
Contributeur : Fabien Teytaud <>
Soumis le : jeudi 22 septembre 2011 - 17:28:40
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 23 décembre 2011 - 02:31:13

Fichier

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

Identifiants

  • HAL Id : inria-00625855, version 1

Collections

Citation

Marc Schoenauer, Fabien Teytaud, Olivier Teytaud. A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize. Artificial Evolution, Oct 2011, Angers, France. 2011. 〈inria-00625855〉

Partager

Métriques

Consultations de la notice

382

Téléchargements de fichiers

840