TY - GEN

T1 - Generalization of the Heavy-Tailed Mutation in the (1+(λ,λ)) Genetic Algorithm

AU - Eremeev, Anton

AU - Topchii, Valentin

N1 - The work is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-282 with the MSHE RF.

PY - 2024/7/14

Y1 - 2024/7/14

N2 - 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.

AB - 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.

KW - genetic algorithm

KW - heavy-tailed mutation

KW - optimization time

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85201968946&origin=inward&txGid=005deaad26f5845c56f1c73777bec061

UR - https://www.mendeley.com/catalogue/968b0522-e5de-3395-9c3b-61de4fb74348/

U2 - 10.1145/3638530.3664095

DO - 10.1145/3638530.3664095

M3 - Conference contribution

SN - 9798400704956

T3 - GECCO 2024 Companion - Proceedings of the 2024 Genetic and Evolutionary Computation Conference Companion

SP - 93

EP - 94

BT - GECCO 2024 Companion - Proceedings of the 2024 Genetic and Evolutionary Computation Conference Companion

PB - Association for Computing Machinery, Inc

T2 - 2024 Genetic and Evolutionary Computation Conference Companion

Y2 - 14 July 2024 through 18 July 2024

ER -