Complexité des problèmes et heuristiques
189
décroissance de la température
, un nombre d'itérations
à effectuer à
température constante, un test d'arrêt.
b) Pour une température donnée :
On explore une suite de
Si
), on retient
Si par ailleurs
alors
Si
on calcule
On tire dans la distribution de la loi uniforme.
Si
on retient ; sinon on ne le retient pas.
c) Lorsque l'on a atteint le nombre d'itérations d'une température donnée, on fait
décroître cette dernière par la fonction
et on reprend en ).
La loi de décroissance de la température est souvent prise de la forme , avec
(suite géométrique tendant vers ).
Comme on le voit, la méthode du recuit simulé est gourmande en choix initiaux. Il s'agit
en effet de choisir de façon efficace un certain nombre d'ingrédients :
- la fonction de voisinage
- la valeur initiale de
- la fonction de décroissance de
- le nombre d'itérations à constant
- la solution initiale
- le test d'arrêt
Un certain nombre de règles empiriques ont été préconisées par les spécialistes de ces
méthodes, mais on ne peut pas dire qu'existe à l'heure actuelle un algorithme unique
s'imposant à l'ensemble des problèmes que l'on cherche à résoudre. Il convient donc
d'ajouter une condition nouvelle pour que ce type de technique se révèle efficace, à
savoir l'expérience du modélisateur, seul susceptible, comme un grand chef dans sa
cuisine, de doser ces divers ingrédients en fonction de la configuration du problème.
Cela dit, la méthode du recuit simulé a fait ses preuves sur des problèmes combinatoires
de grande dimension, notamment des problèmes du type voyageur de commerce ou
encore des problèmes d'ordonnancement d'atelier.
Un de ses avantages est qu'elle est facile à programmer.
Un inconvénient de la méthode est constitué par le nombre important d'ingrédients qu'il
faut fixer au départ et qui, pour le moment, relèvent d'une expertise « pointue ».
La méthode Tabou, qui suit, n'a pas cet inconvénient.