MGS-15 : Analyse de paysage – la corrélation fitness-distance (FDC)

← MGS-14 IslandSynergyFound | ↑ Série MGS

Pourquoi des métriques, et pas seulement des heatmaps ? MGS-8 nous a donné l’œil : on voit la surface de fitness en couleur. Mais l’œil est trompé par l’échelle, la rotation, le nombre de dimensions. Deux paysages visuellement semblables peuvent être radicalement inégaux pour un algorithme. Les métriques d’analyse de paysage donnent le nombre derrière l’image : elles quantifient à quel point la fitness guide vers l’optimum, indépendamment de la visualisation.

Ce notebook introduit la Fitness Distance Correlation (FDC) — Jones & Forrest (1995) — la métrique la plus utilisée pour prédire la difficulté d’un paysage pour un algorithme de recherche. On la calcule sur trois benchmarks canoniques du fork (SphereFitness, RastriginFitness, AckleyFitness), en réutilisant la vraie infrastructure de MGS-8 (chromosome continu, KnownFunctionsBounds, vraies IFitness.Evaluate — composition, jamais de réimplémentation).

Prong-B (problème non-trivial). Ces métriques n’ont d’intérêt que sur des paysages où elles discriminent. On compare donc un paysage facile (Sphere, unimodal) à un paysage multimodal (Rastrigin, pièges locaux) et un paysage à structure fine (Ackley) — là où l’œil humain hésite, le nombre tranche.

Deux familles complémentaires. Le notebook pose deux métriques qui mesurent des choses différentes et se révèlent complémentaires : (1) la FDC (Jones & Forrest 1995) — corrélation globale fitness–distance, prédit si la fitness guide vers l’optimum ; (2) l’autocorrélation de marche aléatoire (Weinberger 1990) et la neutralité — structure locale, quantifient la rugosité et les plateaux. Un paysage de FDC élevée peut être très rugueux (Ackley) : les deux nombres ensemble diagnostiquent ce que chacun, seul, masque.

Câblage : MetaGeneticSharp (fork) + paysages analytiques

On charge les mêmes DLLs du fork que MGS-8 (répertoire self-contained de MetaGeneticSharp.Extensions). On n’a pas besoin des backends graphiques (Skia/DirectBitmap) ici — la FDC est numérique, pas visuelle — mais on les charge quand même pour rester sur le câblage éprouvé de l’explorer (et parce que KnownFunctions vit dans Extensions).

// Fork DLLs loaded from the self-contained Extensions output (one-stop dir: it also ships
// System.Drawing.Common.dll AND SkiaSharp.dll, needed at runtime by the graphic landscape types).
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/GeneticSharp.Infrastructure.Framework.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/GeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Infrastructure.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Extensions.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/System.Drawing.Common.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/SkiaSharp.dll"

using System.Runtime.InteropServices;                   // RuntimeInformation, Architecture, NativeLibrary
using MetaGeneticSharp;                                 // KnownFunctions, KnownFunctionsBounds
using GeneticSharp;                                     // IFitness, ChromosomeBase, RandomizationProvider
using GeneticSharp.Infrastructure.Framework.Images;     // DirectBitmap (verbatim)

// .NET Interactive quirk: preload the arch-matching SkiaSharp native binary (cf MGS-8 cellule de câblage).
string rid = RuntimeInformation.ProcessArchitecture == Architecture.Arm64 ? "win-arm64"
           : RuntimeInformation.ProcessArchitecture == Architecture.X86   ? "win-x86"
           : "win-x64";
NativeLibrary.Load($"../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/runtimes/{rid}/native/libSkiaSharp.dll");

Console.WriteLine("Câblage OK : KnownFunctions + KnownFunctionsBounds + IFitness.");
Console.WriteLine($"  Benchmarks dispos : {string.Join(", ", new[]{typeof(SphereFitness),typeof(RastriginFitness),typeof(AckleyFitness),typeof(GriewankFitness),typeof(SchwefelFitness),typeof(RosenbrockFitness)}.Select(t=>t.Name))}");
Câblage OK : KnownFunctions + KnownFunctionsBounds + IFitness.
  Benchmarks dispos : SphereFitness, RastriginFitness, AckleyFitness, GriewankFitness, SchwefelFitness, RosenbrockFitness

Terrain commun : chromosome continu + échantillonnage borné

On réutilise verbatim le DoubleArrayChromosome de MGS-8 (gènes double nus, bornes par gène). Pour la FDC, on a besoin d’échantillonner la fitness en N points tirés uniformément dans la boîte de recherche, puis de calculer pour chaque point (a) sa valeur de fitness brute et (b) sa distance à l’optimum global.

Convention de signe. GeneticSharp maximise IFitness.Evaluate ; les benchmarks renvoient donc la valeur négativée (ex. SphereFitness renvoie −Σx²). La FDC s’analyse sur la vraie valeur de minimisation (plus bas = meilleur), d’où rawFitness = −Evaluate.

Optimum global. Pour les six benchmarks standards ci-dessus, l’optimum est à l’origine (x = 0). La distance à l’optimum est donc simplement ‖x‖.

// DoubleArrayChromosome (verbatim MGS-8) : gènes double nus + bornes par gène.
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;
        var vals = new double[Length];
        for (int i = 0; i < Length; i++) vals[i] = rand.GetDouble(_min, _max);
        return new DoubleArrayChromosome(vals, _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();
}

// Un échantillon du paysage : point tiré, fitness brute (minimisation), distance à l'optimum.
public record Sample(double[] Point, double RawFitness, double DistToOptimum);

// Échantillonne N points uniformément dans [lo,hi]^dim, évalue la VRAIE fitness du fork,
// et mesure la distance Euclidienne à l'origine (optimum global de ces benchmarks).
// Seed fixe = reproductibilité (cf leçon MGS-10 RNG).
Sample[] SampleLandscape(IFitness f, int dim, int n, int seed = 42)
{
    var (lo, hi) = KnownFunctionsBounds.For(f.GetType());
    var rand = new Random(seed);
    var samples = new Sample[n];
    for (int i = 0; i < n; i++)
    {
        double[] x = new double[dim];
        for (int j = 0; j < dim; j++) x[j] = lo + rand.NextDouble() * (hi - lo);
        var chrom = new DoubleArrayChromosome(x, lo, hi);
        double eval = f.Evaluate(chrom);      // maximisation GA : -raw
        double raw = -eval;                    // vraie valeur de minimisation (plus bas = meilleur)
        double dist = Math.Sqrt(x.Select(v => v * v).Sum());  // ||x - 0||
        samples[i] = new Sample(x, raw, dist);
    }
    return samples;
}

