MGS-7b : projection multi-dimensionnelle des paysages (RenderHeatmap N-D)

← MGS-7 TSP · MGS-8 LandscapeExplorer →

Pourquoi un MGS-7b ?

MGS-6 a présenté les 10 fonctions canoniques de KnownFunctions.cs et montré qu’elles peuvent être visualisées en 2-D via KnownFunctionLandscape.RenderHeatmap. Mais une vraie métaheuristique optimise dans des espaces de dimension bien supérieure (Rastrigin est intéressant à \(n=30\), Schwefel a un optimum trompeur en \(n \geq 10\), Ackley a une « bassine » de minima locaux qu’il faut sonder avec de l’aléatoire). La question naturelle est alors : comment rendre visible un paysage au-delà de 2 dimensions ?

C’est exactement le rôle de la surcharge N-D ajoutée à KnownFunctionLandscape :

using var heatmap = KnownFunctionLandscape.RenderHeatmap(
    new RastriginFitness(),
    dimension: 30,        // hidden coords 2..29 sample dans la boîte recommandée
    nbSamples: 50,        // nombre de tirages uniformes par pixel pour la projection MAX
    rng: new Random(42),  // reproductibilité
    width: 200, height: 200);

L’algorithme est verbatim celui du contrôleur Gtk# LandscapeExplorerSampleController. GetFunctionValue (lignes 640-674 du fork jsboige @ d05826fd, branche Metaheuristics) : pour chaque pixel \((x, y)\), on échantillonne \(N_{\text{samples}}\) fois les coordonnées cachées \(x_2, \ldots, x_{N-1}\) uniformément dans leur intervalle, et on retient le MAX de la fitness. C’est la projection dite « MAX-of-uniform-samples » — elle fait ressortir les pics accessibles depuis le point visible \((x, y)\) en autorisant les coordonnées cachées à varier librement, ce qui répond à la question « où peut m’envoyer la métaheuristique si je relâche temporairement les variables que je n’affiche pas ? ».

Ce notebook

  1. Préliminaire : charger le pont N-D et vérifier que la nouvelle surcharge est exposée.
  2. Sphère 2-D vs 5-D : démontrer que la projection N-D change effectivement la heatmap quand on monte en dimension, et que le bug upstream coordsRange = min - min = 0 est bel et bien corrigé.
  3. Rastrigin en \(n = 2, 5, 10, 30\) : voir comment le paysage « vraiment multimodal » se déforme au-delà de 2 dimensions.
  4. Schwefel en \(n = 5, 30\) : voir comment l’optimum trompeur (loin du centre) émerge.
  5. Ackley en \(n = 2, 30\) : voir comment la bassine centrale de minima locaux se degrade en projection N-D.
  6. Exercice : explorer la convergence de la projection en fonction de nbSamples.

Convention du notebook. Toutes les visualisations sont des PNG produits par KnownFunctionLandscape.RenderHeatmap (le moteur 2-D historique), étendus au N-D via le bridge NDMaxProjectionAdapter codé verbatim à partir du Gtk# controller. Pas de workaround dégradé : le pipeline SOTA est utilisé bout-en-bout (cf. règle H du pr-review-discipline.md).

// Build prereq (submodule path, MGS-series canonical Debug config):
//   git submodule update --init --recursive MyIA.AI.Notebooks/Search/MetaGeneticSharp
//   dotnet build ../MetaGeneticSharp/MetaGeneticSharp.sln -c Debug
// (Debug output matches PR #7595/#7598/#7601-#7614 sweep of MGS-3/4/6/7/8/9/10/11/12-19.)
#r "..\MetaGeneticSharp\src\MetaGeneticSharp.Extensions\bin\Debug\net9.0\MetaGeneticSharp.Extensions.dll"

using MetaGeneticSharp;
using GeneticSharp;

// Sanity check: la surcharge N-D est bien exposée.
var ndOverloads = typeof(KnownFunctionLandscape).GetMethods()
    .Where(m => m.Name == "RenderHeatmap" && m.GetParameters()
        .Any(p => p.Name == "dimension" && p.ParameterType == typeof(int)))
    .ToList();

Console.WriteLine($"Surcharges N-D RenderHeatmap(..., int dimension, ...) exposées : {ndOverloads.Count}");
foreach (var m in ndOverloads)
{
    var ps = string.Join(", ", m.GetParameters().Select(p => $"{{ {p.ParameterType.Name} {p.Name} }}"));
    Console.WriteLine($"  - {m.Name}({ps})");
}
Surcharges N-D RenderHeatmap(..., int dimension, ...) exposées : 2
  - RenderHeatmap({ IFitness fitness }, { Int32 dimension }, { Int32 nbSamples }, { Random rng }, { Int32 width }, { Int32 height })
  - RenderHeatmap({ IFitness fitness }, { ValueTuple`2 xRange }, { ValueTuple`2 yRange }, { Int32 dimension }, { Int32 nbSamples }, { Random rng }, { Int32 width }, { Int32 height })

Sphère 2-D vs 5-D : preuve que la projection fonctionne

La sphère est \(f(\vec x) = -\sum_i x_i^2\) (négative car le moteur maximise). En 2-D, le paysage est un bol centré à l’origine. En 5-D, les coordonnées \(x_2, x_3, x_4\) sont libres dans \([-5.12, 5.12]\) et la projection MAX retient le plus accessible des bols.

Différence attendue : la heatmap 2-D a un minimum global (= optimum, marqué Noir) à \((0, 0)\). La heatmap 5-D, elle, garde \((0, 0)\) comme candidat à un optimum mais le MAX sur les coordonnées cachées peut faire sortir d’autres pixels au-dessus : on doit voir une heatmap plus rouge dans la projection N-D (les autres pixels voient leurs coordonnées cachées prendre des valeurs quasi-nulles par chance, ce qui ramène leur fitness près de 0).

NB : c’est précisément le bug coordsRange = min - min = 0 qui était dans le verbatim Gtk# et qui pinait les coordonnées cachées à \(-5.12\) — la correction est documentée dans KnownFunctionLandscape.cs (ligne 86 : coordsRange = max - min).

// Sphère 2-D : optimum noir au centre, gradient rouge-vert radial.
using System.IO;
using (var h2D = KnownFunctionLandscape.RenderHeatmap(
    new SphereFitness(), dimension: 2, nbSamples: 1,
    width: 100, height: 100))
{
    File.WriteAllBytes(@"assets\landscape_multidim_sphere_2d.png", h2D.ToPngGdi());
    var (px, py) = h2D.ToPixel(0.0, 0.0);
    Console.WriteLine($"Sphère 2-D — pixel (0,0) = {h2D.Bitmap.GetPixel(px, py)} (attendu: Black = optimum).");
}

// Sphère 5-D : MAX projection sur 3 coordonnées cachées dans [-5.12, 5.12].
var rng = new Random(2026);
using (var h5D = KnownFunctionLandscape.RenderHeatmap(
    new SphereFitness(), dimension: 5, nbSamples: 50, rng: rng,
    width: 100, height: 100))
{
    File.WriteAllBytes(@"assets\landscape_multidim_sphere_5d.png", h5D.ToPngGdi());
    var (px, py) = h5D.ToPixel(0.0, 0.0);
    Console.WriteLine($"Sphère 5-D — pixel (0,0) = {h5D.Bitmap.GetPixel(px, py)} (la projection MAX sort de l'optimum).");
}
Sphère 2-D — pixel (0,0) = Color [A=255, R=255, G=0, B=0] (attendu: Black = optimum).
Sphère 5-D — pixel (0,0) = Color [A=255, R=255, G=47, B=0] (la projection MAX sort de l'optimum).

Rastrigin en \(n = 2, 5, 10, 30\) : le multimodal devient lisible

Rastrigin est l’archétype du paysage piégeux : \(f(\vec x) = -10n - \sum_i (x_i^2 - 10\cos(2\pi x_i))\). En 2-D, on voit nettement les cuvettes locales alignées sur une grille. Mais en 30 dimensions, la métaheuristique doit échapper à un nombre astronomique de minima locaux (\(\approx 10^{30}\) cuvettes). La projection MAX capture cette « densité de minima » : plus la dimension monte, plus la heatmap devient rouge, signe que depuis presque chaque \((x, y)\) on peut trouver un point caché qui monte très haut.

L’observation directe : la heatmap Rastrigin-n devient de plus en plus rouge au fur et à mesure que \(n\) monte, parce que les cuvettes cachées pullulent. C’est ce que la métaheuristique « voit » quand elle opère en dimension supérieure — l’intuition du praticien pour calibrer la taille de population et le nombre de redémarrages.

Caveat sur le rendu à dim=10 / nbSamples=25. Le pixel noir observé à (0, 0) pour dim=10 n’est pas un défaut d’interprétation, mais un artefact du passage « heatmap bruitée » (peu de tirages) → « heatmap lisse » (plus de tirages) à mesure que nbSamples monte. Pour dim=2, la projection ne tire qu’une coordonnée cachée avec nbSamples=25 : chaque pixel voit 25 maxima, le MAX final est donc un vrai MAX de 25 valeurs souvent hautes → palette saturée rouge. Pour dim=10, 9 coordonnées cachées sont échantillonnées chacune 25 fois pour chaque pixel : la projection MAX lisse les cuvettes, et le pixel central (0, 0) capture l’optimum profond \(f(\vec 0) = 0\) → noir. C’est le même mécanisme que l’Exercice 1 ci-dessous (convergence de nbSamples) — dim=10 suffit à exposer la concentration près de 0 que dim=2 masque par son faible nombre de coordonnées cachées.

using System.IO;
var rng = new Random(42);

foreach (int dim in new[] { 2, 5, 10, 30 })
{
    using var h = KnownFunctionLandscape.RenderHeatmap(
        new RastriginFitness(), dimension: dim, nbSamples: 25, rng: rng,
        width: 120, height: 120);

    var path = $@"assets\landscape_multidim_rastrigin_d{dim}.png";
    File.WriteAllBytes(path, h.ToPngGdi());

    var (px, py) = h.ToPixel(0.0, 0.0);
    Console.WriteLine($"Rastrigin dim={dim,2} — pixel (0,0) = {h.Bitmap.GetPixel(px, py)} (PNG: {path}).");
}
Rastrigin dim= 2 — pixel (0,0) = Color [A=255, R=0, G=0, B=0] (PNG: assets\landscape_multidim_rastrigin_d2.png).
Rastrigin dim= 5 — pixel (0,0) = Color [A=255, R=255, G=134, B=0] (PNG: assets\landscape_multidim_rastrigin_d5.png).
Rastrigin dim=10 — pixel (0,0) = Color [A=255, R=255, G=203, B=0] (PNG: assets\landscape_multidim_rastrigin_d10.png).
Rastrigin dim=30 — pixel (0,0) = Color [A=255, R=146, G=255, B=0] (PNG: assets\landscape_multidim_rastrigin_d30.png).

Schwefel en \(n = 5\) et \(n = 30\) : l’optimum trompeur émerge

Schwefel a un optimum global à \(x_i \approx 420.97\) — loin du centre de la boîte recommandée \([-500, 500]\). Le deuxième optimum local, lui, est près de l’origine. En 2-D, le praticien voit deux bassines distinctes. Mais en dimension supérieure, la projection MAX fait émerger le « vrai » optimum global dès qu’on autorise les coordonnées cachées à varier : depuis presque chaque \((x, y)\) on peut atteindre un point caché proche de \((420.97, 420.97, \ldots, 420.97)\).

Conséquence : la heatmap Schwefel-n devient nettement plus rouge et plus uniforme que la 2-D — signal classique que la métaheuristique doit pouvoir sortir de la bassine centrale (donc redémarrages, ou stratégie d’évasion).

using System.IO;
var rng = new Random(99);

foreach (int dim in new[] { 5, 30 })
{
    using var h = KnownFunctionLandscape.RenderHeatmap(
        new SchwefelFitness(), dimension: dim, nbSamples: 30, rng: rng,
        width: 120, height: 120);

    var path = $@"assets\landscape_multidim_schwefel_d{dim}.png";
    File.WriteAllBytes(path, h.ToPngGdi());
    Console.WriteLine($"Schwefel dim={dim} rendu ({path}).");
}
Schwefel dim=5 rendu (assets\landscape_multidim_schwefel_d5.png).
Schwefel dim=30 rendu (assets\landscape_multidim_schwefel_d30.png).

Ackley en \(n = 2\) et \(n = 30\) : la “bassine” de minima locaux au bord

Ackley est la 4e fonction canonique de KnownFunctions.cs et complete le panorama MGS-7b sur une geometrie tres differente de Rastrigin et Schwefel. Sa formule est

\[f(\vec x) = -a \exp\left(-b \sqrt{\tfrac{1}{n} \sum_i x_i^2}\right) - \exp\left(\tfrac{1}{n} \sum_i \cos(c x_i)\right) + a + e\]

avec les parametres canoniques \(a = 20\), \(b = 0.2\), \(c = 2\pi\). La bassine centrale est quasi-plate : un enorme plateau legerement ondule entoure l’origine, et un anneau de minima locaux (cos) ceint cette bassine. En dimension superieure, ces minima se demultiplient exponentiellement (~ \(e^{n-1}\) cuvettes) — Ackley est repute parmi les paysages les plus trompeurs pour les metaheuristiques en haute dimension.

Effet attendu de la projection N-D : en 2-D, on voit nettement la bassine centrale (rouge profond sature = haut fitness = l’optimum global) cernee par un anneau ondule (vert/jaune = minima locaux cos). En 30-D, la projection MAX capture les innombrables coordonnees cachees qui peuvent atteindre des valeurs loin du centre → depuis presque chaque pixel visible, il existe un point cache qui grimpe tres haut sur la modulation cos. La heatmap se rapproche d’une saturation rouge uniforme (le praticien lit cela comme : “le paysage est devenu si multimodal qu’aucune direction n’est fiable, il faut des redemarrages massifs”).

C’est precisement la lecon de la projection MAX qu’on cherche a transmettre a travers MGS-7b : Ackley-n en 2-D rassure (bol central visible), Ackley-n en N-D inquiete (le bol n’existe presque plus a l’ecran). Le contraste entre les deux heatmaps ci-dessous est l’illustration la plus parlante du pourquoi les redemarrages et le seeding aleatoire sont indispensables au-dela de la dimension 5.

using System.IO;
var rngAck = new Random(777);

foreach (int dim in new[] { 2, 30 })
{
    using var h = KnownFunctionLandscape.RenderHeatmap(
        new AckleyFitness(), dimension: dim, nbSamples: 30, rng: rngAck,
        width: 120, height: 120);

    var path = $@"assets\landscape_multidim_ackley_d{dim}.png";
    File.WriteAllBytes(path, h.ToPngGdi());

    var (px, py) = h.ToPixel(0.0, 0.0);
    Console.WriteLine($"Ackley dim={dim,2} — pixel (0,0) = {h.Bitmap.GetPixel(px, py)} (PNG: {path}).");
}
Ackley dim= 2 — pixel (0,0) = Color [A=255, R=255, G=0, B=0] (PNG: assets\landscape_multidim_ackley_d2.png).
Ackley dim=30 — pixel (0,0) = Color [A=255, R=35, G=255, B=0] (PNG: assets\landscape_multidim_ackley_d30.png).

Exercices

Convention. Les exercices sont des cellules à compléter. Squelette fourni, à vous de jouer. Les solutions sont dans la logique de la MAX projection — pas de try/except qui masquerait une mauvaise compréhension.

Exercice 1 : convergence de nbSamples

Observer comment la heatmap Rastrigin-dim=10 se stabilise quand nbSamples croît. On s’attend à ce que la moyenne du canal rouge descende puis se stabilise (convergence asymptotique vers une valeur faible). Le pipeline de la cellule est en place — il suffit de remplir la logique d’agrégation.

Intuition théorique : Rastrigin admet un optimum global profond à l’origine \(\vec{x} = \vec{0}\) où \(f(\vec{0}) = 0\). Quand nbSamples augmente, les coordonnées cachées \(x_2, \dots, x_9\) ont plus de chances de tomber proches de zéro par échantillonnage uniforme (loi des grands nombres + concentration près de 0) ; la projection MAX capture donc plus souvent le voisinage de cet optimum central. La palette de Rastrigin sature vers le rouge sombre puis noir quand la fitness est très haute, ce qui correspond à un canal \(R\) faible. Conséquence : mean R descend asymptotiquement, pas il ne monte.

Exercice 2 : effet de seed

Comparer deux heatmaps Rastrigin-dim=10 avec deux seeds différentes pour rng. Lesquelles sont visiblement différentes ? Lesquelles se ressemblent ? C’est l’occasion de voir combien d’aléa la projection MAX injecte (information utile pour décider combien de redémarrages allouer à la métaheuristique).

Exercice 3 : optimum trompeur, localiser le minimum global de Schwefel

Schwefel est le cas déceptif par excellence : son optimum global n’est pas au centre du domaine (contrairement à Rastrigin ou Ackley), mais excentré, près d’un bord. Sur la heatmap Schwefel-d5, identifier le pixel au canal rouge minimal (le puits le plus profond = optimum global) et mesurer sa distance au centre de l’image. Comparer à Rastrigin-d5 (optimum central, distance \(\approx 0\)). Un optimum excentré quantifie la déceptivité — pourquoi une métaheuristique sans population large peut s’enliser dans le puits central attractif, qui n’est pas le bon. Squelette :

using var hSCH = KnownFunctionLandscape.RenderHeatmap(
    new SchwefelFitness(), dimension: 5, nbSamples: 50,
    rng: new Random(42), width: 80, height: 80);
using var hRAS = KnownFunctionLandscape.RenderHeatmap(
    new RastriginFitness(), dimension: 5, nbSamples: 50,
    rng: new Random(42), width: 80, height: 80);
// TODO: pour chaque heatmap, trouver le pixel (x*, y*) au canal R minimal, puis
// calculer sa distance euclidienne au centre (40, 40). Attendu: Schwefel >> 0
// (optimum excentre), Rastrigin ~ 0 (optimum central).
// Exercice 1 : convergence de nbSamples pour Rastrigin dim=10.
// On veut voir la moyenne du canal rouge en fonction de nbSamples.
// TODO etudiant : pour chaque nbSamples de {1, 5, 25, 100}, rendre la heatmap
// (KnownFunctionLandscape.RenderHeatmap, rng new Random(2026), 80x80), calculer
// la moyenne du canal rouge sur tous les pixels et l'ajouter a stats.
// Indice : boucle for classique via h.Bitmap.GetPixel (DirectBitmap pas accessible publiquement).
// Etape 1 : boucle sur new[] { 1, 5, 25, 100 } avec using var h = ...RenderHeatmap(...).
// Etape 2 : sommer h.Bitmap.GetPixel(x, y).R sur les 80x80 pixels.
// Etape 3 : afficher nbSamples et la moyenne, puis commenter la convergence.
var stats = new List<(int nbSamples, double meanRed)>();
// ... collecte et affichage a ecrire ...
Console.WriteLine("Exercice 1 a completer : convergence de nbSamples (moyenne du canal rouge).");
Exercice 1 a completer : convergence de nbSamples (moyenne du canal rouge).
// Exercice 2 : effet de seed sur la variabilite de la heatmap.
// TODO etudiant : afficher la proportion de pixels qui DIFFERENT entre deux seeds.
// Indice : deux appels a RenderHeatmap identiques (Rastrigin dim 10, nbSamples 25, 80x80)
//   avec rng new Random(1) et new Random(99999).
// Indice : comparer hA.Bitmap.GetPixel(x, y).ToArgb() != hB.Bitmap.GetPixel(x, y).ToArgb().
// Attendu : une proportion significative (>50%) — la projection MAX injecte de la
// variabilite qui depend de l'ordre de visite Parallel.For des pixels.
Console.WriteLine("Exercice 2 a completer : proportion de pixels differents entre 2 seeds.");
Exercice 2 a completer : proportion de pixels differents entre 2 seeds.

Exercice 3 : Schwefel — l’optimum au coin vs Rastrigin au centre

Schwefel est l’exception topologique de la série (cellule Schwefel ci-dessus) : son optimum global se cache dans un coin du domaine (\(x_i \approx 420{,}97\) sur \([-500, 500]\)), alors que Rastrigin et Ackley ont leur optimum au centre (origine). La projection MAX préserve-t-elle cette différence de position ?

Mesure à coder : pour SchwefelFitness et RastriginFitness en dimension 2, extraire la valeur du canal rouge au centre de la heatmap et aux 4 coins, puis identifier où se trouve le minimum rouge. Intuition à vérifier : pour Rastrigin, le centre doit être le point le plus sombre (canal rouge minimal, optimum à l’origine) ; pour Schwefel, c’est l’un des coins. Si la projection efface la distinction, c’est le signe que la dimension cachée brouille la topologie 2-D — exactement le piège qui rend Schwefel difficile pour une métaheuristique myope.

// Exercice 3 : Schwefel (optimum au coin) vs Rastrigin (optimum au centre).
// Pour chaque fonction en dimension 2, comparer le canal rouge au centre vs aux 4 coins.
// Squelette : le pipeline RenderHeatmap est documente dans les cellules ci-dessus.
// TODO etudiant :
//   1. using var hS = KnownFunctionLandscape.RenderHeatmap(new SchwefelFitness(),
//        dimension: 2, nbSamples: 50, rng: new Random(2026), width: 80, height: 80);
//   2. idem pour RastriginFitness (hR).
//   3. Pour chaque heatmap : extraire h.Bitmap.GetPixel(40, 40).R (centre) et
//      les 4 coins (0,0),(79,0),(0,79),(79,79).R.
//   4. Afficher ou se trouve le minimum rouge pour Schwefel vs Rastrigin.
Console.WriteLine("Exercice 3 a completer : comparer centre vs coins du canal rouge (Schwefel vs Rastrigin).");
Exercice 3 a completer : comparer centre vs coins du canal rouge (Schwefel vs Rastrigin).

Liens

  • MGS-1 Introduction — le moteur MetaGeneticAlgorithm et la notion d’agencement des primitives.
  • MGS-6 Benchmarks — les 10 fonctions canoniques et leur banc d’essai comparatif.
  • MGS-7 TSP — TSP comme exemple de problème à représentation non-géométrique.
  • MGS-8 LandscapeExplorer — l’explorateur historique 2-D du paysage (la base dont la projection N-D est issue).
  • PR #7483 — port de la projection N-D du fork Gtk# dans le submodule.
  • KnownFunctionLandscape.cs — la classe pont (surcharges 2-D et N-D), avec doc du fix coordsRange = max - min.
  • Tests KnownFunctionLandscapeNdTests — 12 tests NUnit, dont G.9 non-vacuous (le test HiddenCoordsAffectHeatmap échoue sans le fix).
  • LandscapeExplorerSampleController.GetFunctionValue — algorithme verbatim Gtk# (lignes 640-674 du fork jsboige @ d05826fd).
Retour au sommet