Fondements théoriques des algorithmes multivariés à estimation de distribution – MultiEDA

Les algorithmes à estimation de la distribution (AED) sont des heuristiques d’optimisation à usage général qui font évoluer de manière itérative un modèle probabiliste du domaine de recherche. Peu après leur création il y a plus de 20 ans, les AED utilisés dans la pratique ont capturé des dépendances complexes (multivariées) entre les variables du problème via des réseaux bayésiens, ce qui leur a permis de résoudre des problèmes d’optimisation difficiles et de fournir des informations sur l’espace du problème. En revanche, à ce jour, toutes les garanties théoriques de ces AED supposent l’indépendance (c’est-à-dire des dépendances univariées) entre toutes les variables du problème.

Avec ce projet, nous réduirons cet énorme fossé entre la théorie et la pratique et prouverons les premiers résultats théoriques pour de telles AED multivariées. À cette fin, nous étendons naturellement les résultats connus pour les AED univariées en incorporant des degrés de dépendance croissants. Ceci constitue une étape importante pour la théorie des AED et pour le domaine théorique des heuristiques d’optimisation aléatoire dans son ensemble.