Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Fabien Teytaud Connect in order to contact the contributor
Submitted on : Thursday, September 22, 2011 - 5:28:40 PM
Last modification on : Friday, November 18, 2022 - 9:23:27 AM
Long-term archiving on: : Friday, December 23, 2011 - 2:31:13 AM


Files produced by the author(s)


  • HAL Id : inria-00625855, version 1


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



Record views


Files downloads