Abstract: 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 on the distribution function of mutation rate. We show that upper bounds on the expected optimization time of the (1 + (λ, λ)) genetic algorithm obtained by Antipov, Buzdalov and Doerr (2022) for the OneMax fitness function do not only hold for power-law distribution of mutation rate, but also for a wider class of distributions, defined in terms of power-law constraints on the cumulative distribution function of mutation rate. 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 + (λ, λ)) genetic algorithm with any static mutation rate.

Cite: Eremeev A. , Topchii V.
Generalization of the Heavy-Tailed Mutation in the (1+(λ,λ)) Genetic Algorithm
In compilation Proceedings of the Genetic and Evolutionary Computation Conference Companion. – ACM., 2024. – C.93–94. – ISBN 979-8-4007-0495-6. DOI: 10.1145/3638530.3664095 Scopus OpenAlex

Dates:

Published online:	Aug 1, 2024
Published print:	Oct 17, 2024

Identifiers:

Scopus:	2-s2.0-85201968946
OpenAlex:	W4403430298

Citing:

DB	Citing
Scopus	1

Altmetrics: