Article

Local and global order 3/2 convergence of a surrogate evolutionary algorithm

Authors:

Marc Schoenauer,

Olivier TeytaudAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 857 - 864

https://doi.org/10.1145/1068009.1068154

Published: 25 June 2005 Publication History

Abstract

A Quasi-Monte-Carlo method based on the computation of a surrogate model of the fitness function is proposed, and its convergence at super-linear rate 3/2 is proved under rather mild assumptions on the fitness function -- but assuming that the starting point lies within a small neighborhood of a global maximum. A memetic algorithm is then constructed, that performs both a random exploration of the search space and the exploitation of the best-so-far points using the previous surrogate local algorithm, coupled through selection. Under the same mild hypotheses, the global convergence of the memetic algorithm, at the same 3/2 rate, is proved.

References

[1]

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

Digital Library

[2]

H.-G. Beyer. The Theory of Evolutions Strategies. Springer, Heidelberg, 2001.

Digital Library

[3]

R. Cerf. An asymptotic theory of genetic algorithms. In J.-M. Alliot, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, editors, Artificial Evolution, volume 1063 of LNCS, pages 37--53. Springer Verlag, 1996.

Digital Library

[4]

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

Digital Library

[5]

K. Fang and Y. Wang. Number-Theoretic Methods in Statistics. London: Chapman and Hall, 1994.

[6]

O. François. An evolutionary strategy for global minimization and its markov chain analysis. IEEE Transactions on Evolutionary Computation, 2(3):77--91, 1999.

Digital Library

[7]

B. Freisleben and P. Merz. New genetic local search operators for the TSP. In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, PPSN96, LNCS 1141, pages 890--899. Springer Verlag, 1996.

Digital Library

[8]

J. Garnier, L. Kallel, and M. Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7(2):167--203, 1999.

Digital Library

[9]

W. H. Hart. A Convergence Analysis of Unconstrained and Bound Constrained Evolutionary Pattern Search. Evolutionary Computation Journal, 9(1):1--23, 2001.

Digital Library

[10]

M. Lozano, F. Herrera, N. Krasgonor, and D. Molina. Real-coded memetic algorithms with crossover hill-climbing. Evolutionary Computation Journal, 2004.

Digital Library

[11]

P. Merz and B. Freisleben. A genetic local search approach for the QAP. In T. Bäck, editor, Proceedings of the 7th International Conference on Genetic Algorithms, pages 465--470. Morgan Kaufmann, 1997.

[12]

P. Moscato. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Technical Report Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, California, USA, 1989.

[13]

H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia: SIAM, 1992.

Digital Library

[14]

J. Poland. Explicit local models: Towards "optimal" optimization algorithms. Technical Report 09-04, IDSIA / USI-SUPSI, 2004.

Digital Library

[15]

I. Rechenberg. Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Holzboog Verlag, Stuttgart, 1973.

[16]

G. Rudolph. Convergence analysis of canonical genetic algorithm. IEEE Transactions on Neural Networks, 5(1):96--101, 1994.

Digital Library

[17]

G. Rudolph. Convergence of non-elitist strategies. In Z. Michalewicz, J. D. Schaffer, H.-P. Schwefel, D. B. Fogel, and H. Kitano, editors, Proceedings of the First IEEE International Conference on Evolutionary Computation, pages 63--66. IEEE Press, 1994.

[18]

G. Rudolph. How mutation and selection solve long path problems in polynomial expected time. Evolutionary Computation, 4(2):195--205, Summer 1996.

Digital Library

[19]

G. Rudolph. Convergence rates of evolutionary algorithms for a class of convex objective functions. Control and Cybernetics, 26(3):375--390, 1997.

[20]

M. Schoenauer, editor. Special Issue on Memetic Algorithms. MIT press, 2004.

[21]

H.-P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, New-York, 1981. 1995 -- 2nd edition.

Digital Library

Cited By

