Le recuit simulé

Sortir d'un creux

Le chapitre sur la recherche locale a fini sur un constat : une descente s'arrête dans le premier creux qu'elle rencontre, et elle n'en sort pas, puisque sortir d'un creux demande de passer par des tournées plus longues. Les redémarrages contournent la difficulté par la force : ils repartent d'ailleurs, sans rien apprendre des essais précédents. Il existe une autre réponse, parfois plus économe : rester dans la même recherche, et s'autoriser de temps en temps un pas en arrière.

L'idée n'est pas neuve, et l'atelier la connaît. Un métal forgé se durcit, et ses défauts s'y figent : pour le rendre travaillable, on le recuit. On le chauffe assez pour que sa structure interne redevienne mobile, puis on le refroidit lentement. Pendant que la pièce est chaude, la matière se réarrange sans arrêt, y compris vers des états moins favorables, et c'est ce désordre qui lui permet de ne pas rester coincée dans un mauvais arrangement. En refroidissant, ces écarts deviennent de plus en plus rares, et la pièce se fige dans un arrangement très ordonné, en général bien meilleur que celui où l'aurait laissée une trempe, un refroidissement brutal, qui fige tout de suite le premier arrangement venu. La trempe est la descente, le recuit lent est la méthode de ce chapitre.

La transposition tient en trois correspondances. La solution courante est la pièce. Le coût est son énergie, celle qu'on veut minimiser. La température dit combien de désordre on tolère : haute, presque toutes les dégradations passent ; basse, presque aucune. Il ne reste qu'à écrire ce que « tolérer » veut dire, et c'est la règle suivante.

La règle d'acceptation

Cette règle vient de la physique statistique (Metropolis et ses coauteurs, 1953) ; Kirkpatrick, Gelatt et Vecchi (1983), puis Černý (1985), en ont fait une méthode d'optimisation. Son code tient en trois lignes, mais le comportement se lit mieux sur un tableau. Il donne la probabilité d'accepter une dégradation de $\Delta$ millimètres à la température $T$.

Trois lectures à retenir. D'abord, seul le rapport $\Delta / T$ compte : 50 mm à $T = 100$ et 5 mm à $T = 10$ passent avec la même probabilité, 0,61. La température n'est pas un nombre magique, c'est une échelle, à comparer aux dégradations que le problème produit. Ensuite, une petite dégradation passe souvent à chaud (5 mm à $T = 30$ passe 85 fois sur 100) et presque jamais à froid (20 mm à $T = 1$ ne passe pas). Enfin, une grosse dégradation ne passe qu'à chaud : 300 mm à $T = 30$, jamais ; à $T = 300$, 37 fois sur 100.

Les deux extrêmes se comprennent d'eux-mêmes. À température presque nulle, aucune dégradation ne passe, et le recuit est une descente. À température énorme, tout passe, et le recuit est une marche au hasard qui n'améliore rien. Le recuit vit entre les deux, en partant chaud pour explorer et en finissant froid pour se poser.

Le recuit, c'est le squelette avec une autre règle

Le squelette chercher(initiale, voisin, cout, accepter, iterations) du chapitre 7 a quatre étapes : tirer un voisin, le mesurer, décider de l'accepter, retenir la meilleure solution vue. Le recuit ne touche à aucune des quatre. Il ne change que ce que fait la troisième, c'est-à-dire la fonction accepter. Voici les deux règles côte à côte, et le programme qui applique la même charpente aux trois problèmes du chapitre précédent : la tournée, la machine, les postes.

Le tableau qui s'affiche met face à face la descente et le recuit, mêmes graines, mêmes nombres d'itérations. La descente redonne les résultats du chapitre 7 (633,23 ou 645,65 mm pour la tournée, de 17 à 20 heures de retard pour la machine, de 99 à 112 minutes pour les postes). Le recuit trouve 633,23 mm sur quatre graines sur cinq, 17 heures de retard sur les cinq, et 95 minutes, l'optimum, sur trois graines sur cinq. La cinquième graine de la tournée retombe dans le piège du chapitre 7 : 647,35 mm. Rien ne garantit la sortie d'un creux, on la rend seulement probable. Chaque ligne du recuit rappelle aussi sa température finale, le centième de $T_0$ : le refroidissement a bien eu lieu.

