CPGE 2ᵉ année — MP / PSI · Informatique

Les métaheuristiques — le recuit simulé

Pr. EL HADIQ Zouhair

Quand un problème d'optimisation est trop gros pour être résolu exactement, comment trouver rapidement une bonne solution approchée ? Les métaheuristiques explorent intelligemment l'espace des solutions ; le recuit simulé en est l'exemple au programme.

🎯 Objectifs du chapitre

Définir un problème d'optimisation : espace des solutions, fonction objectif (coût).
Comprendre ce qu'est une métaheuristique et pourquoi on l'utilise.
Connaître la notion de voisinage et de recherche locale.
Identifier le piège des optima locaux de la descente (hill climbing).
Expliquer le principe du recuit simulé et son analogie physique.
Comprendre le critère d'acceptation de Metropolis : P = e^−ΔE/T.
Implémenter l'algorithme du recuit simulé en Python.

Sommaire

Les problèmes d'optimisation
Pourquoi les métaheuristiques ?
Qu'est-ce qu'une métaheuristique ?
Recherche locale et voisinage
La descente et le piège des optima locaux
Le principe du recuit simulé
Le critère d'acceptation de Metropolis
L'algorithme du recuit simulé
Le schéma de refroidissement
Exemple complet : le voyageur de commerce
Atouts, limites et réglages
Récapitulatif

1. Les problèmes d'optimisation

Un problème d'optimisation consiste à chercher, parmi un très grand nombre de solutions possibles, celle qui minimise (ou maximise) une certaine quantité. On le décrit par deux ingrédients :

un espace des solutions (ou espace de recherche) S : l'ensemble de toutes les configurations admissibles ;
une fonction objectif f : S → ℝ, aussi appelée fonction de coût (ou énergie), qui mesure la qualité d'une solution.

Résoudre le problème, c'est trouver une solution s* ∈ S telle que f(s*) soit minimale : ∀ s ∈ S, f(s*) ≤ f(s). Une telle solution est dite optimale (globale).

Problème	Une solution s	Coût f(s) à minimiser
Voyageur de commerce	Un ordre de visite des villes (un circuit)	Longueur totale du circuit
Sac à dos	Un sous-ensemble d'objets choisis	L'opposé de la valeur emportée (sous contrainte de poids)
Emploi du temps	Une affectation cours → créneaux	Nombre de conflits

💡 Maximiser, c'est minimiser. Chercher à maximiser g revient à minimiser f = −g. On présente donc tout en minimisation sans perte de généralité.

2. Pourquoi les métaheuristiques ?

Pour beaucoup de problèmes intéressants, l'espace des solutions est gigantesque. Pour le voyageur de commerce à n villes, le nombre de circuits est de l'ordre de (n−1)! / 2 : déjà plus de 60 000 milliards pour seulement 20 villes. Parcourir toutes les solutions (recherche exhaustive) est donc impossible en pratique.

Les méthodes vues précédemment ont leurs limites :

l'approche gloutonne est rapide mais ne garantit pas l'optimum ;
la programmation dynamique donne l'optimum, mais seulement quand le problème a la bonne structure et une taille raisonnable ;
la recherche exhaustive donne l'optimum mais explose en temps (complexité exponentielle ou factorielle).

⚠️ Le compromis fondamental. On échange la garantie d'optimalité contre la rapidité. Une métaheuristique ne promet pas la meilleure solution, mais une solution de bonne qualité en un temps raisonnable.

3. Qu'est-ce qu'une métaheuristique ?

Une heuristique est une méthode de résolution approchée, souvent conçue sur mesure pour un problème particulier (par exemple : « toujours aller vers la ville la plus proche »).

Une métaheuristique (le préfixe méta = « au-delà ») est une stratégie générale de haut niveau, indépendante du problème, qui pilote et coordonne des heuristiques pour explorer efficacement l'espace des solutions. On l'applique au voyageur de commerce, au sac à dos, à l'emploi du temps… avec la même mécanique, en changeant seulement la fonction de coût et la notion de voisinage.

Famille	Exemples
Basées sur une solution unique qu'on améliore	Recuit simulé, recherche tabou
Basées sur une population de solutions	Algorithmes génétiques, colonies de fourmis

💡 Au programme MP/PSI. Le représentant étudié et à savoir implémenter est le recuit simulé (simulated annealing). Il ne garantit pas l'optimum, mais trouve une solution approchée de bonne qualité.

4. Recherche locale et voisinage

L'idée d'une recherche locale est de partir d'une solution puis de l'améliorer par petites modifications, sans jamais reconstruire une solution entière. Pour cela on définit le voisinage V(s) d'une solution s : l'ensemble des solutions obtenues par une petite transformation élémentaire.

Voyageur de commerce : échanger deux villes du circuit, ou inverser un segment.
Sac à dos : ajouter ou retirer un objet.
Fonction numérique : déplacer x d'un petit pas ±ε.

Un voisin s' ∈ V(s) est dit améliorant si f(s') < f(s). La variation de coût se note :

ΔE = f(s') − f(s)

Si ΔE < 0, le voisin est meilleur (le coût baisse) ; si ΔE > 0, il est moins bon.

5. La descente et le piège des optima locaux

La recherche locale la plus simple est la descente (ou hill climbing) : à chaque étape, on remplace la solution courante par un voisin strictement meilleur ; on s'arrête quand aucun voisin n'améliore plus.

def descente(s):
    while True:
        voisins = generer_voisins(s)
        meilleur = min(voisins, key=cout)
        if cout(meilleur) < cout(s):
            s = meilleur          # on descend
        else:
            return s             # aucun voisin meilleur : blocage

Le problème : la descente n'accepte jamais de remonter. Elle se fige donc dans le premier optimum local rencontré — une solution meilleure que tous ses voisins, mais pas forcément la meilleure globalement.

🏔️ L'image de la montagne. Imaginez un paysage de coûts avec des vallées. Une bille qui ne fait que descendre se bloque au fond de la première vallée (optimum local), même s'il existe une vallée plus profonde (optimum global) plus loin. Pour en sortir, il faut parfois accepter de remonter temporairement.

6. Le principe du recuit simulé

Le recuit simulé s'inspire d'un procédé de métallurgie, le recuit : pour obtenir un métal sans défaut, on le chauffe fortement (les atomes s'agitent librement) puis on le refroidit très lentement. Les atomes se réorganisent alors progressivement dans une structure d'énergie minimale (cristal régulier). Un refroidissement trop rapide (trempe) fige au contraire les défauts.

On transpose cette idée à l'optimisation :

Physique (recuit)	Optimisation
État du matériau	Solution s
Énergie de l'état	Coût f(s)
Température T	Paramètre de contrôle T
Refroidissement lent	Décroissance progressive de T
État d'énergie minimale	Solution (quasi) optimale

L'idée maîtresse : pour échapper aux optima locaux, on autorise parfois des mouvements qui dégradent le coût. Cette tolérance est forte quand T est élevée (début : on explore largement) et devient faible quand T baisse (fin : on affine et on se stabilise).

7. Le critère d'acceptation de Metropolis

À chaque étape, on tire un voisin s' au hasard et on calcule ΔE = f(s') − f(s). La décision d'accepter s' suit la règle de Metropolis :

Règle d'acceptation.

Si ΔE ≤ 0 (le voisin est meilleur ou égal) : on l'accepte toujours.
Si ΔE > 0 (le voisin est moins bon) : on l'accepte avec la probabilité P = e^−ΔE/T.

Analysons la probabilité P = e^−ΔE/T d'accepter une dégradation :

Plus la dégradation ΔE est grande, plus P est petite : on accepte rarement les très mauvais mouvements.
Plus la température T est élevée, plus P est proche de 1 : au début, on accepte facilement de remonter (exploration).
Quand T → 0, P → 0 : à la fin, on ne tolère presque plus de dégradation et l'algorithme se comporte comme une simple descente (exploitation).

ΔE	T élevée (T = 100)	T basse (T = 1)
ΔE = 1	P ≈ 0,99	P ≈ 0,37
ΔE = 10	P ≈ 0,90	P ≈ 0,000045

Concrètement, accepter « avec la probabilité P » se programme en tirant un nombre aléatoire u dans [0, 1[ : on accepte si u < P.

8. L'algorithme du recuit simulé

On part d'une solution initiale et d'une température élevée. On répète : tirer un voisin, calculer ΔE, décider selon Metropolis, puis refroidir. On garde en mémoire la meilleure solution rencontrée.

import math, random

def recuit_simule(s0, cout, voisin, T0, alpha, n_iter):
    s = s0                       # solution courante
    c = cout(s)
    meilleur, c_meilleur = s, c  # meilleure solution vue
    T = T0
    for _ in range(n_iter):
        s2 = voisin(s)           # un voisin au hasard
        c2 = cout(s2)
        dE = c2 - c              # variation de coût
        if dE <= 0 or random.random() < math.exp(-dE / T):
            s, c = s2, c2        # on accepte le voisin
            if c < c_meilleur:
                meilleur, c_meilleur = s, c
        T = alpha * T            # refroidissement (0 < alpha < 1)
    return meilleur, c_meilleur

💡 Pourquoi garder « meilleur » séparément ? La solution courante s peut se dégrader (on accepte des remontées). On conserve donc à part la meilleure solution jamais rencontrée, qui sera le résultat final.

9. Le schéma de refroidissement

Le schéma de refroidissement (cooling schedule) décrit comment T diminue. C'est le réglage le plus important. Le plus courant est la décroissance géométrique :

T_k+1 = α · T_k, avec 0 < α < 1 (souvent α entre 0,90 et 0,99)

T₀ (température initiale) : assez grande pour accepter au départ la plupart des mouvements (phase d'exploration).
α (facteur de refroidissement) : proche de 1 ⇒ refroidissement lent ⇒ meilleure qualité mais plus lent. Trop petit ⇒ on fige trop vite (comme une trempe) et on risque de rester coincé.
Critère d'arrêt : un nombre d'itérations fixé, ou une température minimale T_min atteinte.

⚠️ Exploration puis exploitation. Début (T grande) : on parcourt largement l'espace et on franchit des « collines ». Fin (T petite) : on affine localement. Un bon réglage équilibre ces deux phases.

10. Exemple complet : le voyageur de commerce

On dispose de n villes de coordonnées connues. Une solution est un ordre de visite (une permutation des villes), le coût est la longueur totale du circuit fermé, et un voisin s'obtient en échangeant deux villes de la tournée.

import math, random

def distance(a, b):
    return math.hypot(a[0]-b[0], a[1]-b[1])

def longueur(tour, villes):           # coût = circuit fermé
    n = len(tour)
    return sum(distance(villes[tour[i]], villes[tour[(i+1)%n]])
               for i in range(n))

def voisin(tour):                       # échange de deux villes
    t = tour[:]
    i, j = random.sample(range(len(t)), 2)
    t[i], t[j] = t[j], t[i]
    return t

def tsp_recuit(villes, T0=100, alpha=0.995, n_iter=20000):
    s = list(range(len(villes)))
    random.shuffle(s)
    c = longueur(s, villes)
    best, cbest = s[:], c
    T = T0
    for _ in range(n_iter):
        s2 = voisin(s)
        c2 = longueur(s2, villes)
        dE = c2 - c
        if dE <= 0 or random.random() < math.exp(-dE / T):
            s, c = s2, c2
            if c < cbest:
                best, cbest = s[:], c
        T = alpha * T
    return best, cbest

En quelques dizaines de milliers d'itérations, cet algorithme produit un circuit court — généralement très proche de l'optimal — là où l'énumération exhaustive serait totalement hors de portée.

11. Atouts, limites et réglages

Atouts ✅	Limites ⚠️
Simple à implémenter, très général (change juste coût + voisinage).	Aucune garantie d'atteindre l'optimum global.
Capable de sortir des optima locaux.	Résultat aléatoire : deux exécutions diffèrent.
Bon rapport qualité / temps sur de gros problèmes.	Sensible au réglage de T₀, α et du nombre d'itérations.

💡 Bonnes pratiques. Choisir T₀ pour qu'au départ ~80 % des mouvements soient acceptés ; prendre α proche de 1 (0,99) ; lancer plusieurs exécutions et garder la meilleure.

Récapitulatif

Un problème d'optimisation = un espace de solutions S + une fonction de coût f à minimiser.
Une métaheuristique est une stratégie générale qui cherche une bonne solution approchée (sans garantie d'optimalité) en un temps raisonnable.
La recherche locale améliore une solution via son voisinage ; la descente reste piégée dans les optima locaux.
Le recuit simulé s'inspire du refroidissement des métaux : il accepte parfois des dégradations pour s'échapper des optima locaux.
Critère de Metropolis : on accepte un voisin meilleur (ΔE ≤ 0) toujours ; un voisin pire avec P = e^−ΔE/T.
La température baisse géométriquement (T ← αT) : exploration au début, exploitation à la fin.
On mémorise la meilleure solution rencontrée car la solution courante peut se dégrader.

CPGE MP / PSI — Informatique · Chapitre 1‑6 : Métaheuristiques (recuit simulé)