326
11 Optimisation et Combinatoire ´ enum´ erative
Une autre strat´ egie consiste `
a simuler des points distribu´ es al´ eatoirement
selon des mesures de Boltzmann-Gibbs de plus en plus concentr´ es sur l’ensemble A. Par exemple, on pourra consid´ erer les mesures
Ψ G (μ)(dx) =
1
μ(G)
G(x) μ(dx) avec G(x) = e
β1 A (x)
(11.2)
avec un param` etre de temp´ erature inverse β. On peut remarquer que l’on a
Ψ G (μ) = Ψ G (μ) avec G
(x) = e
−β1 E−A (x)
Autrement dit, il est ´ equivalent de consid´ erer des mesures de BoltzmannGibbs qui favorisent ou p´ enalisent les ´ etats `
a l’int´ erieur ou ` a l’ext´ erieur de
A.
Lorsque β ↑ ∞, les mesures d´ ecrites ci-dessus sont des approximations des
mesures restreintes d´ efinies en (11.1). Par exemple, dans le cas de mesure de
comptage μ(x) =
1
|E| sur un ensemble fini, nous avons
G(x)
y∈E G(y)
= 1 A (x)
1
Card(A) + e −β Card(E − A)
+ 1 E−A (x) e
−β
1
Card(A) + Card(E − A)e −β
β↑∞
1
Card(A)
1 A (x)
11.2 Interpr´ etations de Feynman-Kac-Jarzynski
L’ensemble ”cible” A est en g´ en´ eral trop complexe pour r´ esoudre ces deux
probl` emes directement. L’id´ ee naturelle est de choisir une suite d´ ecroissante
de sous ensembles
A 0 = E ⊃ A 1 ⊃ . . . ⊃ A n avec A n = A
(11.3)
avec un niveau de complexit´ e croissant. Par exemple, A k+1 peut ˆ etre d´ efini
en fonction de A k par l’ajout d’une contrainte additionnelle sur ses ´ el´ ements.
On note par la suite η n le flot de mesures de Boltzmann-Gibbs associ´ ees aux
fonctions potentiel G k = 1 A k
η k (dx) =
1
γ k (1)
γ k (dx)
avec