[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3321707.3321848acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs

Published: 13 July 2019 Publication History

Abstract

The runtime analysis of evolutionary algorithms using crossover as search operator has recently produced remarkable results indicating benefits and drawbacks of crossover and illustrating its working principles. Virtually all these results are restricted to upper bounds on the running time of the crossover-based algorithms. This work addresses this lack of lower bounds and rigorously bounds the optimization time of simple algorithms using uniform crossover on the search space {0, 1}n from below via two novel techniques called decoupling and family graphs. First, a simple steady-state crossover-based evolutionary algorithm without selection pressure is analyzed and shown that after O(µ log µ) generations, bit positions are sampled almost independently with marginal probabilities corresponding to the fraction of one-bits at the corresponding position in the initial population. Afterwards, a crossover-based algorithm using tournament selection is analyzed by a novel generalization of the family tree technique originally introduced for mutation-only EAs. Using these so-called family graphs, almost tight lower bounds on the optimization time on the OneMax benchmark function are shown.

References

[1]
Denis Antipov, Benjamin Doerr, Jiefeng Fang, and Tangi Hetet. 2018. Runtime analysis for the (µ+λ) EA optimizing OneMax. In Proc. of GECCO '18. ACM Press, 1459--1466.
[2]
M. Klaričić Bakula, J. Pečarić, and J. Perić. 2012. On the converse Jensen inequality. Applied Mathematics and Computation 218 (2012), 6566--6575.
[3]
Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping Local Optima Using Crossover With Emergent Diversity. IEEE Transactions on Evolutionary Computation 22 (2018), 484--497.
[4]
Benjamin Doerr and Leslie Ann Goldberg. 2013. Adaptive drift analysis. Algorithmica 65 (2013), 224--250.
[5]
Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425 (2012), 17--33.
[6]
Benjamin Doerr, Daniel Johannsen, and Timo Kötzing. 2010. More Effective Crossover Operators for the All-Pairs Shortest Path Problem. In Proc. of PPSN '10. Springer, 184--193.
[7]
Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012. Multiplicative Drift Analysis. Algorithmica 64 (2012), 673--697.
[8]
Benjamin Doerr and Madeleine Theile. 2009. Improved analysis methods for crossover-based algorithms. In Proc. of GECCO '09. ACM Press, 247--254.
[9]
Hilda Geiringer. 1944. On the probability theory of linkage in Mendelian heredity. The Annals of Mathematical Statistics 15 (1944), 25--57.
[10]
Jens Jägersküpper and Carsten Witt. 2005. Rigorous runtime analysis of a (µ+1) ES for the Sphere function. In Proc. of GECCO '05. ACM Press, 849--856.
[11]
Thomas Jansen and Ingo Wegener. 2005. Real royal road functions - where crossover provably is essential. Discrete Applied Mathematics 149 (2005), 111--125.
[12]
Thomas Jansen and Christine Zarges. 2011. On benefits and drawbacks of aging strategies for randomized search heuristics. Theoretical Computer Science 412 (2011), 543--559.
[13]
Timo Kötzing, Dirk Sudholt, and Madeleine Theile. 2011. How Crossover Helps in Pseudo-Boolean Optimization. In Proc. of GECCO '11. ACM Press, 989--996.
[14]
Per Kristian Lehre. 2010. Negative drift in populations. In Proc. of PPSN '10. Springer, 244--253.
[15]
Per Kristian Lehre and Xin Yao. 2011. Crossover can be constructive when computing unique input-output sequences. Soft Computing 15 (2011), 1675--1687.
[16]
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 (2012), 225--241.
[17]
Johannes Lengler. 2018. A General Dichotomy of Evolutionary Algorithms on Monotone Functions. In Proc. of PPSN '18. Springer, 3--15. Extended version: http://arxiv.org/abs/1803.09227.
[18]
Frank Neumann, Pietro S. Oliveto, Günter Rudolph, and Dirk Sudholt. 2011. On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms. In Proc. of GECCO '11. ACM Press, 1587--1594.
[19]
Pietro S. Oliveto, Jun He, and Xin Yao. 2008. Analysis of Population-Based Evolutionary Algorithms for the Vertex Cover Problem. In Proc. of CEC '08. IEEE Press, 1563--1570.
[20]
Pietro S. Oliveto and Carsten Witt. 2015. Improved time complexity analysis of the Simple Genetic Algorithm. Theoretical Computer Science 605 (2015), 21--41.
[21]
Yann Ollivier. 2003. Rate of convergence of crossover operators. Random Struct. Algorithms 23 (2003), 58--72.
[22]
Chao Qian, Yu Yang, and Zhi-Hua Zhou. 2013. An analysis on recombination in multi-objective evolutionary optimization. Artificial Intelligence 204 (2013), 99--119.
[23]
Yuval Rabani, Yuri Rabinovich, and Alistair Sinclair. 1998. A computational view of population genetics. Random Structures and Algorithms 12 (1998), 313--334.
[24]
Yuri Rabinovich, Alistair Sinclair, and Avi Wigderson. 1992. Quadratic Dynamical Systems (Preliminary Version). In Proc. of FOCS '92. IEEE Computer Society, 304--313.
[25]
Dirk Sudholt. 2005. Crossover is Provably Essential for the Ising Model on Trees. In Proc. of GECCO '05. ACM Press, 1161--1167.
[26]
Dirk Sudholt. 2009. The impact of parametrization in memetic evolutionary algorithms. Theoretical Computer Science 410 (2009), 2511--2528.
[27]
Dirk Sudholt. 2017. How Crossover Speeds up Building Block Assembly in Genetic Algorithms. Evolutionary Computation 25 (2017), 237--274.
[28]
Dirk Sudholt and Carsten Witt. 2016. Update Strength in EDAs and ACO: How to Avoid Genetic Drift. In Proc. of GECCO '16. ACM Press, 61--68.
[29]
Richard A. Watson and Thomas Jansen. 2007. A Building-Block Royal Road Where Crossover Is Provably Essential. In Proc. of GECCO '07. ACM Press, 1452--1459.
[30]
Carsten Witt. 2003. Population size vs. runtime of a simple EA. In Proc. of CEC '03. IEEE Press, 1996--2003.
[31]
Carsten Witt. 2006. Runtime Analysis of the (µ+1) EA on Simple Pseudo-Boolean Functions. Evolutionary Computation 14 (2006), 65--86.
[32]
Carsten Witt. 2018. Domino convergence: why one should hill-climb on linear functions. In Proc. of GECCO '18. ACM Press, 1539--1546.

Cited By

View all
  • (2021)Runtime Analysis of Restricted Tournament Selection for Bimodal OptimisationEvolutionary Computation10.1162/evco_a_00292(1-26)Online publication date: 4-Oct-2021
  • (2020)Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative DriftEvolutionary Computation10.1162/evco_a_00283(1-25)Online publication date: 16-Nov-2020
  • (2020)A tight lower bound on the expected runtime of standard steady state genetic algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390212(1323-1331)Online publication date: 25-Jun-2020
  • Show More Cited By

Index Terms

  1. Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference
    July 2019
    1545 pages
    ISBN:9781450361118
    DOI:10.1145/3321707
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 July 2019

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. crossover
    2. decoupling
    3. randomised search heuristics
    4. runtime analysis

    Qualifiers

    • Research-article

    Conference

    GECCO '19
    Sponsor:
    GECCO '19: Genetic and Evolutionary Computation Conference
    July 13 - 17, 2019
    Prague, Czech Republic

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 31 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Runtime Analysis of Restricted Tournament Selection for Bimodal OptimisationEvolutionary Computation10.1162/evco_a_00292(1-26)Online publication date: 4-Oct-2021
    • (2020)Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative DriftEvolutionary Computation10.1162/evco_a_00283(1-25)Online publication date: 16-Nov-2020
    • (2020)A tight lower bound on the expected runtime of standard steady state genetic algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390212(1323-1331)Online publication date: 25-Jun-2020
    • (2020)Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family GraphsAlgorithmica10.1007/s00453-020-00776-6Online publication date: 4-Nov-2020
    • (2020)Lower Bounds for Non-elitist Evolutionary Algorithms via Negative Multiplicative DriftParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58115-2_42(604-618)Online publication date: 2-Sep-2020

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media