Optimisation stochastique · le recuit simulé

📄 Ressources du cours

📥 Télécharger les slides · 🔗 Ouvrir dans un nouvel onglet · 📝 Ouvrir le TD/TP

🎥 Vidéos recommandées

🇫🇷 Cours sur l'Algorithme de Little.avi
Marc BEVERAGGI · 14:22 · 26k vues — Algorithme de résolution des problèmes de Voyageur de commerce
🇫🇷 Code Source en Python de la résolution du problème du voyageur de Commerce TSP avec le Recuit Simulé
Orkia Derkaoui · 10:02 · 7k vues — Code Source en Python de la résolution du problème du voyageur de Commerce TSP avec le Recuit Simulé
🇬🇧 Using simulated annealing and genetic algorithm on TSP
PaulFred (ApproachingTruth) · 11:05 · 44k vues — Statistical Mechanics Project which looks at simulated annealing and genetic algorithms to find possible solutions to the travelling salesman problem.

1. Optimisation difficile

L'optimisation cherche à minimiser (ou maximiser) une fonction objectif sur un espace de recherche. Quand la dimension augmente, l'espace explose exponentiellement.

Malédiction de la dimension (curse of dimensionality) — Quand la dimension du problème augmente, l'espace à explorer explose exponentiellement, rendant l'optimisation exacte impraticable.

Typologie des problèmes

Mono-objectif / multi-objectifs / many-objectifs
Variables discrètes / continues / mixtes
Problèmes sous contraintes
Problèmes à grande dimension
Problèmes dynamiques

🧩 Variables discrètes
Voyageur de commerce (TSP) · Tournée de véhicules · Coloration de graphe · Sac à dos · Planification

📈 Variables continues
Fonction analytique (benchmarks) · Expression non analytique (code de calcul, problème inverse) · Géométrie, chimie, physique

Rappels de complexité

Classe	Définition
P	Algorithme polynomial qui trouve la solution exacte
NP	Algorithme polynomial qui vérifie une solution
NP-difficile	Tous les problèmes NP s'y ramènent par réduction polynomiale
NP-complet	NP + NP-difficile (SAT, TSP, Sac à dos, Clique…)

P = NP ? On ne sait pas. On ne connaît aucun algorithme polynomial pour résoudre les problèmes NP-complets.

2. Méta-heuristiques

Définition Une méta-heuristique est une méthode : globale · stochastique · générique · qui ne garantit pas l'optimalité. Souvent basée sur une analogie avec la nature (physique, biologie, éthologie). Le recuit simulé en est l'exemple historique, dérivé de la métallurgie.

Éléments constitutifs

Une solution initiale
Une stratégie de génération de voisins basée sur l'aléatoire
Un critère d'acceptation d'une nouvelle solution
Des coefficients de contrôle
Un critère de convergence

Exploration vs Exploitation

Dichotomie fondamentale Exploration : parcourir largement l'espace de recherche pour ne pas rester bloqué.
Exploitation : raffiner autour de bonnes solutions connues pour converger.
Tout l'art du recuit simulé est de basculer progressivement de l'exploration (haute température) vers l'exploitation (basse température).

3. Le recuit simulé · principe physique

Le recuit est une technique métallurgique :

On porte le matériau à très haute température pour le liquéfier.
On abaisse progressivement la température pour stabiliser la structure du matériau.

Historique

Variante de l'algorithme de Metropolis-Hastings.
Proposé en 1983 par Kirkpatrick, Gelatt et Vecchi, et en 1985 par Cerny.
Première méta-heuristique proposée.
Adapté à l'origine aux problèmes discrets (placement de composants électroniques).

Analogie physique ↔ optimisation

Physique	Optimisation
Énergie du système	Fonction $f$ à minimiser
État du matériau	Solution $X$
Équilibre thermodynamique	Atteint à un palier de température
Température	Paramètre de contrôle $T$
Perturbation thermique	Critère de Metropolis (acceptation probabiliste)

4. Critère de Metropolis

Évalue la probabilité de choix d'une solution voisine $V$ moins bonne que la solution courante $S$.

Formule $\text{metropolis}(V, S, T) = \exp\!\left(-\dfrac{|f(S) - f(V)|}{T}\right)$
Ou, avec $\Delta f = f(V) - f(S)$ : $P_{\text{accept}}(\Delta f, T) = \exp\!\left(-\dfrac{\Delta f}{T}\right)$

Fonction critereMetropolis(Δf, T)

• Si $\Delta f \le 0$ → retourner VRAI
• Sinon → retourner $\text{aléa}(0,1) < e^{-\Delta f / T}$

Propriétés

📐 Comportement
• Si $\Delta f \le 0$ : voisin accepté automatiquement
• Petite variation a + de chances d'être acceptée qu'une grande
• Fonction stochastique

🔥 Haute température
$e^{-\Delta f / T} \approx 1$ → la plupart des solutions dégradantes acceptées
$T = \infty$ → marche aléatoire pure

🧊 Faible température
$e^{-\Delta f / T} \to 0$ → la plupart des solutions dégradantes rejetées
$T = 0$ → descente pure (jamais de solution dégradante)

5. Algorithme du recuit simulé

Version avec paliers

Algorithme — Recuit simulé avec paliers

Entrée : $X$ solution initiale · $f$ énergie · $T$ température initiale

$f_{\min} \leftarrow f(X)$ ; $X_{\min} \leftarrow X$
Tant que $T > T_{\min}$ ou $\neg$critèreConvergence() :
- Tant que $\neg$équilibreThermodynamique() (palier) :
  - $X_{\text{vois}} \leftarrow \text{perturbation}(X)$
  - $\Delta f = f(X_{\text{vois}}) - f(X)$
  - Si $\Delta f < 0$ ou critèreMetropolis($\Delta f, T$) :
    - Si $\Delta f < 0$ et $f(X_{\text{vois}}) < f_{\min}$ → mettre à jour $f_{\min}, X_{\min}$
    - $f(X) \leftarrow f(X_{\text{vois}})$ ; $X \leftarrow X_{\text{vois}}$
- $T \leftarrow \text{refroidissement}(T)$

Version condensée (TSP)

Algorithme — Version condensée (TSP)

Engendrer une solution initiale $S$ ; $S^* = S$
$T \leftarrow$ température initiale (grande)
Répéter :
- $V \leftarrow$ un voisin de $S$
- Si $f(V) < f(S)$ ou $\text{aléa}() < \text{metropolis}(V, S, T)$ → $S = V$
- Si $f(S) < f(S^*)$ → $S^* = S$
- Mettre à jour $T$
Jusqu'à condition de fin
Retourner $S^*$

Éléments à paramétrer

Solution initiale
Fonction de perturbation (voisinage)
Température initiale $T_0$
Schéma de refroidissement
Condition d'équilibre thermodynamique (palier)
Condition de convergence / arrêt

6. Paramétrage

Initialisation de la température

✅ Conseillé Empiriquement, en fonction du problème par essais successifs.

⚠️ Risqué À partir d'une solution initiale et d'un voisin via la formule de Metropolis (en fixant une faible proba d'acceptation).

Schémas de refroidissement

Schéma	Formule	Usage
Géométrique	$T_{k+1} = \alpha \cdot T_k$	Le plus utilisé. $\alpha = 0{,}99$ typique
Logarithmique	$T_k = \mu / \log(1 + k)$	Très coûteux, peu utilisé
Exponentiel	$T_k = T_0 \cdot \exp(-k/\tau)$	$\tau$ = constante
Ésotérique	—	Remontée possible de $T$ (reheating)

Effet du refroidissement

🔥 Forte décroissance
Empêche une exploration convenable → l'algorithme converge rapidement vers un minimum local.

❄️ Faible décroissance
Forte exploration aux premières itérations, bonne convergence vers minimum global, mais coûteuse.

Critères d'arrêt

La température atteint $T < T_{\min}$
Le nombre d'évaluations atteint une limite
Pas d'amélioration depuis un certain nombre d'itérations
Optimum théorique atteint (difficile à détecter)

7. Application au TSP

Voyageur de commerce (TSP) Recherche du chemin (cycle) hamiltonien de plus petit coût dans un graphe valué.
« Étant donnée une liste de villes et les distances séparant chacune d'entre elles, quelle est la plus courte tournée possible qui visite chaque ville une seule fois et revient au point de départ ? »

Complexité

TSP est NP-complet
Algorithme naïf exponentiel : $(n-1)!$ pour $n$ sommets
TSP symétrique : $(n+1)! / 2$
22 villes : plus de $51 \times 10^{18}$ tournées
304 villes : plus de $2 \times 10^{624}$ tournées

Voisinage pour TSP — 2-opt

Solution = chemin hamiltonien. Voisin = chemin hamiltonien proche.

↔️ Permutation de 2 sommets
A-B-C-D-E-A → A-E-C-D-B-A
4 arêtes modifiées (A-B, B-C, D-E, E-A). Voisinage distant.

🔁 Inversion de sous-chemin (2-opt)
A-B-C-D-E-A → A-E-D-C-B-A
2 arêtes modifiées (A-B et E-A) — en TSP symétrique (D-C = C-D). Voisinage plus proche. Stratégie préférée.

Algorithmes exacts pour TSP

Algorithme de Little (1964-65, B. Roy) Utilise la technique SEP (Séparation Évaluation Progressive). Optimal et utilisable pour plus de 1000 sommets, mais reste exponentiel.

8. TP — recuit simulé

Énoncé EISTI ING2 (IA et optimisation, 2017).

Cas TSP

Ex 1 — Impact d'une température fixe

(a) Fixer une température élevée $10^6$, interpréter le comportement.

(b) Fixer une température proche de 0, interpréter.

(c) Étudier la transition entre les deux comportements.

Ex 2 — Mesures de performance

Afficher le nombre d'améliorations et le rapport amélioration/nb évaluations. Quels critères pour comparer 2 versions ? Comment juger la stabilité ?

Ex 3 — Température variable

Tester la décroissance géométrique $\lambda \in \{0{,}1, 0{,}5, 0{,}8, 0{,}9, 0{,}99\}$.

Étudier l'impact de la longueur du palier et la différence entre 2 équations de température.

Ex 4 — Initialisation et voisinage

Impact d'une initialisation aléatoire. Implémenter une perturbation à 3 arêtes, puis tester la 2-opt (2 arêtes).

Ex 5 — Convergence

(a) Créer un critère qui stoppe le palier après $k$ itérations sans amélioration.

(b) Créer un critère qui arrête l'algorithme après $k$ itérations sans amélioration.

Cas continu — fonctions Sphère & Griewank

Sur $[-600, 600]$, en dimensions 4, 10 et 50. Adapter les paramètres aux exigences de convergence.

★ Réviser le chapitre

Pour vérifier ta compréhension

Pourquoi utiliser une méta-heuristique ?

Pour les problèmes NP-complets où l'optimisation exacte explose. Les méta-heuristiques offrent une solution approchée polynomiale, sans garantir l'optimum.

Pourquoi accepter parfois une solution moins bonne ?

Pour échapper aux minima locaux. C'est le rôle du critère de Metropolis : accepter probabilistiquement les solutions dégradantes, surtout à haute température.

Comment choisir $\alpha$ dans le refroidissement géométrique ?

Typiquement $\alpha = 0{,}99$. Trop petit (refroidissement rapide) → minimum local. Trop grand (refroidissement lent) → coûteux mais meilleure exploration.

Pourquoi la 2-opt est-elle préférée à la permutation pour TSP ?

Elle modifie seulement 2 arêtes au lieu de 4 → voisinage plus proche, exploration plus fine, meilleure convergence.

🃏 Flashcards éclair

Clique pour retourner.

Malédiction de la dim.

En 1 phrase.

tourne →

Quand la dimension augmente, l'espace à explorer explose exponentiellement.

Classes complexité

P, NP, NP-complet.

tourne →

P = polynomial à résoudre
NP = polynomial à vérifier
NP-complet = NP + NP-difficile

Méta-heuristique

5 caractéristiques.

tourne →

① Globale · ② Stochastique · ③ Générique · ④ Ne garantit pas l'optimum · ⑤ Inspirée nature/physique

Recuit — origine

Année + auteurs.

tourne →

1983 (Kirkpatrick, Gelatt, Vecchi) et 1985 (Cerny). Première méta-heuristique. Variante de Metropolis-Hastings.

Critère Metropolis

Formule.

tourne →

P(accept) = exp(-Δf / T)

Si Δf ≤ 0 ?

Que fait Metropolis ?

tourne →

Le voisin est accepté automatiquement.

Haute température

Comportement.

tourne →

$e^{-\Delta f / T} \approx 1$ : la plupart des solutions dégradantes sont acceptées. Marche aléatoire.

Faible température

Comportement.

tourne →

$e^{-\Delta f / T} \to 0$ : la plupart des solutions dégradantes sont rejetées. Descente pure.

Refroidissement géo.

Formule + $\alpha$ typique.

tourne →

T_{k+1} = α · T_k
α = 0,99 typique

TSP — complexité

Naïf vs symétrique.

tourne →

Naïf : $(n-1)!$
Symétrique : $(n+1)!/2$
NP-complet

2-opt vs permutation

Nb d'arêtes modifiées.

tourne →

Permutation de 2 sommets : 4 arêtes
Inversion (2-opt) : 2 arêtes ← préférée

4 critères d'arrêt

Pour RS.

tourne →

① $T < T_{\min}$ · ② Nb d'évaluations max · ③ Pas d'amélioration depuis $k$ iter · ④ Optimum théorique atteint

✎ Quiz éclair

test rapide · 5 questions

0 / 5

1.Une méta-heuristique :

Garantit toujours l'optimum global
Est exclusivement déterministe
Est globale, stochastique, ne garantit pas l'optimum
Est restreinte aux problèmes continus

D'où l'intérêt sur les problèmes NP-complets où l'exact est impraticable.

2.Le critère de Metropolis accepte un voisin :

Toujours
Jamais si $\Delta f > 0$
Seulement si $T = 0$
Avec probabilité $\exp(-\Delta f / T)$ si $\Delta f > 0$

Et automatiquement si $\Delta f \le 0$.

3.Une décroissance trop rapide de $T$ entraîne :

Une convergence garantie vers l'optimum global
Une convergence rapide vers un minimum local
Une explosion exponentielle du coût
Une augmentation de $\alpha$ automatique

L'algorithme n'a pas le temps d'explorer correctement.

4.Le TSP est :

P
NP, non NP-complet
NP-complet
Linéaire

Pas de solution exacte polynomiale connue. Recuit simulé = approximation polynomiale.

5.La stratégie de voisinage préférée pour TSP est :

Permutation de 2 sommets (4 arêtes modifiées)
Inversion (2-opt, 2 arêtes modifiées)
Reroutage complet aléatoire
Suppression de villes

Voisinage plus proche → exploration plus fine.

📌 À retenir

Malédiction de la dim : explosion exponentielle de l'espace
P / NP / NP-complet · TSP = NP-complet
Méta-heuristique : globale · stochastique · générique · sans garantie d'optimum
Exploration vs Exploitation
Recuit physique : chauffer puis refroidir lentement
Recuit simulé : 1983 (Kirkpatrick, Gelatt, Vecchi) — première méta-heuristique
Analogie : énergie ↔ f, état ↔ X, palier ↔ équilibre, T ↔ contrôle, perturbation thermique ↔ Metropolis
Metropolis : $P(\text{accept}) = \exp(-\Delta f / T)$ ; auto si $\Delta f \le 0$
$T \to \infty$ : tout accepté ($\approx 1$) · $T \to 0$ : tout rejeté ($\to 0$)
Schémas refroidissement : géométrique $T_{k+1} = \alpha T_k$ ($\alpha = 0{,}99$), logarithmique, exponentiel
Forte décroissance → min local · Faible décroissance → coûteux mais global
Critères arrêt : $T < T_{\min}$ · nb max éval · pas d'amélioration · optimum théorique
TSP : $(n-1)!$ naïf, $(n+1)!/2$ symétrique. NP-complet. Little/SEP (Roy 1964)
Voisinage TSP : 2-opt (2 arêtes) préférée à permutation (4 arêtes)