@inproceedings{cd63734ea938406ab7ea29acf4d6df14,
title = "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 Θ(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.",
keywords = "Drift, Evolution strategies, Hitting time, Linear convergence",
author = "Youhei Akimoto and Anne Auger and Tobias Glasmachers",
note = "Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s).; 2018 Genetic and Evolutionary Computation Conference, GECCO 2018 ; Conference date: 15-07-2018 Through 19-07-2018",
year = "2018",
month = jul,
day = "2",
doi = "10.1145/3205455.3205606",
language = "English",
series = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery, Inc",
pages = "801--808",
booktitle = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",
}