Certains problèmes réels peuvent se révéler trop complexes pour pouvoir déboucher sur l’obtention de solutions exactes. Le recours à des méthodes d’approximations successives, déterministes ou aléatoires, livre alors souvent des résultats utilisables et relativement fiables. Parmi toutes ces méthodes, le curieusement nommé « recuit simulé » présente plus d’un intérêt, notamment pour la recherche d’optima globaux.
Sortir des poches locales -------------------------
Des fonctions élaborées de plusieurs variables à optimiser peuvent en effet présenter toute une collection d’optima locaux. Lors de la mise en œuvre d’une méthode de calcul approché, comment éviter de se laisser enfermer dans l’une de ces poches locales et de « passer à côté » de l’optimum véritable recherché ? La méthode qui a été développée par trois ingénieurs d’IBM, Scott Kirkpatrick (né en 1941), Charles Daniel Gelatt Jr. (né en 1947) et Mario Pietro Vecchi (né en 1948), dans le cadre de leurs recherches sur les circuits intégrés, fut publiée dans la revue Science en 1983. Elle s’inspire directement de méthodes utilisées en métallurgie, tout en mettant en application une procédure algorithmique déjà existante et publiée en 1949 par Nicholas Metropolis. Cette méthode algorithmique sera améliorée par son créateur en 1953, avant d’être généralisée en 1970 par le statisticien canadien Wilfred Keith Hastings (1930–2016).
Dans le cadre métallurgique, ce que l’on nomme recuit d’une pièce métallique consiste en un procédé de chauffage se traduisant d’abord par un maintien à température élevée, suivi d’un refroidissement contrôlé permettant la modification des caractéristiques du métal. On alterne des cycles de réchauffage (ou de recuit, annealing en anglais, de to anneal, « recuire ») et de refroidissement lent. Lorsque le métal est chauffé, l’énergie qui lui est fournie permet aux molécules qui le constituent de briser certaines de leurs liaisons, rendant aux atomes ainsi formés une certaine mobilité. Lorsque le métal refroidit, cette mobilité diminue et de nouvelles liaisons vont se former.
On constate empiriquement qu’un refroidissement lent se traduit le plus souvent par l’apparition de structures plus stables, correspondant à un minimum global d’énergie. On obtient alors un métal plus souple, plus flexible et présentant peu d’irrégularités.