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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00625855
Contributor : Fabien Teytaud <>
Submitted on : Thursday, September 22, 2011 - 5:28:40 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Friday, December 23, 2011 - 2:31:13 AM

File

qrrsEA.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00625855⟩

Share

Metrics

Record views

493

Files downloads

949