Adaptive operator selection for optimization
Silvestre Fialho, Álvaro Roberto · 2010
Les Algorithmes Evolutionnaires sont des algorithmes d'optimisation qui ont deja montre leur efficacite dans plusieurs domaines ; mais leur performance depend du reglage de plusieurs parametres. Cette these est consacree au developpement de techniques pour automatiser ce reglage par le biais de l'apprentissage automatique. Plus specifiquement, nous avons travaille sur un sous-probleme : etant donne un ensemble d'operateurs, cela consiste a choisir lequel doit etre applique pour la generation de chaque nouvelle solution, base sur la performance connue de chaque operateur. Cette approche est utilisee en ligne, au cours de la resolution du probleme, en utilisant exclusivement l'histoire du processus d'optimisation courant pour decider parmi les differents operateurs ; ce paradigme est couramment reference comme Selection Adaptative d'Operateurs (SAO). Pour faire de la SAO, deux composants sont necessaires. L'Affectation de Credit definit comment recompenser les operateurs selon l'impact de leur application sur le processus de recherche. La Selection d'Operateurs regle leur choix selon les recompenses recues ulterieurement. En resume, la contribution principale de cette these consiste dans la proposition et l'analyse de differentes approches pour la SAO, basees sur le paradigme de Bandit Manchot (BM) ; nous avons propose plusieurs modifications pour transformer un algorithme BM en une technique a la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caracteristiques des problemes diverses. La derniere methode, appele AUC-MAB, est capable de suivre efficacement le meilleur operateur sans necessiter d'un reglage specifique pour chaque probleme.