research-article

Level-Based Analysis of Genetic Algorithms and Other Search Processes

Authors:

Duc-Cuong Dang,

Anton V. Eremeev,

Per Kristian LehreAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 22, Issue 5

Pages 707 - 719

https://doi.org/10.1109/TEVC.2017.2753538

Published: 01 October 2018 Publication History

Abstract

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the <italic>level-based theorem</italic>, a new technique tailored to population-based processes. It applies to any nonelitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

References

[1]

G. Ausiello and M. Protasi, “Local search, reducibility and approximability of $\text{NP}$ -optimization problems,” Inf. Process. Lett., vol. 54, no. 2, pp. 73–79, 1995.

Digital Library

[2]

G. Badkobeh, P. K. Lehre, and D. Sudholt, “Unbiased black-box complexity of parallel search,” in Proc. PPSN XIII, Ljubljana, Slovenia, 2014, pp. 892–901.

[3]

H.-G. Beyer, H.-P. Schwefel, and I. Wegener, “How to analyse evolutionary algorithms,” Theor. Comput. Sci., vol. 287, no. 1, pp. 101–130, 2002.

Digital Library

[4]

T. Chen, J. He, G. Sun, G. Chen, and X. Yao, “A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 39, no. 5, pp. 1092–1106, Oct. 2009.

Digital Library

[5]

T. Chen, P. K. Lehre, K. Tang, and X. Yao, “When is an estimation of distribution algorithm better than an evolutionary algorithm?” in Proc. CEC, Trondheim, Norway, 2009, pp. 1470–1477.

[6]

T. Chen, K. Tang, G. Chen, and X. Yao, “On the analysis of average time complexity of estimation of distribution algorithms,” in Proc. CEC, Singapore, 2007, pp. 453–460.

[7]

T. Chen, K. Tang, G. Chen, and X. Yao, “Rigorous time complexity analysis of univariate marginal distribution algorithm with margins,” in Proc. CEC, Trondheim, Norway, 2009, pp. 2157–2164.

[8]

T. Chen, K. Tang, G. Chen, and X. Yao, “Analysis of computational time of simple estimation of distribution algorithms,” IEEE Trans. Evol. Comput., vol. 14, no. 1, pp. 1–22, Feb. 2010.

Digital Library

[9]

D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre, “Level-based analysis of genetic algorithms and other search processes,” in Proc. PPSN XIII, Ljubljana, Slovenia, 2014, pp. 912–921.

[10]

D.-C. Danget al., “Emergence of diversity and its benefits for crossover in genetic algorithms,” in Proc. PPSN XIV, Edinburgh, U.K., 2016, pp. 890–900.

[11]

D.-C. Dang, T. Jansen, and P. K. Lehre, “Populations can be essential in tracking dynamic optima,” Algorithmica, vol. 78, no. 2, pp. 660–680, 2017.

Digital Library

[12]

D.-C. Dang and P. K. Lehre, “Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms,” in Proc. FOGA XIII, Aberystwyth, U.K., 2015, pp. 62–68.

[13]

D.-C. Dang and P. K. Lehre, “Simplified runtime analysis of estimation of distribution algorithms,” in Proc. GECCO, Madrid, Spain, 2015, pp. 513–518.

[14]

D.-C. Dang and P. K. Lehre, “Runtime analysis of non-elitist populations: From classical optimisation to partial information,” Algorithmica, vol. 75, no. 3, pp. 428–461, 2016.

Digital Library

[15]

D.-C. Dang and P. K. Lehre, “Self-adaptation of mutation rates in non-elitist populations,” in Proc. PPSN XIV, Edinburgh, U.K., 2016, pp. 803–813.

[16]

B. Doerr and C. Doerr, “Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings,” in Proc. GECCO, Madrid, Spain, 2015, pp. 1335–1342.

[17]

B. Doerr and C. Doerr, “A tight runtime analysis of the (1+( $\lambda$, $\lambda$ )) genetic algorithm on OneMax,” in Proc. GECCO, Madrid, Spain, 2015, pp. 1423–1430.

[18]

B. Doerr and M. Künnemann, “How the (1+ $\lambda$ ) evolutionary algorithm optimizes linear functions,” in Proc. GECCO, Amsterdam, The Netherlands, 2013, pp. 1589–1596.

[19]

S. Droste, “A rigorous analysis of the compact genetic algorithm for linear functions,” Nat. Comput., vol. 5, no. 3, pp. 257–283, 2006.

Digital Library

[20]

S. Droste, T. Jansen, and I. Wegener, “On the analysis of the (1+1) evolutionary algorithm,” Theor. Comput. Sci., vol. 276, nos. 1–2, pp. 51–81, 2002.

Digital Library

[21]

S. Droste, T. Jansen, and I. Wegener, “Upper and lower bounds for randomized search heuristics in black-box optimization,” Theor. Comput. Syst., vol. 39, no. 4, pp. 525–544, 2006.

Digital Library

[22]

A. Eremeev, “Hitting times of local and global optima in genetic algorithms with very high selection pressure,” Yugoslav J. Oper. Res., vol. 27, no. 3, pp. 323–339, 2017.

[23]

A. V. Eremeev and J. V. Kovalenko, “Optimal recombination in genetic algorithms for combinatorial optimization problems—Part I,” Yugoslav J. Oper. Res., vol. 24, no. 1, pp. 1–20, 2014.

[24]

U. Feige, “On sums of independent random variables with unbounded variance, and estimating the average degree in a graph,” in Proc. 36th STOC, 2004, pp. 594–603.

[25]

T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton, “The benefit of recombination in noisy evolutionary search,” in Proc. 26th ISAAC, Nagoya, Japan, 2015, pp. 140–150.

[26]

D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Boston, MA, USA: Addison-Wesley, 1989.

Digital Library

[27]

C. González, J. A. Lozano, and P. Larrañaga, “Analyzing the PBIL algorithm by means of discrete dynamical systems,” Complex Syst., vol. 12, no. 4, pp. 465–479, 2000.

[28]

B. Hajek, “Hitting-time and occupation-time bounds implied by drift analysis with applications,” Adv. Appl. Probab., vol. 14, no. 3, pp. 502–525, 1982.

[29]

J. He and X. Yao, “Drift analysis and average time complexity of evolutionary algorithms,” Artif. Intell., vol. 127, no. 1, pp. 57–85, 2001.

Digital Library

[30]

J. He and X. Yao, “From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 6, no. 5, pp. 495–511, Oct. 2002.

Digital Library

[31]

T. Jansen and I. Wegener, “The analysis of evolutionary algorithms—A proof that crossover really can help,” Algorithmica, vol. 34, no. 1, pp. 47–66, 2002.

Digital Library

[32]

T. Kötzing, D. Sudholt, and M. Theile, “How crossover helps in pseudo-Boolean optimization,” in Proc. GECCO, 2011, pp. 989–996.

[33]

M. S. Krejca and C. Witt, “Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax,” in Proc. Found. Genet. Algorithms (FOGA), 2017, pp. 65–79.

[34]

P. Larrañaga and J. A. Lozano, Eds., Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Genetic Algorithms and Evolutionary Computation), vol. 2. New York, NY, USA: Springer, 2002.

Digital Library

[35]

J. Lässig and D. Sudholt, “General upper bounds on the runtime of parallel evolutionary algorithms,” Evol. Comput., vol. 22, no. 3, pp. 405–437, 2014.

Digital Library

[36]

P. K. Lehre, “Fitness-levels for non-elitist populations,” in Proc. GECCO, Dublin, Ireland, 2011, pp. 2075–2082.

[37]

P. K. Lehre and P. T. H. Nguyen, “Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration,” in Proc. GECCO, Berlin, Germany, 2017, pp. 1383–1390.

[38]

P. K. Lehre and C. Witt, “Black-box search by unbiased variation,” Algorithmica, vol. 64, no. 4, pp. 623–642, 2012.

Digital Library

[39]

P. K. Lehre and X. Yao, “Crossover can be constructive when computing unique input–output sequences,” Soft Comput., vol. 15, no. 9, pp. 1675–1687, 2011.

Digital Library

[40]

P. K. Lehre and X. Yao, “On the impact of mutation-selection balance on the runtime of evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 16, no. 2, pp. 225–241, Apr. 2012.

Digital Library

[41]

A. Moraglio and D. Sudholt, “Principled design and runtime analysis of abstract convex evolutionary search,” Evol. Comput., vol. 25, no. 2, pp. 205–236, 2017.

Digital Library

[42]

H. Mühlenbein and G. Paaß, “From recombination of genes to the estimation of distributions I. binary parameters,” in Proc. PPSN IV, Berlin, Germany, 1996, pp. 178–187.

[43]

H. Mühlenbein, “The equation for response to selection and its use for prediction,” Evol. Comput., vol. 5, no. 3, pp. 303–346, 1997.

Digital Library

[44]

F. Neumann, P. S. Oliveto, and C. Witt, “Theoretical analysis of fitness-proportional selection: Landscapes and efficiency,” in Proc. GECCO, Montreal, QC, Canada, 2009, pp. 835–842.

[45]

P. S. Oliveto and C. Witt, “Improved time complexity analysis of the simple genetic algorithm,” Theor. Comput. Sci., vol. 605, pp. 21–41, Nov. 2015.

Digital Library

[46]

M. Pelikan, K. Sastry, and D. E. Goldberg, “Scalability of the Bayesian optimization algorithm,” Int. J. Approx. Reason., vol. 31, no. 3, pp. 221–258, 2002.

[47]

A. Prügel-Bennett, J. E. Rowe, and J. Shapiro, “Run-time analysis of population-based evolutionary algorithm in noisy environments,” in Proc. FOGA XIII, Aberystwyth, U.K., 2015, pp. 69–75.

[48]

J. E. Rowe and D. Sudholt, “The choice of the offspring population size in the (1, $\lambda$ ) evolutionary algorithm,” Theor. Comput. Sci., vol. 545, pp. 20–38, Aug. 2014.

Digital Library

[49]

J. Scharnow, K. Tinnefeld, and I. Wegener, “The analysis of evolutionary algorithms on sorting and shortest paths problems,” J. Math. Model. Algorithms, vol. 3, no. 4, pp. 349–366, 2004.

[50]

J. L. Shapiro, “Drift and scaling in estimation of distribution algorithms,” Evol. Comput., vol. 13, no. 1, pp. 99–123, 2005.

Digital Library

[51]

D. Sudholt, “How crossover speeds up building block assembly in genetic algorithms,” Evol. Comput., vol. 25, no. 2, pp. 237–274, 2017.

Digital Library

[52]

D. Sudholt and C. Witt, “Update strength in EDAs and ACO: How to avoid genetic drift,” in Proc. GECCO, Denver, CO, USA, 2016, pp. 61–68.

[53]

M. D. Vose, The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA, USA: MIT Press, 1999.

Digital Library

[54]

M. D. Vose and A. H. Wright, “Stability of vertex fixed points and applications,” in Proc. FOGA III, Estes Park, CO, USA, 1995, pp. 103–113.

[55]

D. Williams, Probability With Martingales. Cambridge, U.K.: Cambridge Univ. Press, 1991.

[56]

C. Witt, “Runtime analysis of the ( $\mu$ +1) EA on simple pseudo-Boolean functions,” Evol. Comput., vol. 14, no. 1, pp. 65–86, 2006.

Digital Library

[57]

C. Witt, “Upper bounds on the runtime of the univariate marginal distribution algorithm on OneMax,” in Proc. GECCO, Berlin, Germany, 2017, pp. 1415–1422.

[58]

Y. Yu, C. Qian, and Z.-H. Zhou, “Switch analysis for running time analysis of evolutionary algorithms,” IEEE Trans. Evol. Comput., vol. 19, no. 6, pp. 777–792, Dec. 2015.

Digital Library

[59]

Q. Zhang and H. Mühlenbein, “On the convergence of a class of estimation of distribution algorithms,” IEEE Trans. Evol. Comput., vol. 8, no. 2, pp. 127–136, Apr. 2004.

Digital Library

Cited By

Lehre PLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648428(903-927)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648428
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Dang DLehre PLi XHandl J(2024)The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654221(1551-1559)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654221
Show More Cited By

Index Terms

Level-Based Analysis of Genetic Algorithms and Other Search Processes

Index terms have been assigned to the content through auto-classification.

Recommendations

Self-Adaptive Genetic Algorithms with Simulated Binary Crossover

Self-adaptation is an essential feature of natural evolution. However, in the context of function optimization, self-adaptation features of evolutionary search algorithms have been explored mainly with evolution strategy (ES) and evolutionary ...
Probabilistic model-building genetic algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Probabilistic model-building algorithms (PMBGAs) replace traditional variation of genetic and evolutionary algorithms by (1) building a probabilistic model of promising solutions and (2) sampling the built model to generate new candidate solutions. ...
Analysis on the Island Model Parallel Genetic Algorithms for the Genetic Drifts
SEAL'98: Selected papers from the Second Asia-Pacific Conference on Simulated Evolution and Learning on Simulated Evolution and Learning

In our former paper, we have investigated the relation among the mean convergence time, the population size, and the chromosome length of genetic algorithms (GAs). Our analyses of GAs make use of the Markov chain formalism based on the Wright-Fisher ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 22, Issue 5

Oct. 2018

181 pages

ISSN:1089-778X

Issue’s Table of Contents

1089-778X © 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 October 2018

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lehre PLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648428(903-927)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648428
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Dang DLehre PLi XHandl J(2024)The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654221(1551-1559)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654221
Dang DOpris ASudholt DLi XHandl J(2024)Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654177(484-492)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654177
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01232-5
Lehre P(2024)Runtime Analysis of Competitive Co-evolutionary Algorithms for Maximin Optimisation of a Bilinear FunctionAlgorithmica10.1007/s00453-024-01218-386:7(2352-2392)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-024-01218-3
Doerr BGhannane YIbn Brahim M(2024)Runtime Analysis for Permutation-based Evolutionary AlgorithmsAlgorithmica10.1007/s00453-023-01146-886:1(90-129)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00453-023-01146-8
Lehre PQin X(2024)More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain EnvironmentsAlgorithmica10.1007/s00453-022-01044-586:2(396-441)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00453-022-01044-5
Doerr BKötzing T(2024)Lower Bounds from Fitness Levels Made EasyAlgorithmica10.1007/s00453-022-00952-w86:2(367-395)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00453-022-00952-w
Dang DOpris ASudholt D(2024)Level-Based Theorems for Runtime Analysis of Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_16(246-263)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_16
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents