Le recuit simulé


la métallurgie à la rescousse

Daniel Justens

Comment distinguer un minimum local d'un minimum global pendant une procédure de calculs approchés ? Le recuit simulé, fondé sur une pratique courante de l'industrie métallurgique, propose une méthode empirique délicate mais néanmoins efficace pour de nombreuses applications.


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 ... Lire la suite