Search-04-LocalSearch (C#) : Recherche Locale et Métaheuristiques

Navigation : << Recherche informée (Search-3) | Index série Search | Algorithmes génétiques (Search-5) >>

Jumeau .NET du notebook Python Search-04-LocalSearch. Ce notebook est le port C# fidèle des trois familles fondamentales de recherche locale : Hill Climbing, recuit simulé (Simulated Annealing) et recherche tabou (Tabu Search), illustrées sur un paysage de fitness 1D puis sur le problème des N-Reines.

Pourquoi un jumeau C# ?

La recherche locale change de point de vue : quand seule la destination compte (pas le chemin), on abandonne l’arbre d’exploration pour naviguer de voisin en voisin dans un paysage de fitness, en acceptant temporairement de moins bonnes solutions pour s’échapper des optima locaux. Ce notebook montre, en C# / .NET 9.0, comment chaque métaheuristique négocie ce compromis exploration vs exploitation. Les algorithmes sont réimplémentés à partir de la littérature fondatrice (Metropolis 1953 pour le recuit simulé, Kirkpatrick-Gelatt-Vecchi 1983, Glover 1986 pour la recherche tabou) — pas de bibliothèque externe, pour rendre chaque mécanisme lisible.

Fidélité .NET ⇄ Python (G.9). Le générateur aléatoire Random(seed) de .NET n’est pas un Mersenne Twister identique à celui de NumPy : les trajectoires numériques précises (positions, coûts, nombres d’itérations) diffèrent du jumeau Python. Les propriétés pédagogiques sont en revanche intégralement préservées — Hill Climbing se piège dans les optima locaux, le recuit simulé s’en échappe par l’acceptation de Metropolis, Tabu par sa mémoire — ce qui est l’enseignement visé.

1. Paysage de fitness et voisins (~5 min)

La recherche locale part d’une idée simple : un problème d’optimisation est un paysage où l’altitude est la qualité de la solution. On se déplace de voisin en voisin. Tout le jeu est de définir ce qu’est un voisin, et comment on choisit le prochain.

Nous travaillons d’abord sur une fonction 1D multimodale (plusieurs maxima locaux) — le cas canonique où Hill Climbing échoue et où le recuit simulé brille.

// Imports + fonction de fitness 1D multimodale (paysage avec optima locaux)
using System;
using System.Globalization;

// Paysage de fitness : sinusoidal module pour creer plusieurs optima locaux.
// f(x) = sin(x) + 0.4*sin(3*x) sur [xmin, xmax]. Plusieurs pics locaux.
double Fitness(double x) => Math.Sin(x) + 0.4 * Math.Sin(3 * x);

(double xmin, double xmax) domaine = (-2.0, 10.0);

// Affichage ASCII du paysage sur 60 colonnes, 15 lignes.
void AfficherPaysage(Func<double,double> f, double xmin, double xmax, int width = 60, int height = 15) {
    // echantillonnage
    double[] xs = new double[width];
    double[] ys = new double[width];
    for (int i = 0; i < width; i++) {
        xs[i] = xmin + (xmax - xmin) * i / (width - 1);
        ys[i] = f(xs[i]);
    }
    double ymin = ys.Min(), ymax = ys.Max();
    // calcul de la colonne de chaque point pour un rendu "courbe"
    int[] col = new int[height + 1];
    for (int h = 0; h <= height; h++) col[h] = -1;
    var grid = new char[height, width];
    for (int r = 0; r < height; r++)
        for (int c = 0; c < width; c++) grid[r, c] = ' ';
    for (int i = 0; i < width; i++) {
        int row = (int)Math.Round((ymax - ys[i]) / (ymax - ymin) * (height - 1));
        grid[row, i] = '*';
    }
    Console.WriteLine($"Paysage f(x) = sin(x) + 0.4 sin(3x) sur [{xmin}, {xmax}]   (y in [{ymin:F2}, {ymax:F2}])");
    for (int r = 0; r < height; r++) {
        var sb = new System.Text.StringBuilder();
        for (int c = 0; c < width; c++) sb.Append(grid[r, c]);
        Console.WriteLine(sb.ToString());
    }
}

AfficherPaysage(Fitness, domaine.xmin, domaine.xmax);
Paysage f(x) = sin(x) + 0.4 sin(3x) sur [-2, 10]   (y in [-0,99, 0,98])
             **      **                     **      **      
            *  *    *  *                   *  *    *  *     
                *  *                           *  *         
           *     **     *                 *     **     *    
                                                            
                                                            
          *              *               *              *   
                                                            
                                                            
                          *             *                   
         *                                               *  
  *                              *                          
 * **   *                  *    * **   *                  * 
*    *                         *    *                       
      **                    ***      **                    *

Interprétation : paysage de fitness

La courbe montre une fonction multimodale : plusieurs maxima locaux entrecoupés de vallées. Le maximum global est quelque part à droite, mais un algorithme glouton partant de la gauche s’arrêtera dans le premier pic qu’il rencontre.

2. Hill Climbing (~10 min)

Principe

Le Hill Climbing (escalade de colline) est la métaheuristique la plus simple : depuis la position courante, examiner les voisins immédiats, se déplacer vers le meilleur voisin améliorant, s’arrêter quand aucun voisin n’améliore. C’est l’exploitation pure — aucune exploration.

Deux variantes : - Steepest-ascent : comparer tous les voisins, prendre le meilleur (celui que nous implémentons). - First-choice : prendre le premier voisin améliorant trouvé (utile quand le voisinage est grand).

// Hill Climbing steepest-ascent sur fonction 1D.
// Depuis x, comparer x-step et x+step, se deplacer vers le meilleur voisin strictement ameliorant.
// Stop quand aucun voisin n'ameliore.
(double finalX, double finalFx, List<double> trace) HillClimbing(
    Func<double,double> f, double x0, double step, double xmin, double xmax, int maxIter = 200) {
    double x = x0;
    var trace = new List<double> { x };
    for (int it = 0; it < maxIter; it++) {
        double fx = f(x);
        double xLeft = Math.Max(xmin, x - step);
        double xRight = Math.Min(xmax, x + step);
        double fLeft = f(xLeft), fRight = f(xRight);
        // meilleur voisin strictement ameliorant
        double bestNeighbor = x; double bestF = fx;
        if (fLeft > bestF) { bestF = fLeft; bestNeighbor = xLeft; }
        if (fRight > bestF) { bestF = fRight; bestNeighbor = xRight; }
        if (bestNeighbor == x) break;  // optimum local atteint
        x = bestNeighbor;
        trace.Add(x);
    }
    return (x, f(x), trace);
}

// Demarrage a gauche du paysage (zone riche en optima locaux)
var rnd = new Random(42);
double x0 = domaine.xmin + 0.5;
var (xf, fxf, trace) = HillClimbing(Fitness, x0, step: 0.15, domaine.xmin, domaine.xmax);
Console.WriteLine($"Hill Climbing depuis x0 = {x0:F3}");
Console.WriteLine($"  -> converge en x = {xf:F3}, f(x) = {fxf:F3} apres {trace.Count - 1} pas");
Console.WriteLine($"  Trace (premiers 8): {string.Join(", ", trace.Take(8).Select(v => v.ToString("F3", CultureInfo.InvariantCulture)))}...");

// Maximum global de reference (exploration fine)
double bestGlobal = double.NegativeInfinity, xBestGlobal = 0;
for (double x = domaine.xmin; x <= domaine.xmax; x += 0.01) {
    if (Fitness(x) > bestGlobal) { bestGlobal = Fitness(x); xBestGlobal = x; }
}
Console.WriteLine($"\nMaximum global de reference : x = {xBestGlobal:F3}, f(x) = {bestGlobal:F3}");
Console.WriteLine($"Hill Climbing {(fxf >= bestGlobal - 0.01 ? "ATTEINT" : "MANQUE")} le global (ecart {bestGlobal - fxf:F3}) -> piege par un optimum LOCAL." );
Hill Climbing depuis x0 = -1,500
  -> converge en x = -1,500, f(x) = -0,606 apres 0 pas
  Trace (premiers 8): -1.500...

Maximum global de reference : x = 8,680, f(x) = 0,993
Hill Climbing MANQUE le global (ecart 1,599) -> piege par un optimum LOCAL.

Interprétation : Hill Climbing sur fonction 1D

Sortie obtenue : Hill Climbing converge en quelques pas vers le pic le plus proche de son point de départ — un optimum local, pas le global. C’est le piège fondamental : l’algorithme est glouton, il ne descend jamais, donc il ne peut franchir aucune vallée.

Random-Restart Hill Climbing

L’astuce la plus simple pour échapper aux optima locaux : relancer Hill Climbing plusieurs fois depuis des points de départ aléatoires, et garder le meilleur optimum trouvé. Plus on recommence, plus on couvre le paysage.

// Random-Restart Hill Climbing : n relances depuis des departs aleatoires, on garde le meilleur.
(double x, double fx, int restartsUtilises) RandomRestartHC(
    Func<double,double> f, int nRestarts, double step, double xmin, double xmax, Random rnd) {
    double bestX = 0, bestF = double.NegativeInfinity;
    for (int r = 0; r < nRestarts; r++) {
        double x0 = xmin + rnd.NextDouble() * (xmax - xmin);
        var (xf, fxf, _) = HillClimbing(f, x0, step, xmin, xmax);
        if (fxf > bestF) { bestF = fxf; bestX = xf; }
    }
    return (bestX, bestF, nRestarts);
}

var rrRnd = new Random(7);
Console.WriteLine("Random-Restart Hill Climbing (n = 30 relances) :");
var (xRR, fRR, _) = RandomRestartHC(Fitness, nRestarts: 30, step: 0.15, domaine.xmin, domaine.xmax, rrRnd);
Console.WriteLine($"  -> meilleur optimum trouve : x = {xRR:F3}, f(x) = {fRR:F3}");
Console.WriteLine($"  Comparaison global : {bestGlobal:F3} | Random-Restart {(Math.Abs(fRR - bestGlobal) < 0.01 ? "ATTEINT" : "MANQUE")} le global");
Console.WriteLine("  -> en multipliant les departs, on couvre le paysage et on evade les optima locaux." );
Random-Restart Hill Climbing (n = 30 relances) :
  -> meilleur optimum trouve : x = 2,397, f(x) = 0,993
  Comparaison global : 0,993 | Random-Restart ATTEINT le global
  -> en multipliant les departs, on couvre le paysage et on evade les optima locaux.

Interprétation : Random-Restart

Sortie obtenue : avec assez de relances, Random-Restart finit par tomber dans le bassin d’attraction du maximum global. Coût : n exécutions de Hill Climbing (pas de mémoire entre les relances).

3. Recuit simulé — Simulated Annealing (~10 min)

Inspiration physique

Le recuit simulé (Kirkpatrick, Gelatt & Vecchi, 1983) s’inspire de la métallurgie : en chauffant un métal puis en le refroidissant lentement, on laisse les atomes trouver l’état d’énergie minimale. Transposé à l’optimisation : on accepte, avec une probabilité décroissante, des déplacements qui dégradent la fitness — ce qui permet de franchir les vallées.

La probabilité d’accepter un voisin dégradant est donnée par le critère de Metropolis (1953) :

\[P(\text{accepter pire}) = \exp\!\left(-\frac{\Delta f}{T}\right)\]

où \(\Delta f > 0\) est la dégradation et \(T\) la température. À haute température, on accepte presque tout (exploration) ; à basse température, on devient glouton (exploitation). Le programme de refroidissement (cooling schedule) gouverne la décroissance de \(T\).

// Simulated Annealing sur fonction 1D.
// A chaque iteration : voisin aleatoire, acceptation selon le critere de Metropolis.
(double x, double fx, List<double> traceX) SimulatedAnnealing(
    Func<double,double> f, double x0, double T0, double Tmin, double alpha,
    double step, double xmin, double xmax, Random rnd, int maxIter = 2000) {
    double x = x0, fx = f(x);
    double T = T0;
    var traceX = new List<double> { x };
    for (int it = 0; it < maxIter && T > Tmin; it++) {
        // voisin aleatoire dans [x-step, x+step] clamp au domaine
        double xn = x + (rnd.NextDouble() * 2 - 1) * step;
        xn = Math.Clamp(xn, xmin, xmax);
        double fn = f(xn);
        double delta = fn - fx;   // > 0 = amelioration
        bool accept = delta > 0 || rnd.NextDouble() < Math.Exp(delta / T);
        if (accept) { x = xn; fx = fn; }
        traceX.Add(x);
        T *= alpha;               // refroidissement geometrique
    }
    return (x, fx, traceX);
}

// SA depuis le meme point de depart que Hill Climbing (x0 a gauche, optimum local)
var saRnd = new Random(11);
double x0sa = domaine.xmin + 0.5;
var (xSA, fSA, traceSA) = SimulatedAnnealing(
    Fitness, x0sa, T0: 2.0, Tmin: 0.001, alpha: 0.995, step: 0.5, domaine.xmin, domaine.xmax, saRnd);
Console.WriteLine("Simulated Annealing depuis x0 = {0:F3} (T0=2.0, alpha=0.995) :", x0sa);
Console.WriteLine($"  -> termine en x = {xSA:F3}, f(x) = {fSA:F3}");
Console.WriteLine($"  Trace longueur : {traceSA.Count} iterations");
Console.WriteLine($"  Comparaison global : {bestGlobal:F3} | SA {(Math.Abs(fSA - bestGlobal) < 0.05 ? "ATTEINT" : "proche du")} global");
Console.WriteLine("  -> grace au critere de Metropolis, SA a pu DESCENDRE puis franchir la vallee vers un meilleur pic." );
Simulated Annealing depuis x0 = -1,500 (T0=2.0, alpha=0.995) :
  -> termine en x = 2,404, f(x) = 0,993
  Trace longueur : 1518 iterations
  Comparaison global : 0,993 | SA ATTEINT global
  -> grace au critere de Metropolis, SA a pu DESCENDRE puis franchir la vallee vers un meilleur pic.

Comparaison des programmes de refroidissement

Le choix du programme de refroidissement est déterminant. Trois familles classiques :

Programme Décroissance Comportement
Géométrique T *= alpha Exponentielle Rapide, standard
Linéaire T -= (T0-Tmin)/n Constante Modéré
Logarithmique T = T0/ln(iter+k) Lente Théoriquement optimal (convergence garantie) mais très lent 
// Comparaison de 3 programmes de refroidissement (geometrique, lineaire, logarithmique).
(double fx, int iters) SAWithSchedule(string kind, double x0, double T0, double Tmin,
    double step, double xmin, double xmax, Random rnd, int maxIter = 2000) {
    double x = x0, fx = Fitness(x);
    double T = T0;
    int it = 0;
    for (; it < maxIter; it++) {
        if (kind == "geometrique" && T <= Tmin) break;
        double xn = Math.Clamp(x + (rnd.NextDouble() * 2 - 1) * step, xmin, xmax);
        double fn = Fitness(xn);
        double delta = fn - fx;
        if (delta > 0 || rnd.NextDouble() < Math.Exp(delta / T)) { x = xn; fx = fn; }
        if (kind == "geometrique") T *= 0.997;
        else if (kind == "lineaire") T = T0 - (T0 - Tmin) * it / maxIter;
        else if (kind == "logarithmique") T = T0 / Math.Log(it + 2);
        if (T < Tmin) T = Tmin;
    }
    return (fx, it);
}

Console.WriteLine("Comparaison des programmes de refroidissement (meme x0, 5 essais chacun) :");
foreach (var kind in new[] { "geometrique", "lineaire", "logarithmique" }) {
    double mean = 0; int n = 5;
    for (int i = 0; i < n; i++) {
        var (fx, _) = SAWithSchedule(kind, x0: 0.5, T0: 2.0, Tmin: 0.0005, step: 0.5,
                                     domaine.xmin, domaine.xmax, new Random(100 + i));
        mean += fx;
    }
    mean /= n;
    Console.WriteLine($"  {kind,-15} : f moyen = {mean:F3}");
}
Console.WriteLine($"  (global de reference : {bestGlobal:F3})");
Comparaison des programmes de refroidissement (meme x0, 5 essais chacun) :
  geometrique     : f moyen = 0,990
  lineaire        : f moyen = 0,992
  logarithmique   : f moyen = 0,823
  (global de reference : 0,993)

Interprétation : le paradoxe du logarithmique (théorie vs pratique)

Le résultat est contre-intuitif et c’est la leçon la plus importante du recuit simulé :

  géométrique    : f moyen = 0,990
  linéaire       : f moyen = 0,992   ← meilleur
  logarithmique  : f moyen = 0,823   ← le pire !
  (global de référence : 0,993)

Pourtant, le tableau de la cellule précédente annonçait le logarithmique comme « théoriquement optimal (convergence garantie) ». Comment peut-il être ici le pire des trois ?

  • La garantie est asymptotique : Hajek (1988) prouve que \(T = c / \ln(k)\) assure de trouver l’optimum global… à la limite \(k \to \infty\). Mais cette décroissance est si lente qu’avec un budget fixe de 2000 itérations, la température reste trop élevée trop longtemps : l’algorithme n’exploite jamais (reste en exploration pure), d’où le f moyen médiocre (0,823).
  • Le géométrique et le linéaire sont les bons compromis pratiques : ils décroissent assez vite pour basculer de l’exploration à l’exploitation dans le budget imparti, et atteignent quasi l’optimum (0,990 / 0,992 vs 0,993). Le géométrique T *= alpha est le défaut standard dans l’industrie : un seul paramètre (alpha), décroissance régulière, robuste.

Morale : en optimisation, « théoriquement optimal » $ eq$ « meilleur en pratique ». Un algorithme à convergence garantie mais trop lente est moins utile qu’une heuristique rapide sur un budget de calcul réel. C’est ce déséquilibre qui rend le recuit simulé difficile à régler — et qui motive, dans la section suivante, un problème concret (les N-Reines) où le choix du programme de refroidissement se voit directement dans la qualité de la solution.

Application : les N-Reines

Plaçons N reines sur un échiquier N×N sans qu’aucune ne soit attaquée. C’est le banc d’essai classique des métaheuristiques car le voisinage est naturel (permuter deux reines) et le paysage de conflits est rugueux.

Représentation : un tableau reines[i] = j signifie « la reine de la ligne i est en colonne j ». En imposant une reine par ligne (permutation des colonnes), on élimine tous les conflits de ligne et de colonne — il ne reste que les conflits diagonaux.

// N-Reines : representation par permutation + comptage des conflits diagonaux.
// reines[i] = colonne de la reine de la ligne i. Une reine par ligne (permutation) -> 0 conflit ligne/colonne.
int Conflits(int[] reines) {
    int n = reines.Length, c = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int di = Math.Abs(reines[i] - reines[j]);
            int dj = j - i;  // distance en lignes
            if (di == dj) c++;  // meme diagonale -> attaque
        }
    return c;
}

