Les métaheuristiques — le recuit simulé

Pr. EL HADIQ Zouhair

CPGE MP / PSI · Informatique · Chapitre 1‑6

1 / 12

Problème d'optimisationDÉFINITION

Chercher, parmi un grand nombre de solutions, celle qui minimise un coût.

Espace des solutions $S$ : toutes les configurations admissibles.
Fonction de coût $f : S \to \mathbb{R}$ (aussi appelée énergie).
Objectif : trouver $s^\star$ tel que $f(s^\star) \le f(s)$ pour tout $s \in S$.

Maximiser = minimiser. Maximiser $g$ revient à minimiser $f = -g$.

2 / 12

Pourquoi des métaheuristiques ?MOTIVATION

L'espace des solutions est souvent gigantesque. Voyageur de commerce à $n$ villes : $\dfrac{(n-1)!}{2}$ circuits, soit $> 6\times 10^{13}$ pour $n=20$.

Méthode	Optimum ?	Coût
Exhaustive	Oui	Explose (factoriel)
Glouton	Non garanti	Rapide
Prog. dynamique	Oui	Limité en taille

Compromis. On échange la garantie d'optimalité contre la rapidité.

3 / 12

Heuristique vs métaheuristiqueVOCABULAIRE

Heuristique : méthode approchée sur mesure pour un problème (« aller vers la ville la plus proche »).
Métaheuristique : stratégie générale, indépendante du problème, qui pilote la recherche.

Solution unique	Population
Recuit simulé, recherche tabou	Algos génétiques, fourmis

Au programme : le recuit simulé (simulated annealing), à savoir implémenter.

4 / 12

Recherche locale et voisinagePRINCIPE

Partir d'une solution et l'améliorer par petites modifications. Le voisinage $V(s)$ = solutions obtenues par une transformation élémentaire.

Voyageur : échanger deux villes.
Sac à dos : ajouter / retirer un objet.
Fonction : déplacer $x$ de $\pm\varepsilon$.

Variation de coût : $\Delta E = f(s') - f(s)$. $\Delta E < 0$ : voisin meilleur.

5 / 12

La descente et son piègeLIMITE

La descente (hill climbing) n'accepte qu'un voisin strictement meilleur.

while True: m = min(voisins(s), key=cout) if cout(m) < cout(s): s = m else: return s # bloqué

🏔️ Optimum local. La bille qui ne fait que descendre se fige au fond de la première vallée, pas forcément la plus profonde.

6 / 12

Principe du recuit simuléANALOGIE

Inspiré du recuit en métallurgie : chauffer puis refroidir lentement pour atteindre une structure d'énergie minimale.

Physique	Optimisation
État / énergie	Solution $s$ / coût $f(s)$
Température $T$	Paramètre de contrôle $T$
Refroidissement lent	Décroissance de $T$

Idée clé. Autoriser parfois des mouvements qui dégradent le coût pour s'échapper des optima locaux.

7 / 12

Critère de MetropolisCŒUR

On tire un voisin $s'$ et $\Delta E = f(s') - f(s)$ :

Si $\Delta E \le 0$ : on accepte toujours.
Si $\Delta E > 0$ : on accepte avec $P = e^{-\Delta E / T}$.

$\Delta E$	$T=100$	$T=1$
$1$	$P\approx 0{,}99$	$P\approx 0{,}37$
$10$	$P\approx 0{,}90$	$P\approx 4{,}5\cdot10^{-5}$

En pratique : tirer $u \in [0,1[$ et accepter si $u < P$.

8 / 12

L'algorithmeCODE

def recuit_simule(s0, cout, voisin, T0, alpha, n_iter): s = s0; c = cout(s) meilleur, c_best = s, c T = T0 for _ in range(n_iter): s2 = voisin(s); c2 = cout(s2) dE = c2 - c if dE <= 0 or random.random() < math.exp(-dE / T): s, c = s2, c2 if c < c_best: meilleur, c_best = s, c T = alpha * T # refroidissement return meilleur, c_best

Garder « meilleur » à part : la solution courante peut se dégrader.

9 / 12

Schéma de refroidissementRÉGLAGE

Décroissance géométrique : $T_{k+1} = \alpha \cdot T_k$, avec $0 < \alpha < 1$ (souvent $0{,}90$–$0{,}99$).

$T_0$ grand : la plupart des mouvements acceptés au départ (exploration).
$\alpha \to 1$ : refroidissement lent, meilleure qualité.
$T \to 0$ : se comporte comme une descente (exploitation).

Trop rapide (trempe) $\Rightarrow$ on fige les défauts et on reste coincé.

10 / 12

Exemple : voyageur de commerceAPPLICATION

Solution = permutation des villes ; coût = longueur du circuit fermé ; voisin = échange de deux villes.

def voisin(tour): t = tour[:] i, j = random.sample(range(len(t)), 2) t[i], t[j] = t[j], t[i] return t def longueur(tour, villes): n = len(tour) return sum(dist(villes[tour[i]], villes[tour[(i+1)%n]]) for i in range(n))

Quelques $10^4$ itérations $\Rightarrow$ circuit très proche de l'optimal.

11 / 12

À retenirBILAN

Métaheuristique = bonne solution approchée, sans garantie d'optimalité.
Recherche locale + voisinage ; la descente reste piégée dans les optima locaux.
Recuit simulé : accepter parfois une dégradation avec $P = e^{-\Delta E/T}$.
Température $T \leftarrow \alpha T$ : exploration $\to$ exploitation.
Mémoriser la meilleure solution rencontrée.

Atouts : simple, général, sort des optima locaux. Limites : aléatoire, sensible aux réglages.

12 / 12