Recuit simulé (Simulated Annealing)
Objectifs
Comprendre le principe du recuit simulé, son analogie avec la métallurgie, et savoir l'implémenter sur des problèmes d'optimisation combinatoire comme le voyageur de commerce et le sac à dos.
Prérequis
Notions d'optimisation, algorithmes stochastiques, complexité algorithmique.
Le recuit simulé est une métaheuristique d'optimisation inspirée d'un phénomène physique : le recuit des métaux. Ce processus consiste à chauffer un matériau puis à le refroidir lentement pour réduire ses défauts et améliorer sa structure cristalline.
Recuit des métaux — Analogie physique
Lorsque le métal est chauffé à haute température, ses atomes sont désorganisés. En refroidissant lentement, ils s'organisent progressivement en un état stable avec une faible énergie.
- Température élevée : Atomes en désordre → exploration de nombreuses solutions
- Refroidissement progressif : Organisation en un état stable → optimisation de la solution
- Refroidissement trop rapide : État désordonné → risque de minimum local
Recuit des métaux : refroidissement lent pour une structure cristalline stable
Analogie avec l'optimisation
En optimisation, ce processus physique est transposé pour résoudre des problèmes complexes :
Le système démarre avec un paramètre de température élevé, lui permettant d'explorer librement l'espace des solutions. Il accepte parfois des solutions temporairement moins bonnes pour éviter de se bloquer prématurément dans un optimum local. Cette ouverture initiale est essentielle pour découvrir des régions prometteuses et éloignées.
La température diminue progressivement selon un plan de refroidissement contrôlé. Le système réduit peu à peu son acceptation des solutions dégradantes et commence à se concentrer sur l'amélioration locale dans les zones jugées intéressantes. L'exploration large cède doucement la place à une exploitation plus ciblée.
En fin de processus, la température est très basse. Le système n'accepte quasiment plus que les mouvements qui améliorent la solution. Il converge alors vers une configuration stable et affinée, correspondant à un optimum (souvent un très bon minimum local, avec l'espoir d'approcher l'optimum global).
Principe de fonctionnement
L'algorithme transpose ce phénomène physique à l'optimisation mathématique :
- Énergie du système → fonction objectif (ou fonction de coût) à minimiser
- Température → paramètre de contrôle du processus de recherche
Dynamique de transition
Le passage d'un état à un autre suit un protocole rigoureux :
- On part d'un état actuel \(i\) avec une énergie \(E_i\)
- On applique une légère perturbation pour générer un nouvel état \(j\) (une solution voisine) avec une énergie \(E_j\)
- Si \(E_j \le E_i\) : la nouvelle solution est meilleure (ou égale) ; elle est acceptée d'office.
- Si \(E_j > E_i\) : la nouvelle solution est moins bonne. Contrairement aux autres méthodes, le recuit simulé peut l'accepter avec une certaine probabilité \(P\).
La probabilité d'acceptation d'une solution moins bonne est régie par le critère de Metropolis :
\[ \boxed{P(\Delta E, T) = e^{-\frac{\Delta E}{T}}} \]où :
- \(\Delta E = E_j - E_i\) est la différence de qualité (dégradation)
- \(T\) est la température actuelle du système
- À haute température (\(T\) élevé) : \(P \approx 1\). L'algorithme accepte presque toutes les solutions, effectuant une marche aléatoire (random walk) pour explorer l'espace de recherche.
- À basse température (\(T\) faible) : \(P \approx 0\). L'algorithme devient sélectif et tend à ne choisir que les états favorisant la décroissance de la fonction, se comportant comme un algorithme glouton.
Implémentation algorithmique
La mise en œuvre repose sur une boucle principale de refroidissement et une boucle secondaire d'exploration à température constante.
1. Initialiser la température T = T₀ et la solution initiale s
2. Tant que T > T_min :
Répéter N fois (palier de température) :
Générer une solution voisine s' à partir de s
Calculer ΔE = f(s') - f(s)
Si ΔE < 0 OU random() < e^(-ΔE/T) :
Accepter s = s'
Si f(s) < f(meilleure) :
meilleure = s
Réduire la température : T = α × T (α ∈ [0.8, 0.99])
3. Retourner la meilleure solution trouvée
import math
import random
def recuit_simule(solution_initiale, fct_objectif, voisin, T0, T_min, alpha, N):
"""
Algorithme du recuit simulé
Paramètres :
solution_initiale : solution de départ
fct_objectif : fonction à minimiser
voisin : fonction générant une solution voisine
T0 : température initiale
T_min : température d'arrêt
alpha : facteur de refroidissement (0.8 à 0.99)
N : nombre d'itérations par palier
Retourne : meilleure solution trouvée
"""
T = T0
solution = solution_initiale
meilleure_solution = solution
while T > T_min:
for _ in range(N):
nouvelle_solution = voisin(solution)
delta = fct_objectif(nouvelle_solution) - fct_objectif(solution)
# Critère d'acceptation de Metropolis
if delta < 0 or random.random() < math.exp(-delta / T):
solution = nouvelle_solution
# Mise à jour de la meilleure solution
if fct_objectif(solution) < fct_objectif(meilleure_solution):
meilleure_solution = solution
# Refroidissement
T = alpha * T
return meilleure_solution
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
typedef struct {
double* solution;
int taille;
} Solution;
Solution recuit_simule(Solution s_init, double (*f)(Solution),
Solution (*voisin)(Solution),
double T0, double T_min, double alpha, int N) {
double T = T0;
Solution s = s_init;
Solution meilleure = s_init;
int i;
srand(time(NULL));
while (T > T_min) {
for (i = 0; i < N; i++) {
Solution s_new = voisin(s);
double delta = f(s_new) - f(s);
if (delta < 0 || (double)rand() / RAND_MAX < exp(-delta / T)) {
s = s_new;
if (f(s) < f(meilleure)) {
meilleure = s;
}
}
}
T = alpha * T;
}
return meilleure;
}
Exemple 1 : Minimisation d'une fonction mathématique
Exemple — Minimiser \(f(x) = x^2 + 4\cos(x)\)
Le minimum global de cette fonction est d'environ 2,319, atteint pour \(x \approx 1,895\) et \(x \approx -1,895\).
def f(x):
"""Fonction objectif à minimiser"""
return x**2 + 4 * math.cos(x)
def voisin(x, pas=0.5):
"""Génère une solution voisine autour de x"""
return x + random.uniform(-pas, pas)
# Paramètres
solution_initiale = 5
T0 = 100
T_min = 0.01
alpha = 0.95
N = 50
meilleure_solution = recuit_simule(solution_initiale, f,
lambda x: voisin(x),
T0, T_min, alpha, N)
print(f"Meilleure solution trouvée : {meilleure_solution}")
Meilleure solution trouvée : 1.895478463869374
La solution obtenue par recuit simulé présente une convergence optimale, avec un écart négligeable par rapport au minimum théorique calculé.
Exemple 2 : Problème du voyageur de commerce (TSP)
Le problème du voyageur de commerce est l'un des problèmes fondamentaux de l'optimisation combinatoire. Un voyageur doit :
- visiter un ensemble de \(n\) villes,
- passer une et une seule fois par chaque ville,
- revenir à la ville de départ,
- tout en minimisant la longueur totale du trajet.
Exemple avec 4 villes
On considère le graphe pondéré suivant, composé de quatre villes notées A, B, C, D. Chaque arête est associée à un poids représentant la distance.
Une solution est une permutation des villes. Considérons deux tournées :
A → B → C → D → A
10 + 35 + 30 + 20 = 95
A → B → D → C → A
10 + 25 + 30 + 15 = 80
Pour une tournée \(S = (v_1, v_2, \ldots, v_n)\) :
\[ f(S) = \sum_{i=1}^{n-1} d(v_i, v_{i+1}) + d(v_n, v_1) \]où \(d(v_i, v_j)\) est la distance entre deux villes.
Le nombre de tournées possibles est \((n-1)!\). Pour \(n=20\), ce nombre est gigantesque (\( \approx 1,2 \times 10^{17}\)), rendant toute recherche exhaustive impraticable.
Lien avec le recuit simulé
- Solution = une tournée (permutation des villes)
- Voisinage = permutation de deux villes ou inversion d'un sous-chemin
- Fonction objectif = longueur totale du circuit
- Intérêt = accepter temporairement des tournées plus longues pour échapper aux optima locaux
def fct_objectif_tsp(chemin, distances):
"""Calcule la longueur totale d'une tournée"""
n = len(chemin)
distance_totale = 0
for i in range(n):
ville_actuelle = chemin[i]
ville_suivante = chemin[(i + 1) % n] # retour à la ville de départ
distance_totale += distances[ville_actuelle][ville_suivante]
return distance_totale
def voisin_tsp(chemin):
"""Échange simplement deux villes au hasard"""
n = len(chemin)
nouveau_chemin = chemin[:]
i, j = random.sample(range(n), 2)
nouveau_chemin[i], nouveau_chemin[j] = nouveau_chemin[j], nouveau_chemin[i]
return nouveau_chemin
# Matrice des distances (A=0, B=1, C=2, D=3)
distances = [
[0, 10, 15, 20], # A
[10, 0, 35, 25], # B
[15, 35, 0, 30], # C
[20, 25, 30, 0] # D
]
villes = [0, 1, 2, 3]
random.shuffle(villes) # Solution initiale aléatoire
meilleure = recuit_simule(villes,
lambda x: fct_objectif_tsp(x, distances),
voisin_tsp,
T0=100, T_min=0.01, alpha=0.99, N=50)
print(f"Meilleure tournée : {meilleure}")
Meilleure tournée : [0, 1, 3, 2]
La permutation correspond à l'ordre des villes [A, B, D, C], formant la tournée :
A → B → D → C → A
Coût détaillé : \(10 + 25 + 30 + 15 = 80\). Cette tournée présente un coût inférieur à celui d'autres parcours testés.
Exemple 3 : Problème du sac à dos 0/1
Étant donné un ensemble de \(n\) objets, où chaque objet \(i\) possède un poids \(w_i\) et une valeur \(v_i\), et un sac à dos de capacité maximale \(W\), on cherche à déterminer la valeur totale maximale que l'on peut emporter sans dépasser la capacité.
Formalisation mathématique
On introduit une variable binaire pour chaque objet :
\[ x_i = \begin{cases} 1 & \text{si l'objet } i \text{ est sélectionné} \\ 0 & \text{sinon} \end{cases} \]
On cherche à maximiser la valeur totale :
\[ \max \sum_{i=1}^{n} v_i x_i \]
sous la contrainte de capacité :
\[ \sum_{i=1}^{n} w_i x_i \le W \]
Objet 1 : (12, 4) Objet 2 : (1, 2) Objet 3 : (4, 10) Objet 4 : (1, 1) Objet 5 : (2, 2) Capacité W = 15
Objets sélectionnés : 2, 3, 4, 5 Poids total = 1 + 4 + 1 + 2 = 8 Valeur totale = 2 + 10 + 1 + 2 = 15
Lien avec le recuit simulé
- Solution = vecteur binaire \((x_1, \ldots, x_n)\) avec \(\sum w_i x_i \le W\)
- Voisinage = ajout/retrait/échange d'objets
- Fonction objectif = \(- \sum v_i x_i\) (minimisation)
- Gestion des contraintes : pénalité pour solutions non admissibles
Pour explorer efficacement l'espace, on utilise une fonction de pénalité :
\[ f(x) = -\sum_{i=1}^{n} v_i x_i + \lambda \max\!\left(0, \sum_{i=1}^{n} w_i x_i - W\right) \]où \(\lambda\) est un coefficient de pénalité (grand, par exemple 10000).
def poids_total(x, poids):
"""Calcule le poids total de la solution"""
return sum(x[i] * poids[i] for i in range(len(x)))
def valeur_totale(x, valeurs):
"""Calcule la valeur totale de la solution"""
return sum(x[i] * valeurs[i] for i in range(len(x)))
def fct_objectif_sac(x, poids, valeurs, W, lambda_penalite=10000):
"""Fonction objectif avec pénalité pour solutions non admissibles"""
p = poids_total(x, poids)
v = valeur_totale(x, valeurs)
depassement = max(0, p - W)
return -v + lambda_penalite * depassement # Minimisation
def voisin_sac(x, poids, W):
"""Génère une solution voisine admissible"""
n = len(x)
nouv = x[:]
while True:
j = random.randrange(n)
nouv = x[:]
nouv[j] = 1 - nouv[j] # Inversion du bit
if poids_total(nouv, poids) <= W:
break
return nouv
# Données du problème
objets = [(12,4), (1,2), (4,10), (1,1), (2,2)]
poids = [w for (w, v) in objets]
valeurs = [v for (w, v) in objets]
W = 15
solution_initiale = [0] * len(objets) # Sac vide
meilleure = recuit_simule(solution_initiale,
lambda x: fct_objectif_sac(x, poids, valeurs, W),
lambda x: voisin_sac(x, poids, W),
T0=100, T_min=0.01, alpha=0.99, N=50)
print(f"Meilleure solution : {meilleure}")
print(f"Valeur totale : {valeur_totale(meilleure, valeurs)}")
Meilleure solution : [0, 1, 1, 1, 1] Valeur totale : 15
La meilleure solution trouvée est \([0, 1, 1, 1, 1]\), soit :
- Objet 1 (poids 12, valeur 4) : non sélectionné
- Objets 2, 3, 4, 5 : sélectionnés
La valeur totale de 15 est la valeur maximale possible pour cette instance. Ce résultat illustre l'efficacité du recuit simulé pour approcher une solution optimale dans un espace combinatoire, avec un coût bien inférieur à une exploration exhaustive.
Paramètres clés du recuit simulé
| Paramètre | Rôle | Valeurs typiques |
|---|---|---|
| Température initiale \(T_0\)\\ | Contrôle l'exploration initiale\\ | Élevée (100, 1000)\\ |
| Température minimale \(T_{min}\)\\ | Critère d'arrêt\\ | Très faible (0.01, 0.001)\\ |
| Facteur de refroidissement \(\alpha\)\\ | Vitesse de décroissance de T\\ | 0.8 à 0.99 (proche de 1 = refroidissement lent)\\ |
| Palier \(N\)\\ | Nombre d'itérations à T constant\\ | 50 à 500 selon la taille du problème\\ |
- Une température initiale trop basse → risque de convergence prématurée vers un optimum local.
- Un refroidissement trop rapide (\(\alpha\) faible) → exploration insuffisante.
- Un palier trop court → équilibre thermique non atteint.
- Utiliser plusieurs exécutions indépendantes pour évaluer la robustesse.
L'essentiel en bref
- Le recuit simulé est inspiré du recuit des métaux : refroidissement lent pour atteindre un état d'énergie minimale.
- Il accepte temporairement des solutions moins bonnes pour échapper aux optima locaux.
- La règle de Metropolis : \(P(\Delta E, T) = e^{-\Delta E / T}\) contrôle l'acceptation.
- L'équilibre exploration (haute T) / exploitation (basse T) est fondamental.
- Applications typiques : TSP (voyageur de commerce), sac à dos, optimisation de fonctions complexes.
- Les paramètres (\(T_0\), \(\alpha\), \(N\)) doivent être ajustés selon le problème.
Le recuit simulé a été proposé indépendamment par Scott Kirkpatrick, Daniel Gelatt et Mario Vecchi en 1983, ainsi que par Vladimir Černý en 1985. Il s'inspire des travaux de Nicholas Metropolis (1953) sur les algorithmes de Monte Carlo. Cette métaheuristique est devenue l'une des plus utilisées pour les problèmes d'optimisation combinatoire difficiles.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.