Adaptive Operator Selection with Dynamic Multi-Armed Bandits

Luis Da Costa 1, 2 Álvaro Fialho 3 Marc Schoenauer 1, 2, 3, * Michèle Sebag 1, 2, 3
* Auteur correspondant
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 : An important step toward self-tuning Evolutionary Algorithms is to design efficient Adaptive Operator Selection procedures. Such a procedure is made of two main components: a credit assignment mechanism, that computes a reward for each operator at hand based on some characteristics of the past offspring; and an adaptation rule, that modifies the selection mechanism based on the rewards of the different operators. This paper is concerned with the latter, and proposes a new approach for it based on the well-known Multi-Armed Bandit paradigm. However, because the basic Multi-Armed Bandit methods have been developed for static frameworks, a specific Dynamic Multi-Armed Bandit algorithm is proposed, that hybridizes an optimal Multi-Armed Bandit algorithm with the statistical Page-Hinkley test, which enforces the efficient detection of changes in time series. This original Operator Selection procedure is then compared to the state-of-the-art rules known as Probability Matching and Adaptive Pursuit on several artificial scenarios, after a careful sensitivity analysis of all methods. The Dynamic Multi-Armed Bandit method is found to outperform the other methods on a scenario from the literature, while on another scenario, the basic Multi-Armed Bandit performs best.
Type de document :
Communication dans un congrès
Genetic and Evolutionary Computation Conference (GECCO), Jul 2008, Atlanta, United States. pp.913-920, 2008, GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation. 〈10.1145/1389095.1389272〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00278542
Contributeur : Álvaro Fialho <>
Soumis le : mercredi 3 décembre 2008 - 14:12:09
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 11:12:27

Identifiants

Collections

Citation

Luis Da Costa, Álvaro Fialho, Marc Schoenauer, Michèle Sebag. Adaptive Operator Selection with Dynamic Multi-Armed Bandits. Genetic and Evolutionary Computation Conference (GECCO), Jul 2008, Atlanta, United States. pp.913-920, 2008, GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation. 〈10.1145/1389095.1389272〉. 〈inria-00278542v2〉

Partager

Métriques

Consultations de la notice

506

Téléchargements de fichiers

1107