Qu'est-ce que le recuit simulé?
Le recuit simulé est une technique informatique qui permet de trouver de bonnes solutions, même si elles ne sont pas nécessairement optimales, à un problème. Il porte ce nom car il imite le processus de recuit métallurgique. Dans les métaux, le recuit est le processus de purification en chauffant le métal puis en le refroidissant lentement. Le programme informatique "purifie" l'espace de la solution jusqu'à ce qu'il ne reste que les solutions les meilleures ou presque.
L'utilisateur d'un programme de recuit simulé doit spécifier deux facteurs critiques: la température de départ, ou le pourcentage de solutions moins performantes pouvant être explorées; et le taux de refroidissement, qui est le taux auquel ce pourcentage est réduit. Une température de départ basse finira souvent avec un résultat très éloigné de l'optimum. Si vous démarrez à une température très élevée, la recherche prend beaucoup plus de temps que nécessaire. De même, un taux de refroidissement trop élevé générera des résultats médiocres, tandis qu'un taux de refroidissement très faible donnera un programme très long.
L'état "haute température" du programme de recuit simulé est un paramètre qui lui permet d'examiner une large gamme de solutions, dont beaucoup sont pires que les solutions déjà trouvées. L’ordinateur est autorisé à examiner de nombreuses solutions qui sont pires que la solution actuelle pour éviter de s’en tenir à un minimum local qui est sensiblement pire que le meilleur. À titre d’exemple, on peut imaginer commencer au sommet d’une colline ou d’une montagne dans le but d’atteindre la base. En chemin, il peut y avoir des ravins ou des gouffres. Si l'ordinateur ne peut pas monter assez loin pour sortir, il restera bloqué même s'il n'est nulle part près de la base.
Jusqu'où le programme peut aller est déterminé par le pourcentage de pires solutions que le programme est autorisé à examiner. Au fil du temps, de meilleures solutions sont progressivement trouvées et le risque d'un gouffre profond diminue, ce qui diminue le pourcentage de solutions moins performantes que l'ordinateur peut explorer. Diminuer cette fraction est appelé "refroidissement". Lorsque la température atteint une fraction prédéfinie - qui n'a pas besoin d'être égale à 0 - la recherche est terminée.
L’utilisation des techniques de recuit simulé ou d’autres techniques de recherche en intelligence artificielle a pour objectif de réduire le temps nécessaire à la recherche d’une solution quasi optimale. Pour de nombreux problèmes, une recherche exhaustive - la mise à l’épreuve de chaque solution possible - pourrait prendre des mois, voire des années. L'alternative la plus connue au recuit simulé est l'algorithme génétique. D'autres algorithmes de recherche d'intelligence artificielle populaires incluent l'optimisation des colonies de fourmis, l'optimisation des essaims de particules, les plus proches voisins et les classificateurs Bayésiens.