MGS-9 - Trouver l’Everest : relief reel et bassins d’attraction

Serie MetaGeneticSharp | Précédent : MGS-8 - Landscape Explorer

MGS-8 explorait des paysages de fitness synthetiques (Sphere, Rastrigin…). Ici le paysage est un relief terrestre reel : on cherche le point le plus haut - l’Everest - sur quatre cartes d’altitude a zoom croissant, du globe entier a la region du sommet.

Objectifs d’apprentissage

• Traiter une carte d’altitude (DEM) comme un paysage de fitness a maximiser.
• Visualiser le relief en heatmap graphique PNG (sommet = marqueur noir), coherent avec le rendu de MGS-8 via le LandscapeRenderer du fork.
• Lancer le moteur MGS (GA / WOA / Equilibrium Optimizer) sur ce relief, plus une baseline PSO externe, a budget d’evaluations egal.
• Mesurer le taux de reussite de chaque méthode pour localiser le sommet, et relier ce taux au rapport taille du bassin d’attraction / taille de l’espace de recherche.

Prerequis

• MGS-1 a MGS-5 (moteur, compounds geometriques WOA/EO), MGS-8 (heatmaps PNG via le fork).
• Build du fork : dotnet build ..\MetaGeneticSharp\MetaGeneticSharp.sln.

Données

Les cartes d’altitude originales de jsboige (KnownHeightMap : World, TibetanPlateau, NepalBhoutan, EverestMount), acquisitions d’un service d’elevation WMS conservees en PNG d’environ 2560 px, exactement telles qu’elles vivent dans la librairie MGS (ressources embarquees du fork MetaGeneticSharp.Extensions). Aucun appel reseau a l’exécution : on lit les PNG verbatim via ImageHeightMapFunction (niveaux de gris, interpolation inverse-distance, byte-exact @ d05826fd). L’altitude y est codee en niveau de gris (clair = haut) ; on cherche le pixel le plus clair de chaque carte, c’est-a-dire le sommet.

Note d’auteur (AUTHORSHIP). Ce notebook est un habillage pedagogique : il consomme la librairie MGS (moteur, WhaleOptimisationAlgorithm, EquilibriumOptimizer, KnownFunctionGenes, LandscapeRenderer / SkiaLandscapeRenderer, LandscapeMaps.CreateFunction / KnownHeightMap) sans la reimplementer. Les cartes d’altitude sont les ressources PNG verbatim de jsboige. Le PSO est une baseline externe explicite (le bestiaire du fork n’a pas de PSO), au même titre que le RandomSearchOptimizer de la lib.

Reproductibilite. Ce notebook est deterministe de bout en bout : les rendus de paysage le sont par pixel depuis la PR MetaGeneticSharp #49 (graine RNG derivee de (x, y, base) – l’ordre du Parallel.For n’influence plus le rendu), et les moteurs GA/PSO/WOA/EO de la section 4 tournent sous SeededRandomization (graine explicite par run, 10 graines mesurees). Double execution verifiee byte-identique sur l’integralite des cellules code.

Duree estimee : 25-35 min.

// MetaGeneticSharp + GeneticSharp DLLs from the fork's self-contained Extensions output
// (one-stop dir: it also ships System.Drawing.Common.dll and SkiaSharp.dll, needed because
//  the graphic heatmap types now encode PNG via SkiaSharp cross-platform on the fork @ 7d1575c).
// Build prerequisite: dotnet build ..\MetaGeneticSharp\MetaGeneticSharp.sln
#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.Linq;
using System.Runtime.InteropServices;                   // NativeLibrary, RuntimeInformation
using MetaGeneticSharp;                                 // LandscapeRenderer, SkiaLandscapeRenderer
using GeneticSharp;                                     // GA engine, IFitness, KnownFunctionGenes

// .NET Interactive quirk: a #r to the managed SkiaSharp.dll does NOT wire up SkiaSharp's
// runtimes/<rid>/native/ probing, so the first Skia call would P/Invoke a native lib that was
// never loaded (BadImageFormatException 0x8007000B). Preload the arch-matching native binary
// from the self-contained output once, up front (same fix as MGS-8, fork @ 7d1575c).
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("Wiring OK : MetaGeneticSharp + GeneticSharp + Extensions (LandscapeRenderer + SkiaLandscapeRenderer).");
Console.WriteLine($"  Renderers : {typeof(LandscapeRenderer).Name}, {typeof(SkiaLandscapeRenderer).Name} (SkiaSharp, native rid={rid})");
Console.WriteLine($"  Engine    : {typeof(WhaleOptimisationAlgorithm).Name}, {typeof(EquilibriumOptimizer).Name}");

Wiring OK : MetaGeneticSharp + GeneticSharp + Extensions (LandscapeRenderer + SkiaLandscapeRenderer).
  Renderers : LandscapeRenderer, SkiaLandscapeRenderer (SkiaSharp, native rid=win-x64)
  Engine    : WhaleOptimisationAlgorithm, EquilibriumOptimizer

1. Le relief reel comme paysage de fitness

Une carte d’altitude (Digital Elevation Model) code le terrain en niveaux de gris : un pixel clair = un point haut, un pixel fonce = une basse. On la lit en coordonnees normalisees (u, v) dans [0,1]^2 : u parcourt la longitude (ouest -> est), v la latitude (le PNG source est une tuile WMS orientee nord vers le haut, donc v=0 = nord en haut de l’image et v croit vers le sud). Le niveau d’altitude interpole en (u,v) est notre fonction de fitness, a MAXIMISER - l’inverse de MGS-6/MGS-8 ou un objectif synthetique etait minimise. Trouver l’Everest = localiser le maximum global de la carte, c’est-a-dire son pixel le plus clair.

