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

research-article

Fast mutation in crossover-based algorithms

Authors:

Maxim Buzdalov,

Benjamin DoerrAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 1268 - 1276

https://doi.org/10.1145/3377930.3390172

Published: 26 June 2020 Publication History

Abstract

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives.

In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. With a heavy-tailed mutation rate, the runtime of the (1 + (λ, λ)) genetic algorithm on the OneMax benchmark function becomes linear in the problem size. This is asymptotically faster than with any static mutation rate and is the same asymptotic runtime that can be obtained with a self-adjusting choice of the mutation rate. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random MAX-3SAT instances.

References

[1]

Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020. Fast mutation in crossover-based algorithms. CoRR abs/2004.06538 (2020).

[2]

Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2019. A tight runtime analysis for the (1 + (λ, λ)) GA on LeadingOnes. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 169--182.

Digital Library

[3]

Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2020. The (1 + (λ, λ)) GA is even faster on multimodal problems. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM. To appear.

Digital Library

[4]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.

[5]

Thomas Bäck. 1993. Optimal mutation rates in genetic search. In International Conference on Genetic Algorithms, ICGA 1993. Morgan Kaufmann, 2--8.

Digital Library

[6]

Maxim Buzdalov and Benjamin Doerr. 2017. Runtime analysis of the (1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 1343--1350.

Digital Library

[7]

Benjamin Doerr. 2020. Does comma selection help to cope with local optima?. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM. To appear.

Digital Library

[8]

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. Also available at https://arxiv.org/abs/1801.06733.

[9]

Benjamin Doerr and Carola Doerr. 2018. Optimal static and self-adjusting parameter choices for the (1 + (λ, λ)) genetic algorithm. Algorithmica 80 (2018), 1658--1709.

Digital Library

[10]

Benjamin Doerr, Carola Doerr, and Franziska Ebel. 2015. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567 (2015), 87--104.

Digital Library

[11]

Benjamin Doerr, Thomas Jansen, Dirk Sudholt, Carola Winzen, and Christine Zarges. 2013. Mutation rate matters even when optimizing monotone functions. Evolutionary Computation 21 (2013), 1--21.

Digital Library

[12]

Benjamin Doerr and Marvin Künnemann. 2015. Optimizing linear functions with the (1 + λ) evolutionary algorithm---different asymptotic runtimes for different instances. Theoretical Computer Science 561 (2015), 3--23.

Digital Library

[13]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 777--784.

Digital Library

[14]

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

[15]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science 276 (2002), 51--81.

Digital Library

[16]

Christian Gießen and Carsten Witt. 2017. The interplay of population size and mutation probability in the (1 + λ) EA on OneMax. Algorithmica 78 (2017), 587--609.

Digital Library

[17]

Brian W. Goldman and William F. Punch. 2014. Parameter-less population pyramid. In Genetic and Evolutionary Computation Conference, GECCO 2014. ACM, 785--792.

[18]

Jun He and Xin Yao. 2001. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127 (2001), 51--81.

Digital Library

[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 (2005), 413--440.

Digital Library

[21]

Per Kristian Lehre. 2010. Negative drift in populations. In Parallel Problem Solving from Nature, PPSN 2010. Springer, 244--253.

Digital Library

[22]

Per Kristian Lehre. 2011. Fitness-levels for non-elitist populations. In Genetic and Evolutionary Computation Conference, GECCO 2011. ACM, 2075--2082.

Digital Library

[23]

Johannes Lengler. 2018. A general dichotomy of evolutionary algorithms on monotone functions. In Parallel Problem Solving from Nature, PPSN 2018. Springer, 3--15.

[24]

Heinz Mühlenbein. 1992. How genetic algorithms really work: Mutation and hillclimbing. In Parallel Problem Solving from Nature, PPSN 1992. Elsevier, 15--26.

[25]

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

Digital Library

[26]

Eduardo Carvalho Pinto and Carola Doerr. 2018. Towards a more practice-aware runtime analysis of evolutionary algorithms. CoRR abs/1812.00493 (2018).

[27]

Adam Prügel-Bennett. 2004. When a genetic algorithm outperforms hill-climbing. Theoretical Computer Science 320 (2004), 135--153.

Digital Library

[28]

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

[29]

Olivier Teytaud and Sylvain Gelly. 2006. General lower bounds for evolutionary algorithms. In Parallel Problem Solving from Nature, PPSN 2006. Springer, 21--31.

[30]

Abraham Wald. 1945. Some generalizations of the theory of cumulative sums of random variables. The Annals of Mathematical Statistics 16 (1945), 287--293.

[31]

Carsten Witt. 2006. Runtime analysis of the (μ + 1) EA on simple pseudo-Boolean functions. Evolutionary Computation 14 (2006), 65--86.

Digital Library

[32]

Carsten Witt. 2013. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing 22 (2013), 294--318.

Cited By

Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger S(2023)Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/36036293:2(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3603629
Fajardo MSudholt D(2023)Theoretical and Empirical Analysis of Parameter Control Mechanisms in the (1 + (λ, λ)) Genetic AlgorithmACM Transactions on Evolutionary Learning and Optimization10.1145/35647552:4(1-39)Online publication date: 14-Jan-2023
https://dl.acm.org/doi/10.1145/3564755
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
Show More Cited By

Index Terms

Fast mutation in crossover-based algorithms
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random search heuristics
  2. Theory and algorithms for application domains
    1. Theory of randomized search heuristics

Recommendations

The Cost of Randomness in Evolutionary Algorithms: Crossover can Save Random Bits
Evolutionary Computation in Combinatorial Optimization
Abstract
Evolutionary algorithms make countless random decisions during selection, mutation and crossover operations. These random decisions require a steady stream of random numbers.
We analyze the expected number of random bits used throughout a run of an ...
Empirical Analysis of Crossover-Based Evolutionary Algorithms on Rugged Landscape
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

The crossover is considered as an essential component of the evolutionary algorithms. There exist different ways of how to use it, and in this paper we compare two approaches commonly used in pseudo-Boolean optimization, the classic approach of (μ + 1)...
How crossover speeds up building block assembly in genetic algorithms

We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 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 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Best Paper

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
166
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger S(2023)Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/36036293:2(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3603629
Fajardo MSudholt D(2023)Theoretical and Empirical Analysis of Parameter Control Mechanisms in the (1 + (λ, λ)) Genetic AlgorithmACM Transactions on Evolutionary Learning and Optimization10.1145/35647552:4(1-39)Online publication date: 14-Jan-2023
https://dl.acm.org/doi/10.1145/3564755
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
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Vinokurov DBuzdalov MWagner M(2022)On optimal static and dynamic parameter choices for fixed-target optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528875(876-883)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528875
Doerr BHadri OPinard AWagner M(2022)The (1 + (λ, λ)) global SEMO algorithmProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528868(520-528)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528868
Neumann AAntipov DNeumann FWagner M(2022)Coevolutionary Pareto diversity optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528755(832-839)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528755
Doerr BGhannane YBrahim MWagner M(2022)Towards a stronger theory for permutation-based evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528720(1390-1398)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528720
Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger SWagner M(2022)Crossover for cardinality constrained optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528713(1399-1407)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528713
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