Analyzing bandit-based adaptive operator selection mechanisms - Archive ouverte HAL Access content directly
Journal Articles Annals of Mathematics and Artificial Intelligence Year : 2010

Analyzing bandit-based adaptive operator selection mechanisms

(1) , (2, 3) , (1, 2, 3) , (1, 2, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
banditAOS-AMAI10.pdf (607.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

Á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⟩
289 View
879 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More