Generalized heavy-tailed mutation for evolutionary algorithms

A. V. Eremeev   ; D. V. Silaev   ; V. A. Topchii

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 940-959

Résumé

The heavy-tailed mutation operator, proposed by Doerr, Le, Makhmara, and Nguyen (2017) for evolutionary algorithms, is based on the power-law assumption of mutation rate distribution. Here we generalize the power-law assumption using a regularly varying constraint on the distribution function of mutation rate. In this setting, we generalize the upper bounds on the expected optimization time of the $(1+(\lambda,\lambda))$ genetic algorithm obtained by Antipov, Buzdalov and Doerr (2022) for the OneMax function class parametrized by the problem dimension $n$. In particular, it is shown that, on this function class, the sufficient conditions of Antipov, Buzdalov and Doerr (2022) on the heavy-tailed mutation, ensuring the $O(n)$ optimization time in expectation, may be generalized as well. This optimization time is known to be asymptotically faster than what can be achieved by the $(1+(\lambda,\lambda))$ genetic algorithm with any static mutation rate. A new version of the heavy-tailed mutation operator is proposed, satisfying the generalized conditions, and promising results of computational experiments are presented.

Détail

Keywords: Evolutionary algorithms, regularly varying functions, heavy-tailed mutation, optimization time.

Bibliographie

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass. etc., 1974 | MR | Zbl

[2] D. Antipov, M. Buzdalov, B. Doerr, “Fast mutation in crossover-based algorithms”, Algorithmica, 84:6 (2022), 1724–1761 | DOI | MR | Zbl

[3] T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction to algorithms, 3rd Edition, MIT Press, Cambridge, 2009 | MR | Zbl

[4] D.-C. Dang, A.V. Eremeev, P.K. Lehre, X. Qin, “Fast non-elitist evolutionary algorithms with power-law ranking selection”, Proc. GECCO'22–Proceedings of the Genetic and Evolutionary Computation Conference, 1372–1380 | DOI | MR

[5] B. Doerr, C. Doerr, F. Ebel, “From black-box complexity to designing new genetic algorithms”, Theor. Comput. Sci., 567 (2015), 87–104 | DOI | MR | Zbl

[6] B. Doerr, M. Künnemann, “Optimizing linear functions with the $(1+\lambda)$ evolutionary algorithm-different asymptotic runtimes for different instances”, Theor. Comput. Sci., Part A, 561 (2015), 3–23 | DOI | MR | Zbl

[7] S. Droste, T. Jansen, I. Wegener, “Upper and lower bounds for randomized search heuristics in black-box optimization”, Theory Comput. Syst., 39:4 (2006), 525–544 | DOI | MR | Zbl

[8] T. Jansen, K.A. De Jong, I. Wegener, “On the choice of the offspring population size in evolutionary algorithms”, Evol. Comput., 13 (2005), 413–440 | DOI

[9] P. Erdős, A. Rényi, “On two problems of information theory”, Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 8 (1963), 229–243 | MR | Zbl

[10] L.A. Rastrigin, Statisticheskie metody poiska, Theoretical Foundations of Technical Cybernetics, 10, Nauka, M., 1968 | MR

[11] D.E. Goldberg, Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, 1989 | Zbl

[12] H.K. Hwang, A. Panholzer, N. Rolin, T.H. Tsai, W.M. Chen, “Probabilistic analysis of the (1+1)-evolutionary algorithm”, Evolutionary Computation, 26:2 (2018), 299–345 | DOI

[13] P.K. Lehre, “Negative drift in populations”, Parallel Problem Solving from Nature, PPSN XI. PPSN 2010, Lecture Notes in Computer Science, 6238, eds. Schaefer R. et al., Springer, Berlin–Heidelberg, 2010, 244–253 | DOI

[14] P.K. Lehre, “Fitness-levels for non-elitist populations”, Proceedings of the 2011 Genetic and Evolutionary Computation Conference, GECCO 2011, 2011, 2075–2082 https://dl.acm.org/doi/proceedings/10.1145/2001576?tocHeading=heading1

[15] H. Mühlenbein, “How genetic algorithms really work: mutation and hillclimbing”, Parallel Problem Solving from Nature 2, PPSN-II, Elsevier, Brussels, 1992, 15–26 https://www.researchgate.net/publication/220702092_How_Genetic_Algorithms_Really_Work_Mutation_and_Hillclimbing

[16] S. Droste, T. Jansen, I. Wegener, “On the analysis of the (1+1) evolutionary algorithm”, Theor. Comput. Sci., 276:1-2 (2002), 51–81 | DOI | MR | Zbl

[17] C. Witt, “Tight bounds on the optimization time of a randomized search heuristic on linear functions”, Comb. Probab. Comput., 22:2 (2013), 294–318 | DOI | MR | Zbl

[18] B. Doerr, H.P. Le, R. Makhmara, T.D. Nguyen, “Fast genetic algorithms”, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017 (July 2017), 2017, 777–784 | DOI

[19] B. Doerr, C. Doerr, “Optimal static and self-adjusting parameter choices for the $(1 + (\lambda, \lambda))$ genetic algorithm”, Algorithmica, 80:5 (2018), 1658–1709 | DOI | MR | Zbl

[20] A. Eremeev, V. Topchii, “Generalization of the heavy-tailed mutation in the $(1 + (\lambda, \lambda))$ genetic algorithm”, Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion (July 2024), 2024, 93–94 | DOI

[21] P.S. Oliveto, C. Witt, “Improved time complexity analysis of the simple genetic algorithm”, Theor. Comput. Sci., 605 (2015), 21–41 | DOI | MR | Zbl

[22] P.A. Borisovskii, A.V. Eremeev, “Comparison of certain evolutionary algorithms”, Autom. Remote Control, 65:3 (2004), 357–362 | DOI | MR | Zbl

[23] E. Seneta, Regularly varying functions, Nauka, M., 1985 | MR | Zbl

[24] W. Feller, An introduction to probability theory and its applications, v. II, Mir, M., 1984 | MR | Zbl

[25] A.A. Borovkov, Probability theory, Nauka, M., 1976 | MR | Zbl