Algorithmes d'estimation de distribution

Les algorithmes d'estimation de distribution (EDA) sont un paradigme du calcul évolutionnaire dans lequel les opérateurs génétiques traditionnels (croisement et mutation) sont remplacés par la construction et l'échantillonnage d'un modèle probabiliste des solutions prometteuses trouvées jusqu'à présent. Ma recherche sur les EDA s'étend de leurs fondements théoriques à leur application à des problèmes complexes du monde réel. Je suis co-auteur de la monographie Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Springer, 2002), et ma thèse de doctorat était consacrée à l'étude des EDA.

Fondements des EDA

Fondements théoriques

Les EDA comblent le fossé entre la modélisation probabiliste et la recherche évolutionnaire. Plutôt que de combiner des solutions parentes via des opérateurs de croisement et de mutation, les EDA apprennent un modèle probabiliste des meilleurs individus de la population, puis échantillonnent de nouveaux individus à partir de ce modèle. Cette approche rend explicites les dépendances entre les variables du problème et les exploite pour guider la recherche.

Mes premières recherches se sont concentrées sur les propriétés théoriques des EDA, analysant leur comportement de convergence, la qualité des modèles qu'ils apprennent et la relation entre la structure du problème et la performance de l'algorithme. Cela inclut l'étude de l'apprentissage du couplage (linkage learning) et la conception d'EDA capables d'identifier et d'exploiter les interactions entre variables.

Taxonomie des EDA

Les EDA peuvent être classés selon la complexité du modèle probabiliste utilisé. Les EDA univariés (tels que UMDA et PBIL) supposent l'indépendance des variables. Les EDA bivariés (tels que MIMIC et BMDA) peuvent capturer des dépendances par paires. Les EDA multivariés (tels que BOA, EBNA et ECGA) utilisent des modèles graphiques probabilistes complets — réseaux bayésiens ou réseaux de Markov — pour représenter des dépendances d'ordre supérieur entre les variables.

EDA discrets et combinatoires

EDA basés sur les réseaux bayésiens

L'algorithme d'estimation de réseaux bayésiens (EBNA) et ses variantes utilisent des réseaux bayésiens comme modèle probabiliste dans la boucle EDA. L'algorithme apprend la structure et les paramètres d'un réseau bayésien à partir de la population sélectionnée, puis échantillonne de nouvelles solutions candidates à partir du réseau appris.

La recherche sur les EDA à base de réseaux bayésiens a abordé le problème de l'apprentissage structurel (trouver un réseau qui représente précisément les dépendances dans les données), le coût computationnel de l'apprentissage et de l'échantillonnage du réseau, et l'analyse théorique des modèles appris pendant le processus de recherche.

EDA basés sur les réseaux de Markov

Recherche sur l'utilisation des réseaux de Markov (modèles graphiques non orientés) comme modèle probabiliste dans les EDA. Les EDA à réseaux de Markov peuvent représenter des dépendances symétriques entre les variables, ce qui les rend particulièrement appropriés pour les problèmes à structure symétrique. Cette ligne de recherche comprend le développement d'algorithmes d'apprentissage pour les EDA à réseaux de Markov et leur évaluation sur des problèmes de benchmark.

EDA pour l'optimisation combinatoire

Application des EDA à des problèmes difficiles d'optimisation combinatoire, incluant des problèmes de permutation (tels que le problème d'affectation quadratique, le problème du voyageur de commerce et les problèmes d'ordonnancement), les problèmes d'optimisation pseudo-booléenne et l'optimisation combinatoire multi-objectif. Un défi majeur dans ce domaine est la conception de modèles probabilistes appropriés pour les représentations de solutions structurées.

EDA continus

EDA continus basés sur la distribution gaussienne

Extension des EDA aux domaines d'optimisation continue utilisant des distributions de probabilité gaussiennes. Les EDA gaussiens univariés modélisent chaque variable indépendamment avec une distribution gaussienne. Les EDA gaussiens multivariés (tels que EGNA) utilisent des distributions gaussiennes multivariées pour modéliser les dépendances entre les variables. La recherche a examiné comment la structure de covariance du modèle gaussien se rapporte à la structure du paysage de fitness.

EDA continus basés sur les copules

Développement d'EDA utilisant des fonctions copules pour modéliser la distribution conjointe de variables continues. Les copules permettent de modéliser séparément les distributions marginales et la structure de dépendance, offrant une plus grande flexibilité que les modèles gaussiens standard. Cette ligne de recherche inclut les EDA à copules vine qui modélisent des dépendances multivariées complexes à l'aide de séquences de copules bivariées.

ACM TELO 2024 →

Optimisation paramétrique des systèmes énergétiques

Application des EDA continus à l'optimisation paramétrique des centrales géothermiques et d'autres systèmes d'ingénierie. L'objectif est d'optimiser les paramètres de fonctionnement de systèmes physiques complexes pour maximiser l'efficacité ou minimiser les coûts. Les EDA continus offrent une approche structurée pour ce type de problème d'optimisation en boîte noire.

CIIS 2024 →

Analyse des modèles EDA

Ce que les EDA apprennent

Une question de recherche centrale dans l'étude des EDA est : quelle information est capturée dans les modèles probabilistes appris pendant la recherche évolutionnaire ? La recherche a examiné la relation entre le modèle appris par l'EDA et la structure du paysage de fitness, les interactions entre variables dans le problème et les propriétés des solutions optimales.

Les modèles EDA comme représentations de problèmes

Les modèles probabilistes appris par les EDA peuvent être vus comme des représentations compressées de la structure du problème d'optimisation. La recherche a étudié comment extraire des informations utiles de ces modèles au-delà de leur rôle dans la génération de nouvelles solutions candidates. Cela inclut l'utilisation de modèles EDA pour identifier les interactions de variables pertinentes, détecter les symétries du problème et initialiser à chaud (warm-start) de futures exécutions d'optimisation.

Applications

Les EDA pour l'apprentissage automatique

Application des EDA à des tâches d'apprentissage automatique, incluant la sélection de caractéristiques, la recherche d'architecture neuronale et l'optimisation des hyperparamètres. Le modèle probabiliste d'un EDA capture naturellement les dépendances entre les caractéristiques ou les composants de l'architecture, permettant à la recherche d'exploiter ces dépendances pour une exploration plus efficace.

Les EDA pour le calcul scientifique

Application des EDA à des problèmes de calcul scientifique, incluant l'estimation de paramètres pour des équations différentielles stochastiques modélisant des systèmes financiers ou des processus physiques, la prédiction de la structure des protéines et la conception d'expériences. Les EDA offrent une approche structurée pour l'optimisation en boîte noire dans ces domaines.

Math. & Computers in Simulation 2021 →

Publications sélectionnées