MGS-16-AlgorithmSelection : Sélectionner le bon optimiseur selon le paysage

Série : Métaheuristiques & GeneticSharp (16/16) Durée estimée : 70 minutes Prérequis : MGS-10-CenterBias (portfolio de 8 optimiseurs, banc center-bias), MGS-15-LandscapeAnalysis (FDC, autocorrélation, neutralité)

Objectifs

Comprendre le théorème No-Free-Lunch (Wolpert & Macready, 1997) : aucun optimiseur ne domine universellement
Mesurer les caractéristiques de paysage (features de MGS-15) pour décrire un problème avant de l’optimiser
Construire un sélecteur d’algorithmes (cadre de Rice, 1976) : features → recommandation d’optimiseur
Valider la sélection sur un paysage inconnu (Rosenbrock) et discuter honnêtement ses limites

Navigation

Précédent	Suivant
MGS-15-LandscapeAnalysis	(fin de la série)

Capstone de la Partie 4 : ce notebook synthétise deux fils — les métriques de paysage (MGS-15) et le portfolio d’optimiseurs (MGS-10) — pour répondre à la question qui clôt la théorie des métaheuristiques : « face à un nouveau problème, quel optimiseur choisir ? »

1. Le théorème No-Free-Lunch — pourquoi aucun optimiseur ne gagne partout

Wolpert et Macready (1997) ont démontré un résultat fondamental : en moyennant sur toutes les fonctions objectives possibles, tous les algorithmes d’optimisation (déterministes ou aléatoires) ont la même performance. Autrement dit, tout ce qu’un algorithme gagne sur une famille de problèmes, il le perd exactement sur les autres.

Conséquence pratique : il n’existe pas d’optimiseur universellement supérieur. Le choix d’un algorithme doit être informé par la structure du problème.

Le tableau de l’oracle mesuré dans MGS-10 l’illustre crûment : sur le banc center-bias (fonctions déplacées, dim 5, budget 5000 évaluations), le regret (delta objectif déplacé − centré) varie dramatiquement selon le couple optimiseur × fonction :

	Sphere	Rastrigin	Ackley
DE	0,000	−6,442	0,000
BBPSO	0,000	−4,975	0,000
FBI	0,000	0,001	0,002
GA	0,005	−0,793	0,419
WOA	0,002	10,592	4,358
SA	−0,000	4,977	0,001

DE et BBPSO excellent sur Rastrigin (fortement multimodal), là où WOA s’y effondre (delta +10,6) et SA aussi (+4,98). Aucun optimiseur ne domine : le gagnant dépend du paysage. C’est précisément cette dépendance que nous allons apprendre à exploiter.

2. Le cadre de Rice (1976) — sélection d’algorithme comme mapping

Rice (1976) a formalisé la sélection d’algorithme comme un problème à trois éléments :

\[\text{sélection} : \quad \underbrace{f(\text{problème})}_{\text{caractéristiques (features)}} \;\longrightarrow\; \underbrace{a \in \mathcal{A}}_{\text{algorithme du portfolio}} \;\longrightarrow\; \underbrace{p(\text{problème}, a)}_{\text{performance}}\]

Features \(f\) : descripteurs bon marché du problème (calcules sans optimiser) — ici, les métriques de paysage de MGS-15 : FDC, autocorrélation \(\rho_1\), neutralité.
Portfolio \(\mathcal{A}\) : l’ensemble d’optimiseurs candidats (les 8 de MGS-10).
Performance \(p\) : mesurée par l’oracle (le regret center-bias de MGS-10).
Sélecteur : une règle (ici heuristique) qui, étant donné les features, recommande l’algorithme.

L’idée maîtresse : si les features sont informatives, on peut prédire le bon optimiseur sans avoir à tous les exécuter. Nous allons (1) mesurer les features de nos trois paysages connus, (2) construire une règle de sélection, puis (3) la tester sur un quatrième paysage jamais vu (Rosenbrock).

// Câblage : DLLs MetaGeneticSharp + GeneticSharp + Extensions (portfolio + oracle + paysage).
// Prérequis de build (depuis la racine du fork) : dotnet build ../MetaGeneticSharp/MetaGeneticSharp.sln
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Domain/bin/Debug/net9.0/GeneticSharp.Infrastructure.Framework.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Domain/bin/Debug/net9.0/GeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Domain/bin/Debug/net9.0/MetaGeneticSharp.Infrastructure.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Domain/bin/Debug/net9.0/MetaGeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Extensions.dll"

using MetaGeneticSharp;
using GeneticSharp;
using System;
using System.Collections.Generic;
using System.Linq;

Console.WriteLine("DLLs chargees. CenterBiasBenchmark : " + typeof(CenterBiasBenchmark).Name);
Console.WriteLine("  KnownFunctionsBounds : " + typeof(KnownFunctionsBounds).Name);

DLLs chargees. CenterBiasBenchmark : CenterBiasBenchmark
  KnownFunctionsBounds : KnownFunctionsBounds

4.1 Chromosome continu + métriques de paysage

On reprend verbatim l’assistant DoubleArrayChromosome et les métriques de paysage de MGS-15 : coefficient de Pearson, FDC (Fitness Distance Correlation), marche aléatoire de Weinberger (1990) pour l’autocorrélation, et neutralité.

// DoubleArrayChromosome : chromosome minimal stockant des gènes double nus (MGS-6/10/15).
public class DoubleArrayChromosome : ChromosomeBase
{
    private readonly double _min; private readonly double _max;
    public DoubleArrayChromosome(double[] values, double min, double max) : base(values.Length)
    { _min = min; _max = max; for (int i = 0; i < values.Length; i++) ReplaceGene(i, new Gene(values[i])); }
    public override IChromosome CreateNew()
    {
        var rand = RandomizationProvider.Current; int n = Length; var v = new double[n];
        for (int i = 0; i < n; i++) v[i] = rand.GetDouble(_min, _max);
        return new DoubleArrayChromosome(v, _min, _max);
    }
    public override Gene GenerateGene(int geneIndex) => new Gene(RandomizationProvider.Current.GetDouble(_min, _max));
    public double[] GetDoubleValues() => GetGenes().Select(g => (double)g.Value).ToArray();
}

// --- Métriques de paysage (MGS-15 verbatim) ---
public record Sample(double[] Point, double RawFitness, double DistToOptimum);

double Pearson(double[] xs, double[] ys)
{
    int n = xs.Length; double mx = xs.Average(), my = ys.Average(); double num = 0, sx = 0, sy = 0;
    for (int i = 0; i < n; i++) { double dx = xs[i] - mx, dy = ys[i] - my; num += dx * dy; sx += dx * dx; sy += dy * dy; }
    return num / Math.Sqrt(sx * sy);
}

// FDC = Pearson(rawFitness, distance à l'optimum). |FDC| -> 1 = paysage globalement informatif.
double Fdc(Sample[] s) => Pearson(s.Select(t => t.RawFitness).ToArray(), s.Select(t => t.DistToOptimum).ToArray());

// Échantillonnage uniforme du paysage : n points dans [lo,hi]^dim, optimum supposé à l'origine.
Sample[] SampleLandscape(IFitness f, int dim, int n, int seed = 42)
{
    var (lo, hi) = KnownFunctionsBounds.For(f.GetType()); var rand = new Random(seed); var arr = new Sample[n];
    for (int i = 0; i < n; i++)
    {
        double[] x = new double[dim]; double d = 0;
        for (int j = 0; j < dim; j++) { x[j] = lo + rand.NextDouble() * (hi - lo); d += x[j] * x[j]; }
        double fit = -f.Evaluate(new DoubleArrayChromosome(x, lo, hi));   // vraie fitness (minimisation)
        arr[i] = new Sample(x, fit, Math.Sqrt(d));
    }
    return arr;
}

// Marche aléatoire (Weinberger 1990) : amplitude relative eps, rebond miroir aux bords.
double[] RandomWalk(IFitness f, int dim, int steps, double epsRel, int seed = 7)
{
    var (lo, hi) = KnownFunctionsBounds.For(f.GetType()); var rand = new Random(seed);
    double[] x = new double[dim];
    for (int j = 0; j < dim; j++) x[j] = lo + rand.NextDouble() * (hi - lo);
    double eps = epsRel * (hi - lo);
    var fits = new double[steps];
    for (int t = 0; t < steps; t++)
    {
        double[] dir = new double[dim]; double norm = 0;
        for (int j = 0; j < dim; j++) { dir[j] = rand.NextDouble() * 2 - 1; norm += dir[j] * dir[j]; }
        norm = Math.Sqrt(norm); if (norm < 1e-12) norm = 1;
        for (int j = 0; j < dim; j++)
        {
            x[j] += eps * dir[j] / norm;
            if (x[j] < lo) x[j] = lo + (lo - x[j]);
            if (x[j] > hi) x[j] = hi - (x[j] - hi);
        }
        fits[t] = -f.Evaluate(new DoubleArrayChromosome(x, lo, hi));
    }
    return fits;
}

// Autocorrélation de lag 1 : Pearson entre fitness consécutives le long de la marche.
double AutocorrLag1(double[] fits)
{
    int n = fits.Length - 1; double[] a = new double[n], b = new double[n];
    for (int i = 0; i < n; i++) { a[i] = fits[i]; b[i] = fits[i + 1]; }
    return Pearson(a, b);
}

// Neutralité : proportion de pas où |delta fitness| < tol (fraction relative de l'étendue).
double NeutralRatio(double[] fits, double tolRel)
{
    double fmin = fits.Min(), fmax = fits.Max();
    double tol = tolRel * (fmax - fmin); if (tol < 1e-15) tol = 1e-15;
    int neutral = 0;
    for (int i = 1; i < fits.Length; i++) if (Math.Abs(fits[i] - fits[i - 1]) < tol) neutral++;
    return (double)neutral / (fits.Length - 1);
}

Console.WriteLine("DoubleArrayChromosome + métriques paysage (Fdc, RandomWalk, AutocorrLag1, NeutralRatio) definis.");