La classe DemGrid ci-dessous n’est qu’une enveloppe sur la fonction verbatim de la librairie (LandscapeMaps.CreateFunction -> ImageHeightMapFunction) : elle mappe (u,v) aux coordonnees pixel du PNG d’origine et expose le sommet ; aucune logique d’optimisation, aucun re-echantillonnage, aucun int[] embarque n’y vivent.

using GeneticSharp.Extensions.Mathematic.Functions;   // ImageHeightMapFunction (verbatim @ d05826fd)

// A REAL-ELEVATION landscape from jsboige's verbatim height-map assets (KnownHeightMap, ~2560 px,
// originally acquired via a WMS elevation service). The fork streams them through
// ImageHeightMapFunction (grayscale elevation, inverse-distance interpolation) -- byte-exact @ d05826fd.
// No offline resampling and no int[] grid: the high-definition PNG IS the fitness field. We
// MAXIMISE the grayscale level : the brightest pixel is the highest ground, i.e. the summit.
public sealed class DemGrid : IDisposable
{
    public string Name { get; }
    public KnownHeightMap Map { get; }
    public double LatMin, LatMax, LonMin, LonMax;   // qualitative bbox (display only, from the WMS query)
    private readonly ImageHeightMapFunction _fn;
    private readonly double _w, _h;                 // pixel dimensions of the verbatim PNG
    private double _peakU, _peakV;
    public double ElevMin { get; private set; }
    public double ElevMax { get; private set; }
    public int W => (int)_w;
    public int H => (int)_h;

    public DemGrid(KnownHeightMap map, string name, double latMin, double latMax, double lonMin, double lonMax)
    {
        Map = map; Name = name;
        LatMin = latMin; LatMax = latMax; LonMin = lonMin; LonMax = lonMax;
        _fn = LandscapeMaps.CreateFunction(map);
        var ranges = _fn.Ranges(2);
        _w = ranges[0].max + 1; _h = ranges[1].max + 1;
        ScanExtrema();
    }

    // Elevation (grayscale level, brighter = higher) at normalised (u, v) in [0,1]^2. Delegates to
    // the verbatim ImageHeightMapFunction over pixel coordinates (u -> x west->east, v -> y top->bottom
    // of the north-up source PNG, so v=0 = north and v grows toward the south).
    public double Interp(double u, double v)
    {
        double x = Math.Clamp(u * (_w - 1), 0.0, _w - 1);
        double y = Math.Clamp(v * (_h - 1), 0.0, _h - 1);
        return _fn.Function(new[] { x, y });
    }

    // Normalised (u, v) of the brightest pixel = the search target. Found once, by dense sampling of
    // the verbatim field (the renderer samples the same field when it draws the heatmap).
    public (double u, double v, double elev) GlobalMax() => (_peakU, _peakV, ElevMax);

    private void ScanExtrema()
    {
        double min = double.PositiveInfinity, max = double.NegativeInfinity;
        const int S = 240;
        for (int i = 0; i < S; i++)
            for (int j = 0; j < S; j++)
            {
                double e = Interp((double)i / (S - 1), (double)j / (S - 1));
                if (e < min) min = e;
                if (e > max) { max = e; _peakU = (double)i / (S - 1); _peakV = (double)j / (S - 1); }
            }
        ElevMin = min; ElevMax = max;
    }

    public void Dispose() => _fn.Dispose();
}
Console.WriteLine("DemGrid defini : enveloppe sur KnownHeightMap (ImageHeightMapFunction verbatim), relief a MAXIMISER.");

DemGrid defini : enveloppe sur KnownHeightMap (ImageHeightMapFunction verbatim), relief a MAXIMISER.

// The four ORIGINAL jsboige height maps (KnownHeightMap, ~2560 px, verbatim fork assets). They form
// the zoom cascade Monde -> Plateau -> Himalaya -> Everest : each map is a tighter window on the
// same mountain range, so the summit sharpens as we zoom in. No embedded int[] grid, no ETOPO1
// downsample -- the faithful high-definition PNG is the landscape, read by ImageHeightMapFunction.
var world          = new DemGrid(KnownHeightMap.World,          "Monde",   -56.0,  60.0, -180.0, 180.0);
var tibetanPlateau = new DemGrid(KnownHeightMap.TibetanPlateau, "Plateau",  27.0,  45.0,   70.0, 100.0);
var himalayaArc    = new DemGrid(KnownHeightMap.NepalBhoutan,   "Himalaya", 27.0,  30.5,   83.0,  89.0);
var everestRegion  = new DemGrid(KnownHeightMap.EverestMount,   "Everest",  27.7,  28.3,   86.6,  87.2);
var grids  = new[] { world, tibetanPlateau, himalayaArc, everestRegion };
var labels = new[] { "Monde", "Plateau", "Himalaya", "Everest" };

Console.WriteLine($"{"Carte",-10}{"KnownHeightMap",-18}{"pixels",-12}{"niveau gris",-14}sommet (u, v)");
Console.WriteLine(new string('-', 74));
foreach (var g in grids)
{
    var (pu, pv, _) = g.GlobalMax();
    string px = $"{g.W}x{g.H}", gr = $"{g.ElevMin:F0}..{g.ElevMax:F0}";
    Console.WriteLine($"{g.Name,-10}{g.Map,-18}{px,-12}{gr,-14}({pu:F3}, {pv:F3})");
}
Console.WriteLine("\nLe pic se resserre avec le zoom : du globe a la region du sommet, l'objectif devient net.");

Carte     KnownHeightMap    pixels      niveau gris   sommet (u, v)
--------------------------------------------------------------------------
Monde     World             2560x1440   35..216       (0,849, 0,251)
Plateau   TibetanPlateau    2560x1383   0..219        (0,544, 0,916)
Himalaya  NepalBhoutan      2560x1383   0..251        (0,464, 0,640)
Everest   EverestMount      2560x1383   0..255        (0,498, 0,372)

