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
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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.
Type de document :
Article dans une revue
Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2010, 60 (1), pp.25-64. 〈10.1007/s10472-010-9213-y〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger
Contributeur : Álvaro Fialho <>
Soumis le : lundi 20 septembre 2010 - 17:03:13
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:29:35


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers