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.
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

https://hal.inria.fr/inria-00519579
Contributeur : Álvaro Fialho <>
Soumis le : lundi 20 septembre 2010 - 17:03:13
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:29:35

Fichier

banditAOS-AMAI10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Á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〉

Partager

Métriques

Consultations de la notice

645

Téléchargements de fichiers

1297