Analyzing bandit-based adaptive operator selection mechanisms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Annals of Mathematics and Artificial Intelligence Année : 2010

Analyzing bandit-based adaptive operator selection mechanisms

Résumé

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.
Fichier principal
Vignette du fichier
banditAOS-AMAI10.pdf (607.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00519579 , version 1 (20-09-2010)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More