Lyapunov design of a simple step-size adaptation strategy based on success

Claudia R. Correa, Elizabeth F. Wanner*, Carlos M. Fonseca

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A simple success-based step-size adaptation rule for singleparent Evolution Strategies is formulated, and the setting of the corresponding parameters is considered. Theoretical convergence on the class of strictly unimodal functions of one variable that are symmetric around the optimum is investigated using a stochastic Lyapunov function method developed by Semenov and Terkel [5] in the context of martingale theory. General expressions for the conditional expectations of the next values of step size and distance to the optimum under (1 +, λ)-selection are analytically derived, and an appropriate Lyapunov function is constructed. Convergence rate upper bounds, as well as adaptation parameter values, are obtained through numerical optimization for increasing values of λ. By selecting the number of offspring that minimizes the bound on the convergence rate with respect to the number of function evaluations, all strategy parameter values result from the analysis.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIV
Subtitle of host publication14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings
EditorsJulia Handl, Emma Hart, Peter R. Lewis, et al
Place of PublicationCham (CH)
PublisherSpringer
Pages101-110
Number of pages10
ISBN (Electronic)978-3-319-45823-6
ISBN (Print)978-3-319-45822-9
DOIs
Publication statusE-pub ahead of print - 31 Aug 2016
Event14th International Conference on Parallel Problem Solving from Nature - Edinburgh, United Kingdom
Duration: 17 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9921
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Parallel Problem Solving from Nature
Abbreviated titlePPSN 2016
CountryUnited Kingdom
CityEdinburgh
Period17/09/1621/09/16

Fingerprint

Lyapunov functions
Lyapunov Function
Lyapunov
Convergence Rate
Parameter Adaptation
Evolution Strategies
Function evaluation
Numerical Optimization
Conditional Expectation
Evaluation Function
Martingale
Strictly
Upper bound
Minimise
Design
Strategy
Context
Class

Keywords

  • convergence rate
  • evolution strategy
  • Lyapunov function theory
  • step-size adaptation

Cite this

Correa, C. R., Wanner, E. F., & Fonseca, C. M. (2016). Lyapunov design of a simple step-size adaptation strategy based on success. In J. Handl, E. Hart, P. R. Lewis, & et al (Eds.), Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings (pp. 101-110). (Lecture Notes in Computer Science; Vol. 9921). Cham (CH): Springer. https://doi.org/10.1007/978-3-319-45823-6_10
Correa, Claudia R. ; Wanner, Elizabeth F. ; Fonseca, Carlos M. / Lyapunov design of a simple step-size adaptation strategy based on success. Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. editor / Julia Handl ; Emma Hart ; Peter R. Lewis ; et al. Cham (CH) : Springer, 2016. pp. 101-110 (Lecture Notes in Computer Science).
@inproceedings{804292c3ef5e4838a9047d7b66eb9c5f,
title = "Lyapunov design of a simple step-size adaptation strategy based on success",
abstract = "A simple success-based step-size adaptation rule for singleparent Evolution Strategies is formulated, and the setting of the corresponding parameters is considered. Theoretical convergence on the class of strictly unimodal functions of one variable that are symmetric around the optimum is investigated using a stochastic Lyapunov function method developed by Semenov and Terkel [5] in the context of martingale theory. General expressions for the conditional expectations of the next values of step size and distance to the optimum under (1 +, λ)-selection are analytically derived, and an appropriate Lyapunov function is constructed. Convergence rate upper bounds, as well as adaptation parameter values, are obtained through numerical optimization for increasing values of λ. By selecting the number of offspring that minimizes the bound on the convergence rate with respect to the number of function evaluations, all strategy parameter values result from the analysis.",
keywords = "convergence rate, evolution strategy, Lyapunov function theory, step-size adaptation",
author = "Correa, {Claudia R.} and Wanner, {Elizabeth F.} and Fonseca, {Carlos M.}",
year = "2016",
month = "8",
day = "31",
doi = "10.1007/978-3-319-45823-6_10",
language = "English",
isbn = "978-3-319-45822-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "101--110",
editor = "Julia Handl and Emma Hart and Lewis, {Peter R.} and {et al}",
booktitle = "Parallel Problem Solving from Nature – PPSN XIV",
address = "Germany",

}