// Coefficient de corrélation linéaire de Pearson sur deux séries.
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, distanceToOptimum). |FDC| -> 1 = facile (la fitness guide vers l'optimum),
// |FDC| -> 0 = dur / trompeur (la fitness n'informe pas sur la distance).
double Fdc(Sample[] s) => Pearson(s.Select(t => t.RawFitness).ToArray(), s.Select(t => t.DistToOptimum).ToArray());

// Auto-check sur 5 points connus : la corrélation parfaite d'une série avec elle-même = 1.
double selfCorr = Pearson(new[]{1.0,2,3,4,5}, new[]{1.0,2,3,4,5});
Console.WriteLine($"Helpers prêts. Auto-check Pearson(x,x) = {selfCorr:F4} (attendu 1.0000).");
Helpers prêts. Auto-check Pearson(x,x) = 1,0000 (attendu 1.0000).

La FDC en théorie — Jones & Forrest (1995)

Idée. Un paysage est facile pour une recherche si la valeur de fitness est un bon indicateur de la distance au but : tant que « mieux placé en fitness » rime avec « plus proche de l’optimum », un algorithme glouton ou génétique suit le gradient et converge. La FDC quantifie cette intuition :

\[\mathrm{FDC} = \rho\!\left(\, f(x),\; d(x, x^\star)\,\right)\]

où \(\rho\) est la corrélation de Pearson, \(f\) la fitness (minimisation : plus bas = meilleur), et \(d\) la distance à l’optimum global \(x^\star\).

Lecture (règle empirique de Jones & Forrest) :

FDC Paysage Prédiction
\(\vert\mathrm{FDC}\vert \ge 0{,}95\) aligné (fitness guide bien) facile — un GA converge
\(0{,}15 \le \vert\mathrm{FDC}\vert < 0{,}95\) intermédiaire difficulté modérée
\(\vert\mathrm{FDC}\vert \le 0{,}15\) non-corrélé dur — la fitness n’informe plus

Nuance. La FDC mesure une corrélation linéaire. Sphere (\(f=\sum x_i^2\), \(d=\sqrt{\sum x_i^2}\)) a une relation \(f = d^2\) — parfaitement monotone mais non linéaire, donc sa FDC Pearson sera élevée (~0,97) sans atteindre 1,0. C’est précisément ce qui rend la métrique informative : elle n’est pas triviale même sur le cas le plus simple.

// FDC sur 3 benchmarks contrastés, dimension 2 (le terrain où la heatmap de MGS-8 est lisible).
// N=600 échantillons : assez pour stabiliser Pearson, borné en runtime (< 1 s par fonction).
int dim = 2, N = 600;
var benchmarks = new (Type type, string name, string profile)[]
{
    (typeof(SphereFitness),    "Sphere",    "unimodal — un seul bassin, facile"),
    (typeof(RastriginFitness), "Rastrigin", "fortement multimodal — pièges locaux"),
    (typeof(AckleyFitness),    "Ackley",    "multimodal à structure fine"),
};

Console.WriteLine($"FDC (dim={dim}, N={N} échantillons uniformes, distance à l'optimum = origine)");
Console.WriteLine(new string('-', 78));
Console.WriteLine($"{"Fonction",-12} {"FDC",8}   {"|FDC|",8}   Profil");
Console.WriteLine(new string('-', 78));
var results = new List<(string name, double fdc, Sample[] s)>();
foreach (var (t, name, profile) in benchmarks)
{
    var f = (IFitness)Activator.CreateInstance(t)!;
    var s = SampleLandscape(f, dim, N);
    double fdc = Fdc(s);
    results.Add((name, fdc, s));
    Console.WriteLine($"{name,-12} {fdc,8:F4}   {Math.Abs(fdc),8:F4}   {profile}");
}
Console.WriteLine(new string('-', 78));
Console.WriteLine("Lecture : Sphere (|FDC| ~ 0,97) = facile ; Rastrigin chute (multimodal) ; Ackley intermédiaire.");
FDC (dim=2, N=600 échantillons uniformes, distance à l'optimum = origine)
------------------------------------------------------------------------------
Fonction          FDC      |FDC|   Profil
------------------------------------------------------------------------------
Sphere         0,9759     0,9759   unimodal — un seul bassin, facile
Rastrigin      0,7132     0,7132   fortement multimodal — pièges locaux
Ackley         0,7656     0,7656   multimodal à structure fine
------------------------------------------------------------------------------
Lecture : Sphere (|FDC| ~ 0,97) = facile ; Rastrigin chute (multimodal) ; Ackley intermédiaire.

Nuage de points fitness–distance : voir la corrélation

La FDC condense le paysage en un seul nombre ; le nuage (fitness vs distance à l’optimum) montre pourquoi. Un paysage facile dessine une relation propre (fitness croît avec la distance) ; un paysage multimodal disperse le nuage (à distance égale, des fitness très différentes selon le bassin).

On rend ce nuage en SVG inline (aucune dépendance de tracé, cf leçon MGS papermill : les backends #r nuget se bloquent).

// Nuage fitness-vs-distance en SVG inline, 3 sous-figures côte à côte (une par benchmark).
// Format invariant (decimal DOT) : critique pour le rendu SVG. Sur machine fr-FR,
// :F1/:F3 emettent une virgule -> cx='70,0' = "Expected length" (defaults 0), nuage casse.
// Idiome du canon SvgChartHelper.cs (#6942). Cf finding vision-QA po-2024 c.581 / Infer-17 #6946.
string F(double v) => v.ToString("0.###", System.Globalization.CultureInfo.InvariantCulture);

string ScatterSvg(string title, double[] dists, double[] fits, string color)
{
    // Normalisation vers la zone [10,290] x [20,170] (pixels).
    double dmin = dists.Min(), dmax = dists.Max(), fmin = fits.Min(), fmax = fits.Max();
    double dx = dmax - dmin < 1e-12 ? 1 : dmax - dmin;
    double dy = fmax - fmin < 1e-12 ? 1 : fmax - fmin;
    var pts = new StringBuilder();
    for (int i = 0; i < dists.Length; i++)
    {
        double px = 10 + 280 * (dists[i] - dmin) / dx;
        double py = 170 - 150 * (fits[i] - fmin) / dy;
        pts.Append($"<circle cx='{F(px)}' cy='{F(py)}' r='1.4' fill='{color}' opacity='0.55'/>");
    }
    return $"<div style='display:inline-block;vertical-align:top;margin:6px'>"
         + $"<svg width='300' height='190' style='border:1px solid #ccc;background:#fafafa'>"
         + $"<text x='10' y='14' font-size='12' font-family='sans-serif' fill='#333'>{title}</text>"
         + $"<line x1='10' y1='170' x2='290' y2='170' stroke='#888' stroke-width='0.5'/>"
         + $"<line x1='10' y1='20'  x2='10'  y2='170' stroke='#888' stroke-width='0.5'/>"
         + $"<text x='270' y='185' font-size='9' font-family='sans-serif' fill='#777'>distance</text>"
         + $"<text x='12' y='28' font-size='9' font-family='sans-serif' fill='#777'>fitness</text>"
         + $"{pts}</svg></div>";
}

var colors = new Dictionary<string,string>{ {"Sphere","#1f77b4"}, {"Rastrigin","#d62728"}, {"Ackley","#2ca02c"} };
var svgs = new StringBuilder();
foreach (var (name, fdc, s) in results)
{
    var dists = s.Select(t => t.DistToOptimum).ToArray();
    var fits  = s.Select(t => t.RawFitness).ToArray();
    svgs.Append(ScatterSvg($"{name}  FDC={F(fdc)}", dists, fits, colors[name]));
}
display(HTML($"<div>{svgs}</div><div style='font:12px sans-serif;color:#555;clear:both'>"
           + $"<b>Sphere</b> : nuage en croissant propre (fitness ~ distance²). "
           + $"<b>Rastrigin</b> : nuage dispersé verticalement (à distance égale, plusieurs bassins). "
           + $"<b>Ackley</b> : dispersion intermédiaire avec structure.</div>"));
Sphere FDC=0.976distancefitness
Rastrigin FDC=0.713distancefitness
Ackley FDC=0.766distancefitness
Sphere : nuage en croissant propre (fitness ~ distance²). Rastrigin : nuage dispersé verticalement (à distance égale, plusieurs bassins). Ackley : dispersion intermédiaire avec structure.

Exercice 1 — FDC de Griewank

Calculez la FDC de GriewankFitness (dimension 2, N=600) en réutilisant SampleLandscape et Fdc. Indice : Griewank a une structure particulière (beaucoup de local optima qui se annulent loin de l’optimum). Prédisez d’abord la valeur attendue, puis vérifiez.

  • Étape 1 : instancier GriewankFitness
  • Étape 2 : SampleLandscape(f, dim=2, N=600)
  • Étape 3 : Fdc(samples) — comparez à Sphere/Rastrigin/Ackley
// Exercice 1 a completer : FDC de GriewankFitness.
// Resultat attendu (a verifier) : intermediaire entre Sphere et Rastrigin.
double griewankFdc = 0.0;  // TODO etudiant : SampleLandscape + Fdc
Console.WriteLine($"Exercice 1 a completer : FDC Griewank = {griewankFdc:F4} (remplacez 0.0 par votre calcul).");
Exercice 1 a completer : FDC Griewank = 0,0000 (remplacez 0.0 par votre calcul).

Exercice 2 — Effet de la dimension sur la FDC

La difficulté d’un paysage croît avec la dimension (fléau de la dimensionalité). Mesurez comment la FDC de RastriginFitness évolue en dimension 2, 5, 10. Conjecture : la FDC baisse quand la dimension augmente (les bassins locaux deviennent plus nombreux et plus trompeurs).

  • Étape 1 : boucler sur dims = {2, 5, 10}
  • Étape 2 : pour chaque dim, SampleLandscape + Fdc
  • Étape 3 : observer la décroissance — confirme-t-elle la conjecture ?
// Exercice 2 a completer : FDC de Rastrigin vs dimension.
// Resultat attendu (a verifier) : FDC decroit quand dim augmente.
Console.WriteLine("Exercice 2 a completer : bouclez sur dims {2,5,10} et calculez Fdc(Rastrigin) pour chaque.");
Exercice 2 a completer : bouclez sur dims {2,5,10} et calculez Fdc(Rastrigin) pour chaque.

Exercice 3 — Détecter un paysage trompeur (deception)

Un paysage trompeur (deceptive) est celui où la fitness pousse loin de l’optimum global (FDC négative ou quasi-nulle alors que le paysage semble guidé). Construisez un contre-exemple : prenez SphereFitness et comparez sa FDC à celle d’une fonction où l’optimum global est au coin de la boîte (ex. Schwefel, dont l’optimum est loin de l’origine). Question : la distance-à-l’origine reste-t-elle une bonne référence de difficulté quand l’optimum n’est pas à l’origine ?

Indice : pour Schwefel, l’optimum global n’est PAS à l’origine — la FDC (distance-à-l’origine) devient trompeuse.

// Exercice 3 a completer : FDC de SchwefelFitness (optimum NON a l'origine).
// Question ouverte : la metrique distance-a-l'origine est-elle encore valide ?
Console.WriteLine("Exercice 3 a completer : calculez Fdc(Schwefel) et discutez la validite de la reference origine.");
Exercice 3 a completer : calculez Fdc(Schwefel) et discutez la validite de la reference origine.

Rugosité locale : l’autocorrélation de marche aléatoire (Weinberger 1990)

La FDC mesure une corrélation globale — elle ne dit rien de la rugosité locale. Or deux paysages de FDC identique peuvent avoir des rugosités radicalement différentes : un paysage lisse (peu d’optima locaux, gradients propres) se parcourt facilement ; un paysage rugueux (foisonnement d’optima locaux) piège la recherche dans des minima sans issue. Weinberger (1990) propose de quantifier cette rugosité par l’autocorrélation d’une marche aléatoire : on parcourt le paysage en pas aléatoires d’amplitude \(\varepsilon\), et on mesure la corrélation \(\rho_1\) entre fitness consécutives.

  • \(\rho_1 \to 1\) : paysage lisse (le voisin a une fitness proche — le gradient est exploitable).
  • \(\rho_1 \to 0\) : paysage rugueux (chaque pas change drastiquement la fitness — le gradient est du bruit).

La longueur de corrélation \(L = -1/\ln(\rho_1)\) (en nombre de pas) est la distance au-delà de laquelle la fitness se décorréle : plus \(L\) est court, plus le paysage est chaotique pour une recherche locale. On réutilise le même DoubleArrayChromosome et la même IFitness.Evaluate du fork — seul l’échantillonneur change (marche au lieu de tirage uniforme).

// Marche aléatoire sur le paysage : point de départ aléatoire, puis pas de direction uniforme
// et d'amplitude (relative) eps, avec rebond sur les bords de la boîte. Vraie fitness du fork.
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);   // départ uniforme
    double eps = epsRel * (hi - lo);                                            // amplitude absolue du pas
    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]);   // rebond miroir sur le bord inférieur
            if (x[j] > hi) x[j] = hi - (x[j] - hi);   // rebond miroir sur le bord supérieur
        }
        fits[t] = -f.Evaluate(new DoubleArrayChromosome(x, lo, hi));   // vraie fitness (minimisation)
    }
    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);
}

