5. Algorithme à estimation de distributionKHODJA Mohamed

5. Algorithme à estimation de distribution

Les algorithmes à estimation de distribution forment une famille de métaheuristiques inspirée des algorithmes génétiques.

À l'inverse des algorithmes évolutionnaires "classiques", le cœur de la méthode consiste à estimer les relations entre les différentes variables d'un problème d'optimisation, grâce à l'estimation d'une distribution de probabilité, associée à chaque point de l'échantillon.

5.1 Définition

5. Algorithme à estimation de distribution

Le vocabulaire lié aux algorithmes à estimation de distribution est emprunté à celui des algorithmes évolutionnaires, on parlera donc de « population d'individus » plutôt que d'« échantillon de points », ou de « fitness » plutôt que de « fonction objectif », néanmoins, tous ces termes ont la même signification.

5.1 Définition

Afin d’optimiser la fonction objectif , par l’AED on applique l’algorithme suivant : Tirer au hasard M individus, pour former une

population D0. i = 0 Tant qu'un critère d'arrêt n'est pas vérifié : ▪ i = i + 1 ▪ Sélectionner N individus (avec N < M) dans la population

précédente (Di − 1), pour former la population :

▪ Estimer une distribution de probabilité , décrivant la répartition de la population .

▪ Tirer au hasard M individus dans . Fin de la boucle.

5. Algorithme à estimation de distribution5.2 Algorithme

5. Algorithme à estimation de distribution5.2 Algorithme

Avec:• P : la population.• PS : les points

sélectionné • PDe : Distribution de

PS.• PDu : Distribution de

P.Dans cet exemple, on optimise une fonction objectif continue f(X), ayant un seul optimum O. Au fur et à mesure du déroulement de l'algorithme, l'échantillonnage (suivant une loi normale N) se concentre autour de l'optimum.

Dans le problème du « one max », on cherche à maximiser le nombre de 1 sur un nombre de dimensions donné.

Pour un problème à 3 dimensions, une solution aura donc une meilleure qualité qu'une solution

On cherche donc à maximiser une fonction , où peut prendre la valeur 0 ou 1.

Etape 1: Tirer au hasard les individus, avec pour chaque variable,

une chance sur deux de tirer un 1 ou un 0. Avec : et est la probabilité que chaque élément soit

égal à 1

5. Algorithme à estimation de distribution5.3 Exemple « one max »

Population de 6 individus la dernière ligne indique la probabilité pour chaque variable

5. Algorithme à estimation de distribution5.3 Exemple « one max »

)

1 0 1 0 1

2 0 1 0 1

3 1 0 1 2

4 1 0 1 2

5 0 1 1 2

6 1 0 0 1

0.5 0.5 0.5

Etape 2: la sélection des meilleurs

individus, pour former Dans notre exemple, il s'agit simplement de ne garder que les 3 meilleurs individus.

Population de 6 individus la dernière ligne indique la probabilité pour chaque variable

5. Algorithme à estimation de distribution5.3 Exemple « one max »

)

1 0 1 0 1

2 0 1 0 1

3 1 0 1 2

4 1 0 1 2

5 0 1 1 2

6 1 0 0 1

0.5 0.5 0.5

Etape 2: la sélection des meilleurs

individus, pour former Dans notre exemple, il s'agit simplement de ne garder que les 3 meilleurs individus.

5. Algorithme à estimation de distribution5.3 Exemple « one max »

)

3 1 0 1 2

4 1 0 1 2

5 0 1 1 2

0.7 0.3 1

Les trois paramètres () caractérisant la distribution de probabilité ( ) ont changé après la sélection.

En utilisant cette nouvelle distribution, on peut tirer une nouvelle population.

5. Algorithme à estimation de distribution5.3 Exemple « one max »

On obtient la nouvelle population :

Et ainsi de suite jusqu'à vérifier un critère d'arrêt (par exemple quand tous les individus sont à l'optimum, comme l'individu 1 ).

)

1 1 1 1 3

2 0 1 1 2

3 1 0 1 2

4 1 0 1 2

5 1 0 1 2

6 0 0 1 1

0.7 0.3 1

Le graphique représente les distributions des valeurs des optimums trouvés (sur un grand nombre d'exécutions) : l'algorithme passe d'une population de solution très dispersée (A) à une population plus centrée sur l'optimum trouvé (B).

5. Algorithme à estimation de distribution5.4 Comportement

Il a été démontré (généralement à l'aide de modèles de Markov ou de systèmes dynamiques) que la plupart des versions pour l'optimisation combinatoire sont convergentes (c’est-à-dire qu'elles peuvent trouver l'optimum en un temps fini).

5. Algorithme à estimation de distribution5.4 Comportement

Le comportement des algorithmes à estimation de distribution repose en grande partie sur le choix du modèle de distribution utilisé pour décrire l'état de la population.

Les modèles sont classifiés en fonction de leur degré de prise en compte des dépendances entre les variables : Modèles sans dépendances, Modèles avec dépendances bi-variantes, Modèles avec dépendances multi-variantes.

Dans le cas des modèles sans dépendances, la distribution de probabilité est construite à partir d'un ensemble de distributions définies sur une seule variable. Dis autrement, la distribution est factorisée à partir de distributions univariantes, indépendantes sur chaque variable.

5. Algorithme à estimation de distribution5.5 Modèles de distributions

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) l'algorithme génétique compact (« Compact Genetic

Algorithm », CGA).

5. Algorithme à estimation de distribution5.6 Variantes

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étaheuristiques proposées, 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.

5. Algorithme à estimation de distribution5.6 Variantes

fr.wikipedia.org Métaheuristiques d'optimisation vues sous

l'angle de l'échantillonnage de distribution - Johann Dré, Patrick Siarry

5. Algorithme à estimation de distribution5.7 Bibliographie