Correa, CR, Wanner, EF & Fonseca, CM 2016, Lyapunov design of a simple step-size adaptation strategy based on success. in J Handl, E Hart, PR Lewis & et al (eds), Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9921, Springer, Cham (CH), pp. 101-110, 14th International Conference on Parallel Problem Solving from Nature, Edinburgh, United Kingdom, 17/09/16. https://doi.org/10.1007/978-3-319-45823-6_10

Lyapunov design of a simple step-size adaptation strategy based on success. / Correa, Claudia R.; Wanner, Elizabeth F.; Fonseca, Carlos M.

Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. ed. / Julia Handl; Emma Hart; Peter R. Lewis; et al. Cham (CH) : Springer, 2016. p. 101-110 (Lecture Notes in Computer Science; Vol. 9921).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Lyapunov design of a simple step-size adaptation strategy based on success

AU - Correa, Claudia R.

AU - Wanner, Elizabeth F.

AU - Fonseca, Carlos M.

PY - 2016/8/31

Y1 - 2016/8/31

N2 - A simple success-based step-size adaptation rule for singleparent Evolution Strategies is formulated, and the setting of the corresponding parameters is considered. Theoretical convergence on the class of strictly unimodal functions of one variable that are symmetric around the optimum is investigated using a stochastic Lyapunov function method developed by Semenov and Terkel [5] in the context of martingale theory. General expressions for the conditional expectations of the next values of step size and distance to the optimum under (1 +, λ)-selection are analytically derived, and an appropriate Lyapunov function is constructed. Convergence rate upper bounds, as well as adaptation parameter values, are obtained through numerical optimization for increasing values of λ. By selecting the number of offspring that minimizes the bound on the convergence rate with respect to the number of function evaluations, all strategy parameter values result from the analysis.

AB - A simple success-based step-size adaptation rule for singleparent Evolution Strategies is formulated, and the setting of the corresponding parameters is considered. Theoretical convergence on the class of strictly unimodal functions of one variable that are symmetric around the optimum is investigated using a stochastic Lyapunov function method developed by Semenov and Terkel [5] in the context of martingale theory. General expressions for the conditional expectations of the next values of step size and distance to the optimum under (1 +, λ)-selection are analytically derived, and an appropriate Lyapunov function is constructed. Convergence rate upper bounds, as well as adaptation parameter values, are obtained through numerical optimization for increasing values of λ. By selecting the number of offspring that minimizes the bound on the convergence rate with respect to the number of function evaluations, all strategy parameter values result from the analysis.

KW - convergence rate

KW - evolution strategy

KW - Lyapunov function theory

KW - step-size adaptation

UR - http://link.springer.com/chapter/10.1007%2F978-3-319-45823-6_10

UR - http://www.scopus.com/inward/record.url?scp=84988485731&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-45823-6_10

DO - 10.1007/978-3-319-45823-6_10

M3 - Conference contribution

AN - SCOPUS:84988485731

SN - 978-3-319-45822-9

T3 - Lecture Notes in Computer Science

SP - 101

EP - 110

BT - Parallel Problem Solving from Nature – PPSN XIV

A2 - Handl, Julia

A2 - Hart, Emma

A2 - Lewis, Peter R.

A2 - et al,

PB - Springer

CY - Cham (CH)

ER -

Correa CR, Wanner EF, Fonseca CM. Lyapunov design of a simple step-size adaptation strategy based on success. In Handl J, Hart E, Lewis PR, et al, editors, Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings. Cham (CH): Springer. 2016. p. 101-110. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-45823-6_10