Chapitre 11 • Métaheuristiques en optimisation combinatoire
406
méthode de trai te ment des maté riaux (recuit réel) est mise en œuvre pour trai ter un
pro blème d’opti mi sation (recuit simulé).
11.3.2 Recuit réel et recuit simulé
Pour modi fier l’état d’un maté riau, le phy si cien dis pose d’un para mètre de com -
mande : la tem pé ra ture. Le recuit est pré ci sé ment une stra té gie de contrôle de la tem
pé ra ture en vue d’appro cher un état opti mal. Pour fixer les idées, pre nons l’exemple de
la crois sance d’un mono cris tal. La tech nique du recuit consiste à chauf fer préa la ble
ment le maté riau pour lui confé rer une éner gie éle vée. Puis on refroi dit très len te ment
le maté riau, en mar quant des paliers de tem pé ra ture de durée suf fi sante ; si la des cente
en tem pé ra ture est trop rapide, il appa raît des défauts qui peuvent être éli mi nés par
réchauf fe ment local. Cette stra té gie de baisse contrô lée de la tem pé ra ture conduit à
un état solide cris tal lisé, qui est un état stable, cor res pon dant à un mini mum absolu de
l’éner gie. La tech nique oppo sée est celle de la « trempe », qui consiste à abais ser très
rapi de ment la tem pé ra ture du maté riau : on obtient dans ce cas une struc ture amorphe,
état méta stable qui cor res pond à un mini mum local de l’éner gie. Avec la tech nique du
recuit, le refroi dis se ment du maté riau a pro vo qué une trans for ma tion désordre ordre,
tan dis que la tech nique de la trempe a abouti à figer un état désor donné.
L’idée d’uti li ser la tech nique du recuit en vue de trai ter un pro blème d’opti mi
sation a donné nais sance à la méthode du recuit simulé. Elle consiste à intro duire, en
opti mi sation, un para mètre de contrôle, qui joue le rôle de la tem pé ra ture. La « tem
pé ra ture » du sys tème à opti mi ser doit avoir le même effet que la tem pé ra ture du
sys tème phy sique : elle doit condi tion ner le nombre d’états acces sibles et conduire
vers l’état opti mal si elle est abais sée de façon lente et bien contrô lée (tech nique du
recuit) et vers un mini mum local si elle est abais sée bru ta le ment (tech nique de la
trempe). Pour ter mi ner la pré sen ta tion de la méthode, il nous reste à expo ser l’algo
rithme qui per met de pro gram mer le recuit simulé sur un ordi na teur.
11.3.3 Algo rithme du recuit simulé
L’algo rithme s’appuie sur deux résul tats de la phy sique sta tistique :
• D’une part, lorsque l’équi libre ther mo dy na mique est atteint à une tem pé ra ture don -
née T, la pro ba bi lité, pour un sys tème phy sique, de pos sé der une éner gie don née E, est
pro por tion nelle au fac teur de Boltzmann : exp(–E/k B T), où k B désigne la constante de
Boltzmann ; la répar tition des états d’éner gie est alors la dis tri bu tion de Boltzmann à
la tem pé ra ture consi dé rée.
• D’autre part, pour simu ler l’évo lu tion d’un sys tème phy sique vers son équi libre
ther mo dy na mique à une tem pé ra ture don née T, on peut uti li ser l’algo rithme de
Metropolis : par tant d’une confi gu ra tion don née (dans notre cas, un pla ce ment ini -
tial de tous les com po sants), on fait subir au sys tème une modi fi ca tion élé men taire
(par exemple, on trans late un com po sant, ou on échange deux com po sants) ; si cette
trans for ma tion a pour effet de dimi nuer la fonc tion objec tif (ou éner gie) du sys tème,
elle est accep tée ; si elle pro voque au contraire une aug men ta tion DE de la fonc tion
objec tif, elle est accep tée tout de même, avec la pro ba bi lité exp(–DE/T) (en pra tique,
406
méthode de trai te ment des maté riaux (recuit réel) est mise en œuvre pour trai ter un
pro blème d’opti mi sation (recuit simulé).
11.3.2 Recuit réel et recuit simulé
Pour modi fier l’état d’un maté riau, le phy si cien dis pose d’un para mètre de com -
mande : la tem pé ra ture. Le recuit est pré ci sé ment une stra té gie de contrôle de la tem
pé ra ture en vue d’appro cher un état opti mal. Pour fixer les idées, pre nons l’exemple de
la crois sance d’un mono cris tal. La tech nique du recuit consiste à chauf fer préa la ble
ment le maté riau pour lui confé rer une éner gie éle vée. Puis on refroi dit très len te ment
le maté riau, en mar quant des paliers de tem pé ra ture de durée suf fi sante ; si la des cente
en tem pé ra ture est trop rapide, il appa raît des défauts qui peuvent être éli mi nés par
réchauf fe ment local. Cette stra té gie de baisse contrô lée de la tem pé ra ture conduit à
un état solide cris tal lisé, qui est un état stable, cor res pon dant à un mini mum absolu de
l’éner gie. La tech nique oppo sée est celle de la « trempe », qui consiste à abais ser très
rapi de ment la tem pé ra ture du maté riau : on obtient dans ce cas une struc ture amorphe,
état méta stable qui cor res pond à un mini mum local de l’éner gie. Avec la tech nique du
recuit, le refroi dis se ment du maté riau a pro vo qué une trans for ma tion désordre ordre,
tan dis que la tech nique de la trempe a abouti à figer un état désor donné.
L’idée d’uti li ser la tech nique du recuit en vue de trai ter un pro blème d’opti mi
sation a donné nais sance à la méthode du recuit simulé. Elle consiste à intro duire, en
opti mi sation, un para mètre de contrôle, qui joue le rôle de la tem pé ra ture. La « tem
pé ra ture » du sys tème à opti mi ser doit avoir le même effet que la tem pé ra ture du
sys tème phy sique : elle doit condi tion ner le nombre d’états acces sibles et conduire
vers l’état opti mal si elle est abais sée de façon lente et bien contrô lée (tech nique du
recuit) et vers un mini mum local si elle est abais sée bru ta le ment (tech nique de la
trempe). Pour ter mi ner la pré sen ta tion de la méthode, il nous reste à expo ser l’algo
rithme qui per met de pro gram mer le recuit simulé sur un ordi na teur.
11.3.3 Algo rithme du recuit simulé
L’algo rithme s’appuie sur deux résul tats de la phy sique sta tistique :
• D’une part, lorsque l’équi libre ther mo dy na mique est atteint à une tem pé ra ture don -
née T, la pro ba bi lité, pour un sys tème phy sique, de pos sé der une éner gie don née E, est
pro por tion nelle au fac teur de Boltzmann : exp(–E/k B T), où k B désigne la constante de
Boltzmann ; la répar tition des états d’éner gie est alors la dis tri bu tion de Boltzmann à
la tem pé ra ture consi dé rée.
• D’autre part, pour simu ler l’évo lu tion d’un sys tème phy sique vers son équi libre
ther mo dy na mique à une tem pé ra ture don née T, on peut uti li ser l’algo rithme de
Metropolis : par tant d’une confi gu ra tion don née (dans notre cas, un pla ce ment ini -
tial de tous les com po sants), on fait subir au sys tème une modi fi ca tion élé men taire
(par exemple, on trans late un com po sant, ou on échange deux com po sants) ; si cette
trans for ma tion a pour effet de dimi nuer la fonc tion objec tif (ou éner gie) du sys tème,
elle est accep tée ; si elle pro voque au contraire une aug men ta tion DE de la fonc tion
objec tif, elle est accep tée tout de même, avec la pro ba bi lité exp(–DE/T) (en pra tique,