// 3 benchmarks, dim 2, marche de 5000 pas, amplitude relative 5% de la boîte (le grain où la
// rugosité de Rastrigin/Ackley devient visible sans noyer celle de Sphere).
int walkSteps = 5000;
double epsRel = 0.05;
Console.WriteLine($"Autocorrélation de marche aléatoire (dim=2, {walkSteps} pas, pas relatif {epsRel:P0} de la boîte)");
Console.WriteLine(new string('-', 78));
Console.WriteLine($"{"Fonction",-12} {"rho_1",8}   {"L (pas)",10}   Lecture ruggedness");
Console.WriteLine(new string('-', 78));
var walkResults = new List<(string name, double rho1, double corrLen)>();
foreach (var (t, name, _) in benchmarks)
{
    var f = (IFitness)Activator.CreateInstance(t)!;
    var fits = RandomWalk(f, 2, walkSteps, epsRel);
    double rho1 = AutocorrLag1(fits);
    double corrLen = (rho1 > 0 && rho1 < 1) ? -1.0 / Math.Log(rho1) : double.NaN;
    walkResults.Add((name, rho1, corrLen));
    string read = rho1 > 0.95 ? "très lisse" : rho1 > 0.6 ? "modérément rugueux" : "fortement rugueux";
    Console.WriteLine($"{name,-12} {rho1,8:F4}   {corrLen,10:F2}   {read}");
}
Console.WriteLine(new string('-', 78));
Console.WriteLine("Lecture : Sphere très lisse (ρ₁→1, L long) ; Rastrigin/Ackley rugueux (ρ₁ bas, L court).");
Autocorrélation de marche aléatoire (dim=2, 5000 pas, pas relatif 5 % de la boîte)
------------------------------------------------------------------------------
Fonction        rho_1      L (pas)   Lecture ruggedness
------------------------------------------------------------------------------
Sphere         0,9673        30,03   très lisse
Rastrigin      0,3744         1,02   fortement rugueux
Ackley         0,9017         9,67   modérément rugueux
------------------------------------------------------------------------------
Lecture : Sphere très lisse (ρ₁→1, L long) ; Rastrigin/Ackley rugueux (ρ₁ bas, L court).

