Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques

Le problème d’optimisation, le problème du voyageur de commerce, l’algorithme de la colline avec le voisinage 2-opt, les minima locaux et les redémarrages, le recuit simulé, la température et le schéma de refroidissement — sur un itinéraire à travers treize chefs-lieux de région dont l’optimum est connu.

13 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 26 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Le forgeron qui veut une lame solide ne laisse pas le métal chauffé au rouge refroidir brusquement — il le refroidit lentement. Les atomes ont ainsi le temps de trouver un arrangement régulier d’énergie minimale. Si le métal était refroidi d’un coup, les atomes se figeraient là où ils se trouvent et la lame serait cassante. En 1983, des physiciens ont remarqué que c’est exactement ce qui tourmente aussi les algorithmes qui cherchent la meilleure solution : s’ils ne font que « descendre », ils se figent dans le premier creux. Ainsi est né le recuit simulé — et avec lui l’une des idées les plus utiles de l’optimisation.

Cette partie ouvre le module consacré aux algorithmes inspirés par la nature. Elle fait suite à la partie Recherche dans l’espace d’états, où l’algorithme de la colline et le recuit sont apparus pour la première fois.

1. Le problème d’optimisation

Définition — problème d’optimisation et voisinage

On se donne un ensemble de solutions admissibles S et une fonction objectif f : S → ℝ. On cherche s* = argmin_{s ∈ S} f(s) — la solution de plus petite valeur (pour une maximisation, c’est l’inverse).

Un voisinage est une application N : S → 2^S qui associe à chaque solution l’ensemble des solutions « voisines », obtenues à partir d’elle par une petite modification. Une solution s est un minimum local si f(s) ≤ f(s′) pour tout s′ ∈ N(s), et un minimum global si cela vaut pour tout s′ ∈ S.

2. Le problème du voyageur de commerce

Un voyageur de commerce doit visiter les treize chefs-lieux de région de Tchéquie, passer une seule fois dans chacun et revenir à son point de départ. Quel itinéraire est le plus court ? Nous mesurons les distances à vol d’oiseau.

Définition — problème du voyageur de commerce (TSP)

On se donne n villes et les distances d(i, j). Une solution est une permutation cyclique π des villes ; sa longueur est f(π) = ∑_k=1ⁿ d(π_k, π_k+1), où π_n+1 = π₁.

Il existe (n − 1)! / 2 circuits différents (sans tenir compte de l’endroit ni du sens où ils commencent). La version décisionnelle du problème est NP-complète.

nombre de circuits = n! / (n · 2) = (n − 1)! / 2

n!

tous les ordres dans lesquels on peut énumérer n villes — c’est le nombre de permutations ; mais chaque circuit y est compté plusieurs fois

n

un circuit n’a pas de début : Praha → Brno → … → Praha est le même trajet que Brno → … → Praha → Brno. Chaque circuit peut commencer dans n’importe laquelle des n villes, d’où n fois moins

2

la distance à l’aller est la même qu’au retour, donc un circuit parcouru en sens inverse est le même trajet, de même longueur

Exemple — la distance à vol d’oiseau de Praha à Brno

Les villes sont données par leur latitude φ et leur longitude λ en degrés. Sur le territoire tchèque, une projection plane approximative suffit : un degré de latitude mesure 110,57 km, un degré de longitude 111,32 · cos φ₀ km, où φ₀ = 49,8° est le centre du pays (les méridiens convergent vers le pôle). Alors

d(i, j) = √( (71,85 · Δλ)² + (110,57 · Δφ)² ).

Praha (50,08° N, 14,42° E), Brno (49,20°, 16,61°)

Δλ = 2,19° → 71,85 · 2,19 = 157,35 km vers l’est

Δφ = −0,88° → 110,57 · 0,88 = 97,30 km vers le sud

d = √(157,35² + 97,30²) = √(24 759 + 9 467) = √34 226 ≈ 185,0 km

