Algorithmes probabilistes

Algorithmes :


Introduction

Les algorithmes probabilistes sont les algorithmes qui modélisent un problème ou recherchent un espace de problème à l’aide d’un modèle probabiliste de solutions candidates. De nombreux algorithmes de métaheuristique et d’intelligence computationnelle peuvent être considérés comme probabilistes, bien que la différence avec les algorithmes soit l’utilisation explicite (plutôt qu’implicite) des outils de probabilité dans la résolution de problèmes.

Estimation of Distribution Algorithms (EDA) also called Probabilistic Model-Building Genetic Algorithms (PMBGA) are an extension of the field of Evolutionary Computation that model a population of candidate solutions as a probabilistic model. They generally involve iterations that alternate between creating candidate solutions in the problem space from a probabilistic model, and reducing a collection of generated candidate solutions into a probabilistic model.

The model at the heart of an EDA typically provides the probabilistic expectation of a component or component configuration comprising part of an optimal solution. This estimation is typically based on the observed frequency of use of the component in better than average candidate solutions. The probabilistic model is used to generate candidate solutions in the problem space, typically in a component-wise or step-wise manner using a domain specific construction method to ensure validity.