Skip to Main content Skip to Navigation
Journal articles

Analyzing bandit-based adaptive operator selection mechanisms

Álvaro Fialho 1 Luis da Costa 2, 3 Marc Schoenauer 1, 2, 3 Michèle Sebag 1, 2, 3
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Several techniques have been proposed to tackle the Adaptive Operator Selection (AOS) issue in Evolutionary Algorithms. Some recent proposals are based on the Multi-armed Bandit (MAB) paradigm: each operator is viewed as one arm of a MAB problem, and the rewards are mainly based on the fitness improvement brought by the corresponding operator to the individual it is applied to. However, the AOS problem is dynamic, whereas standard MAB algorithms are known to optimally solve the exploitation versus exploration trade-off in static settings. An original dynamic variant of the standard MAB Upper Conf idence Bound algorithm is proposed here, using a sliding time window to compute both its exploitation and exploration terms. In order to perform sound comparisons between AOS algorithms, artificial scenarios have been proposed in the literature. They are extended here toward smoother transitions between different reward settings. The resulting original testbed also includes a real evolutionary algorithm that is applied to the well-known Royal Road problem. It is used here to perform a thorough analysis of the behavior of AOS algorithms, to assess their sensitivity with respect to their own hyperparameters, and to propose a sound comparison of their performances.
Document type :
Journal articles
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Álvaro Fialho Connect in order to contact the contributor
Submitted on : Monday, September 20, 2010 - 5:03:13 PM
Last modification on : Thursday, July 8, 2021 - 3:47:51 AM
Long-term archiving on: : Thursday, June 30, 2011 - 1:29:35 PM


Files produced by the author(s)




Álvaro Fialho, Luis da Costa, Marc Schoenauer, Michèle Sebag. Analyzing bandit-based adaptive operator selection mechanisms. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2010, 60 (1), pp.25-64. ⟨10.1007/s10472-010-9213-y⟩. ⟨inria-00519579⟩



Les métriques sont temporairement indisponibles