Recuit Simulé (Simulated Annealing) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le recuit simulé (Simulated Annealing) est une métaheuristique d’optimisation inspirée du processus physique de recuit en métallurgie. Contrairement aux algorithmes gloutons qui descendent systématiquement vers le meilleur voisin, le recuit simulé optimisation accepte parfois des solutions pires selon une probabilité contrôlée par un paramètre de température décroissante. Ce mécanisme lui permet d’échapper aux minima locaux et de converger asymptotiquement vers l’optimum global. Dans ce guide, nous explorerons les fondements mathématiques, l’intuition physique, une implémentation Python complète sur le problème du voyageur de commerce (TSP), ainsi que les meilleures pratiques de réglage des hyperparamètres.

Principe mathématique

Le recuit simulé résout un problème d’optimisation consistant à trouver une solution $s^*$ qui minimise une fonction coût $E(s)$ définie sur un espace de recherche $S$. L’algorithme procède par itérations successives à partir d’une solution initiale $s_0$.

Étape 1 : Génération d’une solution voisine

À chaque itération $k$, on génère une solution candidate $s’$ dans le voisinage de la solution courante $s_k$. Le voisinage $N(s_k)$ est un ensemble de solutions « proches » de $s_k$, défini selon la structure du problème :

• Pour le TSP (Voyageur de Commerce), échanger deux villes dans la tournée.
• Pour une fonction continue, ajouter un bruit gaussien à chaque coordonnée.
• Pour un problème combinatoire, inverser ou permuter deux éléments.

Étape 2 : Critère d’acceptation de Metropolis

On calcule la variation d’énergie $\Delta E = E(s’) – E(s_k)$. Le critère d’acceptation est le cœur de l’algorithme :

1. Si $\Delta E < 0$ : la solution candidate est meilleure — on l’accepte systématiquement ($s_{k+1} = s’$).
2. Si $\Delta E \geq 0$ : la solution candidate est pire — on l’accepte avec probabilité :

$$P(\text{accepter}) = \exp\left(-\frac{\Delta E}{T_k}\right)$$

où $T_k$ est la température courante. Cette probabilité est comparée à un nombre aléatoire $r \sim U(0, 1)$ : si $r < P$, on accepte malgré la détérioration.

Ce critère, appelé distribution de Boltzmann, garantit que :
– À haute température, les solutions pires sont fréquemment acceptées (exploration forte).
– À basse température, les solutions pires sont rarement acceptées (exploitation forte).
– À température nulle, seuls les mouvements améliorants sont acceptés (descente classique).

Étape 3 : Planification de la température (Cooling Schedule)

La température diminue selon un programme de refroidissement. Le schéma le plus courant est le refroidissement géométrique :

$$T_{k+1} = \alpha \cdot T_k$$

où $\alpha \in ]0, 1[$ est le taux de refroidissement (cooling rate), typiquement $\alpha \in [0.80, 0.99]$.

D’autres schémas existent :
– Refroidissement linéaire : $T_{k+1} = T_k – \delta$
– Refroidissement logarithmique (théoriquement optimal) : $T_k = \frac{c}{\log(k + 1)}$
– Recuit adaptatif : ajustement dynamique basé sur le taux d’acceptation observé

Étape 4 : Convergence

Sous un refroidissement logarithmiquement lent et un espace de voisinage connecté, le recuit simulé converge asymptotiquement vers l’optimum global avec probabilité 1. En pratique, on arrête l’algorithme après un nombre maximum d’itérations ou lorsque la température atteint un seuil minimal.

Implémentation générique en Python

import random
import math

def simulated_annealing(cost_func, neighbor_func, initial_sol,
                         initial_temp=1000.0, cooling_rate=0.995,
                         min_temp=1e-10, max_iter=100000, random_state=None):
    """
    Implémentation générique du recuit simulé.

    Args:
        cost_func: fonction à minimiser E(s) -> float
        neighbor_func: fonction générant un voisin N(s) -> s'
        initial_sol: solution de départ
        initial_temp: température initiale T_0
        cooling_rate: facteur de refroidissement alpha
        min_temp: température minimale d'arrêt
        max_iter: nombre maximum d'itérations
        random_state: graine aléatoire pour reproductibilité

    Returns:
        best_sol: meilleure solution trouvée
        best_cost: coût associé
        history: historique des coûts à chaque itération
    """
    if random_state is not None:
        random.seed(random_state)

    current_sol = initial_sol
    current_cost = cost_func(current_sol)

    best_sol = current_sol
    best_cost = current_cost

    history = [current_cost]
    temp = initial_temp

    for i in range(max_iter):
        # Générer un voisin
        neighbor = neighbor_func(current_sol)
        neighbor_cost = cost_func(neighbor)

        # Variation d'énergie
        delta_e = neighbor_cost - current_cost

        # Critère de Metropolis
        if delta_e < 0:
            # Amélioration : on accepte toujours
            current_sol = neighbor
            current_cost = neighbor_cost
        else:
            # Détérioration : acceptation probabiliste
            acceptance_prob = math.exp(-delta_e / temp) if temp > 0 else 0.0
            if random.random() < acceptance_prob:
                current_sol = neighbor
                current_cost = neighbor_cost

        # Mise à jour du meilleur
        if current_cost < best_cost:
            best_sol = current_sol
            best_cost = current_cost

        history.append(best_cost)

        # Refroidissement
        temp *= cooling_rate

        # Condition d'arrêt
        if temp < min_temp:
            break

    return best_sol, best_cost, history

Intuition physique : le recuit d’un métal

L’analogie avec la métallurgie est à la fois élégante et profondément instructive. Lorsqu’un métallurgiste chauffe un alliage à très haute température, les atomes acquièrent une énergie cinétique considérable et se déplacent librement, sans ordre particulier. La structure désordonnée correspond à un état de haute énergie.

En refroidissant lentement le métal (processus appelé recuit), les atomes perdent progressivement de l’énergie et se réorganisent dans une configuration cristalline ordonnée — l’état d’énergie minimale, le plus stable. Cette structure finale correspond à l’optimum global de notre fonction objectif.

À l’inverse, si on refroidit trop rapidement (trempe), les atomes n’ont pas le temps de se réorganiser correctement et restent figés dans une configuration désordonnée. La structure obtenue est localement stable mais globalement sous-optimale — c’est l’équivalent d’un minimum local en optimisation.

Dans le contexte algorithmique, le recuit simulé optimisation fonctionne exactement selon ce principe :

• La température élevée au début permet d’explorer largement l’espace de recherche, en acceptant parfois des solutions moins bonnes pour sortir des creux locaux. C’est comme si les atomes avaient suffisamment d’énergie pour franchir des barrières énergétiques.
• La température décroissante réduit progressivement cette liberté d’exploration, concentrant la recherche dans les régions prometteuses.
• La température finale approche de zéro : l’algorithme se comporte comme une descente de gradient locale, affinant la solution dans le bassin d’attraction atteint.

Cette métaphore physique explique pourquoi le taux de refroidissement est si critique : un refroidissement trop rapide (α trop petit) conduit à une convergence prématurée vers un minimum local, tandis qu’un refroidissement trop lent (α proche de 1) garantit une meilleure qualité de solution au prix d’un temps de calcul considérablement accru.

Implémentation Python complète : le problème du voyageur de commerce

Le TSP est le banc d’essai classique des méthodes d’optimisation. Étant donné un ensemble de villes et les distances entre elles, il s’agit de trouver la tournée de longueur minimale visitant chaque ville exactement une fois et revenant au point de départ.

Données et fonctions utilitaires

import math
import random

# Générer des villes aléatoires
def generate_cities(n_cities, seed=42, width=100, height=100):
    """Génère n_cities positions aléatoires."""
    rng = random.Random(seed)
    cities = [(rng.uniform(0, width), rng.uniform(0, height)) for _ in range(n_cities)]
    return cities

# Calculer la distance euclidienne entre deux villes
def distance(city_a, city_b):
    return math.sqrt((city_a[0] - city_b[0])**2 + (city_a[1] - city_b[1])**2)

# Calculer la longueur totale d'une tournée
def tour_length(tour, cities):
    total = 0.0
    for i in range(len(tour)):
        total += distance(cities[tour[i]], cities[tour[(i + 1) % len(tour)]])
    return total

# Générer un voisin par échange de deux positions
def swap_neighbor(tour):
    """Échange deux positions aléatoires dans la tournée."""
    new_tour = tour[:]
    i, j = random.sample(range(len(new_tour)), 2)
    new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
    return new_tour

Exécution du recuit simulé sur le TSP

# Configuration
n_cities = 30
cities = generate_cities(n_cities, seed=42)

# Solution initiale : ordre aléatoire
random.seed(42)
initial_tour = list(range(n_cities))
random.shuffle(initial_tour)

# Exécution du recuit simulé optimisation
best_tour, best_length, history = simulated_annealing(
    cost_func=lambda t: tour_length(t, cities),
    neighbor_func=swap_neighbor,
    initial_sol=initial_tour,
    initial_temp=1000.0,
    cooling_rate=0.998,
    min_temp=0.01,
    max_iter=500000,
    random_state=42
)

print(f"Meilleure longueur trouvée : {best_length:.2f}")
print(f"Itérations effectuées : {len(history) - 1}")

Visualisation de la trajectoire avec matplotlib

import matplotlib.pyplot as plt

# Tracer les villes et la meilleure tournée
fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Graphique 1 : la tournée finale
ax1 = axes[0]
for i in range(len(best_tour)):
    a = cities[best_tour[i]]
    b = cities[best_tour[(i + 1) % len(best_tour)]]
    ax1.plot([a[0], b[0]], [a[1], b[1]], 'b-', linewidth=1.5, alpha=0.8)
ax1.scatter( for c in cities],  for c in cities], c='red', s=50, zorder=5)
for i, (x, y) in enumerate(cities):
    ax1.annotate(str(i), (x, y), fontsize=9, ha='center', va='bottom')
ax1.set_title(f'Meilleure tournée (longueur = {best_length:.2f})')
ax1.set_xlabel('x')
ax1.set_ylabel('y')
ax1.grid(True, alpha=0.3)

# Graphique 2 : convergence
ax2 = axes[1]
ax2.plot(history, color='darkgreen', linewidth=1.5)
ax2.set_title('Convergence du recuit simulé')
ax2.set_xlabel('Itération')
ax2.set_ylabel('Longueur de la tournée')
ax2.set_yscale('log')
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Impact du cooling schedule

Le choix du taux de refroidissement α est le paramètre le plus influent. Comparons trois configurations sur le même TSP à 30 villes :

# Comparaison de différents taux de refroidissement
for alpha in [0.90, 0.95, 0.995]:
    random.seed(42)
    init = list(range(n_cities))
    random.shuffle(init)

    _, cost, hist = simulated_annealing(
        cost_func=lambda t: tour_length(t, cities),
        neighbor_func=swap_neighbor,
        initial_sol=init,
        initial_temp=1000.0,
        cooling_rate=alpha,
        min_temp=0.01,
        max_iter=500000,
        random_state=42
    )
    print(f"alpha = {alpha:.3f} -> longueur = {cost:.2f}, itérations = {len(hist)-1}")

Résultats typiques :
– α = 0.90 (refroidissement rapide) : convergence en ~100 itérations, mais solution dégradée — l’algorithme reste piégé dans un minimum local.
– α = 0.95 (modéré) : ~300 itérations, résultat intermédiaire — bon compromis rapidité/qualité.
– α = 0.995 (lent) : ~1000+ itérations, solution la plus proche de l’optimum — exploration approfondie de l’espace.

Cette illustration montre le compromis fondamental entre temps de calcul et qualité de la solution, propre à toutes les métaheuristiques.

Hyperparamètres : guide de réglage

La performance du recuit simulé optimisation dépend fortement de cinq hyperparamètres clés :

Méthode pratique pour calibrer $T_0$

Une bonne pratique consiste à calibrer la température initiale pour obtenir un taux d’acceptation initial d’environ 80 % :

def calibrate_initial_temp(cost_func, neighbor_func, sol, n_samples=100, target_rate=0.8):
    """Estime T_0 pour obtenir un taux d'acceptation cible."""
    import math
    random.seed(42)
    deltas = []
    for _ in range(n_samples):
        neighbor = neighbor_func(sol)
        delta_e = cost_func(neighbor) - cost_func(sol)
        if delta_e > 0:
            deltas.append(delta_e)

    if not deltas:
        return 1000.0

    avg_delta = sum(deltas) / len(deltas)
    # P(accepter) = exp(-delta/T) = target_rate
    # => T = -delta / ln(target_rate)
    t0 = -avg_delta / math.log(target_rate)
    return max(t0, 1.0)

