Qu'est-ce que le recuit simulé?
Le recuit simulé est une technique informatique qui peut trouver des solutions bonnes - mais pas nécessairement optimales - à un problème. Il est ainsi nommé parce qu'il imite le processus métallurgique de recuit. Dans les métaux, le recuit est le processus de purification en chauffant le métal puis le refroidissant lentement. Le programme informatique "purifie" l'espace de solution jusqu'à ce que tout ce qui reste sont des solutions les meilleures ou presque les meilleures.
Il existe deux facteurs critiques que l'utilisateur d'un programme de recuit simulé doit spécifier: la température de démarrage ou le pourcentage de pires solutions qui peuvent être explorées; et le taux de refroidissement, qui est la vitesse à laquelle ce pourcentage est réduit. Une basse température de départ se terminera souvent par un résultat de loin de l'optimum. Commencer à une température très élevée peut entraîner la recherche en prenant bien plus de temps que nécessaire. De même, un taux de refroidissement trop élevé générera de mauvais résultats, tandis qu'un très faible taux de refroidissement entraîneraun programme qui fonctionne pendant très longtemps.
L'état "à haute température" pour le programme de recuit simulé est un paramètre qui lui permet d'examiner une large gamme de solutions, y compris beaucoup qui sont pires que les solutions qu'elle a déjà trouvées. L'ordinateur est autorisé à examiner de nombreuses solutions pires que la solution actuelle pour éviter de coller à un minimum local qui est bien pire que le meilleur. Par exemple, on peut imaginer commencer au sommet d'une colline ou d'une montagne dans le but d'atteindre la base. En cours de route, il peut y avoir des ravins ou des gouffres. Si l'ordinateur ne peut pas aller assez loin pour sortir, il restera coincé même s'il est loin de la base.
La distance à laquelle le programme peut aller est déterminé par le pourcentage de pires solutions, le programme est autorisé à examiner. Avec le temps, des solutions progressivement de meilleuresLe gouffre diminue, donc le pourcentage de pires solutions que l'ordinateur peut explorer est diminué. La diminution de cette fraction est appelée «refroidissement». Lorsque la température atteint une fraction prédéfinie - qui ne doit pas être 0 - la recherche se termine.
La raison d'utiliser un recuit simulé ou d'autres techniques de recherche d'intelligence artificielle est de réduire à une quantité gérable le temps nécessaire pour trouver une solution presque optimale. Pour de nombreux problèmes, une recherche exhaustive - le test de chaque solution possible les uns contre les autres solution possible - pourrait prendre des mois ou des années. L'alternative la plus connue au recuit simulé est les algorithmes génétiques. D'autres algorithmes de recherche populaire de l'intelligence artificielle comprennent l'optimisation des colonies de fourmis, l'optimisation de l'essaim de particules, le voisin le plus proche et les classificateurs bayésiens.