research-article

Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys

Authors:

Duc-Cuong Dang,

Per Kristian LehreAuthors Info & Claims

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

Pages 1133 - 1141

https://doi.org/10.1145/3449639.3459398

Published: 26 June 2021 Publication History

Abstract

It is largely unknown how the runtime of evolutionary algorithms depends on fitness landscape characteristics for broad classes of problems. Runtime guarantees for complex and multi-modal problems where EAs are typically applied are rarely available.

We present a parameterised problem class SparseLocalOpt_α,ε where the class with parameters α, ϵ ∈ [0, 1] contains all fitness landscapes with deceptive regions of sparsity ε and fitness valleys of density α. We study how the runtime of EAs depends on these fitness landscape parameters.

We find that for any constant density and sparsity α, ε ∈ (0, 1), SparseLocalOpt_α,ε has exponential elitist (μ + λ) black-box complexity, implying that a wide range of elitist EAs fail even for mildly deceptive and multi-modal landscapes. In contrast, we derive a set of sufficient conditions for non-elitist EAs to optimise any problem in SparseLocalOpt_α,ε in expected polynomial time for broad values of α and ε. These conditions can be satisfied for tournament selection and linear ranking selection, but not for (μ, λ)-selection.

Supplementary Material

PDF File (p1133-dang.pdf)

p1133-dang.pdf

Download
631.61 KB

References

[1]

Christof K. Biebricher and Manfred Eigen. 2005. The error threshold. Virus Research 107, 2 (2005), 117--127.

[2]

Brendan Case and Per Kristian Lehre. 2020. Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete Problems with Unknown Structure. IEEE Transactions on Evolutionary Computation 24, 4 (2020), 650--663.

[3]

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2018. Level-Based Analysis of Genetic Algorithms and Other Search Processes. IEEE Trans. Evolutionary Computation 22, 5 (2018), 707--719.

Digital Library

[4]

Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre. 2021. Escaping Local Optima with Non-Elitist Evolutionary Algorithms. In Proceedings of AAAI'2021. http://34.94.61.102/paper_AAAI-6811.html

[5]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro Simone Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Escaping Local Optima with Diversity Mechanisms and Crossover. In Proceedings of the 2016 Genetic and Evolutionary Computation Conference (GECCO 2016). ACM, 645--652.

Digital Library

[6]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro Simone Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping Local Optima Using Crossover With Emergent Diversity. IEEE Trans. Evolutionary Computation 22, 3 (2018), 484--497.

[7]

Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre. 2017. Populations Can Be Essential in Tracking Dynamic Optima. Algorithmica 78, 2 (2017), 660--680.

Digital Library

[8]

Duc-Cuong Dang and Per Kristian Lehre. 2015. Efficient Optimisation of Noisy Fitness Functions with Population-Based Evolutionary Algorithms. In Proceedings of the 2015 Conference on Foundations of Genetic Algorithms (FOGA'2015). ACM, 62--68.

Digital Library

[9]

Duc-Cuong Dang and Per Kristian Lehre. 2016. Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information. Algorithmica 75 (2016), 428--461.

Digital Library

[10]

Duc-Cuong Dang and Per Kristian Lehre. 2016. Self-adaptation of Mutation Rates in Non-elitist Populations. In Proceedings of the 2016 Conference on Parallel Problem Solving from Nature (PPSN 2016). Springer, Cham, 803--813.

[11]

Benjamin Doerr. 2020. Does comma selection help to cope with local optima?. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO 2020). ACM, New York, NY, USA, 1304--1313.

Digital Library

[12]

Carola Doerr and Johannes Lengler. 2016. Introducing Elitist Black-Box Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms? Evolutionary Computation 25, 4 (Oct. 2016), 587--606. Publisher: MIT Press.

Digital Library

