11
Optimisation et Combinatoire ´ enum´ erative
11.1 Description des mod` eles
La combinatoire ´ enum´ erative s’int´ eresse aux m´ ethodes de comptage d’´ el´ ements dans un ensemble fini. Dans un autre registre, l’optimisation combinatoire consiste plutˆ ot `
a trouver dans des ensembles finis des ´ etats optimaux
en fonction d’un crit` ere de qualit´ e donn´ e. La r´ esolution pratique de ces deux
probl` emes par de simples techniques d’´ enum´ eration d´ eterministes et exhaustives est en g´ en´ eral hors de port´ ee par les ordinateurs actuels avec des temps
de calculs prohibitifs.
Pour r´ esoudre ces probl` emes, une des id´ ees classiques des m´ ethodes de
simulation de type Monte Carlo consiste `
a traduire ces probl` emes en un
probl` eme de simulation de loi complexe et de calcul de constantes de normalisation. Reprenons par exemple, les mod` eles de Feynman-Kac-Jarzynski
d´ ecrits dans la section 9.3.2. Notons μ la mesure de comptage sur un ensemble
fini E
∀x ∈ E
μ(x) = 1/Card(E)
Consid´ erons le probl` eme suivant : le cardinal de E est connu et il est assez
ais´ e de choisir al´ eatoirement des points dans E. On se donne un sous ensemble
non vide A ⊂ E, et on souhaite calculer son cardinal et choisir des points
al´ eatoirement dans A. Nous sommes exactement dans le sc´ enario pr´ esent´ e dans
la section 9.3.2. En effet, notre objectif est de simuler des points distribu´ es
al´ eatoirement dans A selon la mesure de Boltzmann-Gibbs
Ψ G (μ)(dx) =
1
μ(G)
G(x) μ(dx) avec G = 1 A
(11.1)
De plus, nous souhaitons calculer la constante de normalisation
μ(1 A ) := μ(A) =
Card(A)
Card(E)
P. Del Moral and C. Vergé, Modèles et méthodes stochastiques,
Mathématiques et Applications 75, DOI: 10.1007/978-3-642-54616-7_11,
Ó Springer-Verlag Berlin Heidelberg 2014
3 2 5
Optimisation et Combinatoire ´ enum´ erative
11.1 Description des mod` eles
La combinatoire ´ enum´ erative s’int´ eresse aux m´ ethodes de comptage d’´ el´ ements dans un ensemble fini. Dans un autre registre, l’optimisation combinatoire consiste plutˆ ot `
a trouver dans des ensembles finis des ´ etats optimaux
en fonction d’un crit` ere de qualit´ e donn´ e. La r´ esolution pratique de ces deux
probl` emes par de simples techniques d’´ enum´ eration d´ eterministes et exhaustives est en g´ en´ eral hors de port´ ee par les ordinateurs actuels avec des temps
de calculs prohibitifs.
Pour r´ esoudre ces probl` emes, une des id´ ees classiques des m´ ethodes de
simulation de type Monte Carlo consiste `
a traduire ces probl` emes en un
probl` eme de simulation de loi complexe et de calcul de constantes de normalisation. Reprenons par exemple, les mod` eles de Feynman-Kac-Jarzynski
d´ ecrits dans la section 9.3.2. Notons μ la mesure de comptage sur un ensemble
fini E
∀x ∈ E
μ(x) = 1/Card(E)
Consid´ erons le probl` eme suivant : le cardinal de E est connu et il est assez
ais´ e de choisir al´ eatoirement des points dans E. On se donne un sous ensemble
non vide A ⊂ E, et on souhaite calculer son cardinal et choisir des points
al´ eatoirement dans A. Nous sommes exactement dans le sc´ enario pr´ esent´ e dans
la section 9.3.2. En effet, notre objectif est de simuler des points distribu´ es
al´ eatoirement dans A selon la mesure de Boltzmann-Gibbs
Ψ G (μ)(dx) =
1
μ(G)
G(x) μ(dx) avec G = 1 A
(11.1)
De plus, nous souhaitons calculer la constante de normalisation
μ(1 A ) := μ(A) =
Card(A)
Card(E)
P. Del Moral and C. Vergé, Modèles et méthodes stochastiques,
Mathématiques et Applications 75, DOI: 10.1007/978-3-642-54616-7_11,
Ó Springer-Verlag Berlin Heidelberg 2014
3 2 5