Ce que l’autocorrélation révèle que la FDC masquait. Sphere reste très lisse (\(\rho_1\) proche de 1) : sa surface est un bol régulier, chaque pas voisin a une fitness voisine. Rastrigin et Ackley chutent drastiquement en \(\rho_1\) : leurs optima locaux denses font que deux points immédiatement voisins peuvent avoir des fitness très différentes — le gradient local est trompeur. C’est l’explication mécaniste du verdict FDC : Rastrigin a une FDC basse non pas parce que sa fitness « ne guide pas » en moyenne, mais parce qu’à l’échelle locale elle oscille si vite qu’un algorithme glouton s’y empêtre. Les deux métriques sont complémentaires : la FDC dit si la fitness guide (global), l’autocorrélation dit à quelle échelle elle est fiable (local).

Neutralité : les plateaux (et leur absence)

Un paysage neutre contient des régions où la fitness est constante — des mouvements qui ne changent rien. Cette planéité est typique des paysages discrets (génomes binaires, NK-landscapes de Kauffman) où plusieurs génotypes voisins mappent sur la même fitness. La proportion de pas neutres en marche aléatoire la quantifie. Beaucoup de neutralité est à double tranchant : elle permet à la recherche de dériver sans signal (donc d’explorer loin à moindre coût), mais peut aussi la piéger dans des plateaux sans issue.

Résultat attendu (honnête). Sur nos benchmarks continus différentiables (Sphere/Rastrigin/Ackley), la neutralité exacte est quasi-nulle : une fonction continue ne produit presque jamais deux fitness exactement égales. C’est un résultat en soi — la leçon n’est pas « la métrique échoue » mais chaque métrique a son terrain : la neutralité éclaire les paysages discrets, l’autocorrélation les continus. On le vérifie.

// Neutralité : proportion de pas de la marche où |Δfitness| < tol (mouvement "neutre").
// tol = fraction relative de l'étendue de fitness observée sur la marche.
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($"Neutralité (marche dim=2, {walkSteps} pas, tol = 0,1% de l'étendue de fitness)");
Console.WriteLine(new string('-', 78));
Console.WriteLine($"{"Fonction",-12} {"pas neutres",12}   Lecture");
Console.WriteLine(new string('-', 78));
foreach (var (t, name, _) in benchmarks)
{
    var f = (IFitness)Activator.CreateInstance(t)!;
    var fits = RandomWalk(f, 2, walkSteps, epsRel);
    double neu = NeutralRatio(fits, 0.001);
    string read = neu < 0.01 ? "quasi-nulle (paysage continu, pas de plateau)" : neu < 0.1 ? "faible" : "marquée (plateaux)";
    Console.WriteLine($"{name,-12} {neu,12:P2}   {read}");
}
Console.WriteLine(new string('-', 78));
Console.WriteLine("Lecture : sur ces benchmarks continus, la neutralité ~0 partout — elle ne discrimine pas ici"); Console.WriteLine("(elle devient cruciale sur les paysages discrets : NK, génomes binaires, SAT).");
Neutralité (marche dim=2, 5000 pas, tol = 0,1% de l'étendue de fitness)
------------------------------------------------------------------------------
Fonction      pas neutres   Lecture
------------------------------------------------------------------------------
Sphere             1,22 %   faible
Rastrigin          0,24 %   quasi-nulle (paysage continu, pas de plateau)
Ackley             1,72 %   faible
------------------------------------------------------------------------------
Lecture : sur ces benchmarks continus, la neutralité ~0 partout — elle ne discrimine pas ici
(elle devient cruciale sur les paysages discrets : NK, génomes binaires, SAT).

Exercice 4 — Rugosité de Rosenbrock (la vallée courbe)

RosenbrockFitness a une structure célèbre : une vallée courbe et plate qui mène à l’optimum, encadrée de parois très raides. Sa FDC est intermédiaire, mais son autocorrélation raconte une autre histoire. Prédisez son \(\rho_1\) (élevé ? faible ?), puis vérifiez avec RandomWalk + AutocorrLag1 (dim 2, 5000 pas).

Indice : la marche moyenne mélange deux régimes — la vallée (lisse, ρ₁ haut) et les parois (raides, ρ₁ bas). Le ρ₁ moyen reflète ce mélange.

// Exercice 4 a completer : autocorrelation de RosenbrockFitness.
// Resultat attendu (a verifier) : rho_1 intermediaire, reflet du melange vallee/parois.
Console.WriteLine("Exercice 4 a completer : RandomWalk(Rosenbrock, 2, 5000, 0.05) puis AutocorrLag1(fits).");
Exercice 4 a completer : RandomWalk(Rosenbrock, 2, 5000, 0.05) puis AutocorrLag1(fits).

Conclusion — deux métriques, deux échelles, un diagnostic

Ce qu’on a mesuré. Deux familles de métriques complémentaires, chacune révélant une facette que l’autre masque :

Métrique Échelle Sphere Rastrigin Ackley Ce qu’elle dit
FDC (Jones & Forrest) globale 0,976 0,713 0,766 la fitness guide-t-elle vers l’optimum ?
Autocorr. \(\rho_1\) (Weinberger) locale très lisse rugueux rugueux à quelle échelle la fitness est-elle fiable ?
Neutralité locale ~0 ~0 ~0 y a-t-il des plateaux ? (non, sur ces continus)
  • FDC : Sphere est facile (la fitness est un excellent indicateur de la distance) ; Rastrigin/Ackley plus durs (la multimodalité disperse la relation fitness–distance).
  • Autocorrélation : Sphere est lisse (\(\rho_1 \to 1\), longueur de corrélation longue) ; Rastrigin/Ackley sont rugueux (\(\rho_1\) bas, gradient local trompeur). C’est l’explication mécaniste : leur FDC basse vient d’une oscillation locale trop rapide pour un glouton.
  • Neutralité : quasi-nulle partout — honnête. Les benchmarks continus différentiables n’ont pas de plateaux ; cette métrique discrimine les paysages discrets (NK, génomes binaires), pas ceux-ci. Leçon : chaque métrique a son terrain.

Pour aller plus loin. Ces nombres justifient rétrospectivement le verdict de MGS-10 (étude des optimiseurs) : WOA biaisé vers le centre s’égare sur Ackley parce que ce paysage combine FDC intermédiaire et rugosité élevée — la fitness guide mal et oscille vite. Aucune heatmap ne l’avait quantifié ainsi. Prochain terrain : appliquer ces métriques aux paysages combinatoires (TSP, MGS-7) où la neutralité deviendra informative, et aux paysages dé-biaisés de MGS-13 pour mesurer l’effet de la rotation sur la rugosité.

← MGS-14 | ↑ Série MGS

Retour au sommet