11.6 Le probl` eme du sac `
a dos
337
Pour des valeurs de paliers m k+1 trop ´ elev´ ees, il est possible qu’aucune des
configurations ξ
i
k propos´ ees dans A m k ne soit dans A m k+1 ⊂ A m k . Dans
cette situation, l’algorithme s’arrˆ ete, et on estime les mesures de BoltzmannGibbs et leurs constantes de normalisation par z´ ero. Pour ´ eviter ces probl` emes
d’arrˆ et, on peut aussi choisir les niveaux de qualit´ e m k+1 de fa¸ con adaptative.
Par exemple, on peut convenir de placer le (k +1)-i` eme niveau `
a la plus grande
valeur m k+1 pour laquelle une proportion fix´ ee de configurations est de valeur
minimale sup´ erieure `
a m k+1 .
L’´ etape de mutation consiste `
a explorer ce nouvel espace des configurations
A m k+1 selon une transition de Markov laissant η k+1 invariante. Le choix de
cette transition est loin d’ˆ etre unique.
11.6.2 Quelques strat´ egies d’exploration locale
Nous proposons par la suite une demi-douzaine de transitions de Markov
laissant les distributions η k+1 invariantes.
1. Une fa¸ con assez simple d’explorer al´ eatoirement l’espace E = {0, 1}
d est
la suivante : on choisit un indice I au hasard dans {1, . . . , d} puis on
remplace la coordonn´ ee u I par (1 − u I ) ; le sch´ ema synth´ etique suivant
traduit cette transformation
(u 1 , . . . , u I−1 , u I , u I+1 , . . . , u d ) (u 1 , . . . , u I−1 , (1 − u I ), u I+1 , . . . , u d )
(11.12)
Plus formellement, cette transition de probabilit´ e peut s’´ ecrire sous la
forme suivante
M (u, v) =
1
d
d
i=1
1 (u1,...,ui−1,(1−ui),ui+1,...,u d ) (v 1 , . . . , v d )
Il est important de noter que M (u, v) est une transition de Markov sur
E = {0, 1}
d r´ eversible par rapport ` a la mesure uniforme μ(u) =
1
2 d sur E,
au sens o` u
μ(u) M (u, v) =
1
2 d
1
d
d
i=1
1 (u1,...,ui−1,(1−ui),ui+1,...,u d ) (v 1 , . . . , v d )
=
1
2 d
1
d
d
i=1
1 (v1,...,vi−1,(1−vi),vi+1,...,v d ) (u 1 , . . . , u d )
= μ(v) M (v, u)
Nous sommes ainsi dans les conditions d´ ecrites en (9.7). On construit une
transitions de Markov M k+1 laissant η k+1 invariante en posant simplement :
M k+1 (u, v) = M (u, v) 1 Am k+1 (v) + (1 − M (u, A m k+1 )) 1 u (v) (11.13)
a dos
337
Pour des valeurs de paliers m k+1 trop ´ elev´ ees, il est possible qu’aucune des
configurations ξ
i
k propos´ ees dans A m k ne soit dans A m k+1 ⊂ A m k . Dans
cette situation, l’algorithme s’arrˆ ete, et on estime les mesures de BoltzmannGibbs et leurs constantes de normalisation par z´ ero. Pour ´ eviter ces probl` emes
d’arrˆ et, on peut aussi choisir les niveaux de qualit´ e m k+1 de fa¸ con adaptative.
Par exemple, on peut convenir de placer le (k +1)-i` eme niveau `
a la plus grande
valeur m k+1 pour laquelle une proportion fix´ ee de configurations est de valeur
minimale sup´ erieure `
a m k+1 .
L’´ etape de mutation consiste `
a explorer ce nouvel espace des configurations
A m k+1 selon une transition de Markov laissant η k+1 invariante. Le choix de
cette transition est loin d’ˆ etre unique.
11.6.2 Quelques strat´ egies d’exploration locale
Nous proposons par la suite une demi-douzaine de transitions de Markov
laissant les distributions η k+1 invariantes.
1. Une fa¸ con assez simple d’explorer al´ eatoirement l’espace E = {0, 1}
d est
la suivante : on choisit un indice I au hasard dans {1, . . . , d} puis on
remplace la coordonn´ ee u I par (1 − u I ) ; le sch´ ema synth´ etique suivant
traduit cette transformation
(u 1 , . . . , u I−1 , u I , u I+1 , . . . , u d ) (u 1 , . . . , u I−1 , (1 − u I ), u I+1 , . . . , u d )
(11.12)
Plus formellement, cette transition de probabilit´ e peut s’´ ecrire sous la
forme suivante
M (u, v) =
1
d
d
i=1
1 (u1,...,ui−1,(1−ui),ui+1,...,u d ) (v 1 , . . . , v d )
Il est important de noter que M (u, v) est une transition de Markov sur
E = {0, 1}
d r´ eversible par rapport ` a la mesure uniforme μ(u) =
1
2 d sur E,
au sens o` u
μ(u) M (u, v) =
1
2 d
1
d
d
i=1
1 (u1,...,ui−1,(1−ui),ui+1,...,u d ) (v 1 , . . . , v d )
=
1
2 d
1
d
d
i=1
1 (v1,...,vi−1,(1−vi),vi+1,...,v d ) (u 1 , . . . , u d )
= μ(v) M (v, u)
Nous sommes ainsi dans les conditions d´ ecrites en (9.7). On construit une
transitions de Markov M k+1 laissant η k+1 invariante en posant simplement :
M k+1 (u, v) = M (u, v) 1 Am k+1 (v) + (1 − M (u, A m k+1 )) 1 u (v) (11.13)