328
11 Optimisation et Combinatoire ´ enum´ erative
(η k × M ) 0 (d(x, y)) = η k (dx) M (x, dy)
(η k × M ) 1 (d(x, y)) = η k (dy) M (y, dx).
Dans le cas particulier o` u la transition M (x, dy) est μ-r´ eversible, nous avons
M k (x, dy) : = M (x, dy)
1 ∧ e
β k (1 A (y)−1 A (x))
+
+
1 −
M (x, dz)
1 ∧ e
β k (1 A (z)−1 A (x))
+
δ x (dy)
(11.6)
11.3 Algorithmes de simulation particulaires
Diverses techniques de simulation particulaire des flots de mesures d´ ecrits
dans la section 11.1 sont d´ ecrites dans la section 9. Chacun de ces mod` eles
d´ epend des strat´ egies d’exploration locale de l’espace ´ etudi´ e. Pour illustrer
cette remarque, examinons tout d’abord en d´ etail la simulation des lois restreintes
η n (dx) =
1
μ(A n )
1 An (x) μ(dx) avec A n ↓
par des transitions d’exploration locales M n de mesures invariantes instantann´ ees η n .
L’algorithme stochastique correspondant se traduit par un algorithme
de type g´ en´ etique ξ n = (ξ
i
n ) 1≤i≤N sur l’espace produit E
N . L’´ evolution de
cette chaˆ ıne se d´ ecompose en deux m´ ecanismes. Le premier correspond ` a une
s´ election des individus selon les fonctions potentiel g n . Le second est une exploration pure de l’espace des ´ etats selon les transitions markoviennes M n .
ξ n = (ξ
i
n ) 1≤i≤N
s´ election
− − − − − − − − − − −→
ξ n = (
ξ
i
n ) 1≤i≤N
mutation
− − − − − − − − − − −→ ξ n+1 = (ξ
i
n+1 ) 1≤i≤N
L’´ etape de s´ election consiste `
a poser pour chaque i = 1, . . . , N
ξ
i
n =
ξ
i
n
si
ξ
i
n ∈ A n+1
˜
ξ
i
n
si
ξ
i
n ∈ A n+1
(11.7)
o` u ˜
ξ
i
n d´ esigne une v.a. de “loi empirique uniforme” sur A n+1
N
j=1
1 An+1 (ξ
j
n )
N
k=1
1 An+1 (ξ
k
n )
δ ξ
j
n