Apprentissage automatique pour la résolution de problèmes d'optimisation coûteux


Résumé

Ce projet, mené en collaboration avec City University à Hong Kong, vise à intégrer des modèles issus de l'apprentissage automatique pour l'analyse et la conception de nouvelles méthodes algorithmiques, afin d'en accélérer la convergence.

Projet Recherche
Mots clés : algorithmique, optimisation, apprentissage automatique
Équipe/Entité concernée : Équipe Bonus (CRIStAL / Inria), ANR BigMO (France / Hong Kong)
Sujet affecté à Ryckewaert Valentin (IAGL)

Encadrement

  • Bilel Derbel (mail)
  • Arnaud Liefooghe (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 Hong Kong (City University). Le projet ANR BigMO ("Big Multi-objective Optimization") fédère une dizaine de chercheurs et jeunes-chercheurs partagés entre les établissements français et hongkongais et vise à combiner la théorie et les techniques issus du calcul évolutionnaire, de l'apprentissage automatique, de l'optimisation et de l'utilisation de plates-formes parallèles modernes pour développer des solveurs efficaces pour l'optimisation multi-objectif.

Problématique

Le projet vise à étudier de nouvelles approches alliant des techniques d'apprentissage automatique (Machine Learning) aux techniques d'optimisation multi-objectif basées sur la décomposition afin d'accélérer la convergence et la qualité des algorithmes existants. En effet, l'idée est de décomposer un problème d'optimisation multi-objectif en plusieurs sous-problèmes mono-objectif (en utilisant des fonctions scalaires) et de résoudre ces sous-problèmes de façon collaborative. Ceci est notamment le cas d'algorithmes existants et faisant référence dans le domaine, tel que MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition). La nouveauté vient dans l'incorporation de techniques d'apprentissage pour la résolution de ces sous-problèmes. En effet, en disposant d'un ensemble de sous-problèmes plus facile à résoudre, il devient plus aisé d'utiliser des modèles et des algorithmes d'apprentissage pour prédire la qualité d'un ensemble de solutions nouvellement créées, sans pour autant les évaluer, c'est-à-dire sans calculer les fonctions (coûteuses) définissant le problème à optimiser. Le but est donc double: (i) gagner en temps de calcul puisque seules les solutions prometteuses seront effectivement évaluées, et (ii) gagner en qualité et en convergence puisque les solutions de mauvaises qualités seront préalablement filtrées lors de l'étape de prédiction.

Travail à effectuer

Le travail à mener dans le cadre de ce projet permettra de concevoir et d'analyser de nouvelles approches d'optimisation multi-objectif dédiées au contexte où les fonctions d'évaluation sont coûteuse en temps de calcul. Plus précisément, les contributions suivantes sont attendues :

  • Incorporer de nouvelles stratégies inspirées de l'apprentissage automatique aux techniques d'optimisation multi-objectif

  • Coupler des modèles d'apprentissage (Surrogate Models) à des algorithmes de calcul évolutionnaire en particulier ceux utilisant la décomposition

  • Développer un cadre générique permettant l'expérimentation des différentes variantes ainsi conçues pour différents problèmes académiques issus de l'optimisation multi-objectif

  • Analyser statistiquement la performance de différentes techniques d'apprentissage automatique dans le cadre de la résolution de problèmes d'optimisation multi-objectif

  • Étudier de façon approfondie et analyser statistiquement la performance et le comportement de différentes variantes d'algorithmes ainsi obtenues en se basant sur des indicateurs de performance spécifiques à l'optimisation multi-objectif

  • Concevoir au moins une variante algorithmique améliorant la performance des algorithmes existants, que ce soit en terme de qualité de solutions obtenues ou en terme de temps de calcul

    Bibliographie

    [1] Y. Jin, “Surrogate-assisted evolutionary computation : Recent advances and future challenges,” Swarm and Evolutionary Computation, vol. 1, no. 2, pp. 61–70, 2011

    [2] J. Knowles, “ParEGO : A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems,” Trans. Evol. Comp, vol. 10, pp. 50–66, Sept. 2006.

    [3] Y. S. Liau, K. C. Tan, J. Hu, X. Qiu, and S. B. Gee, “Machine learning enhanced multi-objective evolutionary algorithm based on decomposition,” in Intelligent Data Engineering and Automated Learning–IDEAL 2013, pp. 553–560, Springer, 2013.

    [4] B. Liu, Q. Zhang, and G. Gielen, “A gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems,” Evolutionary Computation, IEEE Transactions on, vol. 18, pp. 180–192, April 2014.

    [5] I. Loshchilov, M. Schoenauer, and M. Sebag, “A Mono Surrogate for Multiobjective Optimization,” in Genetic and Evolutionary Computation Conference 2010 (GECCO-2010), (Portland, OR, United States), July 2010.

    [6] S. Zapotecas Martínez and C. A. Coello Coello, “MOEA/D assisted by RBF networks for expensive multi-objective optimization problems,” in Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO ’13, (New York, NY, USA), pp. 1405–1412, ACM, 2013.

    [7] Q. Zhang and H. Li, “MOEA/D : A multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.

    [8] Q. Zhang, W. Liu, E. Tsang, and B. Virginas, “Expensive multiobjective optimization by MOEA/D with gaussian process model,” Evolutionary Computation, IEEE Transactions on, vol. 14, pp. 456–474, 2010.

    Autres informations

    Ce projet pourra aboutir à un stage financé, en collaboration avec City University, à Lille et/ou à Hong Kong, avec poursuite éventuelle en thèse