Projet ANR PRC Combo

2024 - 2028

Combo




Objectif général du projet

Si les métaheuristiques constituent une approche efficace pour résoudre des problèmes combinatoires complexes, dont les fonctions objectif sont difficiles --- voire impossibles --- à optimiser analytiquement de manière satisfaisante, elles continuent néanmoins de soulever des interrogations quant à leurs propriétés. En particulier, en comparaison des méthodes d'optimisation globale (continue) basées sur une philosophie de descente de gradient dans l'espace de recherche, les métaheuristiques ne disposent pas toujours de garantie de convergence dans les espaces discrets, et sont souvent peu sample-efficient du fait de leur manque de guidage. Dans ce projet, nous proposons de nous appuyer sur les énormes progrès récents de l'apprentissage de représentations (notamment via des architectures neuronales type Transformers) pour reconsidérer le recours à des encodages continus de l'espace de recherche, et établir des méthodes d'exploration mieux guidées en fonction de l'objectif fixé. En particulier, nous proposons de contourner les limitations des métaheuristiques classiques par la modélisation du paysage d'optimisation selon une distribution cible globale, où la masse de probabilité est distribuée en fonction des valeurs respectives des solutions de l'espace support. L'approximation de ce type de distributions est rendue possible par l'émergence d'outils efficaces pour le transport de particules dans des espaces continus, dont on ambitionne de tirer parti pour l'optimisation combinatoire (OC) multimodale. Le projet vise à définir des synergies entre l'apprentissage de représentation et l'optimisation boîte noire (i.e., sans information a priori sur la fonction objectif à optimiser), dans un cadre théorique probabiliste.

Lien slides présentation projet

Equipe

Equipe_projet_Combo

Publications

  1. Emergence of Strategies for Univariate Estimation-of-Distribution Algorithms with Evolved Neural Networks (O. Goudet, A. Goëffon, F. Saubion, S. Verel). 2024. GECCO '24 Companion: Genetic and Evolutionary Computation Conference. Melbourne, VIC, Australia. pdf.
  2. Emergence of new local search algorithms with neuro-evolution (O. Goudet, M. S. Amri Sakhri, A. Goëffon, F. Saubion). 2024. European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar). Aberystwyth, United Kingdom. pdf. Source Code .
  3. A Large Population Island Framework for the Unconstrained Binary Quadratic Problem (O Goudet, A Goëffon, JK Hao). 2024. Computers and Operations Research. pdf . Source Code .