Trois détails du code méritent l'attention.

• Ce qui change tient en une fonction. chercher est recopié tel quel. Passer de seulement_si_meilleur à recuit(T0, refroidissement, graine) est le seul geste, dans l'appel :

  	Descente	Recuit
  règle passée à chercher	seulement_si_meilleur	recuit(T0, r, graine)
  mémoire	aucune	la température, qui baisse à chaque appel
  hasard	aucun	un nombre tiré pour chaque dégradation

• La température vit dans la règle. Elle baisse à chaque appel, et la fonction interne doit s'en souvenir d'un appel à l'autre : c'est le sens de etat = {"T": T0}, un petit carnet que la fonction accepter emporte avec elle et qu'elle modifie à chaque appel, sans que chercher en sache rien. Il reste consultable après coup, dans accepter.etat.

• chercher rend la meilleure solution vue, pas la courante. C'est capital pour le recuit : tant qu'il fait chaud, la solution courante s'éloigne de la meilleure, et la solution où la recherche s'arrête n'est pas forcément la meilleure rencontrée. La quatrième étape du squelette, qui semblait un détail pour la descente, devient ici la moitié de la méthode.

Ce qui reste, ce qui change. Le squelette du chapitre 7 sert tel quel : initiale, voisin, cout, et le suivi de la meilleure solution. Le recuit change accepter : un voisin moins bon passe avec la probabilité exp(-delta / T), et T baisse d'un facteur constant à chaque itération. Rien d'autre.

Les trois réglages

Le code laisse trois choses à décider. Ce sont les seuls réglages du recuit, et le chapitre les traite dans cet ordre.

La décroissance. La température doit baisser. La forme la plus courante est la décroissance géométrique : la température est multipliée par un même facteur $\alpha$, un peu inférieur à 1, à chaque itération, donc $T_k = T_0 \, \alpha^k$. Ce facteur n'est pas ce qu'on choisit d'abord : on choisit où la température doit arriver, par le rapport $T_0 / T_f$ de la température initiale à la température finale, et en combien d'itérations, $N$ ; le facteur s'en déduit, $\alpha = (T_f / T_0)^{1/N}$, puisque $N$ multiplications par $\alpha$ doivent mener de $T_0$ à $T_f$. C'est ce que fait refroidissement_pour dans le code plus haut : « diviser la température par un rapport de cent en $N$ itérations ». La décroissance géométrique perd beaucoup de température en valeur absolue au début, quand elle est élevée, et très peu à la fin, là où la recherche a besoin de temps pour se stabiliser.

L'arrêt. Ici, le recuit s'arrête après un nombre fixé d'itérations, le budget. C'est le choix le plus simple, et surtout le seul qui rende deux méthodes comparables : on ne compare pas deux recherches sans savoir combien chacune a travaillé. Le budget fixe aussi la température finale : avec un rapport de cent, la température finale est le centième de la température initiale, et les dernières itérations ressemblent à une descente, ce qui est voulu. Le rapport compte moins que la température initiale, et se règle aussi par la mesure, ce que fait la section suivante.

La température initiale. C'est le réglage qui décide de tout, et le plus facile à mal faire. Trop froide, le recuit est une descente qui perd son temps à quitter des creux qu'il ne quittera pas. Trop chaude, il erre au hasard pendant le premier tiers de son budget, sans rien construire. La bonne valeur dépend de la taille des dégradations que le problème produit, en millimètres pour la tournée, en minutes pour les postes : un nombre choisi à l'œil pour une plaque ne vaut pas pour l'autre. Une règle simple existe : régler la température de départ pour qu'une proportion donnée des dégradations soit acceptée au début. Cela ramène un réglage en millimètres à un réglage en pourcentage, plus facile à comparer d'un problème à l'autre. La section suivante le mesure. Avant cela, la figure fait sentir ce que ces deux curseurs changent.

Le recuit sur la plaque P-600