Le pic se resserre avec le zoom : du globe a la region du sommet, l'objectif devient net.

2. Visualiser les quatre zooms

Même heatmap graphique PNG que MGS-7 (le LandscapeRenderer du fork, rampe de couleur HSV verbatim jsboige @ d05826fd), mais la cible est inversee. MGS-8 minimise ses fonctions analytiques (l’optimum porte le marqueur blanc) ; ici on maximise l’altitude, donc c’est le maximum - le sommet - qui porte le marqueur noir, cible explicite de la recherche. Les basses terres et oceans s’etalent a une extremite de la rampe, les hauts reliefs a l’autre ; le gradient entre les deux rend le bassin d’attraction du pic immediatement lisible. Le nord (haute latitude) est place en haut de la carte.

// Graphic PNG heatmaps of the four zooms, via the fork's SkiaLandscapeRenderer -- the SAME
// renderer as MGS-8 (color ramp + extrema markers verbatim jsboige @ d05826fd). Wrapping only:
// the relief field (DemGrid.Interp over the verbatim KnownHeightMap) is handed to the renderer as
// a Func<double[],double> over the unit square; nothing is reimplemented. The renderer marks the
// global MIN (White) and MAX (Black); since we maximise elevation, the Black marker falls on the
// summit -- the search target. The canvas samples the full-resolution (~2560 px) field at the
// asset's OWN aspect ratio, so the relief reads in true detail and true proportions -- not the old
// 460x330 thumbnail that under-sampled ~24x AND stretched the 16:9 tile into a 1.39 box.
//
// Orientation: the source PNG is north-up (a WMS elevation tile), so DemGrid.Interp reads v=0 as
// the TOP row = north, v growing toward the south. The renderer maps py=0 (top of canvas) to
// yRange.min, so yRange = (0, 1) places v=0 (north) at the top -- a correct north-up map.
// (An earlier version passed yRange = (1, 0) believing v grew south->north; that flipped the maps
// upside down -- the bug report "les cartes sont a l'envers".)

string HeatmapHtml(byte[] png, string caption, int displayWidth)
{
    string b64 = Convert.ToBase64String(png);
    return $"<figure style='margin:6px 0'>"
         + $"<img src='data:image/png;base64,{b64}' style='width:{displayWidth}px;image-rendering:pixelated;border:1px solid #ccc'/>"
         + $"<figcaption style='font:12px sans-serif;color:#555'>{caption}</figcaption></figure>";
}

void ShowRelief(DemGrid g, int displayWidth = 680)
{
    Func<double[], double> field = arr => g.Interp(arr[0], arr[1]);   // (u, v) -> grayscale altitude
    // Canvas at the asset's own aspect ratio (g.W x g.H) and high enough to read the ~2560 px
    // relief in real detail: the source PNG is the ceiling (no detail beyond it), so we sample
    // close to it rather than the old 460x330 thumbnail. height drives width via g.W/g.H so each
    // map keeps its true shape. yRange = (0, 1): py=0 (canvas top) -> v=0 -> north (top of PNG).
    int h = 560;
    int w = (int)Math.Round(h * g.W / (double)g.H);
    byte[] png = SkiaLandscapeRenderer.RenderHeatmapPng(
        field, (0.0, 1.0), (0.0, 1.0), width: w, height: h);
    display(HTML(HeatmapHtml(png,
        $"{g.Name} ({g.Map}) : niveau d'altitude {g.ElevMin:F0}..{g.ElevMax:F0}  |  sommet = pixel le plus clair (marqueur noir)",
        displayWidth)));
}

foreach (var g in grids) ShowRelief(g);

Monde (World) : niveau d'altitude 35..216 | sommet = pixel le plus clair (marqueur noir)

Plateau (TibetanPlateau) : niveau d'altitude 0..219 | sommet = pixel le plus clair (marqueur noir)

Himalaya (NepalBhoutan) : niveau d'altitude 0..251 | sommet = pixel le plus clair (marqueur noir)

Everest (EverestMount) : niveau d'altitude 0..255 | sommet = pixel le plus clair (marqueur noir)

Lecture. Du Monde a l’Everest, deux choses changent ensemble :

• le pic devient net : au zoom grossier (Monde) la zone haute est un plateau elargi ou se melent les grandes chaînes ; au zoom fin (Everest) un sommet unique emerge du relief ;
• le bassin d’attraction se resserre : sur la carte Monde la zone “haute” couvre une large fraction de l’image (facile a toucher au hasard), alors qu’a la region Everest le pic occupe une petite portion d’une petite boite. C’est ce double mouvement - pic plus net dans un espace plus etroit - qui rend le taux de reussite non trivial (section 4).

3. Chercher le sommet avec le moteur MGS

On encapsule le relief dans une DemFitness : IFitness (altitude interpolee = fitness). L’espace de recherche est la boite normalisee [0,1]^2 ; un chromosome porte (u, v). On compare quatre stratégies a budget d’evaluations egal (NFE = population x generations) :

Méthode	Origine	Rôle
GA	DefaultMetaHeuristic (moteur MGS)	reference evolutionnaire
WOA	WhaleOptimisationAlgorithm (compound geometrique du fork)	meta-heuristique assemblee
EO	EquilibriumOptimizer (compound geometrique du fork)	meta-heuristique assemblee
PSO	baseline externe (canon Kennedy-Eberhart)	contrôle hors-bestiaire

GA/WOA/EO passent par le vrai moteur MetaGeneticAlgorithm ; seul le PSO est un essaim ecrit ici a la main, car le fork n’expose pas de PSO.

// Elevation as a fitness to MAXIMISE. Wrapping only: the relief data and the MGS engine
// are untouched. KnownFunctionGenes.AsDoubles reads the gene values (library helper).
public sealed class DemFitness : IFitness
{
    private readonly DemGrid _g;
    public DemFitness(DemGrid g) => _g = g;
    public double Evaluate(IChromosome c)
    {
        var x = KnownFunctionGenes.AsDoubles(c);
        return _g.Interp(x[0], x[1]);     // metres ; higher = better
    }
}

// DoubleArrayChromosome with per-gene bounds so CreateNew() seeds the initial population
// (same helper as MGS-6/MGS-8). Genes are the normalised coordinates (u, v) in [0,1].
public class DoubleArrayChromosome : ChromosomeBase
{
    private readonly double _min, _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();
}

// Deterministic randomization so each (method, zoom, seed) run is reproducible.
public sealed class SeededRandomization : RandomizationBase
{
    private readonly Random _r;
    public SeededRandomization(int seed) => _r = new Random(seed);
    public override int GetInt(int min, int max) => _r.Next(min, max);
    public override float GetFloat() => (float)_r.NextDouble();
    public override double GetDouble() => _r.NextDouble();
}

Console.WriteLine("DemFitness + DoubleArrayChromosome + SeededRandomization definis.");

DemFitness + DoubleArrayChromosome + SeededRandomization definis.

const int Pop = 30, Gens = 30;   // shared budget : NFE = Pop * Gens = 900 evaluations.

// Run the REAL MGS engine on DemFitness with a given metaheuristic ; return best (u,v,elev).
(double u, double v, double elev) RunEngine(DemGrid g, Func<IMetaHeuristic> buildMh, int seed)
{
    RandomizationProvider.Current = new SeededRandomization(seed);
    var fit = new DemFitness(g);
    var adam = new DoubleArrayChromosome(new[] { 0.5, 0.5 }, 0.0, 1.0);
    var pop = new MetaPopulation(Pop, Pop, adam);
    var ga = new MetaGeneticAlgorithm(pop, fit, new EliteSelection(),
        new UniformCrossover(0.5f), new UniformMutation(true), buildMh());
    ga.Termination = new GenerationNumberTermination(Gens);
    ga.Start();
    // MetaPopulation is order-preserving: derive best via fitness, not CurrentGeneration.BestChromosome.
    var best = ga.Population.CurrentGeneration.Chromosomes.OrderByDescending(c => c.Fitness).First();
    var x = ((DoubleArrayChromosome)best).GetDoubleValues();
    double u = Math.Clamp(x[0], 0, 1), v = Math.Clamp(x[1], 0, 1);
    return (u, v, g.Interp(u, v));
}

IMetaHeuristic BuildGA() => new DefaultMetaHeuristic();

IMetaHeuristic BuildWOA()
{
    var woa = new WhaleOptimisationAlgorithm { MaxGenerations = Gens };
    woa.SetGeometricConverter(new GeometricConverter<double> {
        GeneToDoubleConverter = (_, val) => val, DoubleToGeneConverter = (_, d) => d });
    return woa.Build();
}

IMetaHeuristic BuildEO()
{
    var eo = new EquilibriumOptimizer { MaxGenerations = Gens };
    eo.SetGeometricConverter(new GeometricConverter<double> {
        GeneToDoubleConverter = (_, val) => val, DoubleToGeneConverter = (_, d) => d });
    return eo.Build();
}

// PSO : explicit EXTERNAL baseline (no PSO in the fork). Canonical Kennedy-Eberhart swarm on
// the same DemFitness, same NFE budget (swarm * iters = Pop * Gens).
(double u, double v, double elev) RunPSO(DemGrid g, int seed)
{
    var rng = new Random(seed);
    int swarm = Pop, iters = Gens;
    double w = 0.7, c1 = 1.5, c2 = 1.5;
    var px = new double[swarm]; var py = new double[swarm];
    var vx = new double[swarm]; var vy = new double[swarm];
    var bx = new double[swarm]; var by = new double[swarm]; var bf = new double[swarm];
    double gx = 0, gy = 0, gf = double.NegativeInfinity;
    for (int i = 0; i < swarm; i++)
    {
        px[i] = rng.NextDouble(); py[i] = rng.NextDouble();
        vx[i] = (rng.NextDouble() - 0.5) * 0.1; vy[i] = (rng.NextDouble() - 0.5) * 0.1;
        bx[i] = px[i]; by[i] = py[i]; bf[i] = g.Interp(px[i], py[i]);
        if (bf[i] > gf) { gf = bf[i]; gx = px[i]; gy = py[i]; }
    }
    for (int t = 1; t < iters; t++)
        for (int i = 0; i < swarm; i++)
        {
            vx[i] = w * vx[i] + c1 * rng.NextDouble() * (bx[i] - px[i]) + c2 * rng.NextDouble() * (gx - px[i]);
            vy[i] = w * vy[i] + c1 * rng.NextDouble() * (by[i] - py[i]) + c2 * rng.NextDouble() * (gy - py[i]);
            px[i] = Math.Clamp(px[i] + vx[i], 0, 1); py[i] = Math.Clamp(py[i] + vy[i], 0, 1);
            double f = g.Interp(px[i], py[i]);
            if (f > bf[i]) { bf[i] = f; bx[i] = px[i]; by[i] = py[i]; }
            if (f > gf) { gf = f; gx = px[i]; gy = py[i]; }
        }
    return (gx, gy, gf);
}

var sm = RunEngine(everestRegion, BuildWOA, 0);
var (tu, tv, te) = everestRegion.GlobalMax();
Console.WriteLine($"Smoke WOA @ EverestRegion : best=({sm.u:F3},{sm.v:F3}) niveau={sm.elev:F0}  |  cible=({tu:F3},{tv:F3}) niveau={te:F0}");

Smoke WOA @ EverestRegion : best=(0,501,0,412) niveau=249  |  cible=(0,498,0,372) niveau=255

4. Taux de reussite x 4 zooms

