research-article

Quality Gain Analysis of the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions

Authors:

Youhei Akimoto,

Nikolaus HansenAuthors Info & Claims

FOGA '17: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Pages 111 - 126

https://doi.org/10.1145/3040718.3040720

Published: 12 January 2017 Publication History

Abstract

We investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive the asymptotic quality gain in the limit of the dimension to infinity, and derive the optimal recombination weights and the optimal step-size. This work is an extension of previous works where the asymptotic quality gain of evolution strategies with weighted recombination was derived on the infinite dimensional sphere function. Moreover, for a finite dimensional search space, we derive rigorous bounds for the quality gain on a general quadratic function. They reveal the dependency of the quality gain both in the eigenvalue distribution of the Hessian matrix and on the recombination weights. Taking the search space dimension to infinity, it turns out that the optimal recombination weights are independent of the Hessian matrix, i.e., the recombination weights optimal for the sphere function are optimal for convex quadratic functions.

References

[1]

Y. Akimoto, A. Auger, and N. Hansen. Convergence of the continuous time trajectories of isotropic evolution strategies on monotonic C²-composite functions. In Problem Solving from Nature - PPSN XII, pages 42--51, 2012.

[2]

Y. Akimoto and N. Hansen. Online model selection for restricted covariance matrix adaptation. In Parallel Problem Solving from Nature - PPSN XIV, pages 3--13, 2016.

[3]

Y. Akimoto and N. Hansen. Projection-based restricted covariance matrix adaptation for high dimension. In Genetic and Evolutionary Computation Conference, GECCO, pages 197--204, 2016.

Digital Library

[4]

D. V. Arnold. Optimal weighted recombination. In Foundations of Genetic Algorithms, pages 215--237, 2005.

Digital Library

[5]

D. V. Arnold. On the use of evolution strategies for optimising certain positive definite quadratic forms. In Genetic and Evolutionary Computation Conference, GECCO, pages 634--641, 2007.

Digital Library

[6]

A. Auger. Analysis of Comparison-based Stochastic Continuous Black-Box Optimization Algorithms. Habilitation, Universitè Paris-Sud, 2015.

[7]

A. Auger, D. Brockhoff, and N. Hansen. Mirrored sampling in evolution strategies with weighted recombination. In Genetic and Evolutionary Computation Conference, GECCO, pages 861--868, 2011.

Digital Library

[8]

A. Auger and N. Hansen. Reconsidering the progress rate theory for evolution strategies in finite dimensions. In Genetic and Evolutionary Computation Conference, GECCO, pages 445--452, 2006.

Digital Library

[9]

A. Auger and N. Hansen. Linear convergence of comparison-based step-size adaptive randomized search via stability of markov chains. SIAM Journal on Optimization, 26(3):1589--1624, 2016.

[10]

H.-G. Beyer. Towards a theory of 'evolution strategies': Results for (1+, ł)-strategies on (nearly) arbitrary fitness functions. In Parallel Problem Solving from Nature - PPSN III, pages 58--67, 1994.

[11]

H.-G. Beyer. The Theory of Evolution Strategies. Natural Computing Series. Springer-Verlag, 2001.

[12]

H.-G. Beyer and M. Hellwig. The dynamics of cumulative step size adaptation on the ellipsoid model. Evolutionary Computation, 24(1):25--57, 2016.

Digital Library

[13]

H.-G. Beyer and A. Melkozerov. The dynamics of self-adaptive multirecombinant evolution strategies on the general ellipsoid model. IEEE Transactions on Evolutionary Computation, 18(5):764--778, 2014.

[14]

A. DasGupta. Asymptotic theory of statistics and probability. Springer Science & Business Media, 2008.

[15]

L. Devroye. Non-Uniform Random Variate Generation. Springer New York, 1986.

[16]

S. Finck and H.-G. Beyer. Weighted recombination evolution strategy on a class of pdqf's. In Foundations of Genetic Algorithms, FOGA, pages 1--12, 2009.

Digital Library

[17]

N. Hansen and A. Auger. Principled design of continuous stochastic search: From theory to practice. In Y. Borenstein and A. Moraglio, editors, Theory and Principled Methods for the Design of Metaheuristics. Springer, 2014.

[18]

N. Hansen and S. Kern. Evaluating the cma evolution strategy on multimodal test functions. In Parallel Problem Solving from Nature - PPSN VIII, pages 282--291, 2004.

[19]

J. 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

[20]

M. Jebalia and A. Auger. Log-linear convergence of the scale-invariant (μ/μ_ω,λ)-es and optimal μ for intermediate recombination for large population sizes. In Parallel Problem Solving from Nature - PPSN XI, pages 52--62, 2010.

