research-article

Theoretical analysis of evolutionary computation on continuously differentiable functions

Authors:

Youhei Akimoto,

Shigenobu KobayashiAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 1401 - 1408

https://doi.org/10.1145/1830483.1830742

Published: 07 July 2010 Publication History

Abstract

This paper investigates theoretically the convergence properties of the stochastic algorithms of a class including both CMAESs and EDAs on constrained minimization of continuously differentiable functions. We are interested in algorithms that do not get stuck on a slope of the function, but converge only to local optimal points. Convergence to a point that is neither a stationary point of the function nor a boundary point is evidence that the convergence properties are not well behaved. We investigate what properties are necessary/sufficient for the algorithm to avoid this type of behavior, i.e., what properties are necessary for the algorithm to converge only to local optimal points of the function. We also investigate the analogous conditions on the parameters of two variants of modern EC-based stochastic algorithms, namely, a CMAES employing rank-μ update and an EDA known as EMNA_global. The comparison between the apparently similar two systems shows that they have significantly different theoretical behaviors. This result presents us with an insight into the way we design well-behaved optimization algorithms.

References

[1]

A. Auger. Convergence results for the (1, λ)-SA-ES using the theory of φ-irreducible Markov chains. Theoretical Computer Science, 334(1-3):35--69, 2005.

Digital Library

[2]

A. Bienvenüe and O. François. Global convergence for evolution strategies in spherical problems: some simple proofs and difficulties. Theoretical Computer Science, 306(1-3):269--289, 2003.

Digital Library

[3]

P. Billingsley. Probability and Measure. WILEY SERIES IN PROBABILITY AND MATHEMATICAL STATISTICS. Wiley-Interscience, third edition, 1995.

[4]

H. A. David and H. N. Nagaraja. Order Statistics. WILEY SERIES IN PROBABILITY AND STATISTICS. Wiley-Interscience, third edition, 2003.

[5]

J. Grahl, P. A. N. Bosman, and F. Rothlauf. The correlation-triggered adaptive variance scaling idea. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2006, pages 397--404, 2006. ACM.

Digital Library

[6]

N. Hansen. The CMA evolution strategy: a comparing review. In Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75--102. Springer, 2006.

[7]

N. Hansen, S. Müller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1):1--18, 2003.

Digital Library

[8]

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

Digital Library

[9]

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

Digital Library

[10]

K. C. Kiwiel and K. Murty. Convergence of the steepest descent method for minimizing quasiconvex functions. Journal of Optimization Theory and Applications, 89(1):221--226, 1996.

Digital Library

[11]

P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.

[12]

D.-H. Li and M. Fukushima. On the global convergence of the bfgs method for nonconvex unconstrained optimization problems. SIAM Journal on Optimization, 11(4):1054--1064, 2001.

Digital Library

[13]

M. Locatelli. Simulated annealing algorithms for continuous global optimization: Convergence conditions. Journal of Optimization Theory and Applications, 104(1):121--133, 1 2000.

Digital Library

[14]

J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research. Springer, second edition, 2006.

[15]

A. Ruszczyński. Nonlinear Optimization. Princeton University Press, 2006.

Digital Library

[16]

M. A. Semenov and D. A. Terkel. Analysis of convergence of an evolutionary algorithm with self-adaptation using a stochastic lyapunov function. Evolutionary Computation, 11(4):363--379, 2003.

Digital Library

[17]

O. Teytaud and H. Fournier. Lower bounds for evolution strategies using vc-dimension. In Parallel Problem Solving from Nature - PPSN X, volume 5199 of Lecture Notes in Computer Science, pages 102--111, 2008. Springer-Verlag.

[18]

A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2000.

[19]

C. Witt. Why standard particle swarm optimisers elude a theoretical runtime analysis. In FOGA'09: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, pages 13--20, 2009. ACM.

Digital Library

[20]

R. L. Yang. Convergence of the simulated annealing algorithm for continuous global optimization. Journal of Optimization Theory and Applications, 104(3):691--716, 2000.

Digital Library

Cited By

Toure CAuger AHansen N(2022)Global linear convergence of evolution strategies with recombination on scaling-invariant functionsJournal of Global Optimization10.1007/s10898-022-01249-686:1(163-203)Online publication date: 1-Nov-2022
https://doi.org/10.1007/s10898-022-01249-6
Glasmachers T(2022)The (1+1)-ES Reliably Overcomes Saddle PointsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_22(309-319)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_22
Glasmachers T(2020)Global Convergence of the (1 + 1) Evolution Strategy to a Critical PointEvolutionary Computation10.1162/evco_a_0024828:1(27-53)Online publication date: Mar-2020
https://doi.org/10.1162/evco_a_00248
Show More Cited By

Index Terms

Theoretical analysis of evolutionary computation on continuously differentiable functions
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Local analysis of the feasible primal-dual interior-point method

In this paper we analyze the rate of local convergence of the Newton primal-dual interior-point method when the iterates are kept strictly feasible with respect to the inequality constraints.
It is shown under the classical conditions that the rate is q-...
On differentiable exact penalty functions

In this work, we study a differentiable exact penalty function for solving twice continuously differentiable inequality constrained optimization problems. Under certain assumptions on the parameters of the penalty function, we show the equivalence of ...
Local convergence analysis of inexact Newton-like methods under majorant condition

We present a local convergence analysis of inexact Newton-like methods for solving nonlinear equations under majorant conditions. This analysis provides an estimate of the convergence radius and a clear relationship between the majorant function, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 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 ACM 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: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
157
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Toure CAuger AHansen N(2022)Global linear convergence of evolution strategies with recombination on scaling-invariant functionsJournal of Global Optimization10.1007/s10898-022-01249-686:1(163-203)Online publication date: 1-Nov-2022
https://doi.org/10.1007/s10898-022-01249-6
Glasmachers T(2022)The (1+1)-ES Reliably Overcomes Saddle PointsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_22(309-319)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_22
Glasmachers T(2020)Global Convergence of the (1 + 1) Evolution Strategy to a Critical PointEvolutionary Computation10.1162/evco_a_0024828:1(27-53)Online publication date: Mar-2020
https://doi.org/10.1162/evco_a_00248
Beyer HFinck S(2018)On the Design of Constraint Covariance Matrix Self-Adaptation Evolution Strategies Including a Cardinality ConstraintIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.216996716:4(578-596)Online publication date: 25-Dec-2018
https://dl.acm.org/doi/10.1109/TEVC.2011.2169967
Akimoto YNagata YOno IKobayashi S(2012)Theoretical Foundation for CMA-ES from Information Geometry PerspectiveAlgorithmica10.1007/s00453-011-9564-864:4(698-716)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1007/s00453-011-9564-8

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.

Media

Figures

Other

Tables

View Table of Contents