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 5 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 5 (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 5 : 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.

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, et $\alpha$ s'en déduit, $\alpha = (T_f / T_0)^{1/N}$. 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 une fois sur deux ou plus, 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 5 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 les postes plus bas ; dix fois plus de budget n'y change rien ici (à un million d'évaluations, 80 % donne encore une médiane de 2 979,1 mm, contre 2 808,7 mm à 5 %, sur trente autres graines). 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 suivante 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.

Comparer honnêtement

Une cheffe d'atelier demande simplement : « le recuit est-il meilleur que les redémarrages ? ». La réponse n'est pas un nombre. Le premier constat du chapitre en donne la raison : les cinq résultats du recuit sur la tournée vont de 633,23 à 647,35 mm, les cinq de la descente de 633,23 à 645,65. Avec une graine, on aurait pu conclure ce qu'on voulait. Une méthode qui tire au hasard a une distribution de résultats, et c'est cette distribution qu'on compare.

Le budget peut se compter en évaluations ou en secondes. Les évaluations ne dépendent ni de la machine ni du langage, et c'est pourquoi elles servent ici. Le temps de calcul est plus proche de ce qui intéresse l'atelier, mais il ne se reproduit pas d'une machine à l'autre, et, on va le voir, un même budget en évaluations coûte ici des temps très différents selon la méthode. On peut rapporter les deux, en disant lequel a servi à égaliser.

Sur la grande plaque

Le programme suivant compare le recuit au 2-opt avec redémarrages du chapitre précédent, sur P-600, dont l'optimum, 2 788,70 mm, est démontré. Le budget est de 100 000 évaluations de voisins, dix graines pour chaque méthode, et le programme note aussi le temps de calcul de chacune. Le recuit est réglé à 5 % de dégradations acceptées au départ, à l'intérieur du plateau. Les redémarrages sont mesurés dans deux variantes, descente au meilleur voisin comme dans les figures du chapitre 5, puis descente au premier voisin qui raccourcit : comparer à une seule variante d'un concurrent, c'est risquer de choisir la plus faible. Un bloc du site est interrompu au bout d'environ huit secondes : le programme ne lance donc que le budget de 100 000 évaluations. Les lignes de 300 000 évaluations et d'un million du tableau ont été calculées avec le même programme sur un Python ordinaire, en changeant BUDGETS (un calcul trois fois, puis dix fois plus long).

Les pourcentages sont les écarts à l'optimum. Ce qu'on en tire :

• À 100 000 évaluations, les redémarrages ne finissent même pas une descente : une descente depuis un ordre tiré au hasard demande une centaine de milliers d'évaluations, et en moyenne 0,1 descente arrive à son optimum local. Le budget est trop court pour eux, pas pour le recuit, dont chaque itération n'évalue qu'un voisin.
• À 300 000 évaluations, le recuit reste devant sur les trois colonnes : la médiane est à 1,5 % de l'optimum, contre 4,6 % (meilleur voisin) et 2,5 % (premier voisin). Son pire résultat, à 2,2 %, est meilleur que la médiane des deux variantes de redémarrages. Le premier voisin est la variante qui rattrape le plus, l'écart se réduit mais reste.
• À un million d'évaluations, le meilleur des dix tirages atteint l'optimum pour le recuit et pour les redémarrages au meilleur voisin (0,6 % au premier voisin), mais la médiane et le pire restent nettement meilleurs pour le recuit : 0,3 % et 1,8 %, contre 2,2 % et 4,2 % pour les redémarrages au meilleur voisin, 1,6 % et 3,4 % au premier voisin.

Le constat du million d'évaluations est celui qui justifie la règle 2. À un million d'évaluations, le meilleur des dix tirages ne départage plus le recuit et les redémarrages au meilleur voisin : les deux ont trouvé l'optimum. Un lecteur pressé qui ne regarderait que ce nombre conclurait à l'égalité. Ce sont la médiane et le pire qui montrent que le recuit est plus régulier : on obtient à coup sûr une tournée proche de l'optimum, pas seulement avec de la chance. Refait sur trente graines (0 à 29), hors du navigateur, le classement est le même : médianes à 1,9 %, 1,3 % et 0,6 % de l'optimum pour le recuit à 100 000, 300 000 et un million d'évaluations, contre 6,8 %, 4,2 % et 1,9 % pour les redémarrages au meilleur voisin, 15,9 %, 2,9 % et 1,5 % au premier voisin.

Évaluations ou secondes

Toute la comparaison précédente égalise des évaluations. Or une évaluation ne coûte pas la même chose d'une méthode à l'autre, ni d'un programme à l'autre. Dans le programme ci-dessus, une itération de recuit (deux positions tirées, un nombre tiré, une exponentielle, parfois un segment retourné) demande de trois à cinq fois plus de temps, selon l'ordinateur, qu'une évaluation d'un balayage de descente, qui se réduit à quelques additions de distances : les durées de la sortie le montrent. À durée égale, les redémarrages disposent donc de trois à cinq fois plus d'évaluations, environ un million pour les 300 000 du recuit. Le même recuit écrit avec sample, qui donne exactement les mêmes résultats, coûte de dix à seize fois plus qu'une évaluation : quatre millions. Refait à durée égale avec chacune des deux écritures, hors du navigateur, sur trente graines (médianes, en écart à l'optimum) :

À durée égale, l'avance du recuit passe de 1,6 à 2,9 points à 0,2 à 0,6 point avec le programme du chapitre (sur cent trente graines, de 0,3 à 0,4 point : elle reste établie, mais petite), et s'inverse avec l'autre écriture, alors que le recuit rend exactement les mêmes résultats dans les deux cas. Le classement en secondes est donc autant une propriété du programme que de la méthode.

Sur un second problème : les postes

Le second problème est l'affectation de huit opérateurs à huit postes, de l'optimum connu, 95 minutes (la meilleure de 40 320 affectations). Le voisinage est l'échange de deux postes, 28 voisins, et le budget se compte de la même façon : une itération de recuit est une évaluation, un balayage complet de la descente en coûte 28. Le recuit est mesuré à trois températures, pour montrer ce que son réglage change ; les redémarrages, descentes au meilleur voisin depuis des ordres tirés au hasard, sont comparés à ces trois versions, vingt graines chacune. Les trois réglages sont donnés tous les trois, et aucun n'est choisi après coup pour paraître meilleur. Vingt graines suffisent à voir une grande différence, pas une petite : la suite le dit, avec les chiffres de deux cents graines, calculés hors du navigateur.

Ici, les redémarrages font au moins aussi bien, à chaque budget, même contre le meilleur des trois réglages du recuit essayés. À 1 000 évaluations, ils trouvent l'optimum 15 fois sur 20 contre 11 : l'écart va dans le même sens que le reste, mais vingt graines ne suffisent pas à l'établir. Refait à part sur deux cents graines, le constat tient : 156 optimums sur 200 pour les redémarrages, contre 115 pour le recuit à 50 %. À 3 000 évaluations, l'écart est d'une graine sur vingt (20 contre 19), ce qui ne prouve rien non plus, les deux méthodes trouvant presque toujours l'optimum ; sur deux cents graines, 199 contre 184. La raison de fond se comprend : il n'y a que 40 320 affectations, une descente complète coûte peu, et 1 000 évaluations en font en moyenne six, 3 000 près de vingt, qui explorent déjà une bonne part du petit espace. Le recuit, lui, a besoin de son budget pour refroidir, et il coûte ici environ deux fois plus de temps par évaluation que les redémarrages : à durée égale, l'écart ne ferait que croître. Sur cette taille, la méthode simple suffit, et le recuit coûte plus de réglage pour un résultat qui ne fait pas mieux.

Deux enseignements, qui ne se contredisent pas. Le premier : un pourcentage se transporte mieux qu'une température, mais pas parfaitement. Sur la plaque, tous les réglages de 2 % à 50 % se valent ; sur les postes, dont les dégradations sont de quelques minutes, 5 % et 20 % sont nettement moins bons que 50 % (sur deux cents graines, à 3 000 évaluations : 19 et 67 optimums, contre 184 à 50 % et de 184 à 187 de 50 % à 95 %). Le plateau n'a ni la même largeur ni la même position, et il faut le mesurer pour chaque problème. Le second, plus important : aucune méthode ne gagne partout. À évaluations égales, le recuit devance les redémarrages sur la grande plaque, où les descentes coûtent cher, et ne l'emporte pas sur la petite affectation, où elles coûtent peu ; et sur la grande plaque même, l'avantage ne survit pas toujours à une durée égale. Une comparaison n'a de sens que pour un problème, une taille, un budget et une unité de budget donnés, et le rôle du chapitre est de donner la méthode pour la mener, pas de désigner un vainqueur.

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 de ce chapitre. 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 baisse comme $c / \ln k$, avec $c$ au moins égal à la profondeur du creux le plus profond, 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

Exercices type

La méthode

1. Partir du squelette chercher du chapitre 5 : représentation, voisin, coût. Ne changer que accepter.
2. Écrire la dégradation dans le sens du problème : nouveau - actuel pour un coût, actuel - nouveau pour une marge.
3. Accepter une amélioration toujours, une dégradation avec la probabilité $e^{-\Delta/T}$, en tirant un nombre.
4. Refroidir géométriquement : $T \leftarrow \alpha\,T$ à chaque itération, avec $\alpha$ déduit de la température finale et du budget.
5. Mesurer les dégradations au départ, et régler $T_0$ pour qu'une proportion donnée soit acceptée. Essayer plusieurs proportions sur d'autres graines que celles qui jugeront.
6. Rendre la meilleure solution vue, pas la courante.
7. Comparer : plusieurs graines, meilleure, médiane et pire, budget égal dans une unité dite (évaluations, préparation comprise, ou durée), écart à l'optimum ou à une borne, méthode concurrente réglée avec le même soin, et le cadre de la comparaison dit.
8. Ne rien généraliser au-delà du problème, de la taille et du budget mesurés.

Synthèse

• Le recuit simulé accepte parfois un voisin moins bon, avec la probabilité $e^{-\Delta/T}$, pour sortir des optimums locaux ; la température $T$ s'exprime dans l'unité du coût.
• Seul le rapport $\Delta / T$ compte : une petite dégradation passe souvent à chaud et presque jamais à froid. À température presque nulle, c'est une descente ; à température énorme, une marche au hasard.
• Le recuit est le squelette chercher du chapitre 5 où seule la fonction accepter change, et qui rend la meilleure solution vue, pas la courante.
• Trois réglages : la température initiale, mesurée pour accepter une proportion donnée des dégradations au départ (sur P-600, un large plateau de 2 % à 50 %, pas 80 %) ; la décroissance géométrique, $T_k = T_0 \alpha^k$ ; l'arrêt par budget.
• Une méthode aléatoire se juge sur plusieurs graines : meilleure, médiane, pire ; à budget égal, dans une unité dite (évaluations, préparation comprise, ou durée) ; avec l'écart à l'optimum ou à une borne ; réglages faits avec le même soin sur d'autres graines.
• Sur P-600 (optimum 2 788,70 mm), à évaluations égales, le recuit devance les redémarrages : à 300 000 évaluations, sa médiane est à 1,5 % de l'optimum contre 4,6 % pour les redémarrages au meilleur voisin et 2,5 % au premier voisin. À durée égale, l'avance du recuit fond ou disparaît selon le programme : le classement dépend de l'unité du budget.
• Sur l'affectation, les redémarrages font au moins aussi bien, même contre le meilleur réglage du recuit essayé : aucune méthode ne gagne partout, et le plateau de réglage change d'un problème à l'autre.

Et ensuite

Le recuit ne garde aucun souvenir : pour sortir d'un creux, il s'en remet au hasard, et peut y retomber. Le chapitre suivant garde le squelette, mais échange le hasard contre une mémoire : la recherche tabou prend toujours le meilleur voisin, même moins bon, et s'interdit de revenir en arrière. La méthode de comparaison posée ici, unité du budget comprise, servira pour chacune des méthodes qui suivent. Pour situer ce que vaut une tournée sans connaître l'optimum, les bornes du chapitre 3 servent de règle ; pour le squelette et la descente, la recherche locale.