[21]

M. Jebalia and A. Auger. Log-linear convergence of the scale-invariant (μ/μ_ω,λ)-ES and optimal mu for intermediate recombination for large population sizes. Research Report RR-7275, Jun 2010.

[22]

M. Jebalia, A. Auger, and P. Liardet. Log-linear convergence and optimal bounds for the (1 + 1)-es. In Evolution Artificielle (EA '07), pages 207--218, 2008.

[23]

I. Loshchilov. A computationally efficient limited memory cma-es for large scale optimization. In Genetic and Evolutionary Computation Conference, GECCO, pages 397--404, 2014.

Digital Library

[24]

I. Rechenberg. Evolutionsstrategie '94. Frommann-Holzboog, Stuttgart-Bad Cannstatt, 1994.

[25]

R. Ros and N. Hansen. A simple modification in cma-es achieving linear time and space complexity. In Parallel Problem Solving from Nature - PPSN X, pages 296--305, 2008.

Digital Library

[26]

O. Teytaud and S. Gelly. General lower bounds for evolutionary algorithms. In Parallel Problem Solving from Nature - PPSN IX, pages 21--31, 2006.

Digital Library

Cited By

Chen YHe J(2021)Average convergence rate of evolutionary algorithms in continuous optimizationInformation Sciences10.1016/j.ins.2020.12.076562(200-219)Online publication date: Jul-2021
https://doi.org/10.1016/j.ins.2020.12.076
Chen YHe J(2020)Average Convergence Rate of Evolutionary Algorithms II: Continuous OptimisationArtificial Intelligence Algorithms and Applications10.1007/978-981-15-5577-0_3(31-45)Online publication date: 26-May-2020
https://doi.org/10.1007/978-981-15-5577-0_3
Au CLeung HTakadama K(2018)Analysis of evolution strategies with the optimal weighted recombinationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205632(809-816)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205632
Show More Cited By

Index Terms

Quality Gain Analysis of the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Bio-inspired optimization
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Mirrored sampling in evolution strategies with weighted recombination
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

This paper introduces mirrored sampling into evolution strategies (ESs) with weighted multi-recombination. Two further heuristics are introduced: pairwise selection selects at most one of two mirrored vectors in order to avoid a bias due to ...
Analysis of evolution strategies with the optimal weighted recombination
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

This paper studies the performance for evolution strategies with the optimal weighed recombination on spherical problems in finite dimensions. We first discuss the different forms of functions that are used to derive the optimal recombination weights and ...
Empirical investigation of multiparent recombination operators in evolution strategies

An extension of evolution strategies to multiparent recombination involving a variable number ρ of parents to create an offspring individual is proposed. The extension is experimentally evaluated on a test suite of functions differing in their modality ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '17: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

January 2017

170 pages

ISBN:9781450346511

DOI:10.1145/3040718

Program Chairs:
Christian Igel
University of Copenhagen, Denmark
,
Dirk Sudholt
University of Sheffield, United Kingdom
,
Carsten Witt
Technical University of Denmark, Denmark

Copyright © 2017 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: 12 January 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Japan Society for the Promotion of Science

Conference

FOGA '17

Sponsor:

SIGEVO

FOGA '17: Foundations of Genetic Algorithms XIV

January 12 - 15, 2017

Copenhagen, Denmark

Acceptance Rates

FOGA '17 Paper Acceptance Rate 13 of 23 submissions, 57%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
109
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen YHe J(2021)Average convergence rate of evolutionary algorithms in continuous optimizationInformation Sciences10.1016/j.ins.2020.12.076562(200-219)Online publication date: Jul-2021
https://doi.org/10.1016/j.ins.2020.12.076
Chen YHe J(2020)Average Convergence Rate of Evolutionary Algorithms II: Continuous OptimisationArtificial Intelligence Algorithms and Applications10.1007/978-981-15-5577-0_3(31-45)Online publication date: 26-May-2020
https://doi.org/10.1007/978-981-15-5577-0_3
Au CLeung HTakadama K(2018)Analysis of evolution strategies with the optimal weighted recombinationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205632(809-816)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205632
Uchida KShirakawa SAkimoto YTakadama K(2018)Analysis of information geometric optimization with isotropic gaussian distribution under finite samplesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205487(897-904)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205487
Nishida KAkimoto YTakadama K(2018)PSA-CMA-ESProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205467(865-872)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205467
Miyazawa HAkimoto YBosman P(2017)Effect of the mean vector learning rate in CMA-ESProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071203(721-728)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071203
Yamaguchi TAkimoto Y(2017)Benchmarking the novel CMA-ES restart strategy using the search history on the BBOB noiseless testbedProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3084203(1780-1787)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3084203

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