Optimisation à l'aide du recuit simulé

L'optimisation c'est simplement chercher une configuration d'un système minimisant (ou maximisant) un critère.

Par exemple imaginons que vous vouliez faire un oeuf à la coque, c'est un problème tout con, mais on peut déjà voir un grand nombre de paramètre nous allons en prendre deux parmi les plus évidents : la puissance du feu et le temps de cuisson. Pour voir si vous avez fait du bon boulot on peut mesurer les défauts de votre produit : trop cuit, pas assez, etc... moins il y a de défaut meilleure est votre qualité et donc votre configuration.

On peut d'ailleurs imaginer une projection en trois dimensions sur une surface avec en largeur la puissance du feu, en longueur le temps de cuisson et en hauteur le niveau de défaut. Nous aurions alors une surface avec des creux et des bosses, la meilleure qualité correspondrait au point bas de notre surface.

Pour le recuit simulé, nous nous positionnons en dehors de tout cadre théorique permettant de calculer à coup sûr la meilleure solution. En clair pas d'équation magique pour savoir quel aspect ou goût aura mon oeuf en fonction du temps de cuisson et de la puissance du feu... En clair, l'approche traditionnelle va être d'avancer à tâtons, il nous faut donc trouver une méthode (appelée heuristique) pour guide notre tâtonnement. Généralement les heuristiques sont probabilistes : on est pas sûr d'avoir la meilleure solution, mais on a généralement une solution de très bonne qualité.

Un bon moyen de comprendre cette vue de l'optimisation c'est de s'imaginer parcourir un relief pour en chercher le point le plus bas ou le plus haut. Pour ajouter plus de réalisme et améliorer la métaphore, il faut également s'imaginer dans un brouillard complet, en clair vous ne voyez pas l'aspect du paysage. Vous êtes sur un point de l'espace vous avez donc une latitude et une longitude (temps et puissance de cuisson) qui correspondent à une altitude (le critère que vous cherchez à optimiser), c'est tout ce que vous savez.

Continuons dans notre métaphore pour vous expliquez comment marche le recuit simulé

Vous êtes donc gentiment dans une purée de pois, vous ne voyez pas où vous êtes. Et vous cherchez à descendre le plus possible, vous allez vous déplacer en trois étapes, chaque étape se déroulera comme suit :

• Vous faîtes quatre pas dans une direction de manière aléatoire ;
• Si vous vous êtes élevés alors selon que vous soyez à la première, seconde ou troisième étape vous jetez une pièce une, deux ou trois fois, si vous ne faites que des faces alors restez où vous êtes ;
  
• Si vous n'avez pas fait que des faces, vous retournez d'où vous venez ;
• Si vous êtes descendu vous restez où vous êtes.

L'idée c'est de descendre dès que l'on peut mais de ne pas s'interdire de monter de temps à autres pour éviter de rester bloquer dans des optimums locaux, c'est-à-dire des vallées intermédiaires.

On reste dans la première étape jusqu'à ce que l'on ai l'impression de ne plus trouver de nouvelles vallées (on ne trouve pas de nouveau point bas depuis 20 mouvements par exemple), on passe alors à la seconde étape, et on réitère ensuite pour le passage à la troisième.

Plus en profondeur, le recuit simulé est une métaheuristique inspirée d'un procédé métallurgique qui consiste a recuire puis refroidir lentement un métal, le refroidissement lent permet d'atteindre un niveau d'énergie plus bas qu'un refroidissement rapide (ça y en a être plus solide je crois).

Sous un cadre plus théorique, si un mouvement fait gagner une altitude ΔF, il sera accepté avec une probabilité de :


Où F représente la température, appelée ainsi en référence au modèle de la métallurgie... Plus notre système aura une température élevée, plus il sera susceptible d'accepter des remontés importantes pour s'extraire des vallées. En revanche avec une température proche de 0 aucune remontée ne sera acceptée.

Illustration réalisée avec Terragen (à tester impérativement)

Formule prise ici

Applet pour faire joujou ici