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

research-article

Do additional optima speed up evolutionary algorithms?

Authors:

Dirk SudholtAuthors Info & Claims

FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Article No.: 8, Pages 1 - 11

https://doi.org/10.1145/3450218.3477309

Published: 06 September 2021 Publication History

Abstract

Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT ∪ S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT.

We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,λ) EA on One-Max. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.

References

[1]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics - Foundations and Recent Developments. Number 1 in Series on Theoretical Computer Science. World Scientific.

[2]

Henry Bambury, Antoine Bultel, and Benjamin Doerr. 2021. Generalized Jump Functions. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21). ACM, 1124--1132.

Digital Library

[3]

Maxim Buzdalov, Benjamin Doerr, Carola Doerr, and Dmitry Vinokurov. 2020. Fixed-Target Runtime Analysis. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'20). ACM, 1295--1303.

Digital Library

[4]

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.

[5]

Benjamin Doerr, Wanru Gao, and Frank Neumann. 2016. Runtime Analysis of Evolutionary Diversity Maximization for OneMinMax. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO '16). ACM, 557--564.

Digital Library

[6]

Benjamin Doerr, Thomas Jansen, Dirk Sudholt, Carola Winzen, and Christine Zarges. 2013. Mutation Rate Matters Even When Optimizing Monotonic Functions. Evolutionary Computation 21, 1 (2013), 1--21.

Digital Library

[7]

Benjamin Doerr, Thomas Jansen, Carsten Witt, and Christine Zarges. 2013. A Method to Derive Fixed Budget Results from Expected Optimisation Times. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '13). ACM, 1581--1588.

Digital Library

[8]

Benjamin Doerr and Timo Kötzing. 2021. Lower Bounds from Fitness Levels Made Easy. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21). ACM, 1142--1150.

Digital Library

[9]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast Genetic Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '17). ACM, 777--784.

Digital Library

[10]

Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Springer.

[11]

Carola Doerr. 2020. Complexity Theory for Discrete Black-Box Optimization Heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 133--212.

[12]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the Analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science 276, 1-2 (2002), 51--81.

Digital Library

[13]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. Optimization with randomized search heuristics---the (A)NFL theorem, realistic scenarios, and difficult functions. Theoretical Computer Science 287, 1 (2002), 131--144.

Digital Library