Raponi ERakotonirina NRapin JDoerr CTeytaud O(2025)Optimizing With Low Budgets: A Comparison on the Black-Box Optimization Benchmarking Suite and OpenAI GymIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.334678829:1(91-101)Online publication date: Feb-2025
https://doi.org/10.1109/TEVC.2023.3346788
Bettinger ABrun ABoyer AWagner M(2022)Independent influence of exploration and exploitation for metaheuristic-based recommendationsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3528972(475-478)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3528972
Meunier LRakotoarison HWong PRoziere BRapin JTeytaud OMoreau ADoerr C(2022)Black-Box Optimization Revisited: Improving Algorithm Selection Wizards Through Massive BenchmarkingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.310818526:3(490-500)Online publication date: Jun-2022
https://doi.org/10.1109/TEVC.2021.3108185
Show More Cited By

Index Terms

Local and global order 3/2 convergence of a surrogate evolutionary algorithm
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

Combining Global and Local Surrogate Models to Accelerate Evolutionary Optimization

In this paper, we present a novel surrogate-assisted evolutionary optimization framework for solving computationally expensive problems. The proposed framework uses computationally cheap hierarchical surrogate models constructed through online learning ...
A novel sexual adaptive genetic algorithm based on two-step evolutionary scenario of baldwin effect and analysis of global convergence
GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation

This work presents a novel sexual adaptive genetic algorithm (NSAGA) based on two-step evolutionary scenario of Baldwin effect to overcome the shortcomings of traditional genetic algorithms, such as premature convergence, stochastic roaming, and poor ...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

Copyright © 2005 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
187
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Raponi ERakotonirina NRapin JDoerr CTeytaud O(2025)Optimizing With Low Budgets: A Comparison on the Black-Box Optimization Benchmarking Suite and OpenAI GymIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.334678829:1(91-101)Online publication date: Feb-2025
https://doi.org/10.1109/TEVC.2023.3346788
Bettinger ABrun ABoyer AWagner M(2022)Independent influence of exploration and exploitation for metaheuristic-based recommendationsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3528972(475-478)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3528972
Meunier LRakotoarison HWong PRoziere BRapin JTeytaud OMoreau ADoerr C(2022)Black-Box Optimization Revisited: Improving Algorithm Selection Wizards Through Massive BenchmarkingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.310818526:3(490-500)Online publication date: Jun-2022
https://doi.org/10.1109/TEVC.2021.3108185
Videau MLeite ATeytaud OSchoenauer M(2022)Multi-objective Genetic Programming for Explainable Reinforcement LearningGenetic Programming10.1007/978-3-031-02056-8_18(278-293)Online publication date: 13-Apr-2022
https://doi.org/10.1007/978-3-031-02056-8_18
Cauwet MTeytaud OCoello Coello C(2020)Population control meets doob's martingale theoremsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389957(321-322)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389957
Adam SAlexandropoulos SPardalos PVrahatis M(2019)No Free Lunch Theorem: A ReviewPädiatrie10.1007/978-3-030-12767-1_5(57-82)Online publication date: 11-May-2019
https://doi.org/10.1007/978-3-030-12767-1_5
Auger ATeytaud O(2018)Continuous Lunches Are Free Plus the Design of Optimal Optimization AlgorithmsAlgorithmica10.5555/3118215.311827357:1(121-146)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.5555/3118215.3118273
Chen JXin BPeng ZDou LZhang J(2018)Optimal contraction theorem for exploration-exploitation tradeoff in search and optimizationIEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans10.1109/TSMCA.2009.201243639:3(680-691)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1109/TSMCA.2009.2012436
Fournier HTeytaud O(2018)Lower Bounds for Comparison Based Evolution Strategies Using VC-dimension and Sign PatternsAlgorithmica10.1007/s00453-010-9391-359:3(387-408)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s00453-010-9391-3
Astete-Morales SCauwet MTeytaud OHe JJansen TOchoa GZarges C(2015)Evolution Strategies with Additive NoiseProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725500(76-84)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725500
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