334
11 Optimisation et Combinatoire ´ enum´ erative
11.5 Quelques variantes
Commen¸ cons par examiner la situation o` u l’ensemble “cible” A s’exprime
comme une intersection de m sous ensembles B i ⊂ E
A = ∩
m
i=1 B i
Dans ces conditions, on peut poser dans (11.3)
A 0 = E ⊃ A 1 = B 1 ⊃ A 2 = (B 1 ∩ B 2 ) ⊃ . . . ⊃ A m = ∩
m
i=1 B i
ou encore pour toute permutation σ ∈ G m de l’ensemble {1, . . . , m} :
A 0 = E ⊃ A 1 = B σ(1) ⊃ A 2 =
B σ(1) ∩ B σ(2)
⊃ . . . ⊃ A m = ∩
m
i=1 B σ(i)
Une autre solution est de consid´ erer les mesures de Boltzmann-Gibbs
Ψ G (μ)(dx) =
1
μ (e −βV )
e
−βV (x) μ(dx)
avec la mesure de comptage μ sur E et la fonction de p´ enalisation :
V (x) =
m
i=1
1 E−Ai (x)
Les algorithmes de simulation particulaires associ´ es ` a chacune de ces formulations peuvent ˆ etre d´ ecrits ais´ ement.
Dans un autre registre, dans la section 8.3 nous avons aussi vu qu’il ´ etait
possible de remplacer dans les formules de Feynman-Kac (11.4) et (11.5) les
triplets
(g k , M k , E k ) = (1 A k+1 , M k , E)
par les triplets corrig´ es ( g k ,
M k ,
E k ) d´ ecrits ci-dessous :
E k = {x ∈ E : g k (x) > 0} = A k+1
M k (x, y) :=
M k (x, y)1 A k+1 (y)
M k (x, A k+1 )
∀x ∈
E k−1 = A k
et
∀x ∈
E k = A k+1
g k (x) := M k+1 (g k+1 )(x) = M k+1 (x, A k+2 )
(11.9)
L’algorithme g´ en´ etique correspondant est fond´ e sur des
M k -mutations et
des
g k -s´ elections. Lorsque ces objets sont difficiles ` a calculer et/ou ` a simuler,
on pourra utiliser les formules d’approximations (8.17) d´ ecrites `
a la page 235.
Dans le contexte pr´ esent, ces formules d’approximation sont fond´ ees sur la
11 Optimisation et Combinatoire ´ enum´ erative
11.5 Quelques variantes
Commen¸ cons par examiner la situation o` u l’ensemble “cible” A s’exprime
comme une intersection de m sous ensembles B i ⊂ E
A = ∩
m
i=1 B i
Dans ces conditions, on peut poser dans (11.3)
A 0 = E ⊃ A 1 = B 1 ⊃ A 2 = (B 1 ∩ B 2 ) ⊃ . . . ⊃ A m = ∩
m
i=1 B i
ou encore pour toute permutation σ ∈ G m de l’ensemble {1, . . . , m} :
A 0 = E ⊃ A 1 = B σ(1) ⊃ A 2 =
B σ(1) ∩ B σ(2)
⊃ . . . ⊃ A m = ∩
m
i=1 B σ(i)
Une autre solution est de consid´ erer les mesures de Boltzmann-Gibbs
Ψ G (μ)(dx) =
1
μ (e −βV )
e
−βV (x) μ(dx)
avec la mesure de comptage μ sur E et la fonction de p´ enalisation :
V (x) =
m
i=1
1 E−Ai (x)
Les algorithmes de simulation particulaires associ´ es ` a chacune de ces formulations peuvent ˆ etre d´ ecrits ais´ ement.
Dans un autre registre, dans la section 8.3 nous avons aussi vu qu’il ´ etait
possible de remplacer dans les formules de Feynman-Kac (11.4) et (11.5) les
triplets
(g k , M k , E k ) = (1 A k+1 , M k , E)
par les triplets corrig´ es ( g k ,
M k ,
E k ) d´ ecrits ci-dessous :
E k = {x ∈ E : g k (x) > 0} = A k+1
M k (x, y) :=
M k (x, y)1 A k+1 (y)
M k (x, A k+1 )
∀x ∈
E k−1 = A k
et
∀x ∈
E k = A k+1
g k (x) := M k+1 (g k+1 )(x) = M k+1 (x, A k+2 )
(11.9)
L’algorithme g´ en´ etique correspondant est fond´ e sur des
M k -mutations et
des
g k -s´ elections. Lorsque ces objets sont difficiles ` a calculer et/ou ` a simuler,
on pourra utiliser les formules d’approximations (8.17) d´ ecrites `
a la page 235.
Dans le contexte pr´ esent, ces formules d’approximation sont fond´ ees sur la