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

research-article

Fast genetic algorithms

Authors:

Benjamin Doerr,

Régis Makhmara,

Ta Duy NguyenAuthors Info & Claims

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

Pages 777 - 784

https://doi.org/10.1145/3071178.3071301

Published: 01 July 2017 Publication History

Abstract

For genetic algorithms (GAs) using a bit-string representation of length n, the general recommendation is to take 1/n as mutation rate. In this work, we discuss whether this is justified for multi-modal functions. Taking jump functions and the (1+1) evolutionary algorithm (EA) as the simplest example, we observe that larger mutation rates give significantly better runtimes. For the Jump_{m, n} function, any mutation rate between 2/n and m/n leads to a speedup at least exponential in m compared to the standard choice.

The asymptotically best runtime, obtained from using the mutation rate m/n and leading to a speed-up super-exponential in m, is very sensitive to small changes of the mutation rate. Any deviation by a small (1 ± ε) factor leads to a slow-down exponential in m. Consequently, any fixed mutation rate gives strongly sub-optimal results for most jump functions.

Building on this observation, we propose to use a random mutation rate α/n, where α is chosen from a power-law distribution. We prove that the (1 + 1) EA with this heavy-tailed mutation rate optimizes any Jump_{m, n} function in a time that is only a small polynomial (in m) factor above the one stemming from the optimal rate for this m. Our heavy-tailed mutation operator yields similar speed-ups (over the best known performance guarantees) for the vertex cover problem in bipartite graphs and the matching problem in general graphs.

Following the example of fast simulated annealing, fast evolution strategies, and fast evolutionary programming, we propose to call genetic algorithms using a heavy-tailed mutation operator fast genetic algorithms.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. 2014. Unbiased black-box complexity of parallel search. In Parallel Problem Solving from Nature XIII. Springer, 892--901.

[4]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In PPSN (1) (Lecture Notes in Computer Science), Vol. 6238. Springer, 1--10.

Digital Library

