336
11 Optimisation et Combinatoire ´ enum´ erative
En termes de mesures, nous souhaitons simuler des variables al´ eatoires
distribu´ ees selon les mesures de Boltzmann-Gibbs
η k (dx) =
1
γ k (1)
γ k (dx) avec G k (x) = 1 Am k (x)
De plus, nous souhaitons calculer leurs constantes de normalisation :
γ k (1) := μ(G k ) =
Card(A m k )
Card(E)
L’algorithme de simulation particulaire
L’algorithme g´ en´ etique associ´ e `
a ces lois est d´ ecrit dans la section 11.3. On
commence par simuler une suite de variables al´ eatoires ind´ ependantes dans A 0 .
Dans ce contexte, cette ´ etape consiste simplement ` a simuler N configurations
al´ eatoires ξ 0 = (ξ
i
0 ) 1≤i≤N n’exc´ edant pas le poids maximal autoris´ e
ξ
i
0 =
u
i
1 (0), u
i
2 (0), . . . , u
i
d (0)
∈ {0, 1}
d
telles que
d
j=1
p j u
i
j (0) ≤ p
Supposons que nous ayons fait ´ evoluer l’algorithme jusqu’au temps k. A cette
date, nous avons N individus dans l’ensemble des configurations A m k de valeur
minimale m k ; c’est-` a-dire
∀1 ≤ i ≤ N
ξ
i
k =
u
i
1 (k), u
i
2 (k), . . . , u
i
d (k)
∈ A m k
L’´ etape de s´ election d´ ecrite en (11.7) est une ´ etape d’acceptation-rejet des
configurations ξ k := (ξ
i
k ) 1≤i≤k .
Cette derni` ere consiste ` a accepter les configurations ξ
i
k de valeur minimale
sup´ erieure au niveau suivant. Autrement dit, on pose
ξ
i
k =
u
i
1 (k), u
i
2 (k), . . . , u
i
d (k)
∈ A m k+1
d´ ef.
⇐⇒
d
j=1
w j u
i
j (k) ≥ m k+1
=⇒
ξ
i
k = ξ
i
k
Lorsqu’une configuration ξ
j
k =
u
j
1 (k), u
j
2 (k), . . . , u
j
d (k)
∈ A m k+1 , on la remplace par une configuration de sac choisie au hasard parmi celles de valeur
minimale sup´ erieure `
a m k+1 ; c’est-` a-dire
ξ
j
k d´ esigne une v.a. de loi
N
j=1
1 Am k+1 (ξ
j
k )
N
l=1
1 Am k+1 (ξ
l
k )
1 ξ
j
k