The 1/5-th Rule with Rollbacks: On Self-Adjustment of the Population Size in the $(1+(λ,λ))$ GA
This work addresses performance issues in evolutionary algorithms for specific optimization problems, representing an incremental improvement in parameter adaptation methods.
The authors tackled the problem of performance degradation in the self-adjusting (1+(λ,λ)) genetic algorithm when applied to problems deviating from ideal fitness-distance correlation, by proposing a modified one-fifth rule with rollbacks. Their modification maintained good performance on OneMax and showed improved results on linear functions with random weights and random satisfiable MAX-SAT instances, with theoretical and practical validation.
Self-adjustment of parameters can significantly improve the performance of evolutionary algorithms. A notable example is the $(1+(λ,λ))$ genetic algorithm, where the adaptation of the population size helps to achieve the linear runtime on the OneMax problem. However, on problems which interfere with the assumptions behind the self-adjustment procedure, its usage can lead to performance degradation compared to static parameter choices. In particular, the one fifth rule, which guides the adaptation in the example above, is able to raise the population size too fast on problems which are too far away from the perfect fitness-distance correlation. We propose a modification of the one fifth rule in order to have less negative impact on the performance in scenarios when the original rule reduces the performance. Our modification, while still having a good performance on OneMax, both theoretically and in practice, also shows better results on linear functions with random weights and on random satisfiable MAX-SAT instances.