DoubleArrayChromosome + métriques paysage (Fdc, RandomWalk, AutocorrLag1, NeutralRatio) definis.

5.1 Le portfolio de 8 optimiseurs (MGS-10)

On reconstitue le portfolio de MGS-10 : un délégué Optimizer uniforme qui reçoit une requête (fitness, bornes, dimension, budget d'évaluations) et retourne la meilleure fitness trouvée. Sept métaheuristiques composées (GA, WOA, EO, FBI, DE, BBPSO, SA) plus un contrôle par recherche aléatoire (Random).

const int PopSize = 50;   // taille de population
const int NFE = 5000;     // budget d'évaluations partagé (règle mealpy) -> generations = 100

IMetaHeuristic BuildGA(int g)    => new DefaultMetaHeuristic();
IMetaHeuristic BuildWOA(int g)   => MetaHeuristicsService.CreateMetaHeuristicByName("WhaleOptimisation",           maxGenerations: g, populationSize: PopSize);
IMetaHeuristic BuildEO(int g)    => MetaHeuristicsService.CreateMetaHeuristicByName("EquilibriumOptimizer",       maxGenerations: g, populationSize: PopSize);
IMetaHeuristic BuildFBI(int g)   => MetaHeuristicsService.CreateMetaHeuristicByName("ForensicBasedInvestigation", maxGenerations: g, populationSize: PopSize);
IMetaHeuristic BuildDE(int g)    => MetaHeuristicsService.CreateMetaHeuristicByName("DifferentialEvolution",       maxGenerations: g, populationSize: PopSize);
IMetaHeuristic BuildBBPSO(int g) => MetaHeuristicsService.CreateMetaHeuristicByName("BareBonesParticleSwarm",   maxGenerations: g, populationSize: PopSize);
IMetaHeuristic BuildSA(int g)    => MetaHeuristicsService.CreateMetaHeuristicByName("SimulatedAnnealing",         maxGenerations: g, populationSize: PopSize);

Optimizer MakeOptimizer(Func<int, IMetaHeuristic> buildMh)
{
    return (Optimizer)((req) =>
    {
        int gens = Math.Max(1, req.Evaluations / PopSize);
        var (min, max) = req.Bounds; double mid = 0.5 * (min + max);
        var adam = new DoubleArrayChromosome(Enumerable.Repeat(mid, req.Dimension).ToArray(), min, max);
        var pop = new MetaPopulation(PopSize, PopSize, adam);
        var ga = new MetaGeneticAlgorithm(pop, req.Fitness, new EliteSelection(), new UniformCrossover(0.5f), new UniformMutation(true), buildMh(gens));
        ga.Termination = new GenerationNumberTermination(gens); ga.Start();
        return ga.BestChromosome.Fitness ?? double.NegativeInfinity;
    });
}

var rs = new RandomSearchOptimizer(seed: 7);
Optimizer RandomOptimizer = (Optimizer)((req) => rs.Run(req));

var Portfolio = new (string Name, Optimizer Opt)[]
{
    ("Random", RandomOptimizer),
    ("GA",     MakeOptimizer(BuildGA)),
    ("WOA",    MakeOptimizer(BuildWOA)),
    ("EO",     MakeOptimizer(BuildEO)),
    ("FBI",    MakeOptimizer(BuildFBI)),
    ("DE",     MakeOptimizer(BuildDE)),
    ("BBPSO",  MakeOptimizer(BuildBBPSO)),
    ("SA",     MakeOptimizer(BuildSA)),
};

// Smoke test : GA sur Sphere centrée (l'optimum 0 doit être approché).
FastRandomRandomization.ResetSeed(42);
double smoke = MakeOptimizer(BuildGA)(new OptimizerRequest(new SphereFitness(), KnownFunctionsBounds.For(typeof(SphereFitness)), 5, NFE));
Console.WriteLine("Smoke GA/Sphere centree : objectif = " + (-smoke).ToString("G4") + "  (proche de 0 = OK)");
Console.WriteLine("Portfolio pret : " + Portfolio.Length + " optimiseurs.");

Smoke GA/Sphere centree : objectif = 0,008247  (proche de 0 = OK)
Portfolio pret : 8 optimiseurs.

6. L’oracle — mesurer la performance réelle (ground truth)

Le banc CenterBiasBenchmark exécute chaque optimiseur en configuration centrée (optimum à l’origine) puis déplacée (optimum relogé d’un vecteur aléatoire d’amplitude 2). Le delta objectifDéplacé − objectifCentré mesure le regret : un optimiseur robuste garde un delta faible (idéalement négatif). C’est notre vérité terrain — la performance mesurée, pas prédite.

var budget = new EvaluationBudget(NFE);
double shiftMag = 2.0; int masterSeed = 42; int dim = 5;

var Problems = new List<(IFitness fitness, int dimension)>
{
    (new SphereFitness(),    dim),
    (new RastriginFitness(), dim),
    (new AckleyFitness(),    dim),
};

var rows = new List<(string Opt, CenterBiasResult R)>();
Console.WriteLine(String.Format("{0,-8} {1,-10} {2,12} {3,12} {4,10}", "Opt", "Fonction", "Centré", "Déplacé", "Delta"));
Console.WriteLine(new String('-', 56));
foreach (var (optName, opt) in Portfolio)
{
    FastRandomRandomization.ResetSeed(masterSeed);
    var results = CenterBiasBenchmark.RunSuite(Problems, budget, opt, shiftMag, masterSeed);
    foreach (var r in results)
    {
        rows.Add((optName, r));
        Console.WriteLine(String.Format("{0,-8} {1,-10} {2,12:F3} {3,12:F3} {4,10:F3}",
            optName, r.Function, r.CenteredObjective, r.ShiftedObjective, r.Delta));
    }
}
Console.WriteLine("\n--- Oracle terminé : " + Portfolio.Length + " optimiseurs × " + Problems.Count + " fonctions ---");

Opt      Fonction         Centré      Déplacé      Delta
--------------------------------------------------------
Random   SphereFitness        0,641        0,845      0,205
Random   RastriginFitness       19,404       27,340      7,936
Random   AckleyFitness        8,609        8,727      0,117
GA       SphereFitness        0,008        0,014      0,005
GA       RastriginFitness        1,224        0,431     -0,793
GA       AckleyFitness        1,873        2,292      0,419
WOA      SphereFitness        0,000        0,021      0,021
WOA      RastriginFitness       12,511        1,099    -11,413
WOA      AckleyFitness        0,000        4,193      4,193
EO       SphereFitness        0,000        0,000      0,000
EO       RastriginFitness        3,980        1,990     -1,990
EO       AckleyFitness        0,000        0,000      0,000
FBI      SphereFitness        0,000        0,000      0,000
FBI      RastriginFitness        0,000        1,990      1,990
FBI      AckleyFitness        0,000        0,000      0,000
DE       SphereFitness        0,000        0,000     -0,000
DE       RastriginFitness        2,396        1,110     -1,287
DE       AckleyFitness        0,000        0,000     -0,000
BBPSO    SphereFitness        0,000        0,000     -0,000
BBPSO    RastriginFitness       11,939        4,975     -6,965
BBPSO    AckleyFitness        0,000        0,000      0,000
SA       SphereFitness        0,000        0,000     -0,000
SA       RastriginFitness        3,010        4,002      0,992
SA       AckleyFitness        0,003        0,005      0,002

--- Oracle terminé : 8 optimiseurs × 3 fonctions ---

7. Interprétation — la carte des forces et faiblesses

Le tableau ci-dessus confirme le No-Free-Lunch en acte. Agrégeons par optimiseur pour faire ressortir les profils — en distinguant delta moyen et pire-cas :

// Agrégation : delta moyen ET pire-cas (max sur les 3 fonctions). Le pire-cas est le signal
// de robustesse le plus fiable : un optimiseur robuste n'a AUCUNE fonction où il s'effondre.
// (Le delta moyen est bruité par Rastrigin — cf MGS-10 : Random lui-même y affiche +7,9.)
Console.WriteLine(String.Format("{0,-8} {1,10} {2,10} {3,-34}", "Opt", "Delta moy", "Pire-cas", "Profil (selon pire-cas)"));
Console.WriteLine(new String('-', 68));
foreach (var g in rows.GroupBy(r => r.Opt).OrderBy(g => g.Max(x => x.R.Delta)))
{
    double mean = g.Average(x => x.R.Delta);
    double worst = g.Max(x => x.R.Delta);
    string profil = worst <  0.05 ? "robuste (aucun effondrement)"
                   : worst <  1.50 ? "correct"
                   : worst <  3.00 ? "fragile (1 fonction casse)"
                   :                  "a eviter (effondrement net)";
    Console.WriteLine(String.Format("{0,-8} {1,10:F3} {2,10:F3} {3,-34}", g.Key, mean, worst, profil));
}

Opt       Delta moy   Pire-cas Profil (selon pire-cas)           
--------------------------------------------------------------------
DE           -0,429     -0,000 robuste (aucun effondrement)      
BBPSO        -2,322      0,000 robuste (aucun effondrement)      
EO           -0,663      0,000 robuste (aucun effondrement)      
GA           -0,123      0,419 correct                           
SA            0,331      0,992 correct                           
FBI           0,663      1,990 fragile (1 fonction casse)        
WOA          -2,400      4,193 a eviter (effondrement net)       
Random        2,753      7,936 a eviter (effondrement net)

Lecture : classons par le pire-cas (le plus mauvais des trois deltas) plutôt que par la moyenne. La moyenne est bruitée par Rastrigin — MGS-10 l’a établi : à NFE = 5000 le tirage tombe dans un optimum local différent selon la graine, et Random lui-même y affiche un delta élevé (+7,9). Le pire-cas, lui, isole les effondrements nets : DE, BBPSO et EO ne s’effondrent sur aucune fonction (pire-cas ≈ 0, robustes), tandis que WOA s’effondre sur Ackley (+4,19 — exactement le biais central mesuré en MGS-10) et Random sur Rastrigin (+7,9, contrôle non biaisé mais faible). C’est cette structure par fonction — et non l’étiquette de l’algorithme — que les features de paysage doivent capturer.

8. Caractériser un paysage avant de l’optimiser

Mesurons maintenant les features des trois paysages — sans les optimiser, juste en les échantillonnant (MGS-15). C’est l’entrée du sélecteur de Rice : un descripteur bon marché du problème.

// Résumé des features d'un paysage (le record que MGS-15 n'avait pas formalisé).
public record LandscapeReport(string Name, double Fdc, double Rho1, double CorrLen, double Neutrality);

LandscapeReport Measure(IFitness f, int dim)
{
    var s = SampleLandscape(f, dim, 600);
    double fdc = Fdc(s);
    var fits = RandomWalk(f, dim, 5000, 0.05);
    double rho1 = AutocorrLag1(fits);
    double corrLen = (rho1 > 0 && rho1 < 1) ? -1.0 / Math.Log(rho1) : double.NaN;
    double neu = NeutralRatio(fits, 0.001);
    return new LandscapeReport(f.GetType().Name.Replace("Fitness", ""), fdc, rho1, corrLen, neu);
}

var Features = new List<LandscapeReport>();
Console.WriteLine(String.Format("{0,-10} {1,8} {2,8} {3,10} {4,10}", "Paysage", "FDC", "ρ₁", "L_corr", "Neutre %"));
Console.WriteLine(new String('-', 50));
foreach (var (fit, _) in Problems)
{
    var rep = Measure(fit, dim);
    Features.Add(rep);
    Console.WriteLine(String.Format("{0,-10} {1,8:F3} {2,8:F3} {3,10:F2} {4,10:F2}",
        rep.Name, rep.Fdc, rep.Rho1, rep.CorrLen, rep.Neutrality * 100));
}

Paysage         FDC       ρ₁     L_corr   Neutre %
--------------------------------------------------
Sphere        0,987    0,982      55,79       2,28
Rastrigin     0,737    0,623       2,11       0,64
Ackley        0,739    0,587       1,88       0,92

Lecture des features : - FDC (Fitness Distance Correlation) proche de 1 → la fitness brute indique bien la direction de l’optimum (paysage informative, facile a priori). - ρ₁ (autocorrélation lag 1) proche de 1 → paysage lisse, voisins corrélés (le gradient est du signal, pas du bruit). Proche de 0 → paysage bruité (chaque pas découvre un nouveau régime). - L_corr = −1/ln(ρ₁) : longueur de corrélation (échelle typique d’une structure locale). - Neutralité : sur ces benchmarks continus différentiables, elle est quasi nulle (attendu — cf. MGS-15).

On voit déjà se dessiner la structure : Sphere est lisse et bien corrélée (FDC et ρ₁ élevés), Rastrigin est bruitée (ρ₁ bas, beaucoup de minima locaux), Ackley intermédiaire.

9. Le sélecteur de Rice — des features à la recommandation

Construisons maintenant le cœur du notebook : une règle heuristique qui, étant donné un LandscapeReport, recommande les optimiseurs adaptés et signale ceux à éviter. C’est le mapping du cadre de Rice — délibérément simple et explicable (pas un modèle de ML appris, une expertise encodée).

// Sélecteur heuristique (Rice 1976) : règle lisible basée sur les features.
//   - FDC élevé + ρ₁ élevé  => paysage lisse/informatif : un GA simple suffit (convergence locale).
//   - ρ₁ bas (< 0.5)        => paysage bruité/multimodal : il faut forte diversité => DE/BBPSO.
//   - FDC moyen (< 0.8)     => multimodal : éviter WOA (convergence agressive, s'y piège).
(string top, string avoid, string raison) Select(LandscapeReport r)
{
    if (r.Rho1 < 0.5)
        return ("DE, BBPSO", "WOA, SA",
            "ρ₁ bas => paysage bruité (minima locaux nombreux) : diversité forte requise, les optimiseurs à convergence agressive s'y piègent.");
    if (r.Fdc > 0.85)
        return ("GA, DE", "(aucun critique)",
            "FDC élevé + paysage corrélé => la fitness indique l'optimum : un GA simple converge bien, peu de pièges.");
    return ("DE, BBPSO, FBI", "WOA",
        "FDC modéré/multimodal => éviter WOA (effondrement mesuré sur Ackley), préférer les optimiseurs robustes.");
}

Console.WriteLine(String.Format("{0,-10} {1,-16} {2,-12} {3}", "Paysage", "Recommandé", "À éviter", "Raison"));
Console.WriteLine(new String('-', 96));
foreach (var r in Features)
{
    var (top, avoid, raison) = Select(r);
    Console.WriteLine(String.Format("{0,-10} {1,-16} {2,-12} {3}", r.Name, top, avoid, raison));
}

Paysage    Recommandé       À éviter     Raison
------------------------------------------------------------------------------------------------
Sphere     GA, DE           (aucun critique) FDC élevé + paysage corrélé => la fitness indique l'optimum : un GA simple converge bien, peu de pièges.
Rastrigin  DE, BBPSO, FBI   WOA          FDC modéré/multimodal => éviter WOA (effondrement mesuré sur Ackley), préférer les optimiseurs robustes.
Ackley     DE, BBPSO, FBI   WOA          FDC modéré/multimodal => éviter WOA (effondrement mesuré sur Ackley), préférer les optimiseurs robustes.

Vérifions contre l’oracle : le sélecteur recommande-t-il bien les optimiseurs qui gagnent réellement sur chaque paysage ? Recoupons la recommandation avec le delta mesuré :

// Pour chaque paysage : top-3 optimiseurs par delta mesuré (oracle) vs recommandation du sélecteur.
// NB : r.R.Function contient le nom complet ("SphereFitness") ; Features.Name le stripping ("Sphere").
foreach (var (name, _) in Features.Select(r => (r.Name, 0)))
{
    var ranking = rows.Where(x => x.R.Function.Replace("Fitness", "") == name).OrderBy(x => x.R.Delta).Take(3).ToList();
    string realTop = String.Join(", ", ranking.Select(x => x.Opt + "(" + x.R.Delta.ToString("F2") + ")"));
    var rep = Features.First(f => f.Name == name);
    var (sel, avoid, _) = Select(rep);
    Console.WriteLine(name + " :");
    Console.WriteLine("    Oracle top-3   : " + realTop);
    Console.WriteLine("    Sélecteur      : recommande " + sel + "   évite " + avoid);
    bool ok = ranking.Any(x => sel.Contains(x.Opt));
    bool avoidsBad = ranking.Count == 0 || !ranking.Take(3).Any(x => avoid.Contains(x.Opt)); // n'évite pas un top-3
    Console.WriteLine("    => " + (ok ? "ALIGNÉ (recommandation dans le top-3 réel)" : "DÉSALIGNÉ"));
}

Sphere :
    Oracle top-3   : SA(-0,00), DE(-0,00), BBPSO(-0,00)
    Sélecteur      : recommande GA, DE   évite (aucun critique)
    => ALIGNÉ (recommandation dans le top-3 réel)
Rastrigin :
    Oracle top-3   : WOA(-11,41), BBPSO(-6,96), EO(-1,99)
    Sélecteur      : recommande DE, BBPSO, FBI   évite WOA
    => ALIGNÉ (recommandation dans le top-3 réel)
Ackley :
    Oracle top-3   : DE(-0,00), BBPSO(0,00), EO(0,00)
    Sélecteur      : recommande DE, BBPSO, FBI   évite WOA
    => ALIGNÉ (recommandation dans le top-3 réel)

Le sélecteur, bien qu’heuristique et délibérément simple, recommande un optimiseur du top-3 réel sur chaque paysage d’entraînement (Sphere, Rastrigin, Ackley). Surtout, il signale correctement la catastrophe Ackley : il évite WOA — le seul optimiseur qui s’y effondre (+4,19, biais central mesuré). C’est le gain pratique du cadre de Rice — écarter le mauvais choix sans avoir à tout exécuter.

10. Le vrai test — généraliser à un paysage jamais vu

La validation sur les paysages d’entraînement est circulaire (les features et l’oracle viennent des mêmes fonctions). Le test décisif est la généralisation : un quatrième paysage inconnu, Rosenbrock (la fameuse « vallée banane »). Mesurons ses features, demandons au sélecteur de prédire, puis exécutons l’oracle pour vérifier.

// Rosenbrock : borne [-2.048, 2.048]. Fonction célèbre : vallée étroite et courbe vers l'optimum (1,...,1).
var rosen = new RosenbrockFitness();
var repR = Measure(rosen, dim);
Console.WriteLine(String.Format("Rosenbrock : FDC={0:F3}  ρ₁={1:F3}  L_corr={2:F2}  Neutre={3:F2}%",
    repR.Fdc, repR.Rho1, repR.CorrLen, repR.Neutrality * 100));
var (selR, avoidR, raisonR) = Select(repR);
Console.WriteLine("Sélecteur recommande : " + selR + "   (à éviter : " + avoidR + ")");
Console.WriteLine("Raison : " + raisonR);

Rosenbrock : FDC=0,707  ρ₁=0,978  L_corr=45,42  Neutre=1,98%
Sélecteur recommande : DE, BBPSO, FBI   (à éviter : WOA)
Raison : FDC modéré/multimodal => éviter WOA (effondrement mesuré sur Ackley), préférer les optimiseurs robustes.

// Vérification oracle sur Rosenbrock (la vérité terrain).
var rbRows = new List<(string Opt, CenterBiasResult R)>();
foreach (var (optName, opt) in Portfolio)
{
    FastRandomRandomization.ResetSeed(masterSeed);
    var res = CenterBiasBenchmark.RunSuite(new List<(IFitness, int)> { (rosen, dim) }, budget, opt, shiftMag, masterSeed);
    foreach (var r in res) rbRows.Add((optName, r));
}
Console.WriteLine(String.Format("{0,-8} {1,12}", "Opt", "Delta Rosenbrock"));
Console.WriteLine(new String('-', 24));
foreach (var g in rbRows.OrderBy(x => x.R.Delta))
    Console.WriteLine(String.Format("{0,-8} {1,12:F3}", g.Opt, g.R.Delta));
string oracleTop3R = String.Join(", ", rbRows.OrderBy(x => x.R.Delta).Take(3).Select(x => x.Opt));
bool selHitsR = rbRows.OrderBy(x => x.R.Delta).Take(3).Any(x => selR.Contains(x.Opt));
Console.WriteLine("\nOracle Rosenbrock top-3 : " + oracleTop3R);
Console.WriteLine("Sélecteur recommandait   : " + selR);
Console.WriteLine("=> " + (selHitsR ? "ALIGNÉ (recommandation dans le top-3 réel)" : "DÉSALIGNÉ — generalization gap"));

Opt      Delta Rosenbrock
------------------------
Random         -9,457
BBPSO          -3,461
DE             -1,451
SA             -1,282
GA             -0,193
WOA             1,741
FBI             2,130
EO              2,743

Oracle Rosenbrock top-3 : Random, BBPSO, DE
Sélecteur recommandait   : DE, BBPSO, FBI
=> ALIGNÉ (recommandation dans le top-3 réel)

10.1 Leçon honnête : la prédiction transfère, mais le FDC se trompe sur Rosenbrock

Rosenbrock est révélateur. Ses features : ρ₁ ≈ 0,98 (paysage très lisse, marche fortement corrélée) mais FDC ≈ 0,71 (modéré). Or Rosenbrock est unimodale — ce n’est pas un paysage multimodal. Pourquoi ce FDC trompeur ? Parce que le FDC mesure la corrélation entre fitness brute et distance radiale à l’origine, alors que l’optimum de Rosenbrock est en \((1,\dots,1)\) et surtout sa vallée est courbe : le chemin vers l’optimum n’est pas radial, la fitness ne pointe pas vers le but. Le sélecteur, voyant « FDC modéré », classe Rosenbrock dans la branche multimodale et recommande DE/BBPSO/FBI.

Verdict oracle : la recommandation atterrit quand même dans le top-3 réel (DE et BBPSO y figurent) — les features transfèrent donc raisonnablement. La recommandation est toutefois partiellement contaminée : le sélecteur recommande aussi FBI, qui est en réalité le 2ᵉ pire sur Rosenbrock (+2,13, juste devant EO à +2,74) — un optimiseur qui s’y effondre, glissé dans la recommandation par le FDC trompeur. Le contrôle Random, lui, gagne curieusement (delta le plus négatif) : sur cette fonction difficile, tous les optimiseurs peinent en absolu, et la différence centré/déplacé est dominée par la variance de tirage plutôt que par la qualité de l’algorithme — un rappel que le delta n’est un signal fiable que sur les fonctions assez faciles pour être résolues (cf MGS-10 sur Rastrigin).

C’est l’enseignement honnête : les features de paysage sont une heuristique, pas un oracle. Elles excellent à écarter les catastrophes évidentes (éviter WOA sur Ackley) et orientent vers les optimiseurs robustes (DE/BBPSO), mais elles manquent la géométrie directionnelle (vallée courbe) : un FDC bas signifie tantôt « multimodal » (Rastrigin) tantôt « courbé » (Rosenbrock), et la feature seule ne distingue pas les deux. Les approches modernes (apprentissage de méta-caractéristiques sur un grand jeu de paysages, features directionnelles, coûts d’évaluation adaptatifs) poussent plus loin — c’est l’objet de l’exercice 4.

11. Synthèse — du sélecteur à l’hyper-heuristique

Le sélecteur de Rice que nous avons construit est une hyper-heuristique de sélection : il ne résout pas le problème lui-même, il choisit quel solveur appliquer. C’est l’aboutissement naturel de la Partie 4 :

Notebook	Apport
MGS-1..9	construire et comprendre les métaheuristiques individuelles
MGS-10	un portfolio mesuré de 8 optimiseurs (le banc center-bias)
MGS-11..14	la synergie : comment les combiner (îles, rotations, paysage)
MGS-15	caractériser un paysage (FDC, autocorrélation, neutralité)
MGS-16	décider : features → portfolio, le sélecteur de Rice

La boucle est bouclée : on est parti de métaheuristiques isolées, on les a mesurées (portfolio), on a appris à décrire les problèmes (paysage), et l’on sait désormais faire correspondre les deux. Le No-Free-Lunch n’est pas une condamnation : c’est l’invitation à raisonner sur le problème avant de lancer l’algorithme.

12. Exercices

Stubs à compléter. Le notebook s’exécute de bout en bout même exercices non résolus (convention C.1 : pas de raise/assert False/1/0).

Exercice 1 — Un paysage à évolution neutre

Les benchmarks continus ont une neutralité quasi nulle. Construisez un IFitness artificiellement neutre (par ex. quantifier la fitness de Rastrigin par paliers) et montrez que NeutralRatio grimpe. Que devient la recommandation du sélecteur ?

// Exercice 1 -- À COMPLÉTER
// Indice : IFitness dont Evaluate arrondit/quantifie la fitness par paliers (Math.Floor),
// créant des plateaux neutres. Mesurez NeutralRatio avant/après quantification.
public class QuantizedRastrigin : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        Console.WriteLine("Exercice 1 à compléter : implémentez une Rastrigin quantifiée par paliers.");
        return 0.0;  // TODO étudiant
    }
}
// var rep = Measure(new QuantizedRastrigin(), dim);
// Console.WriteLine(rep);

Exercice 2 — Un sélecteur fondé sur le coût d’évaluation

Jusqu’ici toutes les fonctions coûtent la même chose à évaluer. En pratique, une évaluation peut prendre des secondes (simulation physique). Ajoutez un coût cost au LandscapeReport et modifiez Select pour qu’un paysage cher favorise les optimiseurs économes (BBPSO, recherche aléatoire) sur les gourmands (GA à grande population).

// Exercice 2 -- À COMPLÉTER
// Indice : étendez le record LandscapeReport d'un champ Cost (en secondes/évaluations),
// puis ajoutez une branche dans Select : si Cost > seuil, préférer BBPSO/Random (peu d'évaluations).
Console.WriteLine("Exercice 2 à compléter : intégrez le coût d'évaluation dans le sélecteur.");

Exercice 2 à compléter : intégrez le coût d'évaluation dans le sélecteur.

Exercice 3 — Schwefel et la limite du FDC

La fonction de Schwefel a son optimum loin de l’origine (et KnownFunctionsBounds le reflète : borne [−500, 500]). Or SampleLandscape mesure la distance à l’origine — ce qui fausse le FDC. Exécutez le sélecteur sur Schwefel, comparez à l’oracle, et expliquez pourquoi le FDC devient non-informatif. Comment corriger le calcul de distance ?

// Exercice 3 -- À COMPLÉTER
// Indice : SampleLandscape suppose l'optimum à l'origine (DistToOptimum = ||x||).
// Schwefel rompt cette hypothèse. Testez le sélecteur vs l'oracle sur SchwefelFitness,
// puis proposez une correction (distance au vrai optimum, ou FDC non-radial).
Console.WriteLine("Exercice 3 à compléter : diagnostiquez le FDC trompeur sur Schwefel.");

Exercice 3 à compléter : diagnostiquez le FDC trompeur sur Schwefel.

Exercice 4 — Vers l’apprentissage : un sélecteur appris

Notre sélecteur est une expertise encodée à la main. Générez un jeu d’entraînement : N paysages aléatoires (combinaisons linéaires de Sphere/Rastrigin/Ackley), pour chacun ses features + le meilleur optimiseur mesuré (oracle). Puis remplacez la règle Select par un simple classifieur (k-NN ou arbre de décision) appris sur ces N exemples. Le sélecteur appris bat-il la règle manuelle sur de nouveaux paysages ?

// Exercice 4 -- À COMPLÉTER
// Indice : boucle sur N combinaisons pondérées (a*Sphere + b*Rastrigin + c*Ackley),
// mesurez (features, bestOpt) pour chacune, puis implémentez un k-NN sur les features.
Console.WriteLine("Exercice 4 à compléter : construisez un sélecteur appris (k-NN sur les features).");

Exercice 4 à compléter : construisez un sélecteur appris (k-NN sur les features).

Résumé et perspectives

Ce que vous avez appris :

Concept	Outil	Notebook de référence
No-Free-Lunch	théorème (Wolpert & Macready, 1997)	ce notebook
Cadre de sélection	Rice (1976) : features → algorithme → performance	ce notebook
Features de paysage	FDC, autocorrélation, neutralité	MGS-15
Portfolio mesuré	8 optimiseurs, banc center-bias	MGS-10
Hyper-heuristique	sélection plutôt que résolution	ce notebook (capstone)

Limites honnêtes : (1) nos features sont statiques et radiales (FDC suppose l’optimum à l’origine) — elles ratent les géométries directionnelles (Rosenbrock, Schwefel) ; (2) le sélecteur est heuristique, non appris ; (3) le coût d’évaluation (critique en simulation) n’est pas modélisé ; (4) la généralisation à des familles vraiment étrangères n’est pas garantie (generalization gap).

Pour aller plus loin : - Sélection apprise : Smith-Miles (2008), Towards the provision of information for the algorithm sélection problem ; Kerschke et al. (2019), Automated Algorithm Sélection. - Paysages dynamiques : caractéristiques évoluant dans le temps (cf. MGS-11 îles, MGS-14 synergie). - Hyper-heuristiques de génération : au lieu de sélectionner, générer un nouvel optimiseur composé (cf. MGS-5 métaheuristiques composées).

← MGS-15-LandscapeAnalysis | Retour à la série

Références : Wolpert, D. H. & Macready, W. G. (1997), No free lunch theorems for optimization, IEEE Trans. Evolutionary Computation 1(1) ; Rice, J. R. (1976), The Algorithm Sélection Problem, Advances in Computers 15 ; Weinberger, E. (1990), Correlated and uncorrelated fitness landscapes and how to tell the différence, Biological Cybernetics 63(5) ; Jones, T. & Forrest, S. (1995), Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, ICGA.

Retour au sommet