Les algorithmes à estimation de distribution - EDA

 3. Les algorithmes à estimation de distribution -EDA

3.1 L’optimisation avec les EDA

3.1.1 Définitions

•     Les algorithmes à estimation de distribution forment une famille de méta-heuristiques 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.

•     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.

3.1.2 Algorithme

3.2 L’optimisation combinatoire avec les EDA

3.2.3 Exemple « one max »

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 𝑥₁={1,1,0}  aura donc une meilleure qualité qu'une solution 𝑥₂ = {0,1,0}

On cherche donc à maximiser une fonction 𝑓(𝑥)= ∑³_𝑖=1 𝑥_i, 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 : 𝑃_𝑜(𝑥)= Π³_𝑖=1 P₀(𝑥_𝑖) et P_𝑜(𝑥_𝑖) est la probabilité que chaque élément soit égal à 1

·         Population D₀ de 6 individus

·         la dernière ligne indique la probabilité (𝑥) pour chaque variable

  

i	X1	X2	X3	F(x)
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
	1/2	1/2	1/2

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 D₀ de 6 individus
• la dernière ligne indique la probabilité p(𝑥) pour chaque variable

i	X1	X2	X3	F(x)
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
	1/2	1/2	1/2

Etape3:

·         la sélection des meilleurs individus, pour former 𝐷₁^𝑠, Dans notre exemple, il s'agit simplement de ne garder que les 3 meilleurs individus.

i	X1	X2	X3	F(x)
3	1	0	1	2
4	1	0	1	2
5	0	1	1	2
	2/3	1/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.

i	X1	X2	X3	F(x)
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
	2/3	1/3	1

·         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).