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

research-article

Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation

Authors:

Benjamin Doerr,

Andrew M. SuttonAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1415 - 1422

https://doi.org/10.1145/2739480.2754659

Published: 11 July 2015 Publication History

Abstract

With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942--951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time $O(n \log n)$ with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

References

[1]

Dimitris Achlioptas. Random satisfiability. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 245--270. IOS Press, 2009.

[2]

Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems. Random Structures and Algorithms, 38(3):251--268, 2011.

Digital Library

[3]

Mikhail Alekhnovich and Eli Ben-Sasson. Linear upper bounds for random walk on small density random 3-CNFs. SIAM Journal on Computing, 36(5):1248--1263, 2007.

Digital Library

[4]

Lee Altenberg. Fitness distance correlation analysis: An instructive counterexample. In Thomas Back, editor, Proceedings of the Seventh International Conference on Genetic Algorithms, pages 57--64. Morgan Kaufmann, 1997.

[5]

Anne Auger and Benjamin Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., 2011.

[6]

Eli Ben-Sasson, Yonatan Bilu, and Danny Gutfreund. Finding a randomly planted assignment in a random 3-CNF. Manuscript, 2002.

[7]

James M Crawford and Larry D Auton. Experimental results on the crossover point in satisfiability problems. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-93), pages 21--27, 1993.

Digital Library

[8]

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

Digital Library

[9]

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

Digital Library

[10]

Alan Frieze and Stephen Suen. Analysis of two simple heuristics on a random instance of k-SAT. Journal of Algorithms, 20(2):312--355, 1996.

Digital Library

[11]

Thomas Jansen. On classifications of fitness functions. In Leila Kallel, Bart Naudts, and Alex Rogers, editors, Theoretical Aspects of Evolutionary Computing, Natural Computing Series, pages 371--385. Springer Berlin Heidelberg, 2001.

Digital Library

[12]

Thomas Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013.

[13]

Terry Jones and Stephanie Forrest. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In Larry J. Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 184--192. Morgan Kaufmann, 1995.

Digital Library

[14]

Scott Kirkpatrick and Bart Selman. Critical behavior in the satisfiability of random Boolean expressions. Science, 264(5163):1297--1301, 1994.

[15]

Michael Krivelevich and Dan Vilenchik. Solving random satisfiable 3CNF formulas in expected polynomial time. In Proceedings of the Seventeenth Symposium on Discrete Algorithms (SODA'06), pages 454--463, 2006.

Digital Library

[16]

David Mitchell, Bart Selman, and Hector Levesque. Hard and easy distributions of SAT problems. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 459--465, 1992.

Digital Library

[17]

Michael Mitzenmacher. Tight thresholds for the pure literal rule. Technical Report 1997-011, Digital SRC, 1997.

[18]

Michael Molloy. Cores in random hypergraphs and Boolean formulas. Random Structures and Algorithms, 27(1):124--135, 2005.

Digital Library

[19]

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

[20]

R. J. Quick, Victor J. Rayward-Smith, and G. D. Smith. Fitness distance correlation and ridge functions. In A. E. Eiben, Thomas B\"ack, Marc Schoenauer, and Hans-Paul Schwefel, editors, Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature (PPSN V), volume 1498 of Lecture Notes in Computer Science, pages 77--86. Springer, 1998.

Digital Library

[21]

Jeanette Schmidt-Pruzan and Eli Shamir. Component structure in the evolution of random hypergraphs. Combinatorica, 5(1):81--94, 1985.

[22]

Tobias Storch. Finding large cliques in sparse semi-random graphcs by simple randomized search heuristics. Theoretical Computer Science, 386:114--131, 2007.

Digital Library

[23]

Andrew M. Sutton and Frank Neumann. Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas. In Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipic, and Jim Smith, editors, Proceedings of the Thirteenth International Conference on Parallel Problem Solving from Nature (PPSN XIII), volume 8672 of Lecture Notes in Computer Science, pages 942--951. Springer, 2014.

[24]

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

Digital Library

Cited By

Weise TWu ZLi XChen YLässig J(2023)Frequency Fitness Assignment: Optimization Without Bias for Good Solutions Can Be EfficientIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.319169827:4(980-992)Online publication date: Aug-2023
https://doi.org/10.1109/TEVC.2022.3191698
Bassin ABuzdalov MShalyto A(2022)The “One-Fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ, λ)) Genetic AlgorithmAutomatic Control and Computer Sciences10.3103/S014641162107020855:7(885-902)Online publication date: 1-Feb-2022
https://doi.org/10.3103/S0146411621070208
Xia XHuang ZPeng XChen ZXiang Y(2022)Performance analysis of evolutionary algorithm for the maximum internal spanning tree problemThe Journal of Supercomputing10.1007/s11227-022-04342-578:9(11949-11973)Online publication date: 21-Feb-2022
https://doi.org/10.1007/s11227-022-04342-5
Show More Cited By

Index Terms

Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Runtime analysis of the (1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on some optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect ...
Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas

We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union Seventh Framework Programme
Australian Research Council

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
121
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weise TWu ZLi XChen YLässig J(2023)Frequency Fitness Assignment: Optimization Without Bias for Good Solutions Can Be EfficientIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.319169827:4(980-992)Online publication date: Aug-2023
https://doi.org/10.1109/TEVC.2022.3191698
Bassin ABuzdalov MShalyto A(2022)The “One-Fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ, λ)) Genetic AlgorithmAutomatic Control and Computer Sciences10.3103/S014641162107020855:7(885-902)Online publication date: 1-Feb-2022
https://doi.org/10.3103/S0146411621070208
Xia XHuang ZPeng XChen ZXiang Y(2022)Performance analysis of evolutionary algorithm for the maximum internal spanning tree problemThe Journal of Supercomputing10.1007/s11227-022-04342-578:9(11949-11973)Online publication date: 21-Feb-2022
https://doi.org/10.1007/s11227-022-04342-5
Weise TWu ZLi XChen Y(2021)Frequency Fitness Assignment: Making Optimization Algorithms Invariant Under Bijective Transformations of the Objective Function ValueIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.303209025:2(307-319)Online publication date: Apr-2021
https://doi.org/10.1109/TEVC.2020.3032090
Bassin ABuzdalov MShalyto A(2020)The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic AlgorithmModeling and Analysis of Information Systems10.18255/1818-1015-2020-4-488-50827:4(488-508)Online publication date: 20-Dec-2020
https://doi.org/10.18255/1818-1015-2020-4-488-508
Bassin ABuzdalov M(2020)An Experimental Study of Operator Choices in the $$(1+(\lambda ,\lambda ))$$ Genetic AlgorithmMathematical Optimization Theory and Operations Research10.1007/978-3-030-58657-7_26(320-335)Online publication date: 14-Sep-2020
https://doi.org/10.1007/978-3-030-58657-7_26
Buzdalov MDoerr BBosman P(2017)Runtime analysis of the (1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulasProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071297(1343-1350)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071297
Doerr BNeumann FSutton A(2017)Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF FormulasAlgorithmica10.1007/s00453-016-0190-378:2(561-586)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s00453-016-0190-3

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