344
11 Optimisation et Combinatoire ´ enum´ erative
La confection d’un algorithme particulaire pour la simulation de ces lois
cibles est fond´ ee sur deux seuls et uniques ingr´ edients :
1. Le choix d’un mod` ele d’exploration associ´ e `
a une transition de Markov
M n sur G d telle que
η n = η n M n
2. La formule de factorisation des fonctions potentiel des mesures
G n+1 = g n × G n
Dans les exemples pr´ ec´ edents, ces fonctions sont donn´ ees respectivement
par
g n = e
−(βn+1−βn)V (σ)
et g n = 1 V (σ)≤n+1
Concernant le premier point, on se donne tout d’abord un mod` ele d’exploration locale de l’espace des permutations fond´ e sur des syst` emes de voisinages.
Par exemple, on peut passer d’une permutation σ ` a une permutation τ = σθ i,j
d´ eduite de σ par une simple transposition θ i,j de deux indices (i, j) choisis au
hasard dans {1 ≤ i ≤ j ≤ d}. On peut aussi explorer l’espace des permutations en passant d’une permutation σ ` a une nouvelle permutation τ = σθ i,j
d´ eduite de σ en inversant toute la s´ erie d’indices entre i et j. Nous renvoyons
le lecteur ` a la section 7.5 d´ edi´ ee ` a l’´ etude des syst` emes de voisinages dans l’espace des permutations et aux techniques d’exploration al´ eatoires associ´ ees.
Dans ce contexte, toutes ces techniques d’explorations locales s’expriment par
la donn´ ee d’une transition de Markov M (σ, dτ ) r´ eversible par rapport ` a la
mesure uniforme μ sur G d
μ(dσ) M (σ, dτ ) = μ(dτ ) M (τ, dσ)
Dans ces conditions, il est donc possible de choisir les probabilit´ es de transitions
M n (σ, dτ ) = M (σ, dτ ) G n (τ ) + (1 − M (G n )(σ)) δ σ (dτ )
ou encore des transitions de type recuit simul´ e dans le cas de potentiel exponentiels
M n (σ, dτ ) = M (σ, dτ )
1 ∧ e
−βn(V (τ )−V (σ))
+
+
1 −
M (σ, dθ)
1 ∧ e
−βn(V (θ)−V (σ))
+
δ σ (dτ )
11.9 D´ ecoupage maximal de graphes
Notons G(S, A) un graphe sur ensemble des sommets S et form´ e d’un
ensemble d’arˆ etes A ⊂ (S × S). On consid` ere une fonction de poids
11 Optimisation et Combinatoire ´ enum´ erative
La confection d’un algorithme particulaire pour la simulation de ces lois
cibles est fond´ ee sur deux seuls et uniques ingr´ edients :
1. Le choix d’un mod` ele d’exploration associ´ e `
a une transition de Markov
M n sur G d telle que
η n = η n M n
2. La formule de factorisation des fonctions potentiel des mesures
G n+1 = g n × G n
Dans les exemples pr´ ec´ edents, ces fonctions sont donn´ ees respectivement
par
g n = e
−(βn+1−βn)V (σ)
et g n = 1 V (σ)≤n+1
Concernant le premier point, on se donne tout d’abord un mod` ele d’exploration locale de l’espace des permutations fond´ e sur des syst` emes de voisinages.
Par exemple, on peut passer d’une permutation σ ` a une permutation τ = σθ i,j
d´ eduite de σ par une simple transposition θ i,j de deux indices (i, j) choisis au
hasard dans {1 ≤ i ≤ j ≤ d}. On peut aussi explorer l’espace des permutations en passant d’une permutation σ ` a une nouvelle permutation τ = σθ i,j
d´ eduite de σ en inversant toute la s´ erie d’indices entre i et j. Nous renvoyons
le lecteur ` a la section 7.5 d´ edi´ ee ` a l’´ etude des syst` emes de voisinages dans l’espace des permutations et aux techniques d’exploration al´ eatoires associ´ ees.
Dans ce contexte, toutes ces techniques d’explorations locales s’expriment par
la donn´ ee d’une transition de Markov M (σ, dτ ) r´ eversible par rapport ` a la
mesure uniforme μ sur G d
μ(dσ) M (σ, dτ ) = μ(dτ ) M (τ, dσ)
Dans ces conditions, il est donc possible de choisir les probabilit´ es de transitions
M n (σ, dτ ) = M (σ, dτ ) G n (τ ) + (1 − M (G n )(σ)) δ σ (dτ )
ou encore des transitions de type recuit simul´ e dans le cas de potentiel exponentiels
M n (σ, dτ ) = M (σ, dτ )
1 ∧ e
−βn(V (τ )−V (σ))
+
+
1 −
M (σ, dθ)
1 ∧ e
−βn(V (θ)−V (σ))
+
δ σ (dτ )
11.9 D´ ecoupage maximal de graphes
Notons G(S, A) un graphe sur ensemble des sommets S et form´ e d’un
ensemble d’arˆ etes A ⊂ (S × S). On consid` ere une fonction de poids