188
Recherche opérationnelle
Mais comme la décroissance de la température est un processus difficile à maîtriser
complètement, il peut se faire qu'elle soit trop rapide et qu'elle conduise à des états
métastables. La technique dite du recuit consiste alors à réchauffer le matériau afin que
les molécules quittent leur état d'énergie locale minimale, puis de reprendre la baisse de
la température.
La méthode du recuit simulé, en optimisation combinatoire, va reprendre à sa manière
ces différentes notions : les spécifications des variables seront assimilées aux
coordonnées des molécules, la valeur de la fonction économique à l'énergie ; quant à la
température, elle va donner l'idée d'une fonction de contrôle du protocole d'amélioration
itérative, permettant notamment de calculer des probabilités de choix de solutions
« dégradantes » (analogie avec l'augmentation provisoire de température).
Plus précisément, le principe général est le suivant :
Supposons que nous soyons en une solution
et que la fonction de voisinage nous
donne une solution
On retiendra
avec une probabilité égale à 1 si
et égale à une certaine
fonction si
Cette fonction est de la forme :
étant un paramètre entièrement contrôlé que l'on fait décroître tout au long du
processus, et qui joue le rôle de la température dans le processus du recuit métallurgique
(on continue d'ailleurs à appeler ce paramètre température dans la méthode du recuit
simulé).
Au début du processus, étant élevé, est voisin de et on aura tendance à accepter de
nombreuses solutions qui dégradent . À la fin du processus, est voisin de et on
n'accepte plus que rarement cette circonstance.
La technique permettant de savoir si on retient à partir du moment où
est très simple : à partir d'un programme de génération de nombre aléatoire (il en existe
dans toutes les bibliothèques de programmes informatiques), on extrait une valeur u,
réalisation de la variable uniforme sur
Si
on accepte ; on ne l'accepte pas dans le cas contraire.
La technique du recuit simulé consiste à faire baisser la température par paliers, un
certain nombre d'itérations ayant donc lieu à température constante.
La méthode du recuit simulé peut donc se décliner, d'une façon générale, de la façon
suivante :
a) Initialisation
Partir d'une solution initiale
On se donne par ailleurs une
fonction de voisinage
(ensemble ), une température initiale
, une loi de
Recherche opérationnelle
Mais comme la décroissance de la température est un processus difficile à maîtriser
complètement, il peut se faire qu'elle soit trop rapide et qu'elle conduise à des états
métastables. La technique dite du recuit consiste alors à réchauffer le matériau afin que
les molécules quittent leur état d'énergie locale minimale, puis de reprendre la baisse de
la température.
La méthode du recuit simulé, en optimisation combinatoire, va reprendre à sa manière
ces différentes notions : les spécifications des variables seront assimilées aux
coordonnées des molécules, la valeur de la fonction économique à l'énergie ; quant à la
température, elle va donner l'idée d'une fonction de contrôle du protocole d'amélioration
itérative, permettant notamment de calculer des probabilités de choix de solutions
« dégradantes » (analogie avec l'augmentation provisoire de température).
Plus précisément, le principe général est le suivant :
Supposons que nous soyons en une solution
et que la fonction de voisinage nous
donne une solution
On retiendra
avec une probabilité égale à 1 si
et égale à une certaine
fonction si
Cette fonction est de la forme :
étant un paramètre entièrement contrôlé que l'on fait décroître tout au long du
processus, et qui joue le rôle de la température dans le processus du recuit métallurgique
(on continue d'ailleurs à appeler ce paramètre température dans la méthode du recuit
simulé).
Au début du processus, étant élevé, est voisin de et on aura tendance à accepter de
nombreuses solutions qui dégradent . À la fin du processus, est voisin de et on
n'accepte plus que rarement cette circonstance.
La technique permettant de savoir si on retient à partir du moment où
est très simple : à partir d'un programme de génération de nombre aléatoire (il en existe
dans toutes les bibliothèques de programmes informatiques), on extrait une valeur u,
réalisation de la variable uniforme sur
Si
on accepte ; on ne l'accepte pas dans le cas contraire.
La technique du recuit simulé consiste à faire baisser la température par paliers, un
certain nombre d'itérations ayant donc lieu à température constante.
La méthode du recuit simulé peut donc se décliner, d'une façon générale, de la façon
suivante :
a) Initialisation
Partir d'une solution initiale
On se donne par ailleurs une
fonction de voisinage
(ensemble ), une température initiale
, une loi de