Doctorat
Equipe : Apprentissage et Optimisation
Analyse en cas moyen d'algorithmes d'apprentissage et d'optimisation
Début le 01/10/2005
Direction : SEBAG, Michèle
[CORNUEJOLS Antoine]
Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI
Soutenue le 21/12/2009 devant le jury composé de :
Frédéric Bonnans, Directeur de Recherche INRIA au CMAP, Ecole Polytechnique (examinateur)
Hansen Nikolaus, Chargé de Recherche INRIA au LRI (directeur de thèse)
Le Riche Rodolphe, Chargé de Recherche CNRS à l'Ecole des Mines de Saint-Etienne (rapporteur)
Rudolph Günter, Professeur à la TU Dortmund University (rapporteur)
et Sebag Michèle, Directeur de Recherche CNRS au LRI (directeur de thèse).
Activités de recherche :
Résumé :
Un problème d'optimisation continue peut se définir ainsi : étant donné une fonction objectif de R à la puissance n dans R, chercher un vecteur de dimension n qui minimise la fonction jusqu'à une précision arbitraire. Dans ce contexte, le scénario boîte noire (Black-Box) fait l'hypothèse que seule l'évaluation de la fonction est disponible pour guider son optimisation.
Dans un premier temps, nous étudions le Covariance Matrix Adaptation-Evolution Strategy (CMA-ES) qui est un algorithme reconnu de Black-Box Optimisation (BBO). Nous montrons ses limites en terme de complexité spatio-temporelles pour les problèmes à haute dimensionalité. Pour passer outre ces limites, nous proposons des variantes de CMA-ES ne mettant à jour que des blocs diagonaux de la matrice de covariance et exploitant la séparabilité du problème. Même sur des fonctions non-séparables, ces variantes démontrent de meilleures performances que le CMA-ES si la dimension du problème est grande.
Dans un second temps, nous définissons et exploitons le cadre expérimental BBO Benchmarking (BBOB) dans lequel il est possible de comparer des algorithmes sur des fonctions. Nos résultats montrent une dépendance avec le budget (nombre d'évaluations de la fonction) alloué à l'optimisation. Des méthodes comme NEWUOA ou BFGS sont plus appropriées pour les budgets réduits alors qu'une approche CMA-ES avec redémarrage et gestion de la taille de la population montre de bons résultats pour un budget plus conséquent.
Le logiciel COmparing Continuous Optimisers (COCO) utilisé pour BBOB est décrit en détail en dernier lieu. COCO implémente notre procédure expérimentale et génère les résultats exploités dans ce manuscrit.
Mots-clés :
Optimisation continue, banc d'essai, comparaison empirique, algorithmes évolutionnaires