[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 (2006), 525--544.

Digital Library

[15]

Tobias Friedrich, Timo Kötzing, J.A. Gregor Lagodzinski, Frank Neumann, and Martin Schirneck. 2020. Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theoretical Computer Science 832 (2020), 3--19.

[16]

Wanru Gao and Frank Neumann. 2014. Runtime Analysis for Maximizing Population Diversity in Single-objective Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'14). 777--784.

Digital Library

[17]

Hsien-Kuei Hwang, Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai, and Wei-Mei Chen. 2018. Probabilistic Analysis of the (1+1)-Evolutionary Algorithm. Evolutionary Computation 26, 2 (2018).

[18]

Jens Jägersküpper and Tobias Storch. 2007. When the Plus Strategy Outperforms the Comma Strategy and When Not. In Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (FOCI '07). IEEE, 25--32.

[19]

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

Digital Library

[20]

Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. 2005. On the Choice of the Offspring Population Size in Evolutionary Algorithms. Evolutionary Computation 13, 4 (2005), 413--440.

Digital Library

[21]

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, 6 (2001), 589--599.

Digital Library

[22]

Thomas Jansen and Ingo Wegener. 2005. Real royal road functions---where crossover provably is essential. Discrete Applied Mathematics 149 (2005), 111--125.

Digital Library

[23]

Daniel Johannsen. 2010. Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. Dissertation. Universität des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institut für Informatik.

[24]

Martin S. Krejca and Carsten Witt. 2020. Theory of Estimation-of-Distribution Algorithms. Springer International Publishing, 405--442.

[25]

Jörg Lässig and Dirk Sudholt. 2013. Design and Analysis of Migration in Parallel Evolutionary Algorithms. Soft Computing 17, 7 (2013), 1121--1144.

Digital Library

[26]

Per Kristian Lehre and Dirk Sudholt. 2020. Parallel Black-Box Complexity with Tail Bounds. IEEE Transactions on Evolutionary Computation 24, 6 (2020), 1010--1024.

Digital Library

[27]

Per Kristian Lehre and Carsten Witt. 2012. Black-Box Search by Unbiased Variation. Algorithmica 64, 4 (2012), 623--642.

Digital Library

[28]

Johannes Lengler. 2020. Drift Analysis. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer International Publishing, 89--131.

[29]

Johannes Lengler. 2020. A General Dichotomy of Evolutionary Algorithms on Monotone Functions. IEEE Transactions on Evolutionary Computation 24, 6 (2020), 995--1009.

Digital Library

[30]

Johannes Lengler and Angelika Steger. 2018. Drift Analysis and Evolutionary Algorithms Revisited. Combinatorics, Probability and Computing 27, 4 (2018), 643--666.

[31]

Johannes Lengler and Xun Zou. 2019. Exponential Slowdown for Larger Populations: The (μ + 1)-EA on Monotone Functions. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA'19). ACM, 87--101.

Digital Library

[32]

Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press.

Digital Library

[33]

Frank Neumann, Mojgan Pourhassan, and Carsten Witt. 2019. Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19). ACM, 1506--1514.

Digital Library

[34]

Frank Neumann, Dirk Sudholt, and Carsten Witt. 2009. Analysis of Different MMAS ACO Algorithms on Unimodal Functions and Plateaus. Swarm Intelligence 3, 1 (2009), 35--68.

[35]

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

Digital Library

[36]

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

[37]

R. J. Quick, Victor J. Rayward-Smith, and G. D. Smith. 1998. Fitness Distance Correlation and Ridge Functions. In Parallel Problem Solving from Nature (PPSN V). Springer, 77--86.

[38]

Amirhossein Rajabi and Carsten Witt. 2021. Stagnation Detection with Randomized Local Search. In Evolutionary Computation in Combinatorial Optimization (EvoCOP '21). Springer, 152--168.

[39]

Jonathan E. Rowe and Dirk Sudholt. 2014. The choice of the offspring population size in the (1,λ) evolutionary algorithm. Theoretical Computer Science 545 (2014), 20--38.

Digital Library

[40]

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

Digital Library

[41]

Dirk Sudholt. 2009. The Impact of Parametrization in Memetic Evolutionary Algorithms. Theoretical Computer Science 410, 26 (2009), 2511--2528.

Digital Library

[42]

Dirk Sudholt. 2013. A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation 17, 3 (2013), 418--435.

Digital Library

[43]

Dirk Sudholt and Carsten Witt. 2010. Runtime Analysis of a Binary Particle Swarm Optimizer. Theoretical Computer Science 411, 21 (2010), 2084--2100.

Digital Library

[44]

Ingo Wegener. 2002. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In Evolutionary Optimization, R. Sarker, X. Yao, and M. Mohammadian (Eds.). Kluwer, 349--369.

[45]

Carsten Witt. 2008. Population Size versus Runtime of a Simple Evolutionary Algorithm. Theoretical Computer Science 403, 1 (2008), 104--120.

Digital Library

Cited By

Jorritsma JLengler JSudholt DSilva SPaquete L(2023)Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590488(1602-1610)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590488
Bu CLiu FCao ZLi LZhang YHu XLuo W(2023)Cognitive Diagnostic Model Made More Practical by Genetic AlgorithmIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.31826927:2(447-461)Online publication date: Apr-2023
https://doi.org/10.1109/TETCI.2022.3182692
Hevia Fajardo MSudholt D(2023)Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: Why Success Rates MatterAlgorithmica10.1007/s00453-023-01153-986:2(526-565)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1007/s00453-023-01153-9

Index Terms

Do additional optima speed up evolutionary algorithms?
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
Towards a Runtime Comparison of Natural and Artificial Evolution

Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...
The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

September 2021

130 pages

ISBN:9781450383523

DOI:10.1145/3450218

General Chair:
Steffen Finck
Vorarlberg University of Applied Sciences
,
Program Chairs:
Michael Hellwig
Vorarlberg University of Applied Sciences
,
Pietro S. Oliveto
University of Sheffield

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: 06 September 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '21

Sponsor:

SIGEVO

FOGA '21: Foundations of Genetic Algorithms XVI

September 6 - 8, 2021

Virtual Event, Austria

Acceptance Rates

FOGA '21 Paper Acceptance Rate 10 of 21 submissions, 48%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
95
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jorritsma JLengler JSudholt DSilva SPaquete L(2023)Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590488(1602-1610)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590488
Bu CLiu FCao ZLi LZhang YHu XLuo W(2023)Cognitive Diagnostic Model Made More Practical by Genetic AlgorithmIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.31826927:2(447-461)Online publication date: Apr-2023
https://doi.org/10.1109/TETCI.2022.3182692
Hevia Fajardo MSudholt D(2023)Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: Why Success Rates MatterAlgorithmica10.1007/s00453-023-01153-986:2(526-565)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1007/s00453-023-01153-9

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