void AfficherEchiquier(int[] reines) {
    int n = reines.Length;
    for (int i = 0; i < n; i++) {
        var sb = new System.Text.StringBuilder();
        for (int j = 0; j < n; j++) sb.Append(reines[i] == j ? "R " : ". ");
        Console.WriteLine(sb.ToString());
    }
}

// Etat initial aleatoire (permutation)
var rndQ = new Random(42);
int N = 8;
int[] reines0 = Enumerable.Range(0, N).OrderBy(_ => rndQ.Next()).ToArray();
Console.WriteLine($"Echiquier {N}x{N} initial (permutation aleatoire) :");
AfficherEchiquier(reines0);
Console.WriteLine($"Conflits diagonaux initiaux : {Conflits(reines0)}");
Echiquier 8x8 initial (permutation aleatoire) :
. . R . . . . . 
. R . . . . . . 
. . . . R . . . 
. . . . . R . . 
. . . . . . . R 
. . . R . . . . 
R . . . . . . . 
. . . . . . R . 
Conflits diagonaux initiaux : 6

Lecture - l’encodage par permutation reduit le probleme a un seul type de conflit

La sortie de demo rend un echiquier 8x8 aleatoire avec reines[i] = colonne de la reine de la ligne i. Ce choix d’encodage n’est pas anodin : une reine par ligne et par colonne par construction (c’est une permutation), donc il ne peut y avoir aucun conflit ligne ni colonne – seuls les conflits diagonaux restent a eliminer (ici 6 sur le placement initial rendu).

  • La fonction objectif se reduit a un compteur de conflits diagonaux Conflits(reines) : 0 = solution. Le paysage a une hauteur bien definie et l’optimum est facile a reconnaitre (cout nul) – c’est ce qui rend le probleme utilisable comme banc d’essai.
  • Permutation = bijection : l’espace de recherche est exactement n! (pas n^n), ce qui rend la recherche locale bien plus efficace qu’un encodage par cases ou deux reines peuvent partager une ligne.
  • Le but de toutes les metaheuristiques des cellules suivantes est de faire descendre Conflits de sa valeur initiale (6 sur la demo) a 0, malgre les minima locaux du paysage diagonal.

