research-article

Drift theory in continuous search spaces: expected hitting time of the (1 + 1)-ES with 1/5 success rule

Authors:

Youhei Akimoto,

Tobias GlasmachersAuthors Info & Claims

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 801 - 808

https://doi.org/10.1145/3205455.3205606

Published: 02 July 2018 Publication History

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.

References

[1]

Anne Auger, Dimo Brockhoff, and Nikolaus Hansen. Analyzing the impact of mirrored sampling and sequential selection in elitist evolution strategies. In Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, FOGA '11, pages 127--138, New York, NY, USA, 2011. ACM.

Digital Library

[2]

Anne Auger and Nikolaus Hansen. Linear convergence on positively homogeneous functions of a comparison based step-size adaptive randomized search: the (1+1) ES with generalized one-fifth success rule. CoRR, abs/1310.8397, 2013.

[3]

Claudia R. Correa, Elizabeth F. Wanner, and Carlos M. Fonseca. Lyapunov design of a simple step-size adaptation strategy based on success. In Parallel Problem Solving from Nature (PPSN), pages 101--110, 2016.

[4]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673--697, December 2012.

Digital Library

[5]

Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1):51 -- 81, 2002.

Digital Library

[6]

N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2):159--195, 2001.

Digital Library

[7]

Jens Jägersküpper. Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. Automata, Languages and Programming, pages 188--188, 2003.

[8]

Jens Jägersküpper. How the (1+1)-ES using isotropic mutations minimizes positive definite quadratic forms. Theoretical Computer Science, 361(1):38--56, 2006.

Digital Library

[9]

Jens Jägersküpper. Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoretical Computer Science, 379(3):329--347, 2007.

Digital Library

[10]

S. Kern, S. D. Müller, N. Hansen, D. Büche, J. Ocenasek, and P. Koumoutsakos. Learning probability distributions in continuous evolutionary algorithms-a comparative review. Natural Computing, 3(1):77--112, 2004.

Digital Library

[11]

Per Kristian Lehre. Drift analysis. In Genetic and Evolutionary Computation Conference, GECCO '12, Philadelphia, PA, USA, July 7-11, 2012, Companion Material Proceedings, pages 1239--1258, 2012.

Digital Library

[12]

Per Kristian Lehre and Carsten Witt. General drift analysis with tail bounds. Technical Report arXiv:1307.2559, 2013.

[13]

Johannes Lengler and Angelika Steger. Drift analysis and evolutionary algorithms revisited. Technical Report arXiv:1608.03226, 2016.

[14]

Ingo Rechenberg. Evolutionsstrategie: Optimierung technisher Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, 1973.

[15]

H. Thorisson. Coupling, Stationarity, and Regeneration. Probability and Its Applications. Springer New York, 2000.

Cited By

Auger ARothlauf F(2024)The 2024 ACM SIGEVO Outstanding Contribution AwardeesACM SIGEVOlution10.1145/3717452.371745317:4(1-8)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3717452.3717453
Morinaga DFukuchi KSakuma JAkimoto YLi XHandl J(2024)Linear Convergence Rate Analysis of the (1+1)-ES on Locally Strongly Convex and Lipschitz Smooth FunctionsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664074(49-50)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664074
Morinaga DFukuchi KSakuma JAkimoto Y(2024)Convergence Rate of the (1+1)-ES on Locally Strongly Convex and Lipschitz Smooth FunctionsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.326695528:2(501-515)Online publication date: Apr-2024
https://doi.org/10.1109/TEVC.2023.3266955
Show More Cited By

Index Terms

Drift theory in continuous search spaces: expected hitting time of the (1 + 1)-ES with 1/5 success rule
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Randomized search

Recommendations

Generalized drift analysis in continuous domain: linear convergence of (1 + 1)-ES on strongly convex functions with Lipschitz continuous gradients
FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

We prove the linear convergence of the (1 + 1)-Evolution Strategy (ES) with a success based step-size adaptation on a broad class of functions, including strongly convex functions with Lipschitz continuous gradients, which is often assumed to analyze ...
First-hitting times under drift
Abstract
For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of ...
Premature Convergence in Constrained Continuous Search Spaces
Proceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 5199

The optimum of numerical problems quite often lies on the constraint boundary or even in a vertex of the feasible search space. In such cases the evolutionary algorithm EA frequently suffers from premature convergence because of a low success ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Auger ARothlauf F(2024)The 2024 ACM SIGEVO Outstanding Contribution AwardeesACM SIGEVOlution10.1145/3717452.371745317:4(1-8)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3717452.3717453
Morinaga DFukuchi KSakuma JAkimoto YLi XHandl J(2024)Linear Convergence Rate Analysis of the (1+1)-ES on Locally Strongly Convex and Lipschitz Smooth FunctionsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664074(49-50)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664074
Morinaga DFukuchi KSakuma JAkimoto Y(2024)Convergence Rate of the (1+1)-ES on Locally Strongly Convex and Lipschitz Smooth FunctionsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.326695528:2(501-515)Online publication date: Apr-2024
https://doi.org/10.1109/TEVC.2023.3266955
Frank SGlasmachers T(2024)A Potential Function for a Variable-Metric Evolution StrategyParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_14(221-235)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70068-2_14
Bäck TKononova Avan Stein BWang HAntonov KKalkreuth Rde Nobel JVermetten Dde Winter RYe F(2023)Evolutionary Algorithms for Parameter Optimization—Thirty Years LaterEvolutionary Computation10.1162/evco_a_0032531:2(81-122)Online publication date: 1-Jun-2023
https://doi.org/10.1162/evco_a_00325
Agapie ASolomon OBădin L(2023)Theory of (1+1) ES on SPHERE RevisitedIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.321752427:4(938-948)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3217524
Wu YPeng XWang HJin YXu D(2023)Cooperative Coevolutionary CMA-ES With Landscape-Aware Grouping in Noisy EnvironmentsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.318022427:3(686-700)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3180224
Glasmachers TKrause O(2022)Convergence Analysis of the Hessian Estimation Evolution StrategyEvolutionary Computation10.1162/evco_a_0029530:1(27-50)Online publication date: 1-Mar-2022
https://doi.org/10.1162/evco_a_00295
Akimoto YAuger AGlasmachers TMorinaga D(2022)Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex FunctionsSIAM Journal on Optimization10.1137/20M137381532:2(1402-1429)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/20M1373815
He XZheng ZChen CZhou YLuo CLin Q(2022)Distributed Evolution Strategies for Black-Box Stochastic OptimizationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.316887333:12(3718-3731)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3168873
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten