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