[13]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 1998. On the Optimization of Unimodal Functions with the (1 + 1) Evolutionary Algorithm. In Proceedings of the 1998 Conference on Parallel Problem Solving from Nature (PPSN'1996). Springer-Verlag, Berlin, Heidelberg, 13--22.

[14]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2006. Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization. Theory of Computing Systems 39, 4 (July 2006), 525--544.

Digital Library

[15]

Devdatt Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, NY, USA.

Digital Library

[16]

David E. Goldberg and Kalyanmoy Deb. 1991. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms. Morgan Kaufmann, 69--93.

[17]

Bruce Hajek. 1988. Cooling Schedules for Optimal Annealing. Math. Oper. Res. 13, 2 (1988), 311--329.

[18]

Jun He and Xin Yao. 2001. Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 1 (2001), 57--85.

Digital Library

[19]

Sebastian Herrmann. 2016. Determining the Difficulty of Landscapes by PageRank Centrality in Local Optima Networks. In Evolutionary Computation in Combinatorial Optimization, Francisco Chicano, Bin Hu, and Pablo García-Sánchez (Eds.). Springer International Publishing, Cham, 74--87.

[20]

Jeffrey Horn, David E. Goldberg, and Kalyanmoy Deb. 1994. Long Path Problems. In Proceedings of the 1994 Conference on Parallel Problem Solving from Nature (PPSN'1994) (PPSN III). Springer, Berlin, Heidelberg, 149--158.

[21]

Jens Jägerskupper and Tobias Storch. 2007. When the Plus Strategy Outperforms the Comma Strategy and When Not. In 2007 IEEE Symposium on Foundations of Computational Intelligence. 25--32.

[22]

Per Kristian Lehre. 2010. Negative Drift in Populations. In Proceedings of the 2010 Conference on Parallel Problem Solving from Nature (PPSN'2010). Springer, Berlin, Heidelberg, 244--253.

[23]

Per Kristian Lehre. 2011. Fitness-Levels for Non-Elitist Populations. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference (GECCO 2011). ACM, 2075--2082.

Digital Library

[24]

Per Kristian Lehre and Xin Yao. 2012. On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 16, 2 (April 2012), 225--241.

Digital Library

[25]

Pietro Simone Oliveto, Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2018. How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism. Algorithmica 80, 5 (2018), 1604--1633.

Digital Library

[26]

Pietro Simone Oliveto, Dirk Sudholt, and Christine Zarges. 2019. On the benefits and risks of using fitness sharing for multimodal optimisation. Theor. Comput. Sci. 773 (2019), 53--70.

Digital Library

[27]

Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2017. Towards a Runtime Comparison of Natural and Artificial Evolution. Algorithmica 78, 2 (2017), 681--713.

Digital Library

[28]

C. R. Reeves and A. V. Eremeev. 2004. Statistical Analysis of Local Search Landscapes. The Journal of the Operational Research Society 55, 7 (2004), 687--693. http://www.jstor.org/stable/4102015

[29]

Günter Rudolph. 1996. How Mutation and Selection Solve Long-Path Problems in Polynomial Expected Time. Evol. Comput. 4, 2 (1996), 195--205.

Digital Library

[30]

Peter F. Stadler. 2002. Fitness landscapes. In Biological Evolution and Statistical Physics, Michael Lässig and Angelo Valleriani (Eds.). Springer, Berlin, Heidelberg, 183--204.

[31]

Dirk Sudholt. 2011. Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima. Algorithmica 59, 3 (2011), 343--368.

Digital Library

[32]

Sarah L. Thomson, Fabio Daolio, and Gabriela Ochoa. 2017. Comparing Communities of Optima with Funnels in Combinatorial Fitness Landscapes. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). Association for Computing Machinery, New York, NY, USA, 377--384.

Digital Library

[33]

Ingo Wegener. 2005. Simulated Annealing Beats Metropolis in Combinatorial Optimization. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'2005), Vol. 3580. Springer, Berlin, Heidelberg, 589--601.

Digital Library

[34]

Claus O. Wilke. 2005. Quasispecies theory in the context of population genetics. BMC Evolutionary Biology 5, 1 (2005), 44.

[35]

David Williams. 1991. Probability with Martingales. Cambridge University Press.

[36]

Sewall Wright. 1932. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In Proceedings of the sixth international congress on genetics, Vol. 1. 356--366.

[37]

Andrew C. Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). 222--227. ISSN: 0272-5428.

Digital Library

[38]

Christine Zarges. 2011. Theoretical Foundations of Artificial Immune Systems. Ph.D. Dissertation. Universität Dortmund.

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
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
Lengler JSchiller LSieberling OLi XHandl J(2024)Plus Strategies are Exponentially Slower for Planted Optima of Random HeightProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654088(1587-1595)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654088
Show More Cited By

Index Terms

Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

Fast non-elitist evolutionary algorithms with power-law ranking selection
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and ...
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,...
When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length l, influence the runtime of different strategies for crossing these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 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: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EPSRC
Russian Science Foundation

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
169
Total Downloads

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

Reflects downloads up to 18 Nov 2024

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
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
Lengler JSchiller LSieberling OLi XHandl J(2024)Plus Strategies are Exponentially Slower for Planted Optima of Random HeightProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654088(1587-1595)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654088
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://doi.org/10.1007/s00453-024-01218-3
Dang DOpris ASudholt D(2024)On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them EfficientlyParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_15(230-245)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_15
Lengler JSturm K(2024)Self-adjusting Evolutionary Algorithms are Slow on a Class of Multimodal LandscapesParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_1(3-18)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_1
Dang DEremeev AQin X(2024)Empirical Evaluation of Evolutionary Algorithms with Power-Law Ranking SelectionIntelligent Information Processing XII10.1007/978-3-031-57808-3_16(217-232)Online publication date: 6-Apr-2024
https://doi.org/10.1007/978-3-031-57808-3_16
Lehre PQin X(2023)Self-adaptation Can Improve the Noise-tolerance of Evolutionary AlgorithmsProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607128(105-116)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607128
Lehre POliveto PSilva SPaquete L(2023)Runtime Analysis of Population-based Evolutionary Algorithms - Part I: Steady State EAsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595056(1271-1300)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595056
Lehre PQin XSilva SPaquete L(2023)Self-adaptation Can Help Evolutionary Algorithms Track Dynamic OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590494(1619-1627)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590494
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.

Media

Figures

Other

Tables

View Table of Contents