Top

Published in:

2020 | OriginalPaper | Chapter

Runtime Analysis of a Heavy-Tailed \((1+(\lambda ,\lambda ))\) Genetic Algorithm on Jump Functions

Authors : Denis Antipov, Benjamin Doerr

Published in: Parallel Problem Solving from Nature – PPSN XVI

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

It was recently observed that the \((1+(\lambda ,\lambda ))\) genetic algorithm can comparably easily escape the local optimum of the jump functions benchmark. Consequently, this algorithm can optimize the jump function with jump size k in an expected runtime of only \(n^{(k + 1)/2}k^{-k/2}e^{O(k)}\) fitness evaluations (Antipov, Doerr, Karavaev (GECCO 2020)). This performance, however, was obtained with non-standard parameter setting depending on the jump size k.

To overcome this difficulty, we propose to choose two parameters of the \((1+(\lambda ,\lambda ))\) genetic algorithm randomly from a power-law distribution. Via a mathematical runtime analysis, we show that this algorithm with natural instance-independent choices of the power-law parameters on all jump functions with jump size at most n/4 has a performance close to what the best instance-specific parameters in the previous work obtained. This price for instance-independence can be made as small as an \(O(n\log (n))\) factor. Given the difficulty of the jump problem and the runtime losses from using mildly suboptimal fixed parameters (also discussed in this work), this appears to be a fair price.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Warm-Start AlphaZero Self-play Search Enhancements

next chapter First Steps Towards a Runtime Analysis When Starting with a Good Solution

The omitted proofs can be found in the preprint [3].

Antipov, D., Buzdalov, M., Doerr, B.: Fast mutation in crossover-based algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1268–1276. ACM (2020)

Antipov, D., Buzdalov, M., Doerr, B.: First steps towards a runtime analysis when starting with a good solution. In: Bäck, T., et al. (eds.) PPSN 2020. LNCS, vol. 12270, pp. 560–573. Springer, Switzerland (2020). https://doi.org/10.1007/978-3-030-58115-2_39

Antipov, D., Doerr, B.: Runtime analysis of a heavy-tailed (1+(\(\lambda \), \(\lambda \))) genetic algorithm on jump functions. CoRR abs/2006.03523 (2020). https://arxiv.org/abs/2006.03523

Antipov, D., Doerr, B., Karavaev, V.: A tight runtime analysis for the \({(1 + (\lambda ,\lambda ))}\) GA on LeadingOnes. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 169–182. ACM (2019)

Antipov, D., Doerr, B., Karavaev, V.: The \((1 + (\lambda ,\lambda ))\) GA is even faster on multimodal problems. In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1259–1267. ACM (2020)

Buzdalov, M., Doerr, B.: Runtime analysis of the \({(1+(\lambda ,\lambda ))}\) genetic algorithm on random satisfiable 3-CNF formulas. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 1343–1350. ACM (2017)

Dang, D.-C., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima with diversity mechanisms and crossover. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 645–652. ACM (2016)

Dang, D.-C., Friedrich, T., Kötzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22, 484–497 (2018)CrossRef

Dang, D.-C., Lehre, P.K.: Self-adaptation of mutation rates in non-elitist populations. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 803–813. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_75CrossRef

10.

Doerr, B.: A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1488–1496. ACM (2019)

11.

Doerr, B.: Does comma selection help to cope with local optima? In: Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 1304–1313. ACM (2020)

12.

Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the \({(1+(\lambda,\lambda ))}\) genetic algorithm. Algorithmica 80, 1658–1709 (2018)MathSciNetCrossRef

13.

Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: Provable performance gains through dynamic parameter choices. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation. NCS, pp. 271–321. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_6. https://arxiv.org/abs/1804.05650CrossRefMATH

14.

Doerr, B., Doerr, C., Ebel, F.: Lessons from the black-box: fast crossover-based genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 781–788. ACM (2013)

15.

Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87–104 (2015)MathSciNetCrossRef

