Dynamic Multi-Armed Bandits and Extreme Value-based Rewards for Adaptive Operator Selection in Evolutionary Algorithms

Álvaro Fialho; Luis Da Costa; Marc Schoenauer; Michèle Sebag

Dynamic Multi-Armed Bandits and Extreme Value-based Rewards for Adaptive Operator Selection in Evolutionary Algorithms

Álvaro Fialho ^{1, *} Luis Da Costa ^{2, 3} Marc Schoenauer ^{1, 2, 3} Michèle Sebag ^{1, 2, 3}

* Corresponding author

1 MSR - INRIA - Microsoft Research - Inria Joint Centre

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

3 LRI - Laboratoire de Recherche en Informatique

Abstract : The performance of many efficient algorithms critically depends on the tuning of their parameters, which on turn depends on the problem at hand. For example, the performance of Evolutionary Algorithms critically depends on the judicious setting of the operator rates. The Adaptive Operator Selection (AOS) heuristic that is proposed here rewards each operator based on the extreme value of the fitness improvement lately incurred by this operator, and uses a Multi-Armed Bandit (MAB) selection process based on those rewards to choose which operator to apply next. This Extreme-based Multi-Armed Bandit approach is experimentally validated against the Average-based MAB method, and is shown to outperform previously published methods, whether using a classical Average-based rewarding technique or the same Extreme-based mechanism. The validation test suite includes the easy One-Max problem and a family of hard problems known as "Long k-paths".

Document type :

Conference papers

Domain :

Computer Science [cs] / Artificial Intelligence [cs.AI]

Complete list of metadatas

Cited literature [7 references] Display Hide Download

https://hal.inria.fr/inria-00377401
Contributor : Álvaro Fialho <>
Submitted on : Tuesday, June 23, 2009 - 1:19:22 AM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Wednesday, September 22, 2010 - 12:35:09 PM

Dynamic Multi-Armed Bandits and Extreme Value-based Rewards for Adaptive Operator Selection in Evolutionary Algorithms

Files

Identifiers

Collections

Citation

Export

Metrics

944

1057

Contact

Dynamic Multi-Armed Bandits and Extreme Value-based Rewards for Adaptive Operator Selection in Evolutionary Algorithms

Files

Identifiers

Collections

Citation

Export

Share

Metrics

944

1057

Contact