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

Claudia R. Correa; Elizabeth F. Wanner; Carlos M. Fonseca

doi:10.1007/978-3-319-45823-6_10

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

College of Engineering and Physical Sciences

Centro Federal de Educação Tecnológica de Minas Gerais
Universidade de Coimbra

Research output: Chapter in Book/Published conference output › Conference publication

4 Citations (Scopus)

87 Downloads (Pure)

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 language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XIV
Subtitle of host publication	14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings
Editors	Julia Handl, Emma Hart, Peter R. Lewis, et al
Place of Publication	Cham (CH)
Publisher	Springer
Pages	101-110
Number of pages	10
ISBN (Electronic)	978-3-319-45823-6
ISBN (Print)	978-3-319-45822-9
DOIs	https://doi.org/10.1007/978-3-319-45823-6_10
Publication status	E-pub ahead of print - 31 Aug 2016
Event	14th International Conference on Parallel Problem Solving from Nature - Edinburgh, United Kingdom Duration: 17 Sept 2016 → 21 Sept 2016

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9921
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Parallel Problem Solving from Nature
Abbreviated title	PPSN 2016
Country/Territory	United Kingdom
City	Edinburgh
Period	17/09/16 → 21/09/16

Keywords

convergence rate
evolution strategy
Lyapunov function theory
step-size adaptation

Access to Document

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

Lyapunov design of a simple step-size adaptation strategy based on successAccepted author manuscript, 293 KB

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). Springer. Advance online publication. 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 = aug,

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",

note = "14th International Conference on Parallel Problem Solving from Nature, PPSN 2016 ; Conference date: 17-09-2016 Through 21-09-2016",

}

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/Published conference output › Conference publication

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 - https://www.scopus.com/pages/publications/84988485731

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

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

M3 - Conference publication

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)

T2 - 14th International Conference on Parallel Problem Solving from Nature

Y2 - 17 September 2016 through 21 September 2016

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). Epub 2016 Aug 31. doi: 10.1007/978-3-319-45823-6_10

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Parallel Problem Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings

Preface

Cite this