7.2 La notion de voisinage
195
C’est le cas des formations de macro-mol´ ecules, et de polym` eres dans
des solvants chimiques. Dans ce contexte, les formations cin´ etiques chimiques recherchent des configurations g´ eom´ etriques minimisant un potentiel d’´ energie li´ e aux forces de coh´ esions, ou de r´ epulsions physico-chimiques.
En m´ etallurgie, les techniques de trempes et de refroidissement d’alliages
de m´ etaux conduisent le m´ etal vers des organisations ´ energ´ etiques internes
m´ etastables ou stables. Les configurations d’atomes m´ etastables correspondent
` a des mat´ eriaux tr` es durs. Ces ´ etats r´ esultent d’un refroidissement tr` es rapide
d’un m´ etal port´ e ` a l’´ etat liquide. Les configurations stables sont plutˆ ot associ´ ees ` a des ´ etats plus mal´ eables, et bien moins cassants. On obtient ces
configurations d’atomes bien plus parfaites en refroidissant plus lentement le
m´ etal sur de longs paliers de temp´ eratures interm´ ediaires, de sorte ` a gommer
ses d´ efauts et ses imperfections.
`
A la diff´ erence des probl` emes de combinatoires cit´ es pr´ ec´ edemment, les
syst` emes physiques s’auto-organisent naturellement autour de configurations
optimales. La nature fait donc ` a nouveau bien les choses ! L’id´ ee tout aussi
naturelle est donc de dompter math´ ematiquement ces ph´ enom` enes physiques,
et de les simuler en mimant leur comportement cin´ etique. En adoptant ces
proc´ ed´ es d’exploration physiques nous serons ainsi en mesure de r´ esoudre de
fa¸ con naturelle certains probl` emes d’optimisation complexes.
7.2 La notion de voisinage
Essayons tout d’abord de formaliser les variations d’´ energies pendant ces
recuits thermiques. Le processus physique ´ evolue tel un marcheur virtuel dans
un paysage d’´ energie. Les r´ egions accessibles d´ ependent de la temp´ erature
ambiante.
`
A tr` es haute temp´ erature, le processus ne subit aucune contrainte. Il passe
librement d’une configuration ` a une autre, sans se soucier des diff´ erentes
barri` eres entre leurs niveaux d’energie. Les transitions al´ eatoires d’un ´ etat
vers un autre doivent n´ eanmoins ˆ etre physiquement possibles. Deux ´ etats successifs doivent ˆ etre en un certain sens assez voisins. Cette premi` ere hypoth` ese
sur la dynamique libre de ces processus est en accord avec notre exp´ erience, et
notre perception de la r´ ealit´ e physique : augmentation degr´ e par degr´ e de la
temp´ erature d’un corps, variations lentes d’intensit´ e lumineuse d’une lampe
ou du son dans un amplificateur, explorations pas ` a pas d’une r´ egion, mont´ ees
et descentes par paliers de montagnes, et bien d’autres.
Pour formaliser math´ ematiquement ces dynamiques locales, on se donne un
ensemble de configurations E muni d’un syst` eme de voisinages. Ces structures
topologiques sur E sont souvent associ´ ees ` a la donn´ ee de m´ etriques d(x, y),
ou plus g´ en´ eralement ` a des relations de voisinage x ∼ y sur l’ensemble E.
Les vibrations al´ eatoires et locales du processus peuvent ˆ etre mod´ elis´ ees
par la donn´ ee d’une dynamique al´ eatoire sur E explorant pas ` a pas chaque voi-
195
C’est le cas des formations de macro-mol´ ecules, et de polym` eres dans
des solvants chimiques. Dans ce contexte, les formations cin´ etiques chimiques recherchent des configurations g´ eom´ etriques minimisant un potentiel d’´ energie li´ e aux forces de coh´ esions, ou de r´ epulsions physico-chimiques.
En m´ etallurgie, les techniques de trempes et de refroidissement d’alliages
de m´ etaux conduisent le m´ etal vers des organisations ´ energ´ etiques internes
m´ etastables ou stables. Les configurations d’atomes m´ etastables correspondent
` a des mat´ eriaux tr` es durs. Ces ´ etats r´ esultent d’un refroidissement tr` es rapide
d’un m´ etal port´ e ` a l’´ etat liquide. Les configurations stables sont plutˆ ot associ´ ees ` a des ´ etats plus mal´ eables, et bien moins cassants. On obtient ces
configurations d’atomes bien plus parfaites en refroidissant plus lentement le
m´ etal sur de longs paliers de temp´ eratures interm´ ediaires, de sorte ` a gommer
ses d´ efauts et ses imperfections.
`
A la diff´ erence des probl` emes de combinatoires cit´ es pr´ ec´ edemment, les
syst` emes physiques s’auto-organisent naturellement autour de configurations
optimales. La nature fait donc ` a nouveau bien les choses ! L’id´ ee tout aussi
naturelle est donc de dompter math´ ematiquement ces ph´ enom` enes physiques,
et de les simuler en mimant leur comportement cin´ etique. En adoptant ces
proc´ ed´ es d’exploration physiques nous serons ainsi en mesure de r´ esoudre de
fa¸ con naturelle certains probl` emes d’optimisation complexes.
7.2 La notion de voisinage
Essayons tout d’abord de formaliser les variations d’´ energies pendant ces
recuits thermiques. Le processus physique ´ evolue tel un marcheur virtuel dans
un paysage d’´ energie. Les r´ egions accessibles d´ ependent de la temp´ erature
ambiante.
`
A tr` es haute temp´ erature, le processus ne subit aucune contrainte. Il passe
librement d’une configuration ` a une autre, sans se soucier des diff´ erentes
barri` eres entre leurs niveaux d’energie. Les transitions al´ eatoires d’un ´ etat
vers un autre doivent n´ eanmoins ˆ etre physiquement possibles. Deux ´ etats successifs doivent ˆ etre en un certain sens assez voisins. Cette premi` ere hypoth` ese
sur la dynamique libre de ces processus est en accord avec notre exp´ erience, et
notre perception de la r´ ealit´ e physique : augmentation degr´ e par degr´ e de la
temp´ erature d’un corps, variations lentes d’intensit´ e lumineuse d’une lampe
ou du son dans un amplificateur, explorations pas ` a pas d’une r´ egion, mont´ ees
et descentes par paliers de montagnes, et bien d’autres.
Pour formaliser math´ ematiquement ces dynamiques locales, on se donne un
ensemble de configurations E muni d’un syst` eme de voisinages. Ces structures
topologiques sur E sont souvent associ´ ees ` a la donn´ ee de m´ etriques d(x, y),
ou plus g´ en´ eralement ` a des relations de voisinage x ∼ y sur l’ensemble E.
Les vibrations al´ eatoires et locales du processus peuvent ˆ etre mod´ elis´ ees
par la donn´ ee d’une dynamique al´ eatoire sur E explorant pas ` a pas chaque voi-