Par rapport à un calcul exact sur la sphère, l’erreur est d’environ 1 % pour de telles distances ; pour comparer des itinéraires, cela ne change rien.

Treize villes, c’est encore assez peu pour calculer l’optimum exactement — par la programmation dynamique de Held et Karp sur les sous-ensembles de villes, qui demande 2ⁿ · n² étapes au lieu de (n − 1)!. Le circuit le plus court mesure 1 060,4 km. Grâce à cela, nous verrons exactement, pour chaque algorithme suivant, à quel point il s’est approché de l’optimum :

Algorithme — programmation dynamique de Held et Karp (1962)

Numérotons les villes 0, …, n − 1 et partons de la ville 0. Pour tout ensemble de villes M ∋ 0 et toute ville j ∈ M, notons D(M, j) la longueur du plus court chemin qui part de 0, passe exactement par les villes de M et se termine en j. Alors

D({0}, 0) = 0,   D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ],

et la longueur du circuit optimal est min_{j ≠ 0} [ D(toutes les villes, j) + d(j, 0) ]. Il y a au plus 2ⁿ · n valeurs de D, et chacune est le minimum d’au plus n nombres.

n = 13:   2¹³ · 13² = 8 192 · 169 = 1 384 448 étapes

parcourir tous les ordres depuis un départ fixé : 12! = 479 001 600 — environ 346 fois plus

3. L’algorithme de la colline et le voisinage 2-opt

Définition — le mouvement 2-opt

Un mouvement 2-opt retire du circuit deux arêtes non adjacentes (a, b) et (e, f) et les remplace par les arêtes (a, e) et (b, f) — autrement dit, il inverse l’ordre des villes entre b et e. La longueur varie de Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f). Le voisinage d’un itinéraire passant par n villes compte (n − 1)(n − 2) / 2 mouvements.

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

Δ

de combien le circuit s’allonge ; un Δ négatif signifie un raccourcissement. L’algorithme de la colline comme le recuit décident selon son signe, c’est pourquoi il nous le faut à peu de frais

d(a, e) + d(b, f)

deux nouvelles arêtes qui relient à nouveau les extrémités coupées — elles s’ajoutent, car l’itinéraire les gagne

d(a, b) + d(e, f)

les deux arêtes que nous avons coupées — elles se retranchent, car elles disparaissent de l’itinéraire. Le tronçon entre b et e est seulement parcouru en sens inverse et les distances sont symétriques, sa longueur ne change donc pas et il est absent de la formule

Algorithme — algorithme de la colline (plus forte pente)

Partir d’une solution aléatoire s. Répéter : trouver s′ ∈ N(s) de plus petite valeur f(s′) ; si f(s′) < f(s), passer à s′, sinon s’arrêter — s est un minimum local.

def delta(c, i, j):                    # mouvement 2-opt : inverser c[i..j]
    a, b = c[i - 1], c[i]
    e, f = c[j], c[(j + 1) % len(c)]
    return d(a, e) + d(b, f) - d(a, b) - d(e, f)

def horolezec(c):
    n = len(c)
    while True:
        tahy = [(i, j) for i in range(1, n - 1) for j in range(i + 1, n)]
        i, j = min(tahy, key=lambda t: delta(c, *t))   # plus forte pente
        if delta(c, i, j) >= 0:                        # rien ne raccourcit l’itinéraire
            return c                                    # minimum local
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

Nous laissons la première ville en place (i ≥ 1) — un circuit n’a pas de début, cela n’apporterait donc rien de nouveau. Pour n = 13, les paires 1 ≤ i < j ≤ 12 donnent exactement 12 · 11 / 2 = 66 mouvements.

À partir d’un circuit aléatoire long de 2 402 km, l’algorithme de la colline arrive en 8 étapes à 1 065,8 km — et s’y arrête. Il ne manque que 5 km pour atteindre l’optimum, mais plus aucun mouvement 2-opt isolé ne raccourcit l’itinéraire. Le grimpeur est dans un minimum local et ne le sait pas :

