The “One-Fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ, λ)) Genetic Algorithm

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 functions with random weights, as well as on random satisfiable MAX-3SAT problems.