Hill Climbing sur les N-Reines

Voisinage : permuter deux colonnes. Hill Climbing : parmi tous les swaps, prendre celui qui réduit le plus le nombre de conflits. Comme sur la fonction 1D, il peut se bloquer dans un plateau ou un minimum local où aucun swap n’améliore.

// Hill Climbing sur les N-Reines (voisinage = swap de 2 colonnes, steepest-ascent).
(int[] reines, int conflits, int iterations, bool resolu) HCNQueens(int[] reines0, int maxIter = 1000) {
    int n = reines0.Length;
    int[] reines = (int[])reines0.Clone();
    int conflits = Conflits(reines);
    int it = 0;
    while (conflits > 0 && it < maxIter) {
        int bestDelta = 0, bi = -1, bj = -1;
        // chercher le swap qui reduit le plus les conflits
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                (reines[i], reines[j]) = (reines[j], reines[i]);
                int nouv = Conflits(reines);
                int delta = nouv - conflits;
                if (delta < bestDelta) { bestDelta = delta; bi = i; bj = j; }
                (reines[i], reines[j]) = (reines[j], reines[i]);  // annuler
            }
        }
        if (bi == -1) break;  // aucun swap ameliorant -> minimum local / plateau
        (reines[bi], reines[bj]) = (reines[bj], reines[bi]);
        conflits += bestDelta;
        it++;
    }
    return (reines, conflits, it, conflits == 0);
}

var (solHC, confHC, itHC, okHC) = HCNQueens(reines0);
Console.WriteLine($"Hill Climbing sur {N}-Reines :");
Console.WriteLine($"  Conflits finaux : {confHC} ({(okHC ? "RESOLU" : "BLOQUE en minimum local")}) apres {itHC} iterations");
if (okHC) { Console.WriteLine("  Solution :"); AfficherEchiquier(solHC); }
Hill Climbing sur 8-Reines :
  Conflits finaux : 0 (RESOLU) apres 2 iterations
  Solution :
. . . . R . . . 
. R . . . . . . 
. . . R . . . . 
. . . . . R . . 
. . . . . . . R 
. . R . . . . . 
R . . . . . . . 
. . . . . . R .

Recuit simulé sur les N-Reines

Le recuit simulé applique le même critère de Metropolis : il accepte parfois un swap qui augmente les conflits, pour s’extraire d’un plateau. C’est historiquement l’une des premières démonstrations de puissance du recuit simulé.

// Simulated Annealing sur les N-Reines (voisinage = swap aleatoire, acceptation Metropolis).
(int[] reines, int conflits, int iterations, bool resolu) SANQueens(
    int[] reines0, double T0, double alpha, int maxIter, Random rnd) {
    int[] reines = (int[])reines0.Clone();
    int conflits = Conflits(reines);
    double T = T0;
    int it = 0;
    while (conflits > 0 && it < maxIter) {
        int i = rnd.Next(reines.Length), j = rnd.Next(reines.Length);
        if (i == j) { it++; T *= alpha; continue; }
        (reines[i], reines[j]) = (reines[j], reines[i]);
        int nouv = Conflits(reines);
        int delta = nouv - conflits;
        if (delta <= 0 || rnd.NextDouble() < Math.Exp(-delta / T)) {
            conflits = nouv;  // accepte
        } else {
            (reines[i], reines[j]) = (reines[j], reines[i]);  // refuse -> annuler
        }
        it++; T *= alpha;
    }
    return (reines, conflits, it, conflits == 0);
}

var saQRnd = new Random(99);
var (solSA, confSA, itSA, okSA) = SANQueens(reines0, T0: 4.0, alpha: 0.9995, maxIter: 50000, saQRnd);
Console.WriteLine($"Simulated Annealing sur {N}-Reines (T0=4.0) :");
Console.WriteLine($"  Conflits finaux : {confSA} ({(okSA ? "RESOLU" : "echec")}) apres {itSA} iterations");
if (okSA) { Console.WriteLine("  Solution :"); AfficherEchiquier(solSA); }
Simulated Annealing sur 8-Reines (T0=4.0) :
  Conflits finaux : 0 (RESOLU) apres 89 iterations
  Solution :
. R . . . . . . 
. . . . R . . . 
. . . . . . R . 
R . . . . . . . 
. . R . . . . . 
. . . . . . . R 
. . . . . R . . 
. . . R . . . .

Recherche tabou (Tabu Search) sur les N-Reines

La recherche tabou (Glover, 1986) garde une mémoire court-terme des derniers mouvements interdits (la liste tabou). Quand elle est bloquée, elle prend le meilleur mouvement disponible même s’il dégrade — mais s’interdit de revenir immédiatement en arrière grâce à la liste tabou. Cela permet de traverser les plateaux sans boucler.

// Tabu Search sur les N-Reines.
// Liste tabou (taille fixe) des swaps interdits. A chaque pas : prendre le meilleur swap non-tabou
// (meme s'il degrade), l'ajouter a la liste tabou, jusqu'a resolution ou budget epuise.
(int[] reines, int conflits, int iterations, bool resolu) TabuNQueens(
    int[] reines0, int tabuSize, int maxIter, Random rnd) {
    int n = reines0.Length;
    int[] reines = (int[])reines0.Clone();
    int conflits = Conflits(reines);
    var tabou = new Queue<(int,int)>();
    int bestConflits = conflits;
    int[] bestReines = (int[])reines.Clone();
    int it = 0;
    while (conflits > 0 && it < maxIter) {
        // explorer tous les swaps, retenir le meilleur non tabou
        int bestDelta = int.MaxValue, bi = -1, bj = -1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                var cle = (Math.Min(i,j), Math.Max(i,j));
                if (tabou.Contains(cle)) continue;
                (reines[i], reines[j]) = (reines[j], reines[i]);
                int nouv = Conflits(reines);
                int delta = nouv - conflits;
                if (delta < bestDelta) { bestDelta = delta; bi = i; bj = j; }
                (reines[i], reines[j]) = (reines[j], reines[i]);
            }
        }
        if (bi == -1) break;  // tous tabous
        // appliquer le swap retenu (meme s'il degrade)
        (reines[bi], reines[bj]) = (reines[bj], reines[bi]);
        conflits += bestDelta;
        var cleTabou = (Math.Min(bi,bj), Math.Max(bi,bj));
        tabou.Enqueue(cleTabou);
        if (tabou.Count > tabuSize) tabou.Dequeue();
        if (conflits < bestConflits) { bestConflits = conflits; bestReines = (int[])reines.Clone(); }
        it++;
    }
    return (bestReines, bestConflits, it, bestConflits == 0);
}

var tRnd = new Random(2024);
var (solTS, confTS, itTS, okTS) = TabuNQueens(reines0, tabuSize: 10, maxIter: 5000, tRnd);
Console.WriteLine($"Tabu Search sur {N}-Reines (liste tabou = 10) :");
Console.WriteLine($"  Conflits finaux : {confTS} ({(okTS ? "RESOLU" : "echec")}) apres {itTS} iterations");
if (okTS) { Console.WriteLine("  Solution :"); AfficherEchiquier(solTS); }
Tabu Search sur 8-Reines (liste tabou = 10) :
  Conflits finaux : 0 (RESOLU) apres 2 iterations
  Solution :
. . . . R . . . 
. R . . . . . . 
. . . R . . . . 
. . . . . R . . 
. . . . . . . R 
. . R . . . . . 
R . . . . . . . 
. . . . . . R .

Comparaison des trois algorithmes sur N-Reines

Lançons les trois algorithmes sur plusieurs essais et mesurons le taux de succès (proportion d’essais qui atteignent 0 conflit). C’est le critère empirique qui distingue les métaheuristiques mieux que le coût d’un seul run.

// Benchmark : N essais aleatoires pour chaque algorithme, taux de succes.
void Benchmark(int n, int essais, int seedBase) {
    int okHC = 0, okSA = 0, okTS = 0;
    int itHC = 0, itSA = 0, itTS = 0;
    for (int e = 0; e < essais; e++) {
        var rnd = new Random(seedBase + e);
        int[] init = Enumerable.Range(0, n).OrderBy(_ => rnd.Next()).ToArray();
        var (_, _, _, h) = HCNQueens((int[])init.Clone(), maxIter: 500);
        if (h) okHC++;
        var (_, _, _, s) = SANQueens((int[])init.Clone(), 4.0, 0.9995, 20000, new Random(seedBase*7 + e));
        if (s) okSA++;
        var (_, _, _, t) = TabuNQueens((int[])init.Clone(), 10, 3000, new Random(seedBase*13 + e));
        if (t) okTS++;
    }
    Console.WriteLine($"Benchmark {n}-Reines sur {essais} essais :");
    Console.WriteLine($"  Hill Climbing       : {okHC}/{essais} reussis ({100.0*okHC/essais:F0}%)");
    Console.WriteLine($"  Simulated Annealing : {okSA}/{essais} reussis ({100.0*okSA/essais:F0}%)");
    Console.WriteLine($"  Tabu Search         : {okTS}/{essais} reussis ({100.0*okTS/essais:F0}%)");
}

Benchmark(n: 8, essais: 15, seedBase: 500);
Console.WriteLine();
Benchmark(n: 20, essais: 10, seedBase: 700);
Benchmark 8-Reines sur 15 essais :
  Hill Climbing       : 7/15 reussis (47%)
  Simulated Annealing : 15/15 reussis (100%)
  Tabu Search         : 15/15 reussis (100%)

Benchmark 20-Reines sur 10 essais :
  Hill Climbing       : 4/10 reussis (40%)
  Simulated Annealing : 10/10 reussis (100%)
  Tabu Search         : 10/10 reussis (100%)

Lecture - le benchmark tranche : HC se coince, SA et Tabu sortent toujours

Les tableaux rendus par Benchmark sont la lecon centrale du notebook. Sur 8-Reines (15 essais), Hill Climbing ne reussit que 7/15 (47 %) quand Simulated Annealing et Tabu Search reussissent 15/15 (100 %). Sur 20-Reines (10 essais), la tendance s’accentue : 4/10 (40 %) pour HC contre 10/10 (100 %) pour les deux autres.

  • HC est glouton : il ne monte jamais un voisin de cout strictement superieur, donc il reste bloque dans le premier minimum local rencontre – et les paysages de conflits diagonaux des N-Reines en sont pleins. La chute de 47 % a 40 % quand N passe de 8 a 20 montre que plus le probleme est grand, plus HC se coince (les minima locaux se multiplient).
  • SA echappe aux optima locaux via la temperature (elle accepte des degradations transitoires) ; Tabu via sa memoire (elle interdit de rejouer les recents coups defavorables). Les deux atteignent 100 % dans les deux tailles.
  • Warning CS0219 : itHC/itSA/itTS sont comptees mais jamais utilisees – un reliquat de code (compteur d’iterations dont l’affichage a ete retire). Sans consequence sur les resultats, et le code n’est pas modifie ici (enrichissement markdown-only).

6. Exercices

Les exercices sont à compléter : les squelettes s’exécutent sans erreur (ils retournent un résultat neutre) — à vous d’implémenter la logique demandée.

Exercice 1 : Random-Restart adaptatif

Énoncé : Modifiez RandomRestartHC pour qu’il s’arrête dès qu’un optimum suffisamment proche du global est trouvé (seuil passé en paramètre), plutôt que de faire un nombre fixe de relances. Comparez le nombre moyen de relances utilisées.

// Exercice 1 : Random-Restart adaptatif avec seuil d'arret.
// TODO etudiant : implementer la variante qui s'arrete des que f(x) >= seuil.
(double x, double fx, int restarts) RandomRestartHCAdaptatif(
    Func<double,double> f, int maxRestarts, double seuil, double step,
    double xmin, double xmax, Random rnd) {
    // Indice : boucler sur les relances, appeler HillClimbing, sortir des que fxf >= seuil.
    // Etape 1 : initialiser bestX, bestF, compte.
    // Etape 2 : pour chaque relance, tirer x0, lancer HillClimbing, mettre a jour le meilleur.
    // Etape 3 : si bestF >= seuil, retourner immediatement (avec le compte de relances utilisees).
    double bestX = 0, bestF = double.NegativeInfinity;
    int relances = 0;
    // ... votre code ici ...
    return (bestX, bestF, relances);  // TODO : remplacer par la vraie logique
}

// Test
var res = RandomRestartHCAdaptatif(Fitness, maxRestarts: 100, seuil: bestGlobal - 0.02,
                                   step: 0.15, domaine.xmin, domaine.xmax, new Random(3));
Console.WriteLine($"(Exercice a completer) — relances utilisees : {res.restarts}, f(x) = {res.fx:F3}");
(Exercice a completer) — relances utilisees : 0, f(x) = -∞

Lecture - Exercice 1 : Random-Restart adaptatif

L’exercice demande d’arreter les relances des qu’un seuil de qualite est atteint, plutot que de toujours bruler un nombre fixe de tentatives. La structure attendue garde la boucle de Random-Restart Hill Climbing mais ajoute un break quand le cout retourne tombe sous le seuil – la vraie question de calibration est le compromis qualite visee vs budget de relances. Le stub rend pass, donc l’exercice est a completer : ajouter la condition d’arret puis relire la sortie – le taux de reussite doit montrer que le seuil economise des relances sans perdre de solutions.

Exercice 2 : Tabu Search avec mémoire à long terme

Énoncé : Ajoutez au TabuNQueens une mémoire à long terme (fréquence de visite de chaque swap) qui pénalise les swaps trop souvent visités, pour forcer la diversification. Observez si le taux de succès s’améliore sur N = 20.

// Exercice 2 : Tabu Search avec memoire a long terme (diversification par frequence).
// TODO etudiant : penaliser les swaps frequemment visites.
(int[] reines, int conflits, bool resolu) TabuNQueensDiversifie(int[] reines0, int maxIter, Random rnd) {
    // Indice : maintenir un Dictionary<(int,int),int> frequence.
    // Etape 1 : lors du choix du swap, ajouter un cout = alpha * frequence[swap] au delta.
    // Etape 2 : apres application du swap, incrementer sa frequence.
    int n = reines0.Length;
    int[] reines = (int[])reines0.Clone();
    int conflits = Conflits(reines);
    var freq = new Dictionary<(int,int), int>();
    // ... votre code ici ...
    return (reines, conflits, conflits == 0);
}

// Test (placeholder neutre)
var ex2 = TabuNQueensDiversifie(reines0, maxIter: 100, new Random(5));
Console.WriteLine($"(Exercice a completer) — conflits finaux : {ex2.conflits}");
(Exercice a completer) — conflits finaux : 6

Lecture - Exercice 2 : memoire a long terme

La recherche tabou de la section 5 utilise une liste tabou a taille fixe. L’exercice etend la memoire (diversification : interdire aussi des attributs ou des mouvements “oublies” depuis longtemps, pas seulement les tout derniers). L’idee est une aspiration qui pousse la recherche dans des regions inexplorees. Sur le banc N-Reines, une memoire longue sert surtout quand la liste courte recompute un optimum local deja vu : comparez le taux de reussite a celui de la section 5 pour le mesurer.

Exercice 3 : Comparer trois programmes de refroidissement sur les N-Reines

Énoncé : Adaptez la comparaison des programmes de refroidissement (géométrique, linéaire, logarithmique) au problème des N-Reines. Lequel donne le meilleur taux de succès sur N = 20, à budget d’itérations égal ?

// Exercice 3 : Comparaison des programmes de refroidissement sur N-Reines.
// TODO etudiant : reprendre SANQueens, parameteriser le programme de refroidissement, benchmarker.
void ComparerRefroidissementsNReines(int n, int essais) {
    // Indice : ajouter un parametre 'kind' a SANQueens comme dans SAWithSchedule.
    // Etape 1 : geometrique T *= alpha ; lineaire T = T0 - (T0-Tmin)*it/maxIter ; log T = T0/ln(it+2).
    // Etape 2 : mesurer le taux de succes de chacun sur 'essais' essais.
    Console.WriteLine($"(Exercice a completer) — comparaison sur {n}-Reines, {essais} essais");
}

ComparerRefroidissementsNReines(n: 20, essais: 10);
(Exercice a completer) — comparaison sur 20-Reines, 10 essais

Lecture - Exercice 3 : trois programmes de refroidissement

La section 3 comparait les programmes de refroidissement sur la fonction 1D (et le paradoxe du logarithmique). L’exercice vous demande de refaire cette comparaison sur les N-Reines : le meilleur programme sur une fonction 1D n’est pas forcement le meilleur sur un paysage de permutations. Mesurez le taux de reussite et le nombre d’iterations a 0 conflit pour chaque programme, puis confrontez au verdict de la section 3 – c’est le “No Free Lunch” des schemas de temperature.

7. Résumé

Concepts clés

Concept Définition
Paysage de fitness Espace des solutions où l’altitude = qualité ; la recherche locale s’y déplace de voisin en voisin
Hill Climbing Greedy : prend le meilleur voisin améliorant ; piège dans les optima locaux
Random-Restart Relance Hill Climbing depuis plusieurs départs ; évade par couverture
Critère de Metropolis P(accepter pire) = exp(-Δf/T) ; cœur du recuit simulé
Recuit simulé Accepte des dégradations décroissantes (T baisse) ; franchit les vallées
Liste tabou Mémoire court-terme des mouvements interdits ; traverse les plateaux sans boucler
Exploration vs exploitation Le compromis fondamental : chercher ailleurs (explorer) vs affiner le courant (exploiter)

Leçons empiriques (benchmark N-Reines)

  • Hill Climbing est rapide mais plafonne : bloqué dans les minima locaux dès N modéré.
  • Simulated Annealing et Tabu Search atteignent de bien meilleurs taux de succès grâce à leur capacité à traverser les plateaux — l’un par l’acceptation probabiliste (Metropolis), l’autre par la mémoire (liste tabou).
  • Aucun algorithme ne domine partout : le no-free-lunch (Wolpert & Macready, 1997) — c’est le fil rouge du notebook Search-11 (Métaheuristiques).

Conclusion et perspectives

Ce jumeau C# a couvert les trois familles fondamentales de recherche locale. Le véritable enseignement, au-delà du catalogue, est un réflexe d’ingénieur : chaque métaheuristique négocie différemment le compromis exploration vs exploitation, et le choix dépend de la structure du paysage (rugueux, plat, à optima multiples). Hill Climbing suffit sur un paysage monotone ; le recuit simulé s’impose quand les vallées sont franchissables ; Tabu excelle sur les plateaux.

La suite naturelle : les algorithmes génétiques (Search-5) généralisent l’exploration à une population entière, et le notebook Search-11 confronte ces métaheuristiques (PSO, ABC, recuit) sur des benchmarks communs.

Navigation : << Recherche informée (Search-3) | Index série Search | Algorithmes génétiques (Search-5) >>

Port C# / .NET 9.0 du notebook Python Search-04-LocalSearch — Epic #4956 (parité .NET ⇄ Python des séries).

Retour au sommet