11.7 Organisation optimale multi-crit` eres
341
avec les mesures
(μ k × K) 0 (d(u, v)) = μ k (du) K(u, dv)
(μ k × K) 1 (d(u, v)) = μ k (dv) K(v, du).
En utilisant la r´ eversibilit´ e des transitions K k par rapport aux lois μ k et en
remarquant que l’on a
η k (du) :=
1
μ k ({P ≤ p })
1 {P≤p } (u) μ k (du)
on montre que les transitions d’acceptation-rejet suivantes
M k (u, dv) := K k (u, dv) 1 {P≤p } (v) +
1 − K k
1 {P≤p }
(u)
δ u (dv)
sont η k -invariantes.
Les transitions d´ ecrites ci-dessus permettent d’explorer l’espace des configurations en laissant invariantes les mesures de probabilit´ es courantes. L’´ etape
de s´ election des individus les mieux adapt´ es s’effectue en fonction des fonctions
potentiel g k d´ ecrites ci-dessous :
g k (v) := e
−(β k+1 −β k )V(v) 1 {P≤p } (v)
On remarquera que les transformations de Boltzmann-Gibbs Ψ g k associ´ ees `
a
ces fonctions g k permettent de passer des lois η k aux lois η k+1 . Plus formellement, nous avons
e
−β k+1 V = e
−(β k+1 −β k )V
× e
−β k V =⇒ Ψ g k (η k ) = η k+1
11.7 Organisation optimale multi-crit` eres
Le probl` eme du sac ` a dos d´ ecrit dans la section 6.5.5 et dans la section 11.6
peut s’´ etendre dans des directions diverses et vari´ ees.
La premi` ere consiste `
a remplacer l’espace d’´ etat {0, 1} par un espace un
peu plus g´ en´ eral, disons N ou un espace continu tel le segment [0, 1]. Dans le
premier cas, la pr´ esence ou absence d’un objet individualis´ e est remplac´ e par
celle de plusieurs exemplaires de l’objet. Le cas des espaces continus permet
de traiter des situations o` u on ne prend qu’une proportion des objets. Ces
probl` emes peuvent ˆ etre r´ esolus par les techniques de simulation pr´ ec´ edentes en
rempla¸ cant les explorations dans les espaces de suites {0, 1}
d par des strat´ egies
d’exploration al´ eatoires sur les espaces produits N
d ou [0, 1]
d .
Les probl` emes d’organisation optimale de sacs ` a dos multi-objectifs et
multi-contraintes s’expriment comme pr´ ec´ edemment par la donn´ ee de c 1
crit` eres `
a optimiser
∀1 ≤ i ≤ c 1
W i (u) :=
d
k=1
w
i
k u k
341
avec les mesures
(μ k × K) 0 (d(u, v)) = μ k (du) K(u, dv)
(μ k × K) 1 (d(u, v)) = μ k (dv) K(v, du).
En utilisant la r´ eversibilit´ e des transitions K k par rapport aux lois μ k et en
remarquant que l’on a
η k (du) :=
1
μ k ({P ≤ p })
1 {P≤p } (u) μ k (du)
on montre que les transitions d’acceptation-rejet suivantes
M k (u, dv) := K k (u, dv) 1 {P≤p } (v) +
1 − K k
1 {P≤p }
(u)
δ u (dv)
sont η k -invariantes.
Les transitions d´ ecrites ci-dessus permettent d’explorer l’espace des configurations en laissant invariantes les mesures de probabilit´ es courantes. L’´ etape
de s´ election des individus les mieux adapt´ es s’effectue en fonction des fonctions
potentiel g k d´ ecrites ci-dessous :
g k (v) := e
−(β k+1 −β k )V(v) 1 {P≤p } (v)
On remarquera que les transformations de Boltzmann-Gibbs Ψ g k associ´ ees `
a
ces fonctions g k permettent de passer des lois η k aux lois η k+1 . Plus formellement, nous avons
e
−β k+1 V = e
−(β k+1 −β k )V
× e
−β k V =⇒ Ψ g k (η k ) = η k+1
11.7 Organisation optimale multi-crit` eres
Le probl` eme du sac ` a dos d´ ecrit dans la section 6.5.5 et dans la section 11.6
peut s’´ etendre dans des directions diverses et vari´ ees.
La premi` ere consiste `
a remplacer l’espace d’´ etat {0, 1} par un espace un
peu plus g´ en´ eral, disons N ou un espace continu tel le segment [0, 1]. Dans le
premier cas, la pr´ esence ou absence d’un objet individualis´ e est remplac´ e par
celle de plusieurs exemplaires de l’objet. Le cas des espaces continus permet
de traiter des situations o` u on ne prend qu’une proportion des objets. Ces
probl` emes peuvent ˆ etre r´ esolus par les techniques de simulation pr´ ec´ edentes en
rempla¸ cant les explorations dans les espaces de suites {0, 1}
d par des strat´ egies
d’exploration al´ eatoires sur les espaces produits N
d ou [0, 1]
d .
Les probl` emes d’organisation optimale de sacs ` a dos multi-objectifs et
multi-contraintes s’expriment comme pr´ ec´ edemment par la donn´ ee de c 1
crit` eres `
a optimiser
∀1 ≤ i ≤ c 1
W i (u) :=
d
k=1
w
i
k u k