La figure suivante fait régler et lancer le recuit sur la plaque P-600, soixante trous, à partir du plus proche voisin. Les deux curseurs sont la température initiale et la vitesse de refroidissement. Chaque lancer tire une graine neuve : deux tirages ne se ressemblent pas, et c'est voulu. Les chiffres du texte viennent de graines fixées et se rejouent en Python ; ceux de la figure changent à chaque lancer et ne se rejouent que dans la figure. Aucune référence n'est donnée avant l'essai.

Régler en mesurant

Le code suivant règle la température initiale par la mesure. Il engendre P-600, part du plus proche voisin, tire mille voisins par 2-opt et note les dégradations qu'ils produisent. Une petite fonction trouve alors la température qui fait accepter, en moyenne, une proportion donnée de ces dégradations : il suffit de chercher, par dichotomie, la température pour laquelle la moyenne des $e^{-\Delta/T}$ vaut la proportion visée. Le code règle ensuite le recuit sur plusieurs proportions, chacune sur dix graines, pour voir laquelle convient, avec un budget réduit qui le garde rapide dans le navigateur.

Une remarque avant la lecture. Le squelette chercher recalcule toute la longueur à chaque tirage, soixante distances. Un 2-opt ne change que deux trajets, et sa variation se calcule avec quatre distances, comme au chapitre précédent. Le code contient donc une version plus rapide du même recuit. Elle change aussi la façon de tirer les deux positions : deux_positions reproduit les tirages de sample(range(n), 2) dès que n dépasse 21, donc les mêmes positions sur les soixante trous de P-600, sans le temps que sample perd à se préparer à chaque appel. Elle est équivalente : le premier affichage compare les deux sur la même graine, et donne exactement le même résultat. Un programme rapide qui n'a pas été comparé à l'original n'est pas une version rapide de l'original, c'est un autre programme.

Le plus proche voisin mesure 3 588,87 mm, et les deux versions, à dix mille tirages et la même graine, donnent le même résultat, 2 977,15 mm. Sur les mille voisins tirés, 968 sont des dégradations, de 374 mm en moyenne : ce sont de gros écarts, parce qu'un 2-opt tiré au hasard retourne en général un long segment. Pour que 5 % de ces dégradations soient acceptées en moyenne, il faut une température de 48,1 mm, bien en dessous de la dégradation moyenne : la moyenne des probabilités est tirée par les quelques pour cent de petites dégradations (moins de 50 mm), qui passent au moins une fois sur trois, alors que les trois quarts des dégradations, de plus de 200 mm, ne passent presque jamais.

La dernière partie du programme règle le recuit à quatre proportions, sur dix graines et 20 000 évaluations seulement, pour tenir dans le temps d'un bloc. Elle donne déjà la forme : trop froid (0,5 %), une médiane à 2 966 mm ; 5 %, 2 915 mm ; 50 %, déjà trop chaud à ce petit budget, 3 054 mm ; trop chaud (80 %), 3 588,9 mm, c'est-à-dire le départ lui-même, rien n'ayant été amélioré sur la moitié des graines au moins. Le tableau suivant est la même boucle au budget des comparaisons, 100 000 évaluations, sur trente graines et quatre réglages de plus (1 %, 2 %, 10 % et 30 %) : plus de vingt millions d'itérations, très au-delà de la limite de temps d'un bloc. Il a été calculé hors du navigateur, avec le même programme en remplaçant BUDGET, GRAINES et la liste des proportions.

Il se lit ainsi (trente graines, 100 à 129, 100 000 évaluations, température finale au centième de $T_0$).

