Le recuit simulé

L’expression « recuit simulé » est la traduction de Simulated Annealing. Dans la réalité, le terme « recuit » correspond à un réchauffement suivi d’un refroidissement lent. Un tel procédé est souvent utilisé dans l’industrie. Selon que des métaux chauffés au rouge sont refroidis rapidement ou lentement, ils présentent des propriétés complètement différentes. Pourquoi ? Réfléchissons à ce qui se passe dans un métal à l’échelle atomique.

À l’origine, les atomes qui composent ce métal sont pris dans une structure cristalline solide. Lorsqu’on chauffe le métal, les atomes commencent à se détacher de leurs liaisons et à se déplacer. La structure originelle est alors détruite. Si on le refroidit ensuite lentement, les atomes cherchent à former de nouvelles liaisons. Chose surprenante, ils se répartissent souvent de manière plus régulière que précédemment. Si tout est fait dans les règles de l’art, le métal devient plus souple, plus flexible et présente moins d’irrégularités. Ce procédé est aussi utilisé lors de la fabrication de semi-conducteurs en silicium pour les microprocesseurs et les modules de mémoire des ordinateurs. Ces composants nécessitent un cristal de silicium extrêmement pur, ne présentant en particulier aucune irrégularité. Afin de mieux comprendre l’effet du refroidissement lent, imaginons les atomes comme des petites sphères. Si on jette simplement ces billes dans un récipient (comme dans la première applet ci-dessous), elles risquent de s’éparpiller de manière assez désordonnée. Que pourrait-on faire pour les ordonner ? Les secouer ! Bien sûr, au début, le désordre ne fait qu’augmenter, et les billes voltigent, car le fait de les secouer provoque un réchauffement. Mais si on les secoue de plus en plus lentement, elles s’ordonnent toutes seules ! Sur cette applet, un curseur de régulation permet de secouer les billes plus ou moins fortement, ce qui correspond à une température plus ou moins élevée. Les sphères sont un peu collantes et peuvent également se serrer les unes contre les autres. Secouez-les puis ramenez le curseur à 0 et voyez comment elles s’empilent de manière plus ou moins compacte.

Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.

Surprenant, n’est-ce pas ? Mais quel est le rapport avec l’informatique et les algorithmes, et pourquoi en faire une simulation ? Pour le comprendre, prenons l’exemple d’un problème informatique caractéristique, celui du voyageur de commerce. Un voyageur de commerce veut se rendre dans un grand nombre de villes le plus rapidement possible, en passant une fois et une seule par chaque ville. Il s’agit donc de déterminer le meilleur ordre dans lequel il doit visiter ces villes, de sorte que le chemin parcouru soit le plus court possible. Étonnamment, il s’agit d’un problème très difficile. Peut-être trouverez-vous la meilleure solution en utilisant le recuit simulé. Il est facile de trouver une solution quelconque : prenons un ordre au hasard ! Dans la seconde applet, nous voyons un certain nombre de villes reliées par un parcours aléatoire. Il est bien sûr peu probable que ce chemin soit très court. Comment pouvons-nous améliorer ce parcours ? On peut le faire par petites touches en apportant des modifications locales, et si le parcours obtenu est meilleur, nous conservons la modification, sinon nous l’annulons. Une modification locale possible est d’inverser l’ordre des villes sur une partie du parcours choisie au hasard.

Une autre possibilité consiste à choisir une des villes et à changer sa place dans le parcours tout en conservant l’ordre de toutes les autres villes.

Itérer des modifications locales pour ne conserver que celles qui améliorent le parcours, c’est exactement ce que réalise l’applet suivante pour les températures très basses.

Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.

En laissant le nombre de villes à 50, abaissez la température à 0, puis appuyez sur le bouton de démarrage. Vous verrez que la solution s’améliore continuellement puis se stabilise. Étant donné que la température est basse, seules des modifications améliorant le parcours seront retenues, et il arrive un moment où une telle modification devient impossible à trouver. Mais plus la température est élevée, plus des modifications qui dégradent la solution pourront être retenues. C’est essentiel pour échapper à une solution qui ne serait pas la meilleure, mais ne pourrait toutefois pas être améliorée localement par de simples substitutions. Notez la longueur du parcours calculé et élevez à nouveau la température à 100. Le parcours se modifie à nouveau et vous pouvez alors baisser la température très très lentement. Si vous avez suffisamment de patience, vous devriez obtenir une meilleure solution. Ce procédé d’optimisation simule un processus naturel et ne s’applique pas seulement au problème du voyageur de commerce. Il est également utilisé pour résoudre de nombreux problèmes d’optimisation délicats, pour lesquels il est possible de trouver facilement une solution quelconque et de l’améliorer localement. Ces méthodes, qui fonctionnent souvent très bien, mais n’offrent aucune garantie d’obtenir la solution optimale ou ne serait-ce qu’une bonne solution, sont appelées heuristiques. Le recuit simulé est un procédé inspiré par la nature. Même si la plupart des algorithmes ne présentent pas cette propriété, il existe, outre le recuit simulé, bien d’autres méthodes trouvant leur origine dans des phénomènes naturels, par exemple les algorithmes génétiques.

Une première version de ce document est parue en allemand dans la série Algorithmus der Woche publiée à l’occasion de l’Année de l’informatique (Informatikjahr) 2006.
L’adaptation des applets en français a été réalisée par Hamdi Ben Abdallah.