Apprentissage automatique pour la sélection d'algorithmes d'optimisation


Résumé

Ce projet, mené en collaboration avec l'Université de Shinshu au Japon, vise à étudier des modèles issus de l'apprentissage automatique afin de sélectionner l'algorithme le plus à même de résoudre efficacement un problème d'optimisation multi-objectif.

Projet Recherche
Mots clés : algorithmique, optimisation, apprentissage automatique
Équipe/Entité concernée : Équipe Bonus (CRIStAL / Inria), LIA MODŌ (France / Japon)
Sujet affecté à Maitrot Guillaume (MOCAD)

Encadrement

  • Arnaud Liefooghe (mail)
  • Bilel Derbel (mail)

Prérequis

  • algorithmique
  • optimisation multi-objectif
  • métaheuristiques
  • évolution artificielle
  • programmation et conception orientée-objet (Java ou C++ ou Python)
  • statistique et apprentissage automatique (R ou Python)

Localisation

Bâtiment M3
Inria

Contexte

Ce projet s'inscrit dans le cadre d'une coopération scientifique entre la France (CRIStAL, Université de Lille / Inria) et le Japon (Université de Shinshu à Nagano). Le LIA MODŌ (Laboratoire International Associé "Frontiers in Massive Optimization and Computational Intelligence") fédère une dizaine de chercheurs et jeunes-chercheurs partagés entre les établissements français et japonais et vise à poser les fondations et à développer un solveur autonome unifié capable de répondre, de façon globale et simultanée, aux différents défis soulevés par l'optimisation massive.

Problématique

Les problèmes d’optimisation d’aujourd’hui sont complexes et caractérisés par la grande dimensionnalité de leurs variables et objectifs, leur hétérogénéité, et leur nature coûteuse. En particulier, nous nous intéressons à l'élaboration de nouvelles techniques d’optimisation, conscientes de l’espace où elles opèrent, pour la résolution de problèmes d'optimisation multi-objectif larges et variés. Il existe un grand nombre d'algorithmes pour l'optimisation multi-objectif issus de la littérature. Cependant, leur efficacité dépend de nombreux facteurs, il s'avère donc indispensable de les configurer et de les adapter au mieux au problème à résoudre. Notre objectif est de comprendre les difficultés auxquelles un algorithme doit faire, et ce qui le rend efficace ou au contraire infructueux. Pour cela, une méthodologie basée sur l'analyse de paysage, le benchmarking, et l'apprentissage automatique nous permettrait non seulement de comprendre ce qui rend un problème difficile à résoudre, mais aussi de prévoir les performances de l'algorithme, de sélectionner la configuration la plus appropriée parmi un ensemble d'algorithmes, et d'en adapter et améliorer la conception pour la résolution de nouveaux problèmes.

Travail à effectuer

  • Cerner les bases de l'optimisation multi-objectif [ 5% du projet ]

  • Identifier les principaux algorithmes pour l'optimisation multi-objectif et prendre en main leur implémentation [ 15% du projet ]

  • Analyser et caractériser les instances de la littérature pour l'optimisation multi-objectif et leurs différences [ 10% du projet ]

  • Développer et adapter les algorithmes existants pour la résolution de ces instances [ 20% du projet ]

  • Expérimenter les algorithmiques et étudier leur comportement et leur efficacité en fonction des instances et de leurs caractéristiques [ 20% du projet ]

  • Élaborer un modèle d'apprentissage automatique visant à prédire quel algorithme utiliser en fonction des caractéristiques des instances considérées [ 20% du projet ]

  • Packaging des différents développements et documentation [ 10% du projet ]

    Bibliographie

    [1] Hernán E. Aguirre, Kiyoshi Tanaka. Working principles, behavior, and performance of MOEAs on MNK-landscapes. European Journal of Operational Research, vol. 181, n. 3, pp. 1670-1690, 2007
    http://doi.org/10.1016/j.ejor.2006.08.004

    [2] Nicola Beume, Boris Naujoks, Michael T. M. Emmerich. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, vol. 181, n. 3, pp. 1653-1669, 2007
    http://doi.org/10.1016/j.ejor.2006.08.008

    [3] Fabio Daolio, Arnaud Liefooghe, Sébastien Verel, Hernán Aguirre, Kiyoshi Tanaka. Problem features vs. algorithm performance on rugged multi-objective combinatorial fitness landscapes. Evolutionary Computation, 2017
    http://doi.org//10.1162/EVCO_a_00193

    [4] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation vol. 6, n. 2, pp. 182-197, 2002
    http://doi.org/10.1109/4235.996017

    [5] Katherine M. Malan, Andries P. Engelbrecht. Fitness Landscape Analysis for Metaheuristic Performance Prediction. Recent Advances in the Theory and Application of Fitness Landscapes, pp. 103-132, 2014
    http://doi.org/10.1007/978-3-642-41888-4_4

    [6] Sébastien Verel, Arnaud Liefooghe, Laetitia Jourdan, Clarisse Dhaenens. On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives. European Journal of Operational Research, vol. 227, n. 2, pp. 331-342, 2013
    http://dx.doi.org/10.1016/j.ejor.2012.12.019

    [7] Qingfu Zhang, Hui Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, vol. 11, n. 6, pp. 712-731, 2007
    http://doi.org/10.1109/TEVC.2007.892759

    Autres informations

    Ce projet pourra aboutir à un stage financé, en collaboration avec Shinshu University, à Lille et/ou au Japon, avec poursuite éventuelle en thèse