218
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
la temp´ erature conviennent ! Dans le cas contraire, on doit se contenter de
sch´ emas logarithmiques T n = T 0 / log (n + 1), avec des temp´ eratures initiales
suffisamment ´ elev´ ees.
En pratique, les explorations al´ eatoires locales sont souvent dict´ ees par le
probl` eme `
a ´ etudier. En g´ en´ eral, ces derni` eres ne permettent pas d’acc´ eder directement d’un ´ etat quelconque ` a un autre en une seule ´ etape. N´ eanmoins deux
´ etats quelconques peuvent toujours ˆ etre reli´ es par une succession d’´ etapes locales ´ el´ ementaires. Dans toutes les situations examin´ ees pr´ ec´ edemment, deux
´ etats quelconques peuvent ainsi ˆ etre reli´ es par une chemin de mˆ eme longueur
fix´ ee m. Pour augmenter les capacit´ es exploratoires de l’algorithme de recuit,
et ´ eviter des sch´ emas de temp´ erature logarithmiques, il suffit de consid´ erer
des probabilit´ es de transitions construites en it´ erant m explorations locales.
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
la temp´ erature conviennent ! Dans le cas contraire, on doit se contenter de
sch´ emas logarithmiques T n = T 0 / log (n + 1), avec des temp´ eratures initiales
suffisamment ´ elev´ ees.
En pratique, les explorations al´ eatoires locales sont souvent dict´ ees par le
probl` eme `
a ´ etudier. En g´ en´ eral, ces derni` eres ne permettent pas d’acc´ eder directement d’un ´ etat quelconque ` a un autre en une seule ´ etape. N´ eanmoins deux
´ etats quelconques peuvent toujours ˆ etre reli´ es par une succession d’´ etapes locales ´ el´ ementaires. Dans toutes les situations examin´ ees pr´ ec´ edemment, deux
´ etats quelconques peuvent ainsi ˆ etre reli´ es par une chemin de mˆ eme longueur
fix´ ee m. Pour augmenter les capacit´ es exploratoires de l’algorithme de recuit,
et ´ eviter des sch´ emas de temp´ erature logarithmiques, il suffit de consid´ erer
des probabilit´ es de transitions construites en it´ erant m explorations locales.