[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. Emergence of diversity and its benefits for crossover in genetic algorithms. In PPSN (Lecture Notes in Computer Science), Vol. 9921. Springer, 890--900.

[6]

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 GECCO. ACM, 645--652.

Digital Library

[7]

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

[8]

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

[9]

Benjamin Doerr, Christian Gießen, Carsten Witt, and Jing Yang. 2017. The (1+λ) evolutionary algorithm with self-adjusting mutation rate. In GECCO. ACM.

Digital Library

[10]

Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425 (2012), 17--33.

Digital Library

[11]

Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann, and Madeleine Theile. 2013. More effective crossover operators for the all-pairs shortest path problem. Theoretical Computer Science 471 (2013), 12--26.

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. ArXiv e-prints (March 2017). arXiv:1703.03334

[14]

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

[15]

Simon Fischer and Ingo Wegener. 2005. The one-dimensional Ising model: Mutation versus recombination. Theoretical Computer Science 344 (2005), 208--225.

Digital Library

[16]

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, and Carsten Witt. 2010. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation 18 (2010), 617--633.

Digital Library

[17]

Oliver Giel and Ingo Wegener. 2003. Evolutionary algorithms and the maximum matching problem. In STACS (Lecture Notes in Computer Science), Vol. 2607. Springer, 415--426.

Digital Library

[18]

Oliver Giel and Ingo Wegener. 2004. Searching randomly for maximum matchings. Electronic Colloquium on Computational Complexity (ECCC) 076 (2004).

[19]

Christian Gießen and Carsten Witt. 2015. Population size vs. mutation strength for the (1+λ) EA on OneMax. In GECCO. ACM, 1439--1446.

Digital Library

[20]

GitHub. 2017. Fast genetic algorithms. (2017). https://github.com/FastGA/fast-genetic-algorithms.

[21]

Nikolaus Hansen, Fabian Gemperle, Anne Auger, and Petros Koumoutsakos. 2006. When do heavy-tail distributions help?. In PPSN (Lecture Notes in Computer Science), Vol. 4193. Springer, 62--71.

Digital Library

[22]

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

[23]

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

Digital Library

[24]

Thomas Jansen and Ingo Wegener. 2006. On the analysis of a dynamic evolutionary algorithm. J. Discrete Algorithms 4 (2006), 181--199.

[25]

Timo Kötzing, Dirk Sudholt, and Madeleine Theile. 2011. How crossover helps in pseudo-Boolean optimization. In GECCO. ACM, 989--996.

Digital Library

[26]

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

[27]

Frank Neumann and Ingo Wegener. 2007. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science 378 (2007), 32--40.

Digital Library

[28]

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

Digital Library

[29]

Petr Posik. 2009. BBOB-benchmarking a simple estimation of distribution algorithm with Cauchy distribution. In GECCO (Companion). ACM, 2309--2314.

Digital Library

[30]

Petr Posík. 2010. Comparison of Cauchy EDA and BIPOP-CMA-ES algorithms on the BBOB noiseless testbed. In GECCO (Companion). ACM, 1697--1702.

Digital Library

[31]

Günter Rudolph. 1997. Convergence Properties of Evolutionary Algorithms. Kovac.

[32]

Jens Scharnow, Karsten Tinnefeid, and Ingo Wegener. 2004. The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3 (2004), 349--366.

[33]

Tom Schaul, Tobias Glasmachers, and Jürgen Schmidhuber. 2011. High dimensions and heavy tails for natural evolution strategies. In GECCO. ACM, 845--852.

Digital Library

[34]

Tobias Storch and Ingo Wegener. 2004. Real royal road functions for constant population size. Theoretical Computer Science 320 (2004), 123--134.

Digital Library

[35]

Dirk Sudholt. 2005. Crossover is provably essential for the ising model on trees. In GECCO. ACM, 1161--1167.

Digital Library

[36]

Harold H. Szu and Ralph L. Hartley. 1987. Fast simulated annealing. Physics Letters A 122 (June 1987), 157--162.

[37]

Ingo Wegener. 2001. Theoretical aspects of evolutionary algorithms. In ICALP (Lecture Notes in Computer Science), Vol. 2076. Springer, 64--78.

Digital Library

[38]

Carsten Witt. 2005. Worst-case and average-case approximations by simple randomized search heuristics. In STACS (Lecture Notes in Computer Science), Vol. 3404. Springer, 44--56.

Digital Library

[39]

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

Digital Library

[40]

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

[41]

Xin Yao and Yong Liu. 1997. Fast evolution strategies. In Evolutionary Programming (Lecture Notes in Computer Science), Vol. 1213. Springer, 151--162.

Digital Library

[42]

Xin Yao, Yong Liu, and Guangming Lin. 1999. Evolutionary programming made faster. IEEE Trans. Evolutionary Computation 3 (1999), 82--102.

Digital Library

Cited By

Soleimani HBalivi F(2024)Optimizing Selective Dissemination of Information: Leveraging Genetic Algorithms for Enhanced Content PersonalizationInfoScience Trends10.61186/ist.202401.01.031:1(8-12)Online publication date: 1-May-2024
https://doi.org/10.61186/ist.202401.01.03
Tynchenko VTynchenko VNelyub VBukhtoyarov VBorodulin AKurashkin SGantimurov AKukartsev V(2024)Mathematical Models for the Design of GRID Systems to Solve Resource-Intensive ProblemsMathematics10.3390/math1202027612:2(276)Online publication date: 15-Jan-2024
https://doi.org/10.3390/math12020276
Xu YHuo H(2024)DSASPP: Depthwise Separable Atrous Spatial Pyramid Pooling for PCB Surface Defect DetectionElectronics10.3390/electronics1308149013:8(1490)Online publication date: 14-Apr-2024
https://doi.org/10.3390/electronics13081490
Show More Cited By

Index Terms

Fast genetic algorithms
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Improved biogeography-based optimisation

Biogeography-based optimisation (BBO) is one of the popular evolutionary algorithms, inspired by the theory of island biogeography. It has been successfully applied in various real world optimisation problems such as image segmentation, data clustering, ...
Ensemble of niching algorithms

Although niching algorithms have been investigated for almost four decades as effective procedures to obtain several good and diverse solutions of an optimization problem, no effort has been reported on combining different niching algorithms to form an ...
Two-Loop Real-Coded Genetic Algorithms with Adaptive Control of Mutation Step Sizes

Genetic algorithms are adaptive methods based on natural evolution that may be used for search and optimization problems. They process a population of search space solutions with three operations: selection, crossover, and mutation. Under their initial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 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: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

173
Total Citations
View Citations
747
Total Downloads

Downloads (Last 12 months)103
Downloads (Last 6 weeks)11

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Soleimani HBalivi F(2024)Optimizing Selective Dissemination of Information: Leveraging Genetic Algorithms for Enhanced Content PersonalizationInfoScience Trends10.61186/ist.202401.01.031:1(8-12)Online publication date: 1-May-2024
https://doi.org/10.61186/ist.202401.01.03
Tynchenko VTynchenko VNelyub VBukhtoyarov VBorodulin AKurashkin SGantimurov AKukartsev V(2024)Mathematical Models for the Design of GRID Systems to Solve Resource-Intensive ProblemsMathematics10.3390/math1202027612:2(276)Online publication date: 15-Jan-2024
https://doi.org/10.3390/math12020276
Xu YHuo H(2024)DSASPP: Depthwise Separable Atrous Spatial Pyramid Pooling for PCB Surface Defect DetectionElectronics10.3390/electronics1308149013:8(1490)Online publication date: 14-Apr-2024
https://doi.org/10.3390/electronics13081490
Frazier JHelmuth TLi XHandl J(2024)Explaining Automatically Designed Software Defined Perimeters with a Two Phase Evolutionary Computation SystemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664155(1527-1535)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664155
Zheng WDoerr BLi XHandl J(2024)Hot off the Press: Runtime Analysis of the SMS-EMOA for Many-Objective OptimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664064(69-70)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664064
Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Dang DOpris ASudholt DLi XHandl J(2024)Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654177(484-492)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654177
Doerr BKrejca MVu NLi XHandl J(2024)Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy HeuristicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654140(169-177)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654140
Gadea Harder JKötzing TLi XRadhakrishnan ARuff JLi XHandl J(2024)Run Time Bounds for Integer-Valued OneMax FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654091(1569-1577)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654091
Krejca MWitt CLi XHandl J(2024)A Flexible Evolutionary Algorithm with Dynamic Mutation Rate ArchiveProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654076(1578-1586)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654076
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