16.

Doerr, B., Doerr, C., Kötzing, T.: Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica 80, 1732–1768 (2018)MathSciNetCrossRef

17.

Doerr, B., Doerr, C., Yang, J.: k-bit mutation with self-adjusting k outperforms standard bit mutation. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 824–834. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_77CrossRef

18.

Doerr, B., Gießen, C., Witt, C., Yang, J.: The \({(1 + \lambda )}\) evolutionary algorithm with self-adjusting mutation rate. Algorithmica 81, 593–631 (2019)MathSciNetCrossRef

19.

Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777–784. ACM (2017)

20.

Doerr, B., Witt, C., Yang, J.: Runtime analysis for self-adaptive mutation rates. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 1475–1482. ACM (2018)

21.

Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276, 51–81 (2002)MathSciNetCrossRef

22.

Friedrich, T., Göbel, A., Quinzan, F., Wagner, M.: Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations. CoRR abs/1805.10902 (2018)

23.

Friedrich, T., Göbel, A., Quinzan, F., Wagner, M.: Heavy-tailed mutation operators in single-objective combinatorial optimization. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11101, pp. 134–145. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99253-2_11CrossRef

24.

Friedrich, T., Kötzing, T., Krejca, M.S., Nallaperuma, S., Neumann, F., Schirneck, M.: Fast building block assembly by majority vote crossover. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 661–668. ACM (2016)

25.

Friedrich, T., Quinzan, F., Wagner, M.: Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 293–300. ACM (2018)

26.

Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 785–792. ACM (2014)

27.

Hasenöhrl, V., Sutton, A.M.: On the runtime dynamics of the compact genetic algorithm on jump functions. In: Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 967–974. ACM (2018)

28.

Jansen, T., Wegener, I.: The analysis of evolutionary algorithms - a proof that crossover really can help. Algorithmica 34, 47–66 (2002)MathSciNetCrossRef

29.

Lässig, J., Sudholt, D.: Adaptive population models for offspring populations and parallel evolutionary algorithms. In: Foundations of Genetic Algorithms, FOGA 2011, pp. 181–192. ACM (2011)

30.

Mambrini, A., Sudholt, D.: Design and analysis of schemes for adapting migration intervals in parallel evolutionary algorithms. Evol. Comput. 23, 559–582 (2015)CrossRef

31.

Mironovich, V., Buzdalov, M.: Evaluation of heavy-tailed mutation operator on maximum flow test generation problem. In: Genetic and Evolutionary Computation Conference, GECCO 2017. Companion Material, pp. 1423–1426. ACM (2017)

32.

Rowe, J.E., Aishwaryaprajna: the benefits and limitations of voting mechanisms in evolutionary optimisation. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 34–42. ACM (2019)

33.

Wald, A.: Some generalizations of the theory of cumulative sums of random variables. Ann. Math. Stat. 16, 287–293 (1945)MathSciNetCrossRef

34.

Whitley, D., Varadarajan, S., Hirsch, R., Mukhopadhyay, A.: Exploration and exploitation without mutation: solving the jump function in \(\Theta (n)\) time. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds.) PPSN 2018. LNCS, vol. 11102, pp. 55–66. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99259-4_5CrossRef

35.

Wu, M., Qian, C., Tang, K.: Dynamic mutation based pareto optimization for subset selection. In: Huang, D.-S., Gromiha, M.M., Han, K., Hussain, A. (eds.) ICIC 2018. LNCS (LNAI), vol. 10956, pp. 25–35. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-95957-3_4CrossRef

36.

Ye, F., Wang, H., Doerr, C., Bäck, T.: Benchmarking a \((\mu +\lambda )\) genetic algorithm with configurable crossover probability. CoRR abs/2006.05889 (2020)

Title: Runtime Analysis of a Heavy-Tailed Genetic Algorithm on Jump Functions
Authors: Denis Antipov
Benjamin Doerr
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_38

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner