Métaheuristiques et recuit simulé : cours, voyageur de commerce et exercices corrigés de prépa

Q: Qu'est-ce qu'une métaheuristique ?

Un schéma général de recherche d'une bonne solution d'un problème d'optimisation, qui ne dépend pas d'un problème particulier. Il guide une heuristique, le plus souvent une recherche par voisinage, pour l'empêcher de rester bloquée sur un optimum local ; il fait souvent appel au hasard et s'inspire souvent d'un phénomène naturel. Une heuristique est propre à un problème, comme le plus proche voisin pour les tournées ; une métaheuristique s'applique avec les mêmes lignes de code à des problèmes très différents, pourvu qu'on lui donne la représentation d'une solution, sa fonction de coût et son voisinage. Le recuit simulé, les algorithmes génétiques, les colonies de fourmis et la recherche tabou en sont des familles. Seul le recuit simulé est au programme : un sujet qui en emploie une autre la décrit entièrement, comme Centrale-Supélec 2017 pour un algorithme génétique et Mines-Ponts 2025 pour une colonie de fourmis. Dans tous les cas, la solution obtenue est approchée, sans garantie d'être optimale.

Q: Comment fonctionne l'algorithme du recuit simulé ?

On choisit six ingrédients : la représentation d'une solution, sa fonction de coût, le voisinage, une solution initiale réalisable, la loi de refroidissement et le critère d'arrêt. À chaque étape, on tire un voisin s' de la solution courante s, on calcule Δ = coût(s') - coût(s), on accepte le voisin selon la règle de Metropolis, puis on diminue la température, en général par T ← α T avec 0 T_min`, jamais `while T > 0` : en flottants, la température ne s'annule jamais et la boucle ne s'arrêterait pas.

Q: Quelle est la probabilité d'acceptation du recuit simulé ?

En minimisation, un voisin qui n'est pas plus mauvais, Δ ≤ 0, est toujours accepté ; un voisin plus mauvais, Δ > 0, est accepté avec la probabilité e^(-Δ/T). En Python, le test s'écrit `d <= 0 or random.random() < exp(-d / T)`. Cette probabilité diminue quand la dégradation grandit et quand la température baisse : une dégradation de 10 passe avec la probabilité 0,90 à T = 100, 0,37 à T = 10 et 4,5 · 10^(-5) à T = 1. Température haute, on explore ; température basse, on ne fait plus que descendre. En maximisation d'une valeur v, on pose Δ = v(s') - v(s) et l'on accepte si Δ ≥ 0, sinon avec la probabilité e^(Δ/T). Le signe se vérifie sur une dégradation : une probabilité plus grande que 1 signale une erreur.

Q: Comment choisir la température initiale et le facteur de refroidissement ?

La température initiale se règle d'après les écarts de coût du problème : un bon choix fait accepter au début environ la moitié des dégradations voisines. Trop basse, le recuit n'est qu'une descente ; trop haute pour trop peu d'étapes, il erre au hasard. Le facteur α fixe la durée : de T_0 à T_(min), le refroidissement géométrique fait le plus petit nombre d'étapes k tel que T_0 α^k ≤ T_(min), soit 135 étapes de 1000 à 1 pour α = 0,95 et 688 pour α = 0,99. Sur la tournée de dix lieux, avec T_0 = 50 et T_(min) = 0,1, la tournée la plus courte est atteinte 61 fois sur 200 graines avec α = 0,95, 183 fois avec 0,99 et 199 fois avec 0,995. Refroidir trop vite revient à une trempe : on reste dans un minimum local. On mesure toujours sur plusieurs graines.

Q: Comment appliquer le recuit simulé au problème du voyageur de commerce ?

Une tournée est une liste qui contient une fois chaque lieu et commence par le lieu de départ ; sa longueur compte le retour au départ. Avec n lieux et des distances symétriques, il y a (n-1)!/2 tournées : 181 440 pour 10 lieux, environ 6,1 · 10^(16) pour 20, et aucune méthode exacte rapide n'est connue. On part de la tournée du plus proche voisin et l'on prend comme voisin l'inversion d'un tronçon `t[i..j]`, qui ne change que deux tronçons et défait les croisements : sa variation de longueur se calcule en O(1), par `D[a][c] + D[b][d] - D[a][b] - D[c][d]`. Sur les dix lieux du cours, avec les mêmes réglages, le recuit par inversions atteint 172 km dans 183 cas sur 200, contre 48 avec l'échange de deux lieux. Le voisinage compte autant que les paramètres.

Q: Le recuit simulé donne-t-il toujours la solution optimale ?

Non. On prouve qu'il termine, puisque le nombre d'étapes restantes est un variant, et que deux propriétés restent vraies à chaque tour : la solution courante est réalisable, et la meilleure solution gardée est la meilleure rencontrée. Rien ne prouve qu'elle soit optimale. Deux exécutions avec des graines différentes donnent en général deux résultats différents : on fixe la graine par `random.seed(g)` pour reproduire une expérience, on mesure la méthode sur beaucoup de graines et l'on garde la meilleure de plusieurs exécutions. Sur le chargement du camion, 135 étapes trouvent l'optimum 132 dans 109 cas sur 200 et restent à 131 dans 46. On conclut donc avec prudence : seule une méthode exacte, quand elle est possible, comme l'énumération des tournées de onze ksour, prouve qu'une solution est la meilleure.

Problèmes d'optimisation difficiles, recherche locale et voisinage, minimum local et global, métaheuristique, recuit simulé : température, probabilité d'acceptation de Metropolis, schéma de refroidissement, critère d'arrêt, réglage des paramètres, voyageur de commerce, sac à dos, comparaison avec les méthodes exactes et les heuristiques constructives.

15méthodes
34exercices corrigés
3problèmes
20pièges
44figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Une métaheuristique est un schéma général de recherche, indépendant du problème, qui guide une heuristique pour l'empêcher de rester bloquée sur un optimum local ; elle donne une solution approchée, souvent très bonne, en un temps choisi, sans garantie d'optimalité. Le recuit simulé, inspiré du recuit des métaux, part d'une solution réalisable, tire un voisin au hasard et l'accepte s'il n'est pas plus mauvais, sinon avec la probabilité $e^{-\Delta/T}$ , la règle de Metropolis ; la température $T$ baisse à chaque étape, et l'on garde la meilleure solution vue. Le chapitre est au programme d'informatique de deuxième année en MP, PSI et TSI au Maroc. Il enseigne à formaliser un problème d'optimisation, à compter ses solutions, à définir un voisinage et une descente, à distinguer optimum local et optimum global, puis à programmer le recuit en Python, à régler la température initiale, le facteur de refroidissement et l'arrêt sur plusieurs graines, et à évaluer un voisin par différence. Les exemples sont le sac à dos binaire, où la descente partie du camion vide s'arrête à 131 quand l'optimum vaut 132, et le problème du voyageur de commerce : dix lieux donnent 181 440 tournées, et le recuit par inversions atteint la plus courte, 172 km, dans 183 cas sur 200. Les exercices et les problèmes reprennent des sujets d'informatique de Centrale-Supélec, sur le critère de Metropolis, l'allocation des niveaux de vol et un algorithme génétique, et de Mines-Ponts, sur une colonie de fourmis pour le sac à dos.

Ce que tu sauras faire

Certains problèmes d'optimisation ont tant de solutions qu'il est impossible de les examiner toutes, et aucune méthode exacte ne les résout en un temps raisonnable. On cherche alors une très bonne solution, rapidement, sans promesse qu'elle soit la meilleure. Une métaheuristique organise cette recherche ; le recuit simulé en est l'exemple du programme. Il améliore une solution par petites modifications et accepte parfois de reculer, pour ne pas rester bloqué.

formaliser un problème d'optimisation : solutions, contraintes, coût ou valeur, sens ;
définir un voisinage, écrire une descente et reconnaître un optimum local ;
définir une métaheuristique et dire à quoi elle sert ;
expliquer l'intérêt et le principe du recuit simulé : température, règle d'acceptation, refroidissement, arrêt ;
programmer le recuit simulé en Python et justifier son coût ;
régler ses paramètres par l'expérience, avec une graine fixée ;
conclure honnêtement : la solution obtenue est approchée, non garantie optimale.

L'essentiel : La règle d'acceptation Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

En minimisation, $\Delta = \text{coût}(s') - \text{coût}(s)$ :

$\Delta \le 0$ : le voisin est accepté ;
$\Delta > 0$ : il est accepté avec la probabilité $e^{-\Delta/T}$ , test random.random() < exp(-delta / T).

En maximisation, $\Delta = v(s') - v(s)$ : accepté si $\Delta \ge 0$ , sinon avec la probabilité $e^{\Delta/T}$ . Une dégradation a toujours une probabilité strictement inférieure à 1.

$e^{-\Delta/T}$	$T = 100$	$T = 10$	$T = 1$
$\Delta = 1$	0,99	0,90	0,37
$\Delta = 10$	0,90	0,37	$4{,}5 \cdot 10^{-5}$
$\Delta = 50$	0,61	0,0067	$1{,}9 \cdot 10^{-22}$

Température haute : on explore. Température basse : on ne fait plus que descendre.

Une méthode du chapitre Extrait gratuit

Méthode Écrire la boucle complète du recuit

Quand l’utiliser

« Écrire une fonction qui applique l'algorithme du recuit simulé », avec ou sans fonctions fournies par le sujet.

Rappel de cours

Six ingrédients : représentation, coût, voisin, solution initiale réalisable, refroidissement, arrêt ; garder la meilleure solution vue (cours, section 4).

Démarche

Initialiser la solution courante, son coût, la meilleure solution, son coût, la température.
Écrire la boucle while T > T_min (ou sur un nombre d'étapes).
Dans la boucle : voisin, $\Delta$ , test d'acceptation, mise à jour de la courante et de la meilleure.
Diminuer la température à chaque tour, hors du test d'acceptation.
Renvoyer la meilleure solution et son coût.

Rédaction type

def recuit(s0, cout, voisin, T0, alpha, T_min):
    s = s0
    c = cout(s)
    meilleure, c_meilleure = s, c
    T = T0
    while T > T_min:
        v = voisin(s)
        d = cout(v) - c
        if d <= 0 or random.random() < exp(-d / T):
            s, c = v, c + d
            if c < c_meilleure:
                meilleure, c_meilleure = s, c
        T = alpha * T
    return meilleure, c_meilleure

Exemple traité

def cout_colis(s):
    return ecart(s, P)

random.seed(2026)
print(recuit([0, 0, 0, 0, 0], cout_colis, voisin_colis,
             5, 0.9, 0.1))

Le programme affiche :

([1, 0, 1, 0, 0], 0)

Partie de « tout dans A », écart 22, cette exécution trouve en 38 étapes la répartition « 7 et 4 dans B », écart 0.

Erreurs fréquentes

Diminuer $T$ seulement quand le voisin est accepté.
Renvoyer la solution courante au lieu de la meilleure.
Recalculer cout(meilleure) à chaque tour au lieu de garder sa valeur.

Pour s’entraîner

Exercices 15, 16, 17, 21, 23, 27, 28 et 29 ; problème 1.

Un exercice corrigé Extrait gratuit

Exercice La tournée de onze ksour ★★☆

La coopérative ajoute un onzième ksar à sa tournée. Les onze ksour fictifs, numérotés de 0 à 10, sont séparés par les distances suivantes, en kilomètres.

M11 = [[ 0, 40,  7, 16, 48,  9, 41, 18, 22, 44, 32],
       [40,  0, 41, 42, 36, 48, 17, 23, 21, 14,  8],
       [ 7, 41,  0,  9, 44,  8, 39, 22, 21, 44, 33],
       [16, 42,  9,  0, 37, 14, 36, 26, 21, 41, 34],
       [48, 36, 44, 37,  0, 51, 19, 43, 31, 23, 34],
       [ 9, 48,  8, 14, 51,  0, 47, 27, 29, 51, 40],
       [41, 17, 39, 36, 19, 47,  0, 29, 19,  5, 16],
       [18, 23, 22, 26, 43, 27, 29,  0, 12, 31, 16],
       [22, 21, 21, 21, 31, 29, 19, 12,  0, 23, 13],
       [44, 14, 44, 41, 23, 51,  5, 31, 23,  0, 16],
       [32,  8, 33, 34, 34, 40, 16, 16, 13, 16,  0]]

Calculer la tournée du plus proche voisin et sa longueur.
Écrire descente_inversion(D, t), qui, à chaque tour, essaie toutes les inversions d'un tronçon t[i..j], $1 \le i < j \le n - 1$ , évaluées par delta_inversion, applique la meilleure si elle raccourcit strictement la tournée, et s'arrête sinon. L'appliquer à la tournée du plus proche voisin.
Lancer recuit_tournee(M11, t0, 50, 0.99, 0.1) depuis la même tournée, après random.seed(2026), puis avec les graines 0 à 49.
La fonction meilleure_tournee de l'exercice 10 essaie $10! = 3\,628\,800$ ordres. L'exécuter et conclure.

Indications

Méthodes 7 et 9 : départ par le plus proche voisin, puis recherche locale, puis recuit.
delta_inversion(t, i, j, D) donne la variation de longueur en $O(1)$ .
Méthode 14 : comparer à l'optimum exact, puis écrire une conclusion prudente.

Analyse : comment trouver l’idée

On enchaîne trois méthodes de plus en plus coûteuses : une construction en $O(n^2)$ , une descente qui s'arrête dès qu'aucune inversion ne raccourcit, puis un recuit qui accepte parfois de rallonger. L'énumération, encore possible pour onze ksour, sert d'arbitre.

Correction détaillée

# copie de t où le tronçon de i à j est inversé
def inverse(t, i, j):
    v = t[:]
    while i < j:
        v[i], v[j] = v[j], v[i]
        i = i + 1
        j = j - 1
    return v

# descente par inversions, meilleure amélioration
def descente_inversion(D, t):
    n = len(t)
    while True:
        meilleur = [0, 0, 0]
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                d = delta_inversion(t, i, j, D)
                if d < meilleur[0]:
                    meilleur = [d, i, j]
        if meilleur[0] == 0:
            return t
        t = inverse(t, meilleur[1], meilleur[2])

t0 = plus_proche_voisin(M11)
print(t0, cout_tournee(t0, M11))
t1 = descente_inversion(M11, t0)
print(t1, cout_tournee(t1, M11))
random.seed(2026)
print(recuit_tournee(M11, t0, 50, 0.99, 0.1))
nb = 0
for g in range(50):
    random.seed(g)
    if recuit_tournee(M11, t0, 50, 0.99, 0.1)[1] == 152:
        nb = nb + 1
print(nb)

Le programme affiche :

[0, 2, 5, 3, 8, 7, 10, 1, 9, 6, 4] 172
[0, 5, 2, 3, 8, 4, 6, 9, 1, 10, 7] 158
([0, 7, 8, 10, 1, 9, 6, 4, 3, 2, 5], 152)
31

Puis, avec la fonction meilleure_tournee de l'exercice 10, recopiée :

# (longueur minimale, une tournée qui l'atteint),
# par essai de tous les ordres de passage
def meilleure_tournee(D):
    n = len(D)
    vu = [False] * n
    vu[0] = True
    t = [0]
    meilleur = [-1, []]
    # complète t, de longueur partielle L
    def essai(L):
        if len(t) == n:
            total = L + D[t[n - 1]][0]
            if meilleur[0] == -1 or total < meilleur[0]:
                meilleur[0] = total
                meilleur[1] = t[:]
            return
        x = t[len(t) - 1]
        for y in range(1, n):
            if not vu[y]:
                vu[y] = True
                t.append(y)
                essai(L + D[x][y])
                t.pop()
                vu[y] = False
    essai(0)
    return meilleur[0], meilleur[1]

print(meilleure_tournee(M11))

Le programme affiche :

(152, [0, 5, 2, 3, 4, 6, 9, 1, 10, 8, 7])

Les onze ksour : à gauche la tournée du plus proche voisin, au milieu celle de la descente par inversions, à droite celle du recuit (graine 2026), qui est la plus courte.

Bilan. Le plus proche voisin donne 172 km. La descente par inversions défait ses croisements et descend à 158 km, puis s'arrête : aucune inversion seule ne raccourcit plus la tournée. Le recuit, parti de la même tournée, trouve 152 km avec la graine 2026, et 152 sort 31 fois sur 50 graines. L'énumération, qui a demandé plusieurs secondes, prouve que 152 km est l'optimum. Pour onze ksour, on peut encore vérifier ; pour trente, plus du tout. On conclut : « le recuit a trouvé une tournée de 152 km, 20 km de moins que le plus proche voisin, 6 de moins que la descente ; c'est la plus courte possible, ce que seule l'énumération démontre ici ».

Méthodes à retenir

Plus proche voisin, puis descente, puis recuit : chaque étape part de la précédente et améliore. Le recuit sort du creux où la descente s'arrête. Voir les méthodes 7, 9 et 14.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 15 méthodes, 20 pièges corrigés, la carte mentale, 34 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Voir les offres

Plan du cours

1. Des problèmes trop grands pour tout essayer
- 1.1 Charger le camion
- 1.2 La tournée des ksour
- 1.3 Problème d'optimisation
- 1.4 Compter les solutions
- 1.5 Les méthodes exactes ont leurs limites
2. Heuristiques et recherche locale
- 2.1 Exact et heuristique
- 2.2 Une heuristique constructive : le plus proche voisin
- 2.3 Améliorer pas à pas : voisinage et descente
- 2.4 Optimum local et optimum global
- 2.5 Métaheuristique
3. Le recuit simulé : principe
- 3.1 Le recuit des métaux
- 3.2 De la physique à l'algorithme
- 3.3 La règle d'acceptation
- 3.4 Le rôle de la température
- 3.5 Minimiser ou maximiser
- 3.6 Un peu d'histoire
4. L'algorithme
- 4.1 Le schéma
- 4.2 Le refroidissement
- 4.3 Le critère d'arrêt
- 4.4 Garder la meilleure solution vue
- 4.5 Terminaison, et ce que l'on peut prouver
5. Programmer le recuit en Python
- 5.1 Ce que le sujet fournit
- 5.2 Un recuit générique
- 5.3 Le chargement du camion
- 5.4 La tournée des ksour
- 5.5 Copier ou annuler
6. Le coût d'un recuit
- 6.1 Le coût d'une étape
- 6.2 Évaluer un voisin par différence
- 6.3 Le coût total se règle
7. Les contraintes
- 7.1 Ne proposer que des voisins réalisables
- 7.2 Pénaliser l'excès
8. Hasard, reproductibilité et réglages
- 8.1 Deux exécutions, deux résultats : la graine
- 8.2 Mesurer sur plusieurs graines
- 8.3 Régler la température et le refroidissement
- 8.4 Choisir le voisinage
9. Bilan
- 9.1 Écrire un recuit en sept étapes
- 9.2 Choisir sa méthode
- 9.3 Pour aller plus loin

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Définir une métaheuristique et expliquer l'intérêt du recuit simulé
Formaliser un problème d'optimisation
Compter les solutions et juger la force brute
Choisir la représentation d'une solution et écrire sa fonction de coût
Définir un voisinage et écrire un voisin sans modifier la solution courante
Écrire une descente et reconnaître un optimum local
Construire une solution de départ par une heuristique constructive
Écrire le test d'acceptation, en minimisation et en maximisation
Écrire la boucle complète du recuit
Traiter une contrainte : voisins réalisables ou pénalité
Calculer le nombre d'étapes et le coût d'une étape ; évaluer un voisin par différence
Rendre une expérience reproductible et comparer plusieurs exécutions
Régler les paramètres et lire une courbe de coût
Comparer des méthodes et conclure sans promettre l'optimum
Lire et compléter un algorithme d'optimisation décrit par un sujet

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Trois problèmes à formaliser
Combien de tournées ?
Accepté ou refusé
La longueur d'une tournée
Deux voisins sans toucher à la tournée
Le critère de Metropolis
Les optimums locaux d'un petit chargement
Combien d'étapes de refroidissement
Copier avant de modifier
Le plus proche voisin à la main
Les deux randint
Minimiser ou maximiser : le signe
Trois questions de cours

Entraînement (16)

Une descente sur le chargement
Le recuit du chargement
Trouver les erreurs d'un recuit
La tournée de onze ksour
Évaluer une inversion par différence
Une solution qui n'en est pas une
Choisir la température initiale
Arrêter quand rien ne s'améliore
Le palier
Répartir les caisses entre deux camions
La courbe d'un recuit
Même graine, même résultat
La boucle qui ne s'arrête pas
Un recuit pour deux problèmes
Recuit, glouton et programmation dynamique
Pourquoi la programmation dynamique ne sauve pas la tournée

Approfondissement (5)

Un paysage à plusieurs creux
Des créneaux de livraison sans conflit
Placer les étals d'un souk
Répartir des colis entre trois camions
Une longue exécution ou dix courtes

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Allouer les niveaux de vol
Centrale-Supélec 2016, filières MP, PC, PSI et TSI, épreuve d'informatique, problème « Prévention des collisions aériennes », partie II « Allocation des niveaux de vol », questions II.A.1 à II.D, complétée
Planifier l'exploration d'un robot
Centrale-Supélec 2017, filières MP, PC, PSI et TSI, épreuve d'informatique, problème « Mars Exploration Rovers, mission d'exploration martienne », parties II « Planification d'une exploration : première approche » et III « Deuxième approche : algorithme génétique », complétée
Le sac à dos par une colonie de fourmis
Mines-Ponts 2025, filières MP, PC et PSI, épreuve d'informatique commune, problème « Autour du sac à dos », parties 7 « Résolution approchée par colonie de fourmis (ACO) » et 8 « Analyse des résultats », questions 18 à 24

Questions fréquentes

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

Un schéma général de recherche d'une bonne solution d'un problème d'optimisation, qui ne dépend pas d'un problème particulier. Il guide une heuristique, le plus souvent une recherche par voisinage, pour l'empêcher de rester bloquée sur un optimum local ; il fait souvent appel au hasard et s'inspire souvent d'un phénomène naturel. Une heuristique est propre à un problème, comme le plus proche voisin pour les tournées ; une métaheuristique s'applique avec les mêmes lignes de code à des problèmes très différents, pourvu qu'on lui donne la représentation d'une solution, sa fonction de coût et son voisinage. Le recuit simulé, les algorithmes génétiques, les colonies de fourmis et la recherche tabou en sont des familles. Seul le recuit simulé est au programme : un sujet qui en emploie une autre la décrit entièrement, comme Centrale-Supélec 2017 pour un algorithme génétique et Mines-Ponts 2025 pour une colonie de fourmis. Dans tous les cas, la solution obtenue est approchée, sans garantie d'être optimale.

Comment fonctionne l'algorithme du recuit simulé ?

On choisit six ingrédients : la représentation d'une solution, sa fonction de coût, le voisinage, une solution initiale réalisable, la loi de refroidissement et le critère d'arrêt. À chaque étape, on tire un voisin $s'$ de la solution courante $s$ , on calcule $\Delta = \text{coût}(s') - \text{coût}(s)$ , on accepte le voisin selon la règle de Metropolis, puis on diminue la température, en général par $T \leftarrow \alpha T$ avec $0 < \alpha < 1$ proche de 1. Comme la solution courante peut se dégrader à tout moment, on garde à part la meilleure solution vue et son coût, et c'est elle que l'on renvoie. La boucle s'écrit while T > T_min, jamais while T > 0 : en flottants, la température ne s'annule jamais et la boucle ne s'arrêterait pas.

Quelle est la probabilité d'acceptation du recuit simulé ?

En minimisation, un voisin qui n'est pas plus mauvais, $\Delta \le 0$ , est toujours accepté ; un voisin plus mauvais, $\Delta > 0$ , est accepté avec la probabilité $e^{-\Delta/T}$ . En Python, le test s'écrit d <= 0 or random.random() < exp(-d / T). Cette probabilité diminue quand la dégradation grandit et quand la température baisse : une dégradation de 10 passe avec la probabilité 0,90 à $T = 100$ , 0,37 à $T = 10$ et $4{,}5 \cdot 10^{-5}$ à $T = 1$ . Température haute, on explore ; température basse, on ne fait plus que descendre. En maximisation d'une valeur $v$ , on pose $\Delta = v(s') - v(s)$ et l'on accepte si $\Delta \ge 0$ , sinon avec la probabilité $e^{\Delta/T}$ . Le signe se vérifie sur une dégradation : une probabilité plus grande que 1 signale une erreur.

Comment choisir la température initiale et le facteur de refroidissement ?

La température initiale se règle d'après les écarts de coût du problème : un bon choix fait accepter au début environ la moitié des dégradations voisines. Trop basse, le recuit n'est qu'une descente ; trop haute pour trop peu d'étapes, il erre au hasard. Le facteur $\alpha$ fixe la durée : de $T_0$ à $T_{min}$ , le refroidissement géométrique fait le plus petit nombre d'étapes $k$ tel que $T_0 \alpha^k \le T_{min}$ , soit 135 étapes de 1000 à 1 pour $\alpha = 0{,}95$ et 688 pour $\alpha = 0{,}99$ . Sur la tournée de dix lieux, avec $T_0 = 50$ et $T_{min} = 0{,}1$ , la tournée la plus courte est atteinte 61 fois sur 200 graines avec $\alpha = 0{,}95$ , 183 fois avec 0,99 et 199 fois avec 0,995. Refroidir trop vite revient à une trempe : on reste dans un minimum local. On mesure toujours sur plusieurs graines.

Comment appliquer le recuit simulé au problème du voyageur de commerce ?

Une tournée est une liste qui contient une fois chaque lieu et commence par le lieu de départ ; sa longueur compte le retour au départ. Avec $n$ lieux et des distances symétriques, il y a $(n-1)!/2$ tournées : 181 440 pour 10 lieux, environ $6{,}1 \cdot 10^{16}$ pour 20, et aucune méthode exacte rapide n'est connue. On part de la tournée du plus proche voisin et l'on prend comme voisin l'inversion d'un tronçon t[i..j], qui ne change que deux tronçons et défait les croisements : sa variation de longueur se calcule en $O(1)$ , par D[a][c] + D[b][d] - D[a][b] - D[c][d]. Sur les dix lieux du cours, avec les mêmes réglages, le recuit par inversions atteint 172 km dans 183 cas sur 200, contre 48 avec l'échange de deux lieux. Le voisinage compte autant que les paramètres.

Le recuit simulé donne-t-il toujours la solution optimale ?

Non. On prouve qu'il termine, puisque le nombre d'étapes restantes est un variant, et que deux propriétés restent vraies à chaque tour : la solution courante est réalisable, et la meilleure solution gardée est la meilleure rencontrée. Rien ne prouve qu'elle soit optimale. Deux exécutions avec des graines différentes donnent en général deux résultats différents : on fixe la graine par random.seed(g) pour reproduire une expérience, on mesure la méthode sur beaucoup de graines et l'on garde la meilleure de plusieurs exécutions. Sur le chargement du camion, 135 étapes trouvent l'optimum 132 dans 109 cas sur 200 et restent à 131 dans 46. On conclut donc avec prudence : seule une méthode exacte, quand elle est possible, comme l'énumération des tournées de onze ksour, prouve qu'une solution est la meilleure.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.

Métaheuristiques et recuit simulé : cours, voyageur de commerce et exercices corrigés de prépa

Ce que tu sauras faire

L'essentiel : La règle d'acceptation Extrait gratuit

Une méthode du chapitre Extrait gratuit

Un exercice corrigé Extrait gratuit

Plan du cours

Les méthodes du chapitre

Les exercices corrigés

Application directe (13)

Entraînement (16)

Approfondissement (5)

Les problèmes de concours

Questions fréquentes

Comment y accéder

Toute ta prépa au même endroit