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.
Historiquement, il y a plus de six millénaires, nos ancêtres ont pu découvrir des pépites d’or et de cuivre purs qui pouvaient se transformer en bijoux et autres objets par simple martelage. On suppose que c’est la chute fortuite de l’un de ces objets dans le feu qui leur permit de découvrir que le chauffage des métaux les rendait plus malléables et aussi plus stables. La technique du recuit a dû suivre assez rapidement et date donc probablement de l’Âge du cuivre (entre 5000 et 4000 ans avant notre ère).
Ça chauffe…
La modélisation du phénomène est beaucoup plus récente. Physiquement, les différents états possibles d’un système (étant donnée une certaine température) sont modélisés par une distribution de probabilité attribuée au physicien autrichien Ludwig Eduard Boltzmann (1844–1906), le fondateur de la physique statistique. Selon cette distribution, la probabilité pi qu’un système fermé présente un état énergétique Ei à température T est donnée par une expression du type pi = exp (–β Ei / T), dans laquelle β est une constante positive, que l’on choisira égale à 1 dans le cadre du recuit simulé pour des commodités de programmation.
Lorsque la température T augmente indéfiniment, l’exposant (négatif) présent dans l’expression tend vers 0, et l’exponentielle tend vers 1 par valeurs croissantes. Des états de haute énergie sont alors de plus en plus probables. Par contre, lorsque la température diminue, la probabilité de se retrouver dans un état élevé d’énergie, sans toutefois être nulle, diminue fortement. Supposons à présent que l’on puisse faire passer un système donné d’un état d’énergie E 1 à un état d’énergie E 2. Deux cas sont à envisager. Lorsque E2 < E1, on progresse vers la stabilité et l’on préférera la configuration du système correspondant à E 2. Lorsque E2 > E1, il semblerait que l’on se soit éloigné de la solution espérée, mais cela n’est pas certain car il se pourrait que l’on se retrouve dans le voisinage d’un minimum local. L’état E 2, en principe moins bon, ne va donc pas être systématiquement écarté. On décide que cet état E 2 sera conservé avec probabilité p = exp(–( E 2 – E 1) / T ).
Par complémentarité, le système restera à l’état E1 avec probabilité 1 – p. Plus le système est chaud, plus souvent on acceptera de passer à un état moins favorable. L’avantage en est que l’on échappera également plus souvent aux poches d’extrema locaux. Dans le cadre métallurgique, l’optimum recherché correspond donc toujours à un minimum.
Mais on sait bien que tout problème d’optimum peut se transformer en recherche d’un minimum par un éventuel changement de signe de la fonction à optimiser. De même, on peut remplacer la fonction « énergie » par n’importe quelle autre fonction. Un programme aléatoire de recherche de minimum peut dès lors être mis en place (voir en encadré).
[encadre]
L'algorithme de Metropolis-Hastings
On considère une fonction de plusieurs variables y = f (x1, x2… xn), identifiée à l’énergie E du système, et dont il convient de déterminer le minimum global sur un certain domaine D de ℝn. La procédure à implémenter doit suivre le schéma suivant.
• Partir d’un état initial X = ( x1, x2… xn ) appartenant à D et d’énergie E 1.
• Partir d’une température initiale T « élevée ».
- Introduire une procédure de changement d’état dans le cadre du domaine : X devient X + ΔX.
- Comparer les niveaux d’énergie des deux états (valeurs de la fonction à minimiser).
- Si le niveau E 2 correspondant à l’état X + ΔX est inférieur au niveau E1 correspondant à X, choisir le nouvel état du système, X + ΔX.
- Dans le cas contraire, opter pour l’état X + ΔX avec probabilité p = exp (–( E2 – E1 ) / T )
et pour l’état X avec la probabilité complémentaire q = 1 – p = 1 – exp (–( E2 – E1 ) / T ).
- Recommencer la procédure en partant du nouvel état.
• Modifier la température T du système en optant pour une tendance à la baisse.
[/encadre]
Le problème n’est pas résolu pour autant. Les auteurs de l’article de 1983 énumèrent l’ensemble des éléments à mettre en place avant toute tentative de mise en place du programme :
« L’implémentation de l’algorithme de Metropolis pour simuler le recuit d’un problème d’optimisation demande quatre ingrédients. Il faut tout d’abord une description concise de la configuration du système. Il faut construire un générateur de mouvements arrangeant le système selon une nouvelle configuration voisine. Il faut aussi quantifier objectivement la fonction à optimiser en fonction des paramètres décrivant la configuration du système. Il faut enfin adopter un schéma de recuit contenant la succession des températures choisies et le nombre de boucles associées à chaque température. »
Les auteurs insistent en précisant que ces quatre ingrédients sont rarement aisés à obtenir et qu’il faut le plus souvent procéder par essais–erreurs avant d’obtenir un programme réaliste. Des résultats existent, qualifiant notamment l’allure de la décroissance de la fonction température (qui doit être de type logarithmique ; on peut également la choisir constante par morceaux sur des paliers de longueur exponentielle). Des résultats de convergence en probabilité ont déjà été engrangés dans ces cas particuliers.
Le voyageur de commerce
La littérature désirant présenter des cas concrets illustrant la méthode se tourne le plus souvent vers le célèbre problème du voyageur de commerce, qui fut d’ailleurs l’exemple traité par les initiateurs de la méthode. Dans ce cadre, il est en effet assez aisé de donner une forme explicite de la fonction à minimiser.
Supposons qu’un voyageur doivent se rendre dans n villes notées v1, v2… vn, au départ de l’une d’entre elles, pour revenir ensuite à son point de départ. Soit M la matrice nn, symétrique, dont l’élément m i, j précise la distance séparant les villes vi et vj. Tous les éléments de M sont connus. À tout circuit ( permutation circulaire de v1, v2… vn ) correspond une somme de distances bien précise et aisément calculable. Le problème est que ce nombre de permutations croît en raison de la factorielle du nombre de villes, pour devenir rapidement hors de portée de tout processeur de calcul. Le recours aux méthodes heuristiques devient alors indispensable et le recuit simulé fournit, dans ce cas particulier, des résultats particulièrement fiables.
[encadre]
Une histoire de physiciens
Le physicien américain d’origine grecque Nicholas Metropolis a collaboré avec Robert Oppenheimer et Enrico Fermi dans le cadre de la conception du premier réacteur nucléaire. Dès 1949, il développa la célèbre méthode dite de Monte-Carlo (voir le précédent article de ce dossier), dont le développement théorique fut formalisé par le physicien américain Marshall Nicholas Rosenbluth (1927–2003). Metropolis fut aussi l’un des inventeurs de l’un des tout premiers ordinateurs opérationnels, qu’il baptisa du nom de MANIAC (pour mathematical analyzer, numerical integrator and computer) pour couper court à la mode des acronymes étranges qui désignaient ce genre de machines. MANIAC I fut totalement opérationnel dès 1952.
Scott Kirkpatrick est actuellement professeur à la School of computer science and engineering de l’université de Jérusalem (Israël). Ses travaux concernent la théorie de la complexité et les problèmes appartenant à la classe NP, acronyme de l’expression « non déterministe polynomial ». Un problème appartient à la classe NP s’il est possible de vérifier qu’un candidat solution à un problème de taille n satisfait bien aux contraintes du problème en un temps de calcul « raisonnable », c’est-à-dire majoré par une fonction prenant la forme d’un polynôme de degré n.
À gauche : Nicholas Constantine Metropolis (1915–1999).
À droite : Edward Scott Kirkpatrick (né en 1941).
[/encadre]
Lire la suite