Cette approche automatique évite le tâtonnement manuel et adapte $T_0$ à l’échelle naturelle de la fonction objectif.

Avantages et limites du recuit simulé

Avantages

1. Simplicité conceptuelle et d’implémentation — quelques lignes de code suffisent, sans structure de population complexe.
2. Échappement aux minima locaux — le critère de Metropolis permet de franchir des barrières énergétiques.
3. Applicable à tout problème — tant qu’on peut définir une fonction coût et un voisinage, l’algorithme s’applique. Pas besoin de dérivées ni de continuité.
4. Garantie théorique de convergence — sous refroidissement logarithmique, convergence asymptotique vers l’optimum global.
5. Mémoire minimale — une seule solution courante est stockée, contrairement aux algorithmes génétiques qui maintiennent une population entière.
6. Facile à paralléliser — on peut exécuter plusieurs recuits indépendants depuis différentes solutions initiales.

Limites

1. Lenteur de convergence — la garantie asymptotique exige un refroidissement logarithmique, impraticable en pratique.
2. Sensibilité aux hyperparamètres — un mauvais choix de $T_0$ ou $\alpha$ dégrade sévèrement les performances.
3. Pas d’apprentissage progressif — contrairement aux algorithmes génétiques ou au PSO, le recuit simulé ne capitalise pas sur l’expérience accumulée.
4. Performance inférieure sur certains problèmes — les méthodes spécifiques (programmes linéaires, solveurs exacts) surpassent largement le recuit simulé sur les problèmes où elles s’appliquent.
5. Difficile de définir le voisinage — pour des problèmes complexes, la conception d’un bon voisinage est un art en soi.

4 cas d’usage concrets

1. Ordonnancement industriel (Job Shop Scheduling)

Dans un atelier de production, il s’agit de séquencer un ensemble de tâches sur plusieurs machines en minimisant le makespan (temps total de production). Le recuit simulé explore l’espace des permutations de tâches, acceptant temporairement des ordonnancements plus longs pour découvrir des configurations globalement meilleures. Des industriels comme Airbus et Bosch ont utilisé avec succès cette approche pour optimiser leurs lignes d’assemblage.

Voisinage : inverser deux tâches consécutives dans la séquence. Fonction de coût : durée totale de l’ordonnancement simulé.

2. Placement de composants sur circuit imprimé (VLSI Placement)

Le placement des cellules sur une puce électronique doit minimiser la longueur totale des interconnexions tout en respectant des contraintes de densité et de non-chevauchement. Le recuit simulé est historiquement l’un des premiers algorithmes à avoir été appliqué avec succès à ce problème (outil Timberwolf, années 1980).

Voisinage : déplacer une cellule aléatoirement ou échanger deux cellules. Fonction de coût : somme des longueurs de connexion estimées (modèle HPWL).

3. Clustering et segmentation d’images

En vision par ordinateur, on peut utiliser le recuit simulé pour optimiser l’affectation de pixels à des clusters, en minimisant une énergie combinant fidélité aux centres de cluster et régularité spatiale (pénalisation des voisinages dissemblables, comme dans un modèle de Potts).

Voisinage : réaffecter un pixel à un cluster différent. Fonction de coût : énergie totale du modèle (terme de données + terme de régularisation).

4. Optimisation de portefeuille financier

La construction d’un portefeuille optimal sous contraintes (budget, diversité, risque maximal) est un problème quadratique en nombres entiers difficile. Le recuit simulé explore l’espace des allocations discrètes, cherchant le meilleur compromis rendement/risque.

Voisinage : modifier légèrement le poids d’un actif (augmenter un, diminuer un autre). Fonction de coût : négatif du ratio de Sharpe ajusté au risque.

Voir aussi

• Maîtriser les Arrangements Maximaux en Python : Guide Complet et Astuces pour Développeurs
• Maîtriser les Cercles de Zèbre en Python : Guide Complet pour les Passionnés de Programmation