Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Generalization of the Heavy-Tailed Mutation in the (1+(λ,λ)) Genetic Algorithm. / Eremeev, Anton; Topchii, Valentin.
GECCO 2024 Companion - Proceedings of the 2024 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, Inc, 2024. p. 93-94 (GECCO 2024 Companion - Proceedings of the 2024 Genetic and Evolutionary Computation Conference Companion).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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 -
ID: 60746484