More Web Proxy on the site http://driver.im/

research-article

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus

Authors:

Benjamin Doerr,

Andrew James KelleyAuthors Info & Claims

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1555 - 1564

https://doi.org/10.1145/3583131.3590393

Published: 12 July 2023 Publication History

Abstract

We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the (1 + 1) evolutionary algorithm on the Needle problem due to Garnier, Kallel, and Schoenauer (1999).

We also use this method to analyze the runtime of the (1 + 1) evolutionary algorithm on a benchmark consisting of n/ℓ plateaus of effective size 2^ℓ - 1 which have to be optimized sequentially in a LeadingOnes fashion.

Using our new method, we determine the precise expected runtime both for static and fitness-dependent mutation rates. We also determine the asymptotically optimal static and fitness-dependent mutation rates. For ℓ = o(n), the optimal static mutation rate is approximately 1.59/n. The optimal fitness dependent mutation rate, when the first k fitness-relevant bits have been found, is asymptotically 1/(k + 1). These results, so far only proven for the single-instance problem LeadingOnes, thus hold for a much broader class of problems. We expect similar extensions to be true for other important results on LeadingOnes. We are also optimistic that our Fourier analysis approach can be applied to other plateau problems as well.

References

[1]

Denis Antipov and Benjamin Doerr. 2021. Precise runtime analysis for plateau functions. ACM Transactions on Evolutionary Learning and Optimization 1 (2021), 13:1--13:28.

Digital Library

[2]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.

[3]

Henry Bambury, Antoine Bultel, and Benjamin Doerr. 2021. Generalized jump functions. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 1124--1132.

Digital Library

[4]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In Parallel Problem Solving from Nature, PPSN 2010. Springer, 1--10.

Digital Library

[5]

Dimo Brockhoff, Tobias Friedrich, Nils Hebbinghaus, Christian Klein, Frank Neumann, and Eckart Zitzler. 2007. Do additional objectives make a problem harder?. In Genetic and Evolutionary Computation Conference, GECCO 2007. ACM, 765--772.

Digital Library

[6]

Francisco Chicano, Andrew M. Sutton, L. Darrell Whitley, and Enrique Alba. 2015. Fitness probability distribution of bit-flip mutation. Evolutionary computation 23 (2015), 217--248.

[7]

Benjamin Doerr. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 1--87. Also available at https://arxiv.org/abs/1801.06733.

[8]

Benjamin Doerr. 2021. Exponential upper bounds for the runtime of randomized search heuristics. Theoretical Computer Science 851 (2021), 24--38.

[9]

Benjamin Doerr. 2021. The runtime of the compact genetic algorithm on Jump functions. Algorithmica 83 (2021), 3059--3107.

Digital Library

[10]

Benjamin Doerr, Carola Doerr, and Johannes Lengler. 2021. Self-adjusting mutation rates with provably optimal success rules. Algorithmica 83 (2021), 3108--3147.

Digital Library

[11]

Benjamin Doerr and Leslie A. Goldberg. 2013. Adaptive drift analysis. Algorithmica 65 (2013), 224--250.

Digital Library

[12]

Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425 (2012), 17--33.

Digital Library

[13]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012. Multiplicative drift analysis. Algorithmica 64 (2012), 673--697.

Digital Library

[14]

Benjamin Doerr and Andrew James Kelley. 2023. Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus. CoRR abs/2302.08021 (2023). arXiv:2302.08021

[15]

Benjamin Doerr and Timo Kötzing. 2021. Lower bounds from fitness levels made easy. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 1142--1150.

Digital Library

[16]

Benjamin Doerr and Timo Kötzing. 2021. Multiplicative up-drift. Algorithmica 83 (2021).

Digital Library

[17]

Benjamin Doerr and Martin S. Krejca. 2020. Significance-based estimation-of-distribution algorithms. IEEE Transactions on Evolutionary Computation 24 (2020), 1025--1034.

Digital Library

[18]

Benjamin Doerr and Marvin Künnemann. 2013. Royal road functions and the (1 + Λ) Evolutionary Algorithm: Almost no speed-up from larger offspring populations. In Congress on Evolutionary Computation, CEC 2013. IEEE, 424--431.

[19]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 777--784.

Digital Library

[20]

Benjamin Doerr, Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2018. On the runtime analysis of selection hyper-heuristics with adaptive learning periods. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 1015--1022.

Digital Library

[21]

Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization. Springer. Also available at http://www.lix.polytechnique.fr/Labo/Benjamin.Doerr/doerr_neumann_book.html.

[22]

Benjamin Doerr, Dirk Sudholt, and Carsten Witt. 2013. When do evolutionary algorithms optimize separable functions in parallel?. In Foundations of Genetic Algorithms, FOGA 2013. ACM, 48--59.

Digital Library

[23]

Benjamin Doerr and Weijie Zheng. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 12293--12301.

Digital Library

[24]

Carola Doerr and Markus Wagner. 2018. Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 943--950.

Digital Library

[25]

Carola Doerr, Furong Ye, Naama Horesh, Hao Wang, Ofer M. Shir, and Thomas Bäck. 2020. Benchmarking discrete optimization heuristics with IOHprofiler. Applied Soft Computing 88 (2020), 106027.

Digital Library

[26]

Stefan Droste. 2002. Analysis of the (1+1) EA for a dynamically changing OneMaxvariant. In Congress on Evolutionary Computation, CEC 2002. IEEE, 55--60.

[27]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276 (2002), 51--81.

Digital Library

[28]

Anton V. Eremeev. 2020. On non-elitist evolutionary algorithms optimizing fitness functions with a plateau. In Mathematical Optimization Theory and Operations Research, MOTOR 2020. Springer, 329--342.

[29]

Anton V. Eremeev and Alexander V. Spirov. 2021. Modeling SELEX for regulatory regions using Royal Road and Royal Staircase fitness functions. Biosystems 200 (2021), 104312.

[30]

Tobias Friedrich, Nils Hebbinghaus, and Frank Neumann. 2009. Comparison of simple diversity mechanisms on plateau functions. Theoretical Computer Science 410 (2009), 2455--2462.

Digital Library

[31]

Tobias Friedrich, Nils Hebbinghaus, and Frank Neumann. 2010. Plateaus can be harder in multi-objective optimization. Theoretical Computer Science 411 (2010), 854--864.

[32]

Josselin Garnier, Leila Kallel, and Marc Schoenauer. 1999. Rigorous hitting times for binary mutations. Evolutionary Computation 7 (1999), 173--203.

Digital Library

[33]

Paul Garrett. 2012. Fourier Analysis on Finite Abelian Groups. (2012). Preprint. Available at https://www-users.cse.umn.edu/~garrett/m/mfms/notes_c/fin_ab_fourier.pdf.

[34]

Oliver Giel and Ingo Wegener. 2003. Evolutionary algorithms and the maximum matching problem. In Symposium on Theoretical Aspects of Computer Science, STACS 2003. Springer, 415--426.

[35]

Jun He and Xin Yao. 2001. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127 (2001), 51--81.

Digital Library

[36]

Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (1963), 13--30.

[37]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

Digital Library

[38]

Thomas Jansen. 2015. On the black-box complexity of example functions: the real jump function. In Foundations of Genetic Algorithms, FOGA 2015. ACM, 16--24.

Digital Library

[39]

Thomas Jansen and Ingo Wegener. 2001. Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation 5 (2001), 589--599.

Digital Library

[40]

Jörg Lässig and Dirk Sudholt. 2014. General upper bounds on the runtime of parallel evolutionary algorithms. Evolutionary Computation 22 (2014), 405--437.

Digital Library

[41]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2019. On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 154-- 168.

Digital Library

[42]

Per Kristian Lehre and Carsten Witt. 2021. Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Combinatorics, Probability and Computing 30 (2021), 550--569.

[43]

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2017. On the runtime analysis of generalised selection hyper-heuristics for pseudo-Boolean optimisation. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 849--856.

Digital Library

[44]

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2020. Simple hyper-heuristics control the neighbourhood size of randomised local search optimally for LeadingOnes. Evolutionary Computation 28 (2020), 437--461.

Digital Library

[45]

Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953. Equation of state calculations by fast computing machines. The Journal of Chemical Physics 21 (1953), 1087--1092.

[46]

Melanie Mitchell, Stephanie Forrest, and John H. Holland. 1992. The royal road for genetic algorithms: fitness landscapes and GA performance. In Proc. of the First European Conference on Artificial Life. MIT Press, 245--254.

[47]

Heinz Mühlenbein. 1992. How genetic algorithms really work: mutation and hillclimbing. In Parallel Problem Solving from Nature, PPSN 1992. Elsevier, 15--26.

[48]

Frank Neumann. 2008. Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Computers & OR 35 (2008), 2750--2759.

Digital Library

[49]

Frank Neumann and Ingo Wegener. 2007. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science 378 (2007), 32--40.

Digital Library

[50]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.

Digital Library

[51]

Pietro S. Oliveto and Carsten Witt. 2011. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59 (2011), 369--386.

[52]

Jonathan E. Rowe, Michael D. Vose, and Alden H. Wright. 2004. Structural search spaces and genetic operators. Evolutionary Computation 12 (2004), 461--493.

Digital Library

[53]

Günter Rudolph. 1997. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovǎc.

[54]

Jens Scharnow, Karsten Tinnefeld, and Ingo Wegener. 2004. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms 3 (2004), 349--366.

[55]

Dirk Sudholt. 2013. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17 (2013), 418--435.

Digital Library

[56]

Andrew M. Sutton, Francisco Chicano, and L. Darrell Whitley. 2013. Fitness function distributions over generalized search neighborhoods in the q-ary hypercube. Evolutionary Computation 21 (2013), 561--590.

Digital Library

[57]

Erik van Nimwegen and James P. Crutchfield. 2001. Optimizing epochal evolutionary search: population-size dependent theory. Machine Learning 45 (2001), 77--114.

Digital Library

[58]

Michael D. Vose and Alden H. Wright. 1998. The simple genetic algorithm and the Walsh transform: Part I, theory. Evolutionary Computation 6 (1998), 253--273.

Digital Library

[59]

Shouda Wang, Weijie Zheng, and Benjamin Doerr. 2021. Choosing the right algorithm with hints from complexity theory. In International Joint Conference on Artificial Intelligence, IJCAI 2021. ijcai.org, 1697--1703.

[60]

Ingo Wegener. 2001. Theoretical aspects of evolutionary algorithms. In Automata, Languages and Programming, ICALP 2001. Springer, 64--78.

[61]

Ingo Wegener and Carsten Witt. 2005. On the optimization of monotone polynomials by simple randomized search heuristics. Combinatorics, Probability & Computing 14 (2005), 225--247.

Digital Library

[62]

Carsten Witt. 2014. Fitness levels with tail bounds for the analysis of randomized search heuristics. Information Processing Letters 114 (2014), 38--41.

Digital Library

[63]

Carsten Witt. 2023. How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoretical Computer Science 940 (2023), 18--42.

Digital Library

[64]

Christopher Zhang. 2023. Formulas for Hitting Times and Cover Times for Random Walks on Groups. CoRR abs/2302.01963 (2023). arXiv:2302.01963

Cited By

Doerr CJanett DLengler J(2024)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsAlgorithmica10.1007/s00453-024-01258-986:10(3115-3152)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00453-024-01258-9
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5

Index Terms

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
Abstract
We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. This immediately gives a concise proof of the classic estimate of the expected runtime of the $(1 + 1)$ evolutionary algorithm on ... $^{}$
Precise runtime analysis for plateau functions: (hot-off-the-press track at GECCO 2022)
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n-dimensional Plateau_k function as benchmark and analyze how different variants of the (1 + 1) EA optimize it. The ...
Precise Runtime Analysis for Plateau Functions
To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n-dimensional Plateau_k function as natural benchmark and analyze how different variants of the (1 + 1) EA optimize it. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 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 the author(s) 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 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence National de Recherche

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
36
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr CJanett DLengler J(2024)Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear FunctionsAlgorithmica10.1007/s00453-024-01258-986:10(3115-3152)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00453-024-01258-9
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5

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