Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule

Abstract : This paper explores the use of the standard approach for proving runtime bounds in discrete domains---often referred to as drift analysis---in the context of optimization on a continuous domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension $d$. The bounds are akin to linear convergence. We then study the dependency of the different terms on $d$ proving a convergence rate dependency of $\Theta(1/d)$. Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with continuous domain.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01778116
Contributor : Anne Auger <>
Submitted on : Wednesday, April 25, 2018 - 2:16:01 PM
Last modification on : Friday, April 27, 2018 - 1:15:14 AM

Links full text

Identifiers

  • HAL Id : hal-01778116, version 1
  • ARXIV : 1802.03209

Collections

Citation

Youhei Akimoto, Anne Auger, Tobias Glasmachers. Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule. Proceedings of the GECCO 2018 Conference, 2018, Kyoto, Japan. ⟨hal-01778116⟩

Share

Metrics

Record views

71