196
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
sinage. Dans le jargon probabiliste, ces processus d’exploration sans m´ emoire
sont souvent appel´ es des chaˆ ınes de Markov.
`
A chaque ´ etape n, ces processus d’exploration de voisinages ´ evoluent d’un
´ etat X n vers un autre ´ etat X n+1 choisi al´ eatoirement parmi les ´ etats voisins
V(X n ) de l’´ etat courant X n . On peut r´ esumer sch´ ematiquement ces explorations par le diagramme fl´ ech´ e suivant
X 0 −→ X 1 ∈ V(X 0 ) −→ X 2 ∈ V(X 1 ) −→ . . . −→ X n ∈ V(X n−1 )
Afin d’´ eclaircir ces premiers objets math´ ematiques, citons un exemple
´ el´ ementaire d’explorations locales sur des syst` emes de voisinages.
L’´ evolution d’un promeneur solitaire sur une surface plane quadrill´ ee peut
ˆ etre mod´ elis´ ee par une marche al´ eatoire ou d´ eterministe sur le r´ eseau plan
E = Z
2 . L’ensemble des sites est muni d’une structure de graphe naturelle en
consid´ erant les 4 voisins d’un point i = (i 1 , i 2 ) ∈ E, c’est-` a-dire
j
1 = (i 1 , i 2 + 1)
j
4 = (i 1 − 1, i 2 ) ↔ i = (i 1 , i 2 ) ↔ j
2 = (i 1 + 1, i 2 )
j
3 = (i 1 , i 2 − 1)
Ces relations de voisinages sur l’ensemble des sites E correspondent aussi `
a la
donn´ ee de la relation de voisinage suivante
i = (i 1 , i 2 ) ∼ i
= (i
1 , i
2 ) ⇐⇒ |i 1 − i
1 | + |i 2 − i
2 | ≤ 1
Dans ce contexte, le marcheur avance pas `
a pas, d’un ´ etat vers l’un de ces
quatre voisins. Une transition al´ eatoire simple d’un site i vers un site voisin
j consiste `
a rendre une visite al´ eatoire `
a l’un de ses quatre voisins. Cette
transition al´ eatoire peut s’´ ecrire sous la forme synth´ etique suivante
i j = i + U
o` u U d´ esigne un vecteur al´ eatoire choisi uniform´ ement dans l’ensemble
U = {u = (u
1 , u
2 ) ∈ Z
2 ‘ : |u
1
| + |u
2
| = 1} = {u 1 , u 2 , u 3 , u 4 }
des quatre vecteurs directionnels unitaires
u 1 =
1
0
u 2 =
0
1
u 3 =
−1
0
u 4 =
0
−1
La figure 7.1 repr´ esente l’´ evolution d’une marche al´ eatoire sur Z
2 sur 12
it´ erations.
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
sinage. Dans le jargon probabiliste, ces processus d’exploration sans m´ emoire
sont souvent appel´ es des chaˆ ınes de Markov.
`
A chaque ´ etape n, ces processus d’exploration de voisinages ´ evoluent d’un
´ etat X n vers un autre ´ etat X n+1 choisi al´ eatoirement parmi les ´ etats voisins
V(X n ) de l’´ etat courant X n . On peut r´ esumer sch´ ematiquement ces explorations par le diagramme fl´ ech´ e suivant
X 0 −→ X 1 ∈ V(X 0 ) −→ X 2 ∈ V(X 1 ) −→ . . . −→ X n ∈ V(X n−1 )
Afin d’´ eclaircir ces premiers objets math´ ematiques, citons un exemple
´ el´ ementaire d’explorations locales sur des syst` emes de voisinages.
L’´ evolution d’un promeneur solitaire sur une surface plane quadrill´ ee peut
ˆ etre mod´ elis´ ee par une marche al´ eatoire ou d´ eterministe sur le r´ eseau plan
E = Z
2 . L’ensemble des sites est muni d’une structure de graphe naturelle en
consid´ erant les 4 voisins d’un point i = (i 1 , i 2 ) ∈ E, c’est-` a-dire
j
1 = (i 1 , i 2 + 1)
j
4 = (i 1 − 1, i 2 ) ↔ i = (i 1 , i 2 ) ↔ j
2 = (i 1 + 1, i 2 )
j
3 = (i 1 , i 2 − 1)
Ces relations de voisinages sur l’ensemble des sites E correspondent aussi `
a la
donn´ ee de la relation de voisinage suivante
i = (i 1 , i 2 ) ∼ i
= (i
1 , i
2 ) ⇐⇒ |i 1 − i
1 | + |i 2 − i
2 | ≤ 1
Dans ce contexte, le marcheur avance pas `
a pas, d’un ´ etat vers l’un de ces
quatre voisins. Une transition al´ eatoire simple d’un site i vers un site voisin
j consiste `
a rendre une visite al´ eatoire `
a l’un de ses quatre voisins. Cette
transition al´ eatoire peut s’´ ecrire sous la forme synth´ etique suivante
i j = i + U
o` u U d´ esigne un vecteur al´ eatoire choisi uniform´ ement dans l’ensemble
U = {u = (u
1 , u
2 ) ∈ Z
2 ‘ : |u
1
| + |u
2
| = 1} = {u 1 , u 2 , u 3 , u 4 }
des quatre vecteurs directionnels unitaires
u 1 =
1
0
u 2 =
0
1
u 3 =
−1
0
u 4 =
0
−1
La figure 7.1 repr´ esente l’´ evolution d’une marche al´ eatoire sur Z
2 sur 12
it´ erations.