Principe du recuit simulé

Principe

Le recuit simulé est une méthode méta-heuristique adaptée à des problèmes complexes d’optimisation. Cette méthode, utilisée en métallurgie ou en cristallographie, consiste à chauffer un métal (cristal) puis à le refroidir progressivement, afin d’obtenir les propriétés physiques et mécaniques recherchées (dureté / déformabilité).

Cet algorithme d’optimisation manipule un problème en le changeant de très nombreuses fois d'état, par l'intermédiaire de transitions. A chaque changement de l'état du problème, il évalue le coût de la solution, et retient au final le coût le plus faible.

Ces problèmes d’optimisation n’admettent aucune méthode connue permettant de trouver la solution optimale en un temps fini, le nombre de solutions à envisager étant souvent bien trop grand.

Exemple d’un cas de planification simple dans une structure lambda, pour des plannings au quart d'heure :

Admettons un paramétrage qui contient :

• des heures de début de journée possibles entre 8h et 18h ((18-8)*4 = 40 possibilités d’heure de début)
• des durées de travail comprises entre 3h et 8h ((8-3)*4 = 20 possibilités de durées)
• 5 jours de travail
• 6 possibilités de placement pour le jour de repos

Cela représente 40*20*5*6 = 24000 possibilités.

L’horaire d’une personne admet dans ce cas de figure 24000 solutions possibles sur une semaine. Les horaires de 23 personnes admettent donc 24000²³ solutions, c’est-à-dire plus de 10¹⁰⁰ solutions.

Et dans cet exemple, on ne tient pas compte des coupures déjeuner, des pauses, etc.

Fonctionnement en planification

Par analogie, en planification, on parle de la température de recuit pour désigner l’état d’avancement du calcul.

Au démarrage du calcul celui-ci est à la température initiale. Un certain nombre d’itérations sont effectuées, chacune réalisant une modification élémentaire de l’état courant du problème à la suite de laquelle l’état courant est évalué : s’il est meilleur que l’état précédent il est conservé, sinon il peut tout de même être conservé en fonction d’une probabilité dépendant de la température ou rejeté. Si le nouvel état est meilleur que la meilleure solution trouvée jusqu’à présent, celui-ci devient la meilleure solution. Quand le nombre maximum d’itérations a été atteint, on baisse la température et on applique le même nombre d’itérations à cette nouvelle température. On continue comme cela jusqu’à atteindre la température finale ou trouver une solution parfaite (c’est-à-dire satisfaisant les conditions demandées : pendant la phase de légalisation une solution « légale » c’est-à-dire respectant tous les paramètres de calcul, ou une solution à coût nul pendant la phase d’optimisation).

Le nombre total d’itérations effectuées est donc fini et dépend du nombre de pas de température et du nombre d’itérations par pas de température. Les valeurs par défaut de la température initiale, température finale et le nombre d’itérations peuvent être paramétrés dans les réglages de l’application. Ces valeurs sont différentes pour la phase de légalisation et pour la phase d’optimisation.

En planification, le coût à minimiser est le nombre de quarts d’heure de surplus et de manque, c’est-à-dire l’écart entre les besoins et les ressources. Il y en a d'autre, comme l'affectation des personnes les plus compétentes pour une tâche donnée ou le respect de contraintes sociales comme l'équité.

On représente graphiquement le problème sous forme d’une courbe à deux dimensions donnant le coût en ordonnées en fonction de tous les états possibles en abscisses : il faut donc trouver le point le plus bas de la courbe, la solution de plus bas coût.

La température

On peut imaginer l’analogie suivante : on lâche une bille à un quelconque endroit de la courbe et la bille roulera jusqu’au creux le plus proche et s’y arrêtera, ne pouvant aller plus bas. Le risque est que la bille s’arrête dans un minima local, c’est-à-dire un creux de la courbe situé beaucoup plus haut que le point le plus bas possible.

Pour cela, le recuit simulé reprend cette méthodologie simple en y ajoutant un concept fondamental : celui de la température. Ce paramètre permet à la bille de « remonter » certaines bosses, afin de pouvoir atteindre d’autres « creux » situés derrière.

La température peut se représenter comme la hauteur des bosses que la bille peut remonter.

Le principe consiste à partir d’une température très haute (la bille peut passer par-dessus des pics très hauts), pour atteindre à la fin une température nulle (la bille ne pourra plus remonter du tout).

Ainsi, au début du recuit, on pose une température élevée, cette température va descendre par paliers successifs. Plus la température est élevée, plus les deltas-coûts positifs élevés sont acceptés. Donc au début du recuit on pourra avoir de gros deltas-coûts positifs, et à la fin on n'acceptera plus que les delta-coûts négatifs.

Sur le schéma suivant, la bille placée en A peut passer par-dessus le pic B, pour « rouler » ensuite jusqu’au point C, mais elle pourra ensuite plus remonter vers B et A.

Deux recuits successifs

Tout au long du recuit, le problème manipulé doit rester dans un état cohérent et légal.

Par exemple dans un calcul d'horaires, un planning est cohérent si ses plages de travail ne se chevauchent pas, si les tâches sont entièrement incluses dans des plages de travail, etc.
Un planning est légal s'il respecte les paramètres de calcul saisis par l'utilisateur.

Le recuit simulé doit donc manipuler un problème cohérent et légal, et cela doit être vrai dès le début du calcul. Le principe est qu’un premier recuit simulé va calculer ce problème légal. Ce qu'optimise ce premier recuit, c'est la légalité des paramètres de calcul. La « légalité » à l'intérieur de ce premier calcul n'est que la cohérence du problème.

Pour un calcul d'horaires comme pour un calcul d'annualisation, un calcul est en réalité constitué de deux recuits successifs : Un recuit de légalisation du problème qui produit un problème conforme aux paramètres de calcul, et un recuit d'optimisation qui « place au mieux » les horaires des personnes par rapport aux charges de travail.

Itérations et transitions

A chaque itération de l'algorithme, un essai de modification simple est effectué sur le planning d'une personne : on applique une transition. Cette modification entraîne une variation du coût de la solution, que l'on appelle delta-coût. Si cette variation est négative (c'est-à-dire qu'elle fait baisser le coût global de la solution), la modification est conservée. Sinon, elle est acceptée selon une probabilité dépendant de la valeur du delta-coût et de la température actuelle de l'algorithme.

Conclusion

Sous certaines conditions, lorsque le temps de calcul tend vers l’infini, la probabilité de trouver la solution optimale tend vers 1 : on est sûr de trouver la meilleure solution en calculant suffisamment longtemps. C’est pourquoi, en utilisant cette méthode, on est sûr, en augmentant le temps de calcul, d’augmenter la qualité (probable) de la solution trouvée.