• Trop froid, 0,5 % et 1 % : les médianes montent à 2 938,9 et 2 906,2 mm, on retrouve une descente, dont le chapitre 7 a chiffré le résultat depuis le plus proche voisin, 2 944,01 mm.
• Trop chaud, 80 % : 3 155,8 mm, une grande part du budget passe à errer. Le recuit fait moins bien que la descente qu'il devait améliorer.
• De 2 % à 50 %, les médianes vont de 2 825,8 à 2 853,3 mm, un écart de moins de 30 mm, que l'incertitude d'une médiane de trente graines (de l'ordre de 10 à 20 mm) ne permet pas de lire, alors qu'un même réglage donne, d'une graine à l'autre, des résultats qui s'étalent sur 100 à 150 mm. Le réglage se trouve sur un plateau, large, pas sur un point, et on choisit à l'intérieur, pas au bord : ici 5 %.

La règle, souvent citée, d'accepter 80 % des dégradations au départ ne convient pas ici : c'est le plus mauvais des réglages du tableau. Elle peut convenir à d'autres voisinages, dont les dégradations sont petites, comme celui des postes au chapitre 12 ; dix fois plus de budget n'y change rien ici (à un million d'évaluations, 80 % donne encore une médiane de 2 977,4 mm, contre 2 817,1 mm à 5 %, sur trente autres graines, 130 à 159). Ce qui convient dépend du problème, du voisinage et du budget, et se trouve par la mesure, pas par une règle apprise.

Le rapport de refroidissement se règle de la même manière, et compte moins : à 5 %, avec un rapport de dix, cent puis mille (RAPPORT dans le programme), les médianes sur trente graines sont de 2 837,5, 2 841,8 et 2 852,0 mm, à quinze millimètres près, un écart que trente graines ne permettent pas de lire. Le rapport de cent est un bon choix par défaut, pas une loi.

Le coût de cette mesure compte aussi. Les mille tirages qui ont servi à mesurer les dégradations sont des évaluations comme les autres : dans le programme, ils sont retirés du budget (99 000 itérations de recuit pour 100 000 évaluations). Une comparaison à budget égal qui oublierait de compter la préparation avantagerait le recuit. La figure, elle, donne cette mesure sans la compter.

Deux pièges à éviter dans un tel réglage. Le premier : les graines qui règlent ne sont pas celles qui jugent. Le tableau ci-dessus utilise les graines 100 à 129, et la comparaison du chapitre 12 les graines 0 à 9. Régler et juger sur les mêmes graines revient à régler un instrument sur l'échantillon qui doit ensuite servir à le contrôler. (La mesure des dégradations ne juge aucun résultat, elle fixe seulement l'échelle : elle prend la graine 0 ; celle des postes, une graine à part.) Le second : régler avec le même soin les deux méthodes qu'on compare, sinon on compare un réglage bien fait à un réglage bâclé (un T0 = 100 pris à l'œil contre un concurrent soigneusement mis au point ne dit rien sur les méthodes, il mesure la qualité des réglages). La mesure du chapitre coûte mille évaluations et se refait pour chaque problème.

Reste à savoir si le recuit ainsi réglé fait mieux que les redémarrages du chapitre 7. La réponse n'est pas un nombre : la méthode pour la donner, plusieurs graines, à budget égal dans une unité dite, avec l'écart à une référence, fait l'objet du chapitre 12, qui compare les deux méthodes sur la grande plaque et sur les postes.

Autres réglages, autres arrêts

La décroissance géométrique et l'arrêt par budget sont les choix les plus simples, pas les seuls. Plusieurs variantes existent et se lisent d'après ce chapitre.

• Refroidir par paliers : garder la même température pendant un nombre fixé d'itérations, puis la baisser d'un coup. C'est une forme classique, où l'on règle deux nombres au lieu d'un.
• Arrêter plus tôt quand la température est trop basse pour accepter la moindre dégradation, ou quand plusieurs milliers d'itérations n'ont rien amélioré. Le budget fixe est plus simple et rend la comparaison possible.
• Repartir : relancer le recuit depuis la meilleure solution vue, avec une température de départ plus basse. C'est un moyen d'utiliser un budget plus grand quand la première passe n'a plus rien à donner.

Aucune n'est meilleure par principe. Chacune ajoute un réglage, et la méthode pour les juger est celle du chapitre 12. La théorie ne dispense pas de mesurer : un résultat de Hajek (1988) garantit que la probabilité d'être sur un optimum global tend vers 1 si la température de l'itération $k$ baisse comme $c / \ln k$, avec $c$ au moins égal à la profondeur du plus profond des creux qui ne contiennent pas d'optimum global (la hausse de coût qu'il faut accepter pour en sortir), mais cette décroissance est trop lente pour servir en pratique, et la décroissance géométrique n'a pas cette garantie. Elle se juge par la mesure, comme tout ce chapitre.

Les erreurs d'un débutant

Mettre en pratique