Adaptive Operator Selection for Optimization

Selection Adaptative d'Operateurs pour l'Optimisation

Álvaro Fialho (1)

1 MSR - INRIA - Microsoft Research - Inria Joint Centre

Evolutionary Algorithms have demonstrated their ability to address a wide range of optimization problems; but their performance relies on tuning a few parameters, depending on the problem at hand. During this thesis work, we have focused on the development of tools to automatically set some of these parameters, using machine learning techniques. More specifically, we have worked on the following sub-problem: given a number of available variation operators, it consists in selecting which is the best operator to be applied at each moment of the search, based on how the operators have performed up to the given time instant of the current search/optimization process. This approach is applied online, i.e., while solving the problem, using only the history of the current run to evaluate and decide between the operators; this paradigm is commonly referred to as Adaptive Operator Selection (AOS). To do AOS, we need two components: a Credit Assignment scheme, that defines how to reward the operators based on their impact in the search process, and an Operator Selection mechanism that, based on the rewards received, decides which is the best operator to be applied next. The contributions of this thesis, in summary, lie in the proposal and analysis of schemes to solve the AOS problem based on the Multi-Armed Bandit (MAB) paradigm; we have proposed different techniques, in order to enable a MAB algorithm to efficiently cope with the dynamics of evolution and with the very different characteristics of the problems to be tackled. The latest one, referred to as AUC-MAB, is able to efficiently control the application of operators, while being robust with respect to its own parameters.

Les Algorithmes Évolutionnaires sont des algorithmes d'optimisation qui ont déjà montré leur efficacité dans plusieurs domaines; mais leur performance dépend du réglage de plusieurs paramètres. Cette thèse est consacrée au développement de techniques pour automatiser ce réglage par le biais de l'apprentissage automatique. Plus spécifiquement, nous avons travaillé sur un sous-problème: étant donné un ensemble d'opérateurs, cela consiste à choisir lequel doit être appliqué pour la génération de chaque nouvelle solution, basé sur la performance connue de chaque opérateur. Cette approche est utilisée en ligne, au cours de la résolution du problème, en utilisant exclusivement l'histoire du processus d'optimisation courant pour décider parmi les différents opérateurs; ce paradigme est couramment référencé comme Sélection Adaptative d'Opérateurs (SAO). Pour faire de la SAO, deux composants sont nécessaires. L'Affectation de Crédit définit comment récompenser les opérateurs selon l'impact de leur application sur le processus de recherche. La Sélection d'Opérateurs règle leur choix selon les récompenses reçues ultérieurement. En résumé, la contribution principale de cette thèse consiste dans la proposition et l'analyse de différentes approches pour la SAO, basées sur le paradigme de Bandit Manchot (BM); nous avons proposé plusieurs modifications pour transformer un algorithme BM en une technique à la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caractéristiques des problèmes diverses. La dernière méthode, appelé AUC-MAB, est capable de suivre efficacement le meilleur opérateur sans nécessiter d'un réglage spécifique pour chaque problème.

Mots clés: evolutionary algorithms; on-line parameter control; adaptive operator selection; multi-armed bandits

Mots clés: algorithms évolutionnaires; contrôle de paramètres en-ligne; selection adaptative d'operateurs; bandit manchot

Domaines: Informatique [cs]

Álvaro Fialho. Adaptive Operator Selection for Optimization. Computer Science [cs]. Université Paris Sud - Paris XI, 2010. English. ⟨NNT : ⟩. ⟨tel-00578431⟩