Métaheuristique : Recuit simulé
CPGE Salmane Al Farissi - Salé
2024 - 2025
Introduction
Un problème d’optimisation consiste à trouver la meilleure solution parmi
un ensemble de solutions possibles, en maximisant ou minimisant une
fonction objectif.
Dans certains cas, trouver la solution exacte est très difficile, voire
impossible, car le nombre de possibilités est trop grand et les algorithmes
exacts demandent un temps de calcul exponentiel.
Les métaheuristiques permettent de trouver une solution approximative en
un temps raisonnable. Elles ne garantissent pas l’optimum global, mais
offrent une bonne solution adaptée aux contraintes du problème.
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 2 / 11
Introduction
Définition : Méta-heuristique
Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à
résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la
recherche opérationnelle, de l’ingénierie ou de l’intelligence artificielle) pour
lesquels on ne connaît pas de méthode classique plus efficace. Ces méthodes
utilisent cependant un haut niveau d’abstraction, leur permettant d’être adaptées
à une large gamme de problèmes différents.
De Nombreuses méta-heuristiques reposent sur des analogies avec des
processus naturels : physique, biologie ,...etc.
Dans ce chapitre, on s’intéresse à la méta-heuristique du recuit simulé
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 3 / 11
Recuit simulé
Inventée en 1983 par S. Kirkpatrick et ses collègues chez IBM.
Son principe repose sur la technique expérimentale du recuit, employée par
les métallurgistes pour obtenir un état solide “bien ordonné”, d’énergie
minimale, en n évitant que le système se retrouve dans des états stables mais
sous-optimaux, appelés minimums locaux d’énergie.
Cette technique consiste à porter le matériau à haute température, puis à
abaisser lentement celle-ci.
On représente sur le schéma du slide suivant l’effet de la technique du recuit,
et celui de la technique opposée de la trempe, sur un système formé d’un
ensemble de particules.
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 4 / 11
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 5 / 11
Recuit simulé
Définition
Le recuit simulé est une métaheuristique d’optimisation - inspirée du
processus de refroidissement des métaux.
L’objectif principal est de trouver une solution approximative à un problème
complexe - en explorant de manière intelligente l’espace des solutions.
Au début de l’algorithme, des solutions moins bonnes peuvent être acceptées
- ce qui permet d’éviter de se bloquer dans des optima locaux.
Ensuite, au fur et à mesure de l’itération, l’algorithme devient plus strict - en
privilégiant les solutions de meilleure qualité.
Cette approche permet de trouver une solution satisfaisante en un temps
raisonnable - sans garantir nécessairement l’optimalité absolue.
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 6 / 11
Recuit simulé :Principe
1 Choisir une température initiale T = T0 et une solution initiale S = S0 .
2 Générer une solution aléatoire dans le voisinage de la solution actuelle.
3 Si la modification génère une diminution de la fonction objectif (ou de
l’énergie du système), la nouvelle solution est directement acceptée. Sinon, si
elle entraîne une augmentation de l’énergie ∆E , elle est acceptée avec une
probabilité exp −∆E
T , avec ∆E = f (Svoisin ) − f (S) et T la température.
4 On répète ensuite ce procédé, en gardant la température constante, jusqu’à
ce que l’équilibre thermodynamique soit atteint.
5 Généralement, après un nombre suffisant de modifications, on abaisse alors la
température, avant d’effectuer une nouvelle série de transformations.
6 On continue de baisser la température lentement jusqu’à ce qu’elle atteigne
une valeur proche de 0.
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 7 / 11
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 8 / 11
Recuit simulé :Implémentation
Exemple
Nous cherchons à déterminer le minimum global de la fonction suivante :
1 |x −0.5| 2 |x +0.5|
f (x ) = − e − 0.5 − e − 0.2 , x ∈ R.
3 3
Pour ce faire, nous proposons d’utiliser l’algorithme de recuit simulé afin de
trouver le minimum global de la fonction f (x ) sur l’intervalle [−2, 2].
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 9 / 11
Code de l’algorithme en Python
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 10 / 11
Recuit simulé :Implémentation
Le graphique suivant donne la courbe de la fonction f (x ). On remarque que le
minimum global est ≈ 0.5.
Le minimum global retourné par la méthode de recuit simulé avec Tinit = 25,
α = 0.99, solution initiale S0 = 3, tfinal = 10−4 , et max_iter = 90.
(CPGE Salmane Al Farissi - Salé ) Métaheuristique : Recuit simulé 2024 - 2025 11 / 11
