Open AccessThe “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm
Author(s) -
Антон Олегович Басин,
Максим Викторович Буздалов,
Анатолий Абрамович Шалыто
Publication year - 2020
Publication title -
modelirovanie i analiz informacionnyh sistem
Language(s) - English
Resource type - Journals
eISSN - 2313-5417
pISSN - 1818-1015
DOI - 10.18255/1818-1015-2020-4-488-508
Subject(s) - evolutionary algorithm , population , genetic algorithm , algorithm , function (biology) , fitness function , mathematics , boolean satisfiability problem , order (exchange) , computer science , mathematical optimization , biology , evolutionary biology , demography , sociology , finance , economics
Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the (1 + (λ,λ)) genetic algorithm, where adaptation of the population size helps to achieve the linear running time on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to the performance degradation. In particular, this is the case with the “one-fifth rule” on problems with weak fitness-distance correlation.We propose a modification of the “one-fifth rule” in order to have less negative impact on the performance in the cases where the original rule is destructive. Our modification, while still yielding a provable linear runtime on OneMax, shows better results on linear function with random weights, as well as on random satisfiable MAX-3SAT problems.