Algorithme à estimation de distribution - Définition

Le monde de l'estimation de distribution

Exemple de problème d'optimisation difficile, que les métaheuristiques (comme l'estimation de distribution) tentent de résoudre. Le but est ici de trouver l'optimum global (ayant la valeur la plus basse), uniquement à partir des informations données par un échantillonnage ponctuel d'une fonction objectif.

Historique

• 1965 : Rechenberg conçoit le premier algorithme utilisant des stratégies d'évolution.
• 1975 : travaillant sur les automates cellulaires, Holland propose les premiers algorithmes génétiques.
• 1990 : Les algorithmes de colonie de fourmis sont proposées par Marco Dorigo, dans sa thèse de doctorat.
• 1994 : S. Baluja s'inspire des algorithmes évolutionnaires et propose l’apprentissage incrémental à population (« Population Based Incremental Learning », PBIL).
• 1996 : Mühlenbein et Paaß proposent les algorithme à estimation de distribution.

Variantes

Les variantes les plus connues de l'estimation de distribution sont l'apprentissage incrémental à population (« Population Based Incremental Learning », PBIL), l'algorithme à distribution marginale univariée (« Univariate Marginal Distribution Algorithm », UMDA) ou encore l'algorithme génétique compact (« Compact Genetic Algorithm », CGA).

Il existe également des variantes utilisant des mécanismes de partitionnement de données pour l'optimisation multimodale, des adaptations au calcul parallèle, etc.

De par la place centrale du côté probabiliste, l'estimation de distribution partage de nombreux points communs avec les stratégies d'évolution, une des premières métaheuristique proposée, et les algorithmes de colonie de fourmis. Mais on peut également pointer les similarités avec le recuit simulé (qui utilise la fonction objectif comme distribution de probabilité pour construire un échantillon) et les algorithmes génétiques, dont les algorithmes à estimation de distribution sont issues, et dont ils utilisent toujours les opérateurs de sélection.

Exemple de distribution univariante obtenue à l'aide d'un mélange de deux noyaux gaussiens.

De la même façon, on trouve de nombreux points communs entre ces métaheuristiques d'optimisation et les outils de l'apprentissage automatique, comme les méthodes utilisant des arbres de décision ou des modèles de mélanges gaussiens. La différence est parfois difficile à préciser ; on peut en effet rencontrer des métaheuristiques effectuant des tâches d'apprentissage, des méthodes d'apprentissage résolvant des problèmes d'optimisation difficile, ou encore des outils d'apprentissage utilisés au sein de métaheuristiques.