Theory for non-theoreticians
Pages 389 - 412
References
[1]
{AD11} Anne Auger and Benjamin Doerr. Theory of Randomized Search Heuristics. World Scientific, 2011.
[2]
{BBD<sup>+</sup>09} Surender Baswana, Somenath Biswas, Benjamin Doerr, Tobias Friedrich, Piyush P. Kurur, and Frank Neumann. Computing single source shortest paths using single-objective fitness functions. In Proc. of Foundations of Genetic Algorithms (FOGA), pages 59--66. ACM, 2009.
[3]
{BDN10} S. Böttcher, B. Doerr, and F. Neumann. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In Proc. of Parallel Problem Solving from Nature (PPSN), pages 1--10. Springer, 2010.
[4]
{DD15a} Benjamin Doerr and Carola Doerr. Optimal parameter choices through self-adjustment: Applying the 1/5-th rule in discrete settings. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1335--1342. ACM, 2015.
[5]
{DD15b} Benjamin Doerr and Carola Doerr. A tight runtime analysis of the (1+(λ, λ)) genetic algorithm on OneMax. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1423--1430. ACM, 2015.
[6]
{DDE15} Benjamin Doerr, Carola Doerr, and Franziska Ebel. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 567:87 -- 104, 2015.
[7]
{DDY16} Benjamin Doerr, Carola Doerr, and Jing Yang. Optimal parameter choices via precise black-box analysis. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 2016. To appear.
[8]
{DHK07} Benjamin Doerr, Edda Happ, and Christian Klein. A tight analysis of the (1+1)-EA for the single source shortest path problem. In Proc. of Congress on Evolutionary Computation (CEC), pages 1890--1895. IEEE, 2007.
[9]
{DHK08} Benjamin Doerr, Edda Happ, and Christian Klein. Crossover can provably be useful in evolutionary computation. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 539--546. ACM, 2008.
[10]
{DHN06} Benjamin Doerr, Nils Hebbinghaus, and Frank Neumann. Speeding up evolutionary algorithms through restricted mutation operators. In Proc. of Parallel Problem Solving from Nature (PPSN), volume 4193 of Lecture Notes in Computer Science, pages 978--987. Springer, 2006.
[11]
{DJ07} Benjamin Doerr and Daniel Johannsen. Adjacency list matchings: an ideal genotype for cycle covers. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1203--1210. ACM, 2007.
[12]
{DJ10} Benjamin Doerr and Daniel Johannsen. Edge-based representation beats vertex-based representation in shortest path problems. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 758--766. ACM, 2010.
[13]
{DJK<sup>+</sup>11} Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, and Carola Winzen. Faster black-box algorithms through higher arity operators. In Proc. of Foundations of Genetic Algorithms (FOGA), pages 163--172. ACM, 2011.
[14]
{DJK<sup>+</sup>13} Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann, and Madeleine Theile. More effective crossover operators for the all-pairs shortest path problem. Theoretical Computer Science, 471:12--26, 2013.
[15]
{DJS<sup>+</sup>13} Benjamin Doerr, Thomas Jansen, Dirk Sudholt, Carola Winzen, and Christine Zarges. Mutation rate matters even when optimizing monotonic functions. Evolutionary Computation, 21:1--27, 2013.
[16]
{DJW98} Stefan Droste, Thomas Jansen, and Ingo Wegener. A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs. Evolutionary Computation, 6:185--196, 1998.
[17]
{DJW02} Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276:51--81, 2002.
[18]
{DK15} Benjamin Doerr and Marvin Künnemann. Optimizing linear functions with the (1+λ) evolutionary algorithm - different asymptotic runtimes for different instances. Theoretical Computer Science, 561:3--23, 2015.
[19]
{DKS07} Benjamin Doerr, Christian Klein, and Tobias Storch. Faster evolutionary algorithms by superior graph representation. In Proc. of Symposium on Foundations of Computational Intelligence (FOCI), pages 245--250. IEEE, 2007.
[20]
{DL15} Carola Doerr and Johannes Lengler. Elitist black-box models: Analyzing the impact of elitist selection on the performance of evolutionary algorithms. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 839--846. ACM, 2015.
[21]
{Doe16} Benjamin Doerr. Optimal parameter settings for the (1 + (λ, λ)) genetic algorithm. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 2016. To appear.
[22]
{dPdLDD15} Axel de Perthuis de Laillevault, Benjamin Doerr, and Carola Doerr. Money for nothing: Speeding up evolutionary algorithms through better initialization. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 815--822. ACM, 2015.
[23]
{Dro02} Stefan Droste. Analysis of the (1+1) EA for a dynamically changing OneMax-variant. In Proc. of Congress on Evolutionary Computation (CEC), pages 55--60. IEEE, 2002.
[24]
{Dro03} Stefan Droste. Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), volume 2723 of Lecture Notes in Computer Science, pages 909--921. Springer, 2003.
[25]
{DSW13} Benjamin Doerr, Dirk Sudholt, and Carsten Witt. When do evolutionary algorithms optimize separable functions in parallel? In Proc. of Foundations of Genetic Algorithms (FOGA), pages 51--64. ACM, 2013.
[26]
{DT09} Benjamin Doerr and Madeleine Theile. Improved analysis methods for crossover-based algorithms. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 247--254. ACM, 2009.
[27]
{EHM99} Agoston Endre Eiben, Robert Hinterding, and Zbigniew Michalewicz. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 3:124--141, 1999.
[28]
{FHH<sup>+</sup>09} Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, and Carsten Witt. Analyses of simple hybrid algorithms for the vertex cover problem. Evolutionary Computation, 17:3--19, 2009.
[29]
{FM92} Stephanie Forrest and Melanie Mitchell. Relative building-block fitness and the building block hypothesis. In Proc. of Foundations of Genetic Algorithms (FOGA), pages 109--126. Morgan Kaufmann, 1992.
[30]
{FW04} Simon Fischer and Ingo Wegener. The ising model on the ring: Mutation versus recombination. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), volume 3102 of Lecture Notes in Computer Science, pages 1113--1124. Springer, 2004.
[31]
{Gol89} David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., 1989.
[32]
{GP14} Brian W. Goldman and William F. Punch. Parameter-less population pyramid. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 785--792. ACM, 2014.
[33]
{GW15} Christian Gießen and Carsten Witt. Population size vs. mutation strength for the (1+λ) EA on OneMax. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1439--1446. ACM, 2015.
[34]
{HGD94} Jeff Horn, David Goldberg, and Kalyan Deb. Long path problems. In Proc. of Parallel Problem Solving from Nature (PPSN), LNCS 866, pages 149--158. Springer, 1994.
[35]
{HJKN08} Edda Happ, Daniel Johannsen, Christian Klein, and Frank Neumann. Rigorous analyses of fitness-proportional selection for optimizing linear functions. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 953--960. ACM, 2008.
[36]
{Hol75} J.H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
[37]
{Jan13} Thomas Jansen. Analyzing Evolutionary Algorithms---The Computer Science Perspective. Springer, 2013.
[38]
{JOZ13} Thomas Jansen, Pietro Simone Oliveto, and Christine Zarges. Approximating vertex cover using edge-based representations. In Proc. of Foundations of Genetic Algorithms (FOGA), pages 87--96. ACM, 2013.
[39]
{JS05} Thomas Jansen and Ulf Schellbach. Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 841--848. ACM, 2005.
[40]
{JW99} Thomas Jansen and Ingo Wegener. On the analysis of evolutionary algorithms - A proof that crossover really can help. In Proc. of European Symposium of Algorithms (ESA), volume 1643 of Lecture Notes in Computer Science, pages 184--193. Springer, 1999.
[41]
{JW05} Thomas Jansen and Ingo Wegener. Real royal road functions-where crossover provably is essential. Discrete Applied Mathematics, 149(1--3):111--125, 2005.
[42]
{JW06} Thomas Jansen and Ingo Wegener. On the analysis of a dynamic evolutionary algorithm. Journal of Discrete Algorithms, 4:181--199, 2006.
[43]
{KHE15} G. Karafotias, M. Hoogendoorn, and A.E. Eiben. Parameter control in evolutionary algorithms: Trends and challenges. IEEE Transactions on Evolutionary Computation, 19:167--187, 2015.
[44]
{KM12} Timo Kötzing and Hendrik Molter. ACO beats EA on a dynamic pseudo-boolean function. In Proc. of Parallel Problem Solving from Nature (PPSN), volume 7491 of Lecture Notes in Computer Science, pages 113--122. Springer, 2012.
[45]
{LS11} Jörg Lässig and Dirk Sudholt. Adaptive population models for offspring populations and parallel evolutionary algorithms. In Proc. of Foundations of Genetic Algorithms(FOGA), pages 181--192. ACM, 2011.
[46]
{LW12} Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica, 64:623--642, 2012.
[47]
{LW14} Andrei Lissovoi and Carsten Witt. MMAS vs. population-based EA on a family of dynamic fitness functions. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1399--1406. ACM, 2014.
[48]
{LW15} Andrei Lissovoi and Carsten Witt. Runtime analysis of ant colony optimization on dynamic shortest path problems. Theoretical Computer Science, 561:73--85, 2015.
[49]
{Neu04} F. Neumann. Expected runtimes of evolutionary algorithms for the eulerian cycle problem. In Proc. of Congress on Evolutionary Computation (CEC), pages 904--910. IEEE, 2004.
[50]
{NOW09} Frank Neumann, Pietro Simone Oliveto, and Carsten Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 835--842. ACM, 2009.
[51]
{NW07} Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378:32--40, 2007.
[52]
{NW10} Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, 2010.
[53]
{OHY09} Pietro Simone Oliveto, Jun He, and Xin Yao. Analysis of the (1+1) -ea for finding approximate solutions to vertex cover problems. IEEE Transactions on Evolutionary Computation, 13:1006--1029, 2009.
[54]
{OW15} Pietro Simone Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science, 605:21--41, 2015.
[55]
{OZ15} Pietro Simone Oliveto and Christine Zarges. Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change. Theoretical Computer Science, 561:37--56, 2015.
[56]
{PPHST15} Tiago Paixao, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. First steps towards a runtime comparison of natural and artificial evolution. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 1455--1462. ACM, 2015.
[57]
{Rud97} Günter Rudolph. Convergence Properties of Evolutionary Algorithms. Kovac, 1997.
[58]
{Sto06} Tobias Storch. How randomized search heuristics find maximum cliques in planar graphs. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 567--574. ACM, 2006.
[59]
{STW04} Jens Scharnow, Karsten Tinnefeld, and Ingo Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3:349--366, 2004.
[60]
{Sud05} Dirk Sudholt. Crossover is provably essential for the ising model on trees. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 2005.
[61]
{SW04} Tobias Storch and Ingo Wegener. Real royal road functions for constant population size. Theoretical Computer Science, 320(1):123--134, 2004.
[62]
{Wit05} Carsten Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of Symposium on Theoretical Aspects of Computer Science (STACS), pages 44--56. Springer, 2005.
[63]
{Wit13} Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability & Computing, 22:294--318, 2013.
[64]
{Wit14} Carsten Witt. Revised analysis of the (1+1) EA for the minimum spanning tree problem. In Proc. of Genetic and Evolutionary Computation Conference (GECCO), pages 509--516. ACM, 2014.
Recommendations
Fast genetic algorithms
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference
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) ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2017
1934 pages
ISBN:9781450349390
DOI:10.1145/3067695
Copyright © 2017 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 July 2017
Check for updates
Qualifiers
- Tutorial
Conference
GECCO '17
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 69Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in