On declare une recherche reussie si le meilleur point trouve tombe a une distance normalisee <= tau de la cellule du maximum global (rayon tau = 0.06, soit ~6% du cote de la boite). Pour chaque (méthode, zoom) on lance Seeds graines independantes et on rapporte le pourcentage de reussites - a budget d’evaluations identique pour les quatre méthodes.

const double Tau = 0.06;     // success radius : ~6% of the box side
const int Seeds = 10;

bool Hit(DemGrid g, double u, double v)
{
    var (gu, gv, _) = g.GlobalMax();
    double du = u - gu, dv = v - gv;
    return Math.Sqrt(du * du + dv * dv) <= Tau;
}

double Rate(DemGrid g, Func<DemGrid, int, (double u, double v, double elev)> run)
{
    int hits = 0;
    for (int s = 0; s < Seeds; s++) { var r = run(g, s); if (Hit(g, r.u, r.v)) hits++; }
    return 100.0 * hits / Seeds;
}

var methods = new (string name, Func<DemGrid, int, (double u, double v, double elev)> run)[]
{
    ("GA",  (g, s) => RunEngine(g, BuildGA,  s)),
    ("PSO", (g, s) => RunPSO(g, s)),
    ("WOA", (g, s) => RunEngine(g, BuildWOA, s)),
    ("EO",  (g, s) => RunEngine(g, BuildEO,  s)),
};

Console.WriteLine($"Taux de reussite (%) -- {Seeds} graines, budget NFE = {Pop * Gens}, tau = {Tau}\n");
Console.WriteLine(string.Format("{0,-6}{1,10}{2,10}{3,10}{4,10}", "methode", "Monde", "Plateau", "Himalaya", "Everest"));
Console.WriteLine(new string('-', 46));
foreach (var m in methods)
{
    var sb = new System.Text.StringBuilder(string.Format("{0,-6}", m.name));
    foreach (var g in grids) sb.Append(string.Format("{0,9:F0}%", Rate(g, m.run)));
    Console.WriteLine(sb.ToString());
}

Taux de reussite (%) -- 10 graines, budget NFE = 900, tau = 0,06

methode     Monde   Plateau  Himalaya   Everest
----------------------------------------------
GA           50%        0%       10%       40%
PSO          80%        0%       20%       40%
WOA          50%        0%       30%       40%
EO           80%       10%        0%       60%

Lecture (No Free Lunch). Les chiffres ci-dessus sont produits a l’exécution - on les lit sans les maquiller :

• Aucune méthode ne domine partout. Sur ce relief et a ce budget, c’est même le PSO (baseline externe, hors-bestiaire) qui mene plusieurs colonnes : l’assemblage geometrique WOA/EO n’a pas d’avantage decisif sur un essaim simple. La sophistication n’est pas gratuite - signature du theoreme No Free Lunch.
• Le taux n’est pas monotone en zoom. Un pic plus net (Everest) est plus dur a localiser précisément, mais il vit dans une boite plus petite ou le même tau couvre proportionnellement plus de terrain : les deux effets se compensent differemment selon la méthode.
• Certaines colonnes frolent 0 %. Quand le maximum tombe pres d’un bord de la carte ou dans un bassin très etroit, le rayon tau = 0.06 devient serre et toutes méthodes peinent. C’est un cas-limite honnete, pas un bug - le smoke-test de la section 3 confirme que le moteur trouve bien de la haute altitude.

5. Convergence : la population qui se contracte vers le sommet

La section précédente agregeait le taux de reussite sur N runs. Ici on regarde un seul run se jouer : on capture la population du GA a quelques generations selectionnees, sur la region Everest, et on en fait un flipbook. Le nuage d’individus (violet) se resserre generation après generation vers le sommet (cyan = meilleur courant ; marqueur noir = altitude maximale, la cible). C’est le même mécanisme orchestral qu’en MGS-8 – on s’abonne a l’événement GenerationRan du MetaGeneticAlgorithm (declenche après chaque generation), on instantane CurrentGeneration.Chromosomes, puis on rend chaque image via le même SkiaLandscapeRenderer.RenderHeatmapPng(..., population, best) et la surimpression verbatim (diamants BlueViolet / Aqua de jsboige). Aucune nouvelle fonction de rendu, aucun changement de librairie, aucun bump de submodule : pur port-fidele @ d05826fd, applique au relief reel.

Gotcha order-preserving (reutilise de MGS-8). MetaPopulation n’appelle jamais Generation.End() ; CurrentGeneration.BestChromosome est null dans le handler. On derive le meilleur via Chromosomes.OrderByDescending(Fitness).First() – exactement comme RunEngine.

// Convergence flipbook on the Everest relief -- the SAME GenerationRan orchestration as MGS-8
// (#3199, port-fidele @ d05826fd): the REAL MetaGeneticAlgorithm fires GenerationRan after each
// generation; we snapshot the live population at every generation and hand each frame to the
// fork's SkiaLandscapeRenderer (individuals = BlueViolet diamonds, current best = Aqua, summit =
// the renderer's Black max-marker). The sampled frames are then assembled into ONE looping animated
// GIF via SkiaLandscapeRenderer.EncodeAnimatedGif -- a co-evolution feature added to the fork
// (jsboige/MetaGeneticSharp#29 + #30, See #1203): SkiaSharp ships no animated-GIF encoder, so the
// GIF89a container + a median-cut palette + giflib-schedule LZW are authored there. The win:
// a real image/gif renders on GitHub's static notebook viewer, where a JS/CSS flipbook would be
// stripped. We pass maxColors:64 to #30's palette parameter -- a smooth grayscale relief barely
// compresses at 256 colors (adjacent indices rarely repeat -> no LZW runs), whereas banding it to
// 64 colors creates the flat runs LZW needs, keeping the embedded GIF compact while the saturated
// violet/cyan/black markers survive quantization. Pure orchestration over the verbatim renderer
// (color ramp + extrema markers verbatim jsboige @ d05826fd) and the DemGrid field from section 1.
//
// Budget tuned for legibility (denser + longer than the Pop=30/Gens=30 success-rate sweep, so the
// contraction reads): 200 individuals, 40 generations. GA (DefaultMetaHeuristic via BuildGA), seed 0.

List<(int gen, List<double[]> pop, double[] best)> RunGaTraced(DemGrid g, int seed, ISet<int> snapGens)
{
    RandomizationProvider.Current = new SeededRandomization(seed);
    var fit = new DemFitness(g);
    var adam = new DoubleArrayChromosome(new[] { 0.5, 0.5 }, 0.0, 1.0);
    var pop = new MetaPopulation(200, 200, adam);
    var ga = new MetaGeneticAlgorithm(pop, fit, new EliteSelection(),
        new UniformCrossover(0.5f), new UniformMutation(true), BuildGA());
    ga.Termination = new GenerationNumberTermination(40);
    var trace = new List<(int, List<double[]>, double[])>();
    int genCount = 0;
    ga.GenerationRan += (s, e) =>
    {
        genCount++;
        if (!snapGens.Contains(genCount)) return;
        var chroms = ga.Population.CurrentGeneration.Chromosomes;
        var snap = chroms.Select(c => ((DoubleArrayChromosome)c).GetDoubleValues()).ToList();
        var best = ((DoubleArrayChromosome)chroms.OrderByDescending(c => c.Fitness).First()).GetDoubleValues();
        trace.Add((genCount, snap, best));
    };
    ga.Start();
    return trace;
}

// Sample 20 of the 40 generations, weighted toward the early contraction (where the cloud actually
// collapses) and sparser over the static tail: dense gens 1..10, then every 2nd to 20, every 4th to
// 40. This keeps the animation smooth where it matters and the embedded GIF compact.
var snapList = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40 };
var snapSet = new HashSet<int>(snapList);
var trace = RunGaTraced(everestRegion, 0, snapSet);
var byGen = new Dictionary<int, int>();
for (int i = 0; i < trace.Count; i++) { byGen[trace[i].gen] = i; }
var (su, sv, se) = everestRegion.GlobalMax();
Console.WriteLine($"Flipbook convergence GA @ EverestRegion : {trace.Count} frames echantillonnees sur 40 generations.");
Console.WriteLine($"  -> cible = sommet ({su:F3}, {sv:F3}) niveau {se:F0}");

// Render one heatmap PNG per sampled generation (verbatim renderer), once.
// Orientation matches ShowRelief (section 2): yRange = (0, 1) -> north up. Canvas kept small
// (240x180) so the 20-frame GIF stays compact -- the flipbook shows the contraction, not the relief.
Func<double[], double> everestField = arr => everestRegion.Interp(arr[0], arr[1]);
var frames = new List<byte[]>(trace.Count);
foreach (var (gen, snap, best) in trace)
{
    frames.Add(SkiaLandscapeRenderer.RenderHeatmapPng(
        everestField, (0.0, 1.0), (0.0, 1.0), width: 240, height: 180, population: snap, best: best));
}

// Item 4 : assemble the per-generation frames into ONE looping animated GIF (image/gif).
// maxColors:64 (fork #30) bands the grayscale relief into LZW-compressible flat runs.
byte[] gif = SkiaLandscapeRenderer.EncodeAnimatedGif(frames, delayCentiseconds: 12, loopCount: 0, maxColors: 64);
display(HTML($"<figure style='margin:6px 0'>"
    + $"<img src='data:image/gif;base64,{Convert.ToBase64String(gif)}' style='width:380px;image-rendering:pixelated;border:1px solid #ccc'/>"
    + $"<figcaption style='font:12px sans-serif;color:#555'>Convergence animee ({frames.Count} generations) : le nuage violet (individus) se contracte vers le sommet (marqueur noir), meilleur individu courant en cyan. Cible = pixel le plus clair.</figcaption></figure>"));
Console.WriteLine($"  -> GIF anime : {frames.Count} frames, {gif.Length / 1024.0:F1} KB (image/gif, lisible sur le viewer statique GitHub).");

// At-a-glance static strip : a few key generations side by side (before / mid / after).
int[] stripGens = { 1, 10, 20, 40 };
foreach (int g in stripGens)
{
    int fi = byGen[g];   // sampled generations are sparse: look up the frame by generation number.
    var (gen, snap, best) = trace[fi];
    display(HTML(HeatmapHtml(frames[fi],
        $"Generation {gen} : {snap.Count} individus (violet) -- meilleur en cyan, sommet = marqueur noir", 240)));
}

Flipbook convergence GA @ EverestRegion : 20 frames echantillonnees sur 40 generations.
  -> cible = sommet (0,498, 0,372) niveau 255

Convergence animee (20 generations) : le nuage violet (individus) se contracte vers le sommet (marqueur noir), meilleur individu courant en cyan. Cible = pixel le plus clair.

  -> GIF anime : 20 frames, 495,1 KB (image/gif, lisible sur le viewer statique GitHub).

Generation 1 : 200 individus (violet) -- meilleur en cyan, sommet = marqueur noir

Generation 10 : 200 individus (violet) -- meilleur en cyan, sommet = marqueur noir

Generation 20 : 200 individus (violet) -- meilleur en cyan, sommet = marqueur noir

Generation 40 : 200 individus (violet) -- meilleur en cyan, sommet = marqueur noir

Lecture. Au fil des generations, le nuage violet se resserre et grimpe vers le marqueur noir du sommet : la population converge. Le mouvement n’est ni uniforme ni garanti – des individus retardataires se fixent dans des bassins secondaires, et le meilleur (cyan) ne rejoint le sommet que si le bassin d’attraction de l’Everest a ete atteint. C’est l’image dynamique du taux de reussite de la section 4 : ce que la statistique agregeait sur N runs, on le voit ici se jouer sur un seul. A comparer avec le flipbook MGS-8 (Rastrigin) : la-bas la lecon etait la multimodalite (plusieurs bassins concurrents) ; ici, sur un relief reel, le sommet est unique mais le terrain est irregulier – la difficulte est de localiser un pic etroit, pas de choisir entre plusieurs.

5b. Voir un benchmark a 5 dimensions : la projection N-D

Le relief de l’Everest (section 2) est un paysage 2D : chaque point \((u, v)\) a une altitude, et l’oeil le lit directement. Mais un benchmark d’optimisation classique comme Schwefel vit en dimension \(N \geq 5\) – son optimum global est un pic isole au milieu d’un plateau bruite, et ce pic n’est visible qu’en projetant les dimensions cachees sur le plan \((x_0, x_1)\).

Le rendu graphique du fork offre desormais une surcharge N-D : SkiaLandscapeRenderer.RenderHeatmapPng(function, dimension, nbSamples, rng, ...). Pour chaque pixel du canvas 2D, elle tire nbSamples fois les coordonnees cachees \(x_2 \dots x_{N-1}\) uniformement dans la range recommandee, evalue la fitness, et garde le MAX – le meme operateur MAX que le controleur Gtk# original de jsboige @ d05826fd (LandscapeExplorerSampleController.GetFunctionValue, lignes 640-674). La ou l’echantillonnage est assez dense, le pic isole de Schwefel perce le plateau et devient visible : c’est exactement la signature d’un optimum dur a trouver – et donc le terrain ou un metaheuristique doit gagner sa vie.

Miroir du port #7483 (Prong-B). La surcharge publique est livree dans le submodule MetaGeneticSharp (PR #42, sha 0433fad0c, additive +46/-0) ; NDMaxProjectionAdapter reste internal sealed. Ici on exerce cette capacite depuis le notebook CoursIA, sur un benchmark a 5 dimensions via le meme rendu graphique que la section 2.

Verification sur rendu deterministe (MetaGeneticSharp #49) : le marqueur NOIR (pixel MAX) tombe a ~10 px de l’optimum theorique (420,97/1000 de la trame, soit dans le bassin du pic), lecture verifiee sur le rendu commite ci-dessus – la position exacte du marqueur depend des tirages par pixel, sa presence dans le bassin est le fait stable.

// --- Projection N-D : Schwefel en dimension 5 projete sur le plan (x0, x1) ---
// Nouvelle surcharge publique du renderer : RenderHeatmapPng(IFitness, int dimension, ...).
// Pour chaque pixel, nbSamples tirages uniformes des coords cachees x2..x4, on garde le MAX
// (operateur verbatim du controleur Gtk# @ d05826fd). Le pic isole de Schwefel perce le plateau.
using GeneticSharp.Extensions.Mathematic.Functions;   // SchwefelFitness (IFitness)

var schwefel5 = new SchwefelFitness();                // IFitness, optimum global isole
int dim = 5;                                           // 3 coords cachees (x2, x3, x4) echantillonnees
int nbSamples = 12;                                    // tirages uniformes / pixel (verbatim controller = 10 ; +2 reduit le bruit de projection)
var rng = new Random(42);                              // seedable -> heatmap reproductible

// Canvas carre (Schwefel est symetrique : la range recommandee est la meme sur chaque axe).
byte[] pngNd = SkiaLandscapeRenderer.RenderHeatmapPng(
    schwefel5, dim, nbSamples, rng, width: 480, height: 480);

// Meme affichage HTML que la section 2 (display + base64), rien de reimplemente.
display(HTML(HeatmapHtml(pngNd,
    $"Schwefel dim={dim} projete N-D vers 2D (MAX sur {nbSamples} tirages/pixel) : le pic isole perce le plateau bruite",
    520)));

// Schwefel : optimum theorique isole = 418.9829 * N (atteint en x_i = 420.9687 pour tout i).
// Le marqueur NOIR du heatmap (pixel MAX) tombe dans le bassin de cet optimum, pas sur le
// plateau bruite environnant -- c'est le diagnostic visuel que le pic a perce le bruit de projection.
Console.WriteLine($"Schwefel dim={dim} : optimum theorique = {418.9829 * dim:F2} (en x_i = 420.9687). "
    + $"Heatmap {480}x{480} rendu via la surcharge N-D publique (MAX sur {nbSamples} tirages/pixel).");

Schwefel dim=5 projete N-D vers 2D (MAX sur 12 tirages/pixel) : le pic isole perce le plateau bruite

Schwefel dim=5 : optimum theorique = 2094,91 (en x_i = 420.9687). Heatmap 480x480 rendu via la surcharge N-D publique (MAX sur 12 tirages/pixel).

Lecture 5b – pourquoi ce pic est dur a trouver

Schwefel est le benchmark canonique du deceptive landscape : la majorite de l’espace est un plateau bruite qui ne guide pas vers l’optimum, et l’optimum lui-meme est un pic etroit, isole, loin du centre. Un algorithme qui exploite le gradient local (hill-climber, gradient ascent) se fait pieger par le plateau ; un metaheuristique avec diversification (GA, PSO, WOA – les memes que la section 3 sur l’Everest) a une chance de tirer un individu dans le bassin du pic.

La projection N-D rend ce phenomene visible : le pic isole apparait comme une tache isolee dans un plan bruite. Avec trop peu d’echantillons (nbSamples faible), le pic est masque par le bruit de projection et la heatmap ressemble a du bruit uniforme – c’est la signature d’un optimum intrinsequement dur. Avec assez d’echantillons, il perce : c’est ce que rend la cellule ci-dessus. Capacite exercee (Prong-B) : la surcharge N-D est la signature distinctive du renderer fork (un renderer 2D standard ne peut pas montrer une dimension >= 5) ; ici elle est invoquee sur un benchmark ou cette capacite est necessaire, pas optionnelle.

6. Exercices

Trois exercices completables hors-ligne (aucune donnee supplementaire requise). Decommentez et completez ; chaque cellule s’execute déjà telle quelle (stub conforme).

Exercice 1 — Sensibilite a la tolerance tau

Le taux de reussite depend du rayon d’acceptation tau. Re-tabulez les 4 méthodes x 4 zooms pour tau dans { 0.03, 0.06, 0.12 } et observez comment la hiérarchie des méthodes bouge selon qu’on est strict ou tolerant.

Objectif. Mesurer la sensibilite d’une métaheuristique au rayon de reussite.

Indices. - Parametrez Hit/Rate pour accepter tau en argument, puis re-affichez la table de la section 4. - Un tau petit = critere strict (peu de méthodes reussissent) ; un tau grand = tolerant. - Une méthode robuste garde une hiérarchie stable quand tau varie.

// Exercice 1 : sensibilite a la tolerance tau.
// Le taux de reussite depend du rayon d'acceptation. Re-tabulez les 4 methodes x 4 zooms
// pour tau dans { 0.03, 0.06, 0.12 } et observez comment la hierarchie des methodes bouge.
// TODO etudiant :
//   foreach (double tau in new[] { 0.03, 0.06, 0.12 }) {
//       // Indice : copiez Hit/Rate en parametrant tau, puis ré-affichez la table.
//   }

Console.WriteLine("Exercice a completer : taux de reussite en fonction de tau (0.03 / 0.06 / 0.12).");

Exercice a completer : taux de reussite en fonction de tau (0.03 / 0.06 / 0.12).

Exercice 2 — Ajouter une baseline « hill-climber »

Ajoutez une 5e ligne au tableau : un hill-climber (montee de gradient stochastique). Depart aleatoire, petits pas (u, v) ± epsilon, on garde le pas s’il monte. Même budget NFE = Pop * Gens que les métaheuristiques. Ou se classe-t-il face a GA/PSO/WOA/EO ?

Objectif. Comparer une recherche locale gloutonne aux métaheuristiques populationnelles.

Indices. - 1 seul point courant, NFE = Pop * Gens evaluations, pas epsilon ~ 0.05, clamp [0,1]. - Un hill-climber est vite piege dans un optimum local sur un relief multimodal comme l’Everest. - C’est précisément ce qui justifie les métaheuristiques populationnelles (diversite).

// Exercice 2 : ajouter une baseline "hill-climber" (montee de gradient stochastique).
// Une 5e ligne au tableau : depart aleatoire, petits pas (u,v) +- epsilon, on garde le pas
// s'il monte. Meme budget NFE = Pop * Gens. Ou se classe-t-il face a GA/PSO/WOA/EO ?
// TODO etudiant :
//   (double u, double v, double elev) RunHillClimber(DemGrid g, int seed) {
//       // Indice : 1 point courant, NFE = Pop*Gens evaluations, pas epsilon ~ 0.05, clamp [0,1].
//       return (0, 0, 0); // remplacer
//   }

Console.WriteLine("Exercice a completer : baseline hill-climber, meme budget NFE.");

Exercice a completer : baseline hill-climber, meme budget NFE.

Exercice 3 — Taux de reussite vs budget NFE

Faites varier le budget NFE (par ex. Pop * Gens dans { 200, 450, 900, 1800 }) pour la WOA sur everestRegion et tracez (en ASCII ou en colonne) le taux de reussite correspondant. Le scaling est-il lineaire, sous-lineaire, ou a seuil ?

Objectif. Etudier la convergence d’une métaheuristique en fonction du budget.

Indices. - Ajustez Gens = nfe / Pop (gardez Pop fixe), relancez Rate(everestRegion, ...). - Un seuil (NFE minimal pour atteindre le sommet) est plus informatif qu’une pente lineaire. - Comparez la forme de la courbe WOA a celle d’un hill-climber (exercice 2).

// Exercice 3 : courbe taux de reussite vs budget, sur la region Everest.
// Faites varier le budget NFE (par ex. Pop*Gens dans { 200, 450, 900, 1800 }) pour la WOA
// sur everestRegion et tracez (en ASCII ou en colonne) le taux de reussite correspondant.
// TODO etudiant :
//   foreach (int nfe in new[] { 200, 450, 900, 1800 }) {
//       // Indice : ajustez Gens = nfe / Pop, relancez Rate(everestRegion, ...), affichez.
//   }

Console.WriteLine("Exercice a completer : taux de reussite vs budget NFE (region Everest).");

Exercice a completer : taux de reussite vs budget NFE (region Everest).

Conclusion

Élément	Ce que MGS-9 montre
Relief reel comme fitness	les cartes d’altitude originales de jsboige (KnownHeightMap), lues verbatim via ImageHeightMapFunction, maximisees (trouver le sommet)
Rendu	heatmap graphique PNG via le LandscapeRenderer du fork, coherent avec MGS-8 ; le sommet (max) porte le marqueur noir, en vraie resolution (~2560 px)
Moteur	GA / WOA / EO via le vrai MetaGeneticAlgorithm + compounds geometriques
Baseline	PSO externe explicite (le fork n’a pas de PSO) - contrôle a budget egal
Lecon	bassin d’attraction vs taille de l’espace : le sommet se resserre avec le zoom, et aucune méthode ne gagne partout (No Free Lunch)

Pour aller plus loin : MGS-6 - Benchmarks (WOA vs Islands sur fonctions analytiques), MGS-8 - Landscape Explorer (paysages synthetiques et biais de centre).

Données : cartes d’altitude KnownHeightMap (jsboige), ressources PNG embarquees du fork MetaGeneticSharp.Extensions (~2560 px), lues via ImageHeightMapFunction verbatim @ d05826fd.