4. Où l’algorithme de la colline reste bloqué

Sur cent départs aléatoires, l’algorithme de la colline a fini dans l’optimum 61 fois. Dans les 39 cas restants, il est resté bloqué ailleurs, au pire à 1 162,6 km — cent kilomètres de plus. Les pièges sont au nombre de trois :

• Minimum local — un creux d’où chaque pas mène vers le haut.
• Plateau — tous les voisins sont aussi bons, le grimpeur ne sait donc pas où aller.
• Crête — une bonne direction existe, mais elle ne suit aucun mouvement isolé ; on ne l’atteint qu’en passant par de moins bonnes solutions.

Exemple — pourquoi l’algorithme de la colline ne sort pas de 1 065,8 km

L’algorithme de la colline lancé depuis le premier départ a fini sur le circuit Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. Calculons Δ pour les 66 mouvements 2-opt : l’un d’eux (inverser tout sauf la première ville) donne le même circuit en sens inverse et Δ = 0, tous les autres allongent l’itinéraire. Le moins coûteux d’entre eux inverse la paire Pardubice – Hradec Králové :

a = Olomouc, b = Pardubice, e = Hradec Králové, f = Liberec

Δ = d(a, e) + d(b, f) − d(a, b) − d(e, f)

  = 122,9 + 95,9 − 116,8 − 83,0 = +19,0 km

Chaque mouvement isolé allonge donc l’itinéraire d’au moins 19,0 km — alors que l’optimum n’est plus court que de 5,4 km. Le chemin qui y mène passe par des circuits moins bons, et l’algorithme de la colline ne les accepte jamais.

Le remède le plus simple, ce sont les redémarrages aléatoires : relancer l’algorithme depuis un autre endroit et garder le meilleur résultat. Si un départ réussit avec une probabilité de 0,61, alors sur cinq départs au moins un réussit avec une probabilité de 1 − 0,39⁵ ≈ 99 %. Pour un petit problème, cela suffit. Pour un grand, il y a des millions de creux et il faudrait beaucoup trop de redémarrages.

P_r = 1 − (1 − p)^r

P_r

la probabilité qu’au moins un des r départs trouve l’optimum — nous la calculons par le complémentaire, car « au moins un » prend de nombreuses formes, alors que « aucun » n’en prend qu’une

1 − p

la probabilité qu’un départ échoue (chez nous 0,39 sur cent essais)

r

le nombre de départs en exposant : les départs sont indépendants (chacun a une graine aléatoire différente), les probabilités d’échec se multiplient donc

5. Le recuit simulé

Algorithme — recuit simulé

Partir d’une solution aléatoire s avec une température initiale T₀. À chaque itération :

1. choisir un voisin aléatoire s′ ∈ N(s) et calculer Δ = f(s′) − f(s) ;
2. si Δ ≤ 0, passer à s′ ; sinon y passer avec une probabilité e^−Δ/T (critère de Metropolis) ;
3. abaisser la température selon le schéma de refroidissement, par exemple T ← α · T avec 0 < α < 1.

Renvoyer la meilleure solution rencontrée en chemin.

P(accepter) = min(1, e^{−Δ / T})

P(accepter)

la probabilité de passer au voisin proposé ; dans le programme, nous tirons u uniformément dans [0, 1) et acceptons le mouvement si u < P

min(1, …)

pour une amélioration (Δ ≤ 0), l’exponentielle est ≥ 1 et une probabilité ne peut pas dépasser 1 — un meilleur pas est donc toujours accepté, comme dans l’algorithme de la colline

Δ

de combien le voisin est moins bon, en km. Il figure dans l’exposant avec un signe moins, si bien que chaque kilomètre de dégradation supplémentaire multiplie la chance par le même nombre inférieur à 1 — les grandes dégradations sont exponentiellement plus rares que les petites

T

la température, dans les mêmes unités que Δ (km). Elle divise Δ et fixe ainsi l’échelle : une dégradation de T km passe avec une probabilité 1/e ≈ 0,37 à n’importe quelle température. Une T élevée rend « petites » les grandes dégradations, T → 0 les interdit toutes

La règle d’acceptation d’un pas moins bon vient de la physique : en 1953, Nicholas Metropolis et ses collègues l’ont utilisée pour simuler des atomes en équilibre thermique, où la probabilité d’un état d’énergie E est proportionnelle à e^−E/kT. En 1983, Kirkpatrick, Gelatt et Vecchi, chez IBM, l’ont adaptée indépendamment à l’optimisation — et deux ans plus tard, tout aussi indépendamment, le physicien slovaque Vladimír Černý, justement sur le problème du voyageur de commerce.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # refroidissement géométrique
    T, delka = T0, delka_okruhu(c)
    nej, nej_delka = c, delka
    for k in range(K):
        i, j = sorted(random.randint(1, len(c) - 1) for _ in range(2))
        if i != j:                          # i = j : aucun mouvement
            D = delta(c, i, j)
            if D <= 0 or random.random() < math.exp(-D / T):
                c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]
                delka += D
                if delka < nej_delka:
                    nej, nej_delka = c, delka
        T *= alfa
    return nej

À quoi cela ressemble en vrai : les six premières itérations de notre exécution et six itérations du milieu. p est la probabilité d’acceptation min(1, e^−Δ/T), u le nombre tiré ; un mouvement qui dégrade passe si u < p.

Au début, à T ≈ 200, même un mouvement qui allonge l’itinéraire de 146,6 km passe — la chance est de 0,48 et le tirage a donné u = 0,14. À mi-parcours, T = 10 et l’itinéraire est déjà dans l’optimum ; les mouvements qui l’allongeraient de 70 kilomètres ou plus ont une chance inférieure à un pour mille et sont tous rejetés. Il arrive que les deux nombres aléatoires tombent au même endroit (i = j) et que l’itération ne propose rien — sur toute l’exécution, c’est arrivé 824 fois.

Théorème — distribution de Boltzmann (formulation actuelle)

Si l’on maintient la température T fixe et que l’on propose les voisins de façon symétrique (le voisin s′ est proposé depuis s avec la même probabilité que s depuis s′ — c’est le cas pour 2-opt, car le même mouvement (i, j) ramène aussi en arrière), alors le processus de Metropolis est une chaîne de Markov dont la distribution stationnaire est

π_T(s) = e^−f(s)/T / Z(T)

π_T(s)

à quelle fréquence, après une longue errance à la température T, nous nous retrouvons dans la solution s

e^−f(s)/T

le poids d’une solution : plus l’itinéraire f(s) est court, plus il est grand. C’est exactement le poids que le critère de Metropolis équilibre — le rapport des poids de deux voisins vaut e^−Δ/T

Z(T)

la somme des poids sur toutes les solutions ; nous divisons par elle pour que les probabilités totalisent 1

Preuve (condition d’équilibre détaillé) : pour des voisins tels que f(s′) = f(s) + Δ, Δ > 0, le flux de s vers s′ est proportionnel à π(s) · e^−Δ/T et le flux inverse à π(s′) · 1. Pour π = π_T, les deux expressions valent e^−f(s′)/T / Z, les flux s’équilibrent et la distribution ne change plus.

optimum (1 060,4 km) contre le piège de l’algorithme de la colline (1 065,8 km) : rapport des fréquences e^5,38/T

T = 100: 1,06   T = 10: 1,71   T = 1: 217   T = 0,5: 47 089

6. Température et schéma de refroidissement

Quelle chance a un pas qui allonge l’itinéraire de 20 km ? Cela dépend de la température :

À 200, presque chaque pas qui dégrade passe, à 0,5 aucun — le recuit se comporte alors comme l’algorithme de la colline. Le schéma de refroidissement détermine combien de temps l’algorithme « erre » et combien de temps il « descend ». La sortie la moins coûteuse du piège de l’algorithme de la colline (+19,0 km, voir plus haut) passerait à T = 50 avec une probabilité de 0,68, à T = 10 avec 0,15 et à T = 2 pratiquement jamais.

T_k = T₀ · α^k,   α = (T_K / T₀)^1/K

T_k

la température à la k-ième itération — elle détermine quelle taille de dégradation est encore acceptée à ce moment

T₀

la température initiale ; on la choisit de sorte qu’au début la plupart des dégradations passent — ici 200 km, plus qu’un mouvement 2-opt typique sur un itinéraire aléatoire

α

le coefficient de refroidissement, juste en dessous de 1 ; nous le calculons à partir de la température finale T_K et du nombre d’itérations K, pour que l’exécution s’arrête exactement là où nous le voulons

k

le numéro d’itération en exposant : chaque itération multiplie la température par le même nombre, si bien qu’en un même nombre d’itérations la température baisse toujours dans le même rapport — de 200 à 100 aussi longtemps que de 1 à 0,5

Théorème — convergence du recuit

Si la température décroît assez lentement, de façon logarithmique : T_k = c / ln(k + 1) avec une constante c assez grande, alors la probabilité que le recuit finisse dans le minimum global tend vers un lorsque le nombre d’itérations croît (Hajek, 1988).

« Assez grande » signifie précisément c ≥ d*, où d* est la profondeur du plus profond minimum local qui n’est pas global : de combien au moins un chemin qui en part doit monter avant d’atteindre une meilleure solution.

si c = 20 km suffisait, nous n’atteindrions la température 0,5 qu’à ln(k + 1) = 20 / 0,5 = 40,

soit après k ≈ e⁴⁰ ≈ 2,4 · 10¹⁷ itérations — environ un milliard de fois plus que l’ensemble des 239 500 800 circuits

7. Le recuit sur les chefs-lieux de région

Lançons le recuit sur le même problème : 10 000 itérations, la température baisse géométriquement de 200 à 0,5. La carte montre l’itinéraire au début et après 1 000, 3 000, 5 000 et 10 000 itérations :

Après mille itérations, l’itinéraire est encore chaotique (1 985 km) — à haute température, le recuit accepte presque tout. Après trois mille, il a déjà une forme (1 159 km), et après cinq mille il est dans l’optimum, 1 060,4 km. Sur les 1 498 mouvements acceptés, 695 étaient des dégradations ; l’algorithme de la colline n’en aurait fait aucun. Le graphique montre comment la longueur de l’itinéraire saute vers le haut et vers le bas, jusqu’à ce que la température baisse :

Le passage de l’errance à la descente se voit aussi dans le nombre de mouvements acceptés par tranche de mille itérations : 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. Dans le premier millier, quand T est entre 200 et 110, plus de la moitié des propositions sont acceptées. À partir du cinquième millier (T sous 20), seulement quelques dizaines ; parmi elles, 37 étaient des dégradations, dont 26 minimes, sous 3 km.

Et ce n’est pas le hasard d’une seule exécution : sur cent exécutions avec des graines différentes, 98 ont fini dans l’optimum et les deux autres à moins de 3 km. Comparé aux 61 % de l’algorithme de la colline avec un seul départ, c’est une grande différence.

8. Quand le recuit vaut la peine

Pour être honnête : le recuit a fait 10 000 itérations, l’algorithme de la colline depuis un seul départ seulement six cents évaluations environ. Sur un petit problème, l’algorithme de la colline avec redémarrages aurait fait aussi bien pour le même prix. La différence apparaît sur un problème plus grand. Prenons 60 villes placées au hasard et donnons aux deux algorithmes le même budget — 200 000 mouvements 2-opt évalués :

L’algorithme de la colline n’a tenu que deux fois dans le budget : avec 60 villes, le voisinage compte 1 711 mouvements, et la plus forte pente les examine tous à chaque étape. Le recuit essaie un mouvement aléatoire à la fois et répartit le même budget sur l’exploration de tout le paysage. Chacune de ses trois exécutions a fini mieux que l’algorithme de la colline.

9. Le recuit en intelligence artificielle et ailleurs

• Conception de puces et emplois du temps. Le placement des composants sur une puce a été l’une des premières grandes applications du recuit dans les années 1980 ; aujourd’hui encore, on l’utilise pour les emplois du temps, les tournées de véhicules ou l’agencement des entrepôts.
• Entraînement des réseaux de neurones. La descente de gradient stochastique calcule le gradient sur un petit lot de données, si bien que chaque pas est un peu aléatoire — comme le recuit, elle peut glisser hors d’un creux peu profond. Les schémas de taux d’apprentissage qui le font baisser progressivement s’appellent même cosine annealing.
• La température des modèles de langage. Quand un modèle de langage choisit le mot suivant, il divise les scores des mots par une température T et les transforme par la fonction softmax en probabilités proportionnelles à e^z/T — la même formule de Boltzmann. Une température élevée signifie un texte plus inventif et plus risqué, une basse un texte plus prudent et plus prévisible.
• Recuit quantique. Des ordinateurs spécialisés (par exemple D-Wave) cherchent le minimum d’énergie physiquement, en exploitant des effets quantiques. S’ils sont plus rapides que les algorithmes classiques, et quand, reste un sujet de recherche.

Exemple — la température dans le choix du mot suivant

Un modèle attribue à trois candidats pour le mot suivant les scores z = (2, 1, 0). La probabilité du i-ième mot est p_i = e^z_i/T / ∑_j e^z_j/T — la distribution de Boltzmann de la section sur le recuit, simplement avec l’« énergie » −z.

T = 1:   (e², e¹, e⁰) = (7,39 ; 2,72 ; 1), somme 11,11 → 0,665 ; 0,245 ; 0,090

T = 0,5:   (e⁴, e², 1) = (54,6 ; 7,39 ; 1), somme 62,99 → 0,867 ; 0,117 ; 0,016

T = 2:   (e¹, e^0,5, 1) = (2,72 ; 1,65 ; 1), somme 5,37 → 0,506 ; 0,307 ; 0,186

Une température plus basse déplace la probabilité vers le meilleur candidat (pour T → 0, c’est toujours lui), une plus haute la répand aussi sur des mots moins probables — tout comme le recuit à haute température accepte aussi des itinéraires moins bons.

10. Résumé

• Un problème d’optimisation cherche la solution ayant la meilleure valeur de la fonction objectif ; la recherche locale se déplace dans le voisinage de la solution courante.
• L’algorithme de la colline va toujours vers un meilleur voisin et reste bloqué dans un minimum local — sur les chefs-lieux de région, dans 39 départs sur 100. Les redémarrages aléatoires aident pour les petits problèmes.
• Le recuit simulé accepte aussi des pas moins bons, avec une probabilité e^−Δ/T ; à mesure que la température baisse, il passe de l’exploration à la descente.
• Sur les chefs-lieux de région, il a trouvé l’optimum dans 98 exécutions sur 100 ; sur un problème plus grand, il a battu l’algorithme de la colline à budget égal.
• La même formule de Boltzmann vit dans la température des modèles de langage, et l’idée du refroidissement dans les schémas d’apprentissage des réseaux de neurones.

Envie de mettre la main à la pâte ? Demandez à un agent d’IA d’écrire un recuit pour votre propre itinéraire — par exemple par les endroits où vous voulez aller pendant les vacances — et voyez ce que donne un refroidissement trop rapide.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.