MGS-21 : Représentation contre algorithme — la preuve croisée

← MGS-19 Métropolis | ↑ Série MGS

Question centrale. Sur un même problème, avec le même budget d’évaluations et les mêmes graines, qu’est-ce qui pèse le plus : le choix de l’algorithme de recherche, ou le choix de la représentation de l’espace de recherche ? Ce notebook répond par une expérience croisée — deux représentations × deux algorithmes — et non par un récit.

La thèse à éprouver, issue du geste récurrent du dépôt (« changer de représentation plutôt qu’insister ») :

le choix de l’espace et des opérateurs qui le respectent peut DOMINER le choix de l’algorithme.

L’expérience a déjà eu lieu, par morceaux, dans Sudoku-05 : la Tranche 3 y montre un PSO canonique à vélocité enchaîné sur une relaxation continue + arrondi (échec massif : 34 conflits restants après 37 s), la Tranche 4 un PSO à opérateurs d’échange nativement dans l’espace des permutations (résolu en 111 ms). Même famille d’algorithmes, même problème. Ce qui a changé, c’est l’espace. Ici nous en faisons une mesure propre : un plan croisé où chaque algorithme rencontre chaque représentation, pour attribuer l’effet plutôt que le raconter.

1. Le problème et les deux représentations

Le problème est la grille facile de référence de la série Sudoku (la même que les Tranches 1 à 4 de Sudoku-05), reprise littéralement ici pour que l’expérience soit auto-contenue. La fonction de coût est identique pour les quatre cellules du plan : le nombre total de conflits (lignes + colonnes + blocs) — zéro conflit signifie grille résolue. Aucune cellule du croisement ne reçoit un avantage de fonction de coût.

Les deux représentations diffèrent par la façon dont elles décrivent un candidat :

	R1 — continue + arrondi	R2 — permutation + échange
Un candidat est…	un vecteur de réels, une coordonnée par cellule vide	une grille dont chaque ligne est une permutation des chiffres manquants
Décodage vers une grille	arrondi puis clamp vers 1..9	identité — le candidat EST une grille à lignes valides
Mouvements du moteur	déplacements continus dans \([1, 10)^{n}\)	échanges de deux cellules vides d’une même ligne (swaps)
Lignes des candidats	presque toujours invalides (doublons après arrondi)	valides par construction

R1 est la représentation « naturelle » pour un moteur continu comme un PSO à vélocité : rien à implémenter, on arrondit au décodage. R2 demande des opérateurs dédiés (l’algèbre de swaps de la Tranche 4), mais elle respecte une contrainte structurelle : quoi que fasse le moteur, chaque ligne reste une permutation. Le coût des conflits de lignes est, dans R2, identiquement nul sur tout l’espace atteignable — une dimension entière du problème a disparu de l’espace de recherche.

C’est cette différence structurelle que le croisement va mesurer.

// === MGS-21 : socle commun — DLLs MGS, grille de reference, fonction de cout ===
// DLLs du build local du submodule (pattern MGS-1..19). GeneticSharp 3.1.4 est la
// couche porteuse de MetaGeneticSharp : selection/crossover/mutation + RNG global.
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Domain/bin/Debug/net9.0/GeneticSharp.Infrastructure.Framework.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"
using MetaGeneticSharp;
using GeneticSharp;
using System.Diagnostics;

// Grille facile Easy[0] de Sudoku_Easy51.txt — la MEME que les Tranches 1-4 de Sudoku-5
// (81 chiffres, 0 = cellule vide). Reprise litteralement pour un notebook auto-contenu.
public static string PuzzleLine = "902005403100063025508407060026309001057010290090670530240530600705200304080041950";

public static int[,] ParsePuzzle()
{
    var g = new int[9, 9];
    for (int i = 0; i < 81; i++) g[i / 9, i % 9] = PuzzleLine[i] - '0';
    return g;
}

// Fonction de cout UNIQUE pour les quatre cellules du croisement : conflits totaux
// (lignes + colonnes + blocs) sur une grille PLEINE (aucun zero apres decodage).
// Renvoie 0 ssi la grille est resolue.
public static int CountConflicts(int[,] g)
{
    int conflicts = 0;
    for (int i = 0; i < 9; i++)
    {
        var row = new HashSet<int>(); var col = new HashSet<int>(); var blk = new HashSet<int>();
        for (int j = 0; j < 9; j++)
        {
            if (!row.Add(g[i, j])) conflicts++;
            if (!col.Add(g[j, i])) conflicts++;
            int br = 3 * (i / 3) + j / 3, bc = 3 * (i % 3) + j % 3;
            if (!blk.Add(g[br, bc])) conflicts++;
        }
    }
    return conflicts;
}

// Sanity dedie aux indices : ne compte les doublons qu'entre valeurs NON NULLES
// (les zeros sont des cellules vides, pas des valeurs en conflit).
public static int CountGivensConflicts(int[,] g)
{
    int conflicts = 0;
    for (int i = 0; i < 9; i++)
    {
        var row = new HashSet<int>(); var col = new HashSet<int>(); var blk = new HashSet<int>();
        for (int j = 0; j < 9; j++)
        {
            if (g[i, j] != 0 && !row.Add(g[i, j])) conflicts++;
            if (g[j, i] != 0 && !col.Add(g[j, i])) conflicts++;
            int br = 3 * (i / 3) + j / 3, bc = 3 * (i % 3) + j % 3;
            if (g[br, bc] != 0 && !blk.Add(g[br, bc])) conflicts++;
        }
    }
    return conflicts;
}

public static int CountEmpty(int[,] p) { int n = 0; foreach (var v in p) if (v == 0) n++; return n; }

var Puzzle = ParsePuzzle();
Console.WriteLine($"Grille de reference : {CountEmpty(Puzzle)} cellules vides, " +
                  $"{81 - CountEmpty(Puzzle)} indices fixes.");
Console.WriteLine($"Conflits entre indices (hors cellules vides) : {CountGivensConflicts(Puzzle)} (attendu : 0).");

The below script needs to be able to find the current output cell; this is an easy method to get it.

Grille de reference : 36 cellules vides, 45 indices fixes.
Conflits entre indices (hors cellules vides) : 0 (attendu : 0).

// === Les deux decodeurs : d'un candidat moteur vers une grille evaluee ===
// R1 : vecteur de reels (une coordonnee par cellule vide) -> arrondi + clamp vers 1..9.
//      Le decodeur peut produire des doublons dans une ligne : R1 n'impose rien.
public static int[,] DecodeR1(double[] genes, int[,] problem, List<(int r, int c)> empties)
{
    var g = (int[,])problem.Clone();
    for (int i = 0; i < empties.Count; i++)
    {
        double v = genes[i];
        g[empties[i].r, empties[i].c] = Math.Max(1, Math.Min(9, (int)Math.Round(v)));
    }
    return g;
}

// R2 : une grille a lignes-permutations EST le candidat (decodage = identite).
//      RandomR2 : chaque ligne = permutation uniforme des chiffres manquants (Fisher-Yates).
public static int[,] RandomR2(int[,] problem, Random rnd)
{
    var g = (int[,])problem.Clone();
    for (int r = 0; r < 9; r++)
    {
        var present = new HashSet<int>();
        for (int c = 0; c < 9; c++) if (g[r, c] != 0) present.Add(g[r, c]);
        var missing = Enumerable.Range(1, 9).Where(d => !present.Contains(d)).ToList();
        for (int i = missing.Count - 1; i > 0; i--) { int j = rnd.Next(i + 1); (missing[i], missing[j]) = (missing[j], missing[i]); }
        int k = 0;
        for (int c = 0; c < 9; c++) if (g[r, c] == 0) g[r, c] = missing[k++];
    }
    return g;
}

// Demonstration (graine 42) : trois candidats aleatoires par representation.
var empties = new List<(int r, int c)>();
for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (Puzzle[r, c] == 0) empties.Add((r, c));

int RowDuplicates(int[,] g)
{
    int dup = 0;
    for (int r = 0; r < 9; r++) { var s = new HashSet<int>(); for (int c = 0; c < 9; c++) if (!s.Add(g[r, c])) dup++; }
    return dup;
}

var demoRnd = new Random(42);
Console.WriteLine("Candidats aleatoires initiaux (graine 42) :");
Console.WriteLine("  rep    conflits  doublons lignes");
for (int i = 0; i < 3; i++)
{
    var genes = Enumerable.Range(0, empties.Count).Select(_ => demoRnd.NextDouble() * 9 + 1).ToArray();
    var g1 = DecodeR1(genes, Puzzle, empties);
    Console.WriteLine($"  R1    {CountConflicts(g1),9} {RowDuplicates(g1),16}");
}
var g2 = RandomR2(Puzzle, demoRnd);
Console.WriteLine($"  R2    {CountConflicts(g2),9} {RowDuplicates(g2),16}   (lignes valides par construction)");

Candidats aleatoires initiaux (graine 42) :
  rep    conflits  doublons lignes
  R1           59               21
  R1           62               22
  R1           67               23
  R2           37                0   (lignes valides par construction)

// === Moteurs R1 : PSO a velocite et GA, via les compounds MGS (factory) ===
// Chromosome continu : une gene double par cellule vide, bornes [1, 10). Le decodeur
// R1 (arrondi) vit dans le passage chromosome -> grille, exactement comme la Tranche 3
// de Sudoku-5. La fitness est -CountConflicts (GeneticSharp maximise).
public class SudokuR1Chromosome : ChromosomeBase
{
    public static int[,] Problem;
    public static List<(int r, int c)> Empties;
    public SudokuR1Chromosome() : base(Empties.Count) { CreateGenes(); }
    public override Gene GenerateGene(int index)
        => new Gene(RandomizationProvider.Current.GetDouble(1.0, 10.0));
    public override IChromosome CreateNew() => new SudokuR1Chromosome();
    public int[,] ToGrid() => Mgs21Host.DecodeR1(
        GetGenes().Select(gv => (double)gv.Value).ToArray(), Problem, Empties);
}

// Fitness instrumentee : compte les evaluations pour verifier la parite de budget.
public class SudokuR1Fitness : IFitness
{
    public static long Evals;
    public double Evaluate(IChromosome chromosome)
    {
        Evals++;
        return -CountConflicts(((SudokuR1Chromosome)chromosome).ToGrid());
    }
}

public static class Mgs21Host
{
    public static int[,] DecodeR1(double[] genes, int[,] problem, List<(int r, int c)> empties)
    {
        var g = (int[,])problem.Clone();
        for (int i = 0; i < empties.Count; i++)
            g[empties[i].r, empties[i].c] = Math.Max(1, Math.Min(9, (int)Math.Round(genes[i])));
        return g;
    }

    // Un run R1 : compound MGS par nom ("ParticleSwarmOptimization" ou "Default" = GA),
    // seeding REEL via FastRandomRandomization.ResetSeed AVANT la creation de la
    // population (le RNG est consomme par CreateNew() — lecon #12071/#12190).
    public static (int conflicts, long evals, double ms) RunR1(string compoundName, int seed, int pop, int gens)
    {
        SudokuR1Chromosome.Problem = Mgs21Host.PuzzleRef;
        SudokuR1Chromosome.Empties = Mgs21Host.EmptiesRef;
        SudokuR1Fitness.Evals = 0;
        FastRandomRandomization.ResetSeed(seed);

        var compound = MetaHeuristicsService.CreateMetaHeuristicByName(compoundName, maxGenerations: gens, populationSize: pop);
        var adam = new SudokuR1Chromosome();
        var population = new MetaPopulation(pop, pop, adam);
        var ga = new MetaGeneticAlgorithm(
            population, new SudokuR1Fitness(),
            new EliteSelection(), new UniformCrossover(0.5f), new UniformMutation(true),
            compound);
        ga.Termination = new GenerationNumberTermination(gens);

        var sw = Stopwatch.StartNew();
        ga.Start();
        sw.Stop();
        var best = (SudokuR1Chromosome)ga.BestChromosome;
        return (CountConflicts(best.ToGrid()), SudokuR1Fitness.Evals, sw.Elapsed.TotalMilliseconds);
    }

    public static int[,] PuzzleRef;
    public static List<(int r, int c)> EmptiesRef;
}
Mgs21Host.PuzzleRef = Puzzle;
Mgs21Host.EmptiesRef = empties;

// Smoke test : un run PSO et un run GA, graine 0, pour valider le branchement.
var (smC, smE, smMs) = Mgs21Host.RunR1("ParticleSwarmOptimization", 0, 10, 10);
Console.WriteLine($"Smoke PSO-R1 : {smC} conflits, {smE} evals, {smMs:F0} ms");
var (smC2, smE2, smMs2) = Mgs21Host.RunR1("Default", 0, 10, 10);
Console.WriteLine($"Smoke GA-R1  : {smC2} conflits, {smE2} evals, {smMs2:F0} ms");

Smoke PSO-R1 : 58 conflits, 100 evals, 45 ms
Smoke GA-R1  : 47 conflits, 86 evals, 3 ms

// === Moteurs R2 : swap-PSO et GA a permutations, natifs dans l'espace admissible ===
// Reference de l'algebre : A. Hernandez & Y. Gonzalez, "Metaheuristics in C#" (MIT,
// Univ. de La Havane, 2012), Common/DiscretePSO.cs — reimplementation compacte adaptee
// de la Tranche 4 de Sudoku-5. La velocite est une LISTE DE SWAPS sur cellules vides
// d'une meme ligne : quel que soit le mouvement, chaque ligne reste une permutation.
public readonly record struct RowSwap(int Row, int A, int B);

public static class SwapAlgebra21
{
    public static int[,] Move(int[,] pos, IReadOnlyList<RowSwap> vel, int[,] problem)
    {
        var res = (int[,])pos.Clone();
        foreach (var s in vel)
            for (int c = 0; c < 9; c++)
            {
                if (problem[s.Row, c] != 0) continue;
                if (res[s.Row, c] == s.A) res[s.Row, c] = s.B;
                else if (res[s.Row, c] == s.B) res[s.Row, c] = s.A;
            }
        return res;
    }
    public static List<RowSwap> Minus(int[,] target, int[,] current, int[,] problem)
    {
        var vel = new List<RowSwap>();
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                if (problem[r, c] == 0 && current[r, c] != target[r, c])
                    vel.Add(new RowSwap(r, current[r, c], target[r, c]));
        return vel;
    }
    public static List<RowSwap> Times(double k, IReadOnlyList<RowSwap> vel)
    {
        var res = new List<RowSwap>();
        if (k <= 0 || vel.Count == 0) return res;
        if (k <= 1) res.AddRange(vel.Take((int)(k * vel.Count)));
        else { for (int f = 0; f < (int)Math.Floor(k); f++) res.AddRange(vel); res.AddRange(vel.Take((int)((k - Math.Floor(k)) * vel.Count))); }
        return res;
    }
}

// swap-PSO : recurrence classique, chaque terme est une liste de swaps, inertie
// decroissante 0.9 -> 0.3. Seede par Random(seed).
public static (int conflicts, long evals, double ms) RunSwapPso(int[,] problem, int seed, int swarm, int iters)
{
    var rnd = new Random(seed);
    long evals = 0;
    int Cost(int[,] p) { evals++; return CountConflicts(p); }

    var pos = new int[swarm][,];
    var pbest = new int[swarm][,];
    var pbestC = new int[swarm];
    for (int i = 0; i < swarm; i++)
    {
        pos[i] = RandomR2(problem, rnd); pbest[i] = (int[,])pos[i].Clone(); pbestC[i] = Cost(pos[i]);
    }
    int[,] gbest = (int[,])pbest[0].Clone(); int gbestC = pbestC[0];
    for (int i = 1; i < swarm; i++) if (pbestC[i] < gbestC) { gbest = (int[,])pbest[i].Clone(); gbestC = pbestC[i]; }

    var sw = Stopwatch.StartNew();
    for (int it = 0; it < iters; it++)
    {
        double w = 0.9 - (0.6 * it) / iters;
        for (int i = 0; i < swarm; i++)
        {
            var v1 = SwapAlgebra21.Times(w * rnd.NextDouble(), SwapAlgebra21.Minus(pbest[i], pos[i], problem));
            var v2 = SwapAlgebra21.Times(1.0 * rnd.NextDouble(), SwapAlgebra21.Minus(gbest, pos[i], problem));
            var vel = v1.Concat(v2).ToList();
            pos[i] = SwapAlgebra21.Move(pos[i], vel, problem);
            int c = Cost(pos[i]);
            if (c < pbestC[i]) { pbest[i] = (int[,])pos[i].Clone(); pbestC[i] = c; }
            if (c < gbestC) { gbest = (int[,])pos[i].Clone(); gbestC = c; }
        }
        if (gbestC == 0) break;
    }
    sw.Stop();
    return (gbestC, evals, sw.Elapsed.TotalMilliseconds);
}

// GA a permutations : croisement uniforme PAR LIGNE (chaque ligne herite d'un parent,
// les lignes restent des permutations) + mutation par echange intra-ligne. Elitisme 2,
// selection par tournoi. Seede par Random(seed).
public static (int conflicts, long evals, double ms) RunPermGa(int[,] problem, int seed, int pop, int gens)
{
    var rnd = new Random(seed);
    long evals = 0;
    int Cost(int[,] p) { evals++; return CountConflicts(p); }

    var population = new List<(int[,] g, int c)>();
    for (int i = 0; i < pop; i++) { var g = RandomR2(problem, rnd); population.Add((g, Cost(g))); }
    population = population.OrderBy(x => x.c).ToList();

    int[,] Child(int[,] a, int[,] b)
    {
        var ch = (int[,])a.Clone();
        for (int r = 0; r < 9; r++) if (rnd.Next(2) == 0) for (int c = 0; c < 9; c++) ch[r, c] = b[r, c];
        return ch;
    }
    void Mutate(int[,] g)
    {
        int r = rnd.Next(9);
        var empt = new List<int>();
        for (int c = 0; c < 9; c++) if (problem[r, c] == 0) empt.Add(c);
        if (empt.Count >= 2) { int i = rnd.Next(empt.Count); int j = rnd.Next(empt.Count); (g[r, empt[i]], g[r, empt[j]]) = (g[r, empt[j]], g[r, empt[i]]); }
    }

    var sw = Stopwatch.StartNew();
    for (int gen = 0; gen < gens; gen++)
    {
        var next = new List<(int[,] g, int c)> { population[0], population[1] }; // elitisme
        while (next.Count < pop)
        {
            (int[,] a, _) = population[rnd.Next(pop / 2)];
            (int[,] b, _) = population[rnd.Next(pop / 2)];
            var ch = Child(a, b);
            if (rnd.NextDouble() < 0.7) Mutate(ch);
            next.Add((ch, Cost(ch)));
        }
        population = next.OrderBy(x => x.c).ToList();
        if (population[0].c == 0) break;
    }
    sw.Stop();
    return (population[0].c, evals, sw.Elapsed.TotalMilliseconds);
}

// Smoke test des deux moteurs R2.
var (r2a, r2aE, r2aMs) = RunSwapPso(Puzzle, 0, 10, 10);
Console.WriteLine($"Smoke swap-PSO-R2 : {r2a} conflits, {r2aE} evals, {r2aMs:F0} ms");
var (r2b, r2bE, r2bMs) = RunPermGa(Puzzle, 0, 10, 10);
Console.WriteLine($"Smoke GA-R2       : {r2b} conflits, {r2bE} evals, {r2bMs:F0} ms");

Smoke swap-PSO-R2 : 23 conflits, 110 evals, 14 ms
Smoke GA-R2       : 22 conflits, 90 evals, 2 ms

2. Le plan croisé

L’expérience est un plan factoriel 2 × 2 : chaque algorithme (PSO à vélocité, algorithme génétique) rencontre chaque représentation (R1 continue + arrondi, R2 permutation + échange). Si l’on n’avait mesuré que PSO-R1 contre PSO-R2 (comme le racontent les Tranches 3 et 4 de Sudoku-05), l’effet de la représentation serait confondu avec quoi que ce soit qui distingue ces deux cellules ; le croisement permet au contraire d’isoler l’effet propre de la représentation (comparaison en ligne) et l’effet propre de l’algorithme (comparaison en colonne) sur le même budget.

Protocole pré-enregistré :

• Budget : population 40 × 200 générations pour les quatre cellules — parité par construction, vérifiée par les évaluations comptées (la fitness est instrumentée) et rapportées avec les résultats.
• Graines : {0, 1, 7, 42} — quatre graines nommées par cellule, le seeding est réel (FastRandomRandomization.ResetSeed pour les moteurs MGS, Random(seed) pour les moteurs natifs ; leçon #12071).
• Métrique : conflits restants du meilleur candidat (0 = résolu). Rapportés avec dispersion (médiane, min, max) — jamais en moyenne seule.
• Critère de verdict (fixé avant l’exécution) : la représentation « domine » si, dans chaque colonne d’algorithme, l’écart R1→R2 dépasse l’écart entre algorithmes dans chaque ligne ; « effets comparables » si les deux écarts sont du même ordre ; « non concluant » si les dispersions se recouvrent.

// === LE CROISEMENT : 2 representations x 2 algorithmes x 4 graines ===
int POP = 40, GENS = 200;
int[] SEEDS = { 0, 1, 7, 42 };

(string rep, string algo, Func<int, (int c, long e, double ms)> run)[] cells =
{
    ("R1", "PSO", s => Mgs21Host.RunR1("ParticleSwarmOptimization", s, POP, GENS)),
    ("R1", "GA",  s => Mgs21Host.RunR1("Default",                 s, POP, GENS)),
    ("R2", "PSO", s => RunSwapPso(Puzzle, s, POP, GENS)),
    ("R2", "GA",  s => RunPermGa(Puzzle, s, POP, GENS)),
};

var cross = new List<string>();
foreach (var (rep, algo, run) in cells)
{
    var results = new List<(int seed, int c, long e, double ms)>();
    foreach (var s in SEEDS)
    {
        var (c, e, ms) = run(s);
        results.Add((s, c, e, ms));
        Console.WriteLine($"[{rep}/{algo}] graine {s,2} : {c,2} conflits | {e,5} evals | {ms,7:F0} ms {(c == 0 ? "- RESOLU" : "")}");
    }
    var cs_ = results.Select(r => (double)r.c).OrderBy(x => x).ToList();
    double median = (cs_[1] + cs_[2]) / 2.0;
    int solved = results.Count(r => r.c == 0);
    cross.Add($"| {rep} | {algo} | {median:F1} | {cs_[0]:F0} | {cs_[3]:F0} | {results.Average(r => r.e):F0} | {results.Average(r => r.ms):F0} | {solved}/4 |");
}

Console.WriteLine();
Console.WriteLine("Tableau croise — conflits restants (0 = resolu), 4 graines par cellule :");
Console.WriteLine("| rep | algo | mediane | min | max | evals moy. | ms moy. | resolus |");
Console.WriteLine("|---|---|---|---|---|---|---|---|");
foreach (var line in cross) Console.WriteLine(line);

[R1/PSO] graine  0 : 46 conflits |  8000 evals |    1748 ms 
[R1/PSO] graine  1 : 50 conflits |  8000 evals |     964 ms 
[R1/PSO] graine  7 : 39 conflits |  8000 evals |     853 ms 
[R1/PSO] graine 42 : 44 conflits |  8000 evals |    1049 ms 
[R1/GA] graine  0 :  4 conflits |  6030 evals |     139 ms 
[R1/GA] graine  1 :  8 conflits |  5950 evals |     108 ms 
[R1/GA] graine  7 : 13 conflits |  6090 evals |     123 ms 
[R1/GA] graine 42 : 15 conflits |  5994 evals |      91 ms 
[R2/PSO] graine  0 :  6 conflits |  8040 evals |      66 ms 
[R2/PSO] graine  1 :  2 conflits |  8040 evals |      82 ms 
[R2/PSO] graine  7 :  6 conflits |  8040 evals |      75 ms 
[R2/PSO] graine 42 : 13 conflits |  8040 evals |      68 ms 
[R2/GA] graine  0 :  0 conflits |   876 evals |       8 ms - RESOLU
[R2/GA] graine  1 :  0 conflits |   914 evals |       8 ms - RESOLU
[R2/GA] graine  7 :  0 conflits |   838 evals |      14 ms - RESOLU
[R2/GA] graine 42 :  0 conflits |   724 evals |       7 ms - RESOLU

Tableau croise — conflits restants (0 = resolu), 4 graines par cellule :
| rep | algo | mediane | min | max | evals moy. | ms moy. | resolus |
|---|---|---|---|---|---|---|---|
| R1 | PSO | 45,0 | 39 | 50 | 8000 | 1154 | 0/4 |
| R1 | GA | 10,5 | 4 | 15 | 6016 | 115 | 0/4 |
| R2 | PSO | 6,0 | 2 | 13 | 8040 | 73 | 0/4 |
| R2 | GA | 0,0 | 0 | 0 | 838 | 9 | 4/4 |

Lecture du croisement — la représentation a le dernier mot, l’algorithme n’est pas innocent

Le tableau, lu avec le critère pré-enregistré :

lecture	écart mesuré	ce qu’il dit
Effet représentation, colonne PSO	45,0 → 6,0 de médiane (−39 conflits, ×7,5) ; R1/PSO ne descend jamais sous 39, R2/PSO jamais au-dessus de 13	le changement d’espace rapporte au PSO plus que tout changement d’algorithme ne lui rapportera
Effet représentation, colonne GA	10,5 → 0,0 — et 0/4 → 4/4 résolus	le GA ne résout jamais en R1 à ce budget ; il résout toujours en R2
Effet algorithme, ligne R1	45,0 → 10,5 (×4,3)	l’algorithme compte aussi : à représentation fixée, le GA creuse bien mieux que le PSO
Effet algorithme, ligne R2	6,0 → 0,0 (4/4 résolus)	idem en R2

Application du critère pré-enregistré. « La représentation domine » exige que, dans chaque colonne, l’écart R1→R2 dépasse les écarts entre algorithmes des deux lignes (34,5 et 6). C’est vrai pour le PSO (39 > 34,5 > 6), faux pour le GA (10,5 < 34,5) : sur la colonne GA, les effets des deux facteurs sont comparables. Le verdict honnête est donc en deux temps : la thèse « la représentation peut dominer l’algorithme » est démontrée sur la colonne PSO ; sur la colonne GA, représentation et algorithme pèsent du même ordre — et seule leur combinaison (R2 × GA) produit la résolution 4/4. Aucune cellule R1 n’approche la solution (min 4 conflits) : à budget égal, aucun choix d’algorithme ne compense la représentation continue + arrondi sur ce problème.

Deux asymétries à ne pas sur-lire. (1) Les évaluations de R2/GA (838 en moyenne) sont plus basses que 8 000 parce que la bouche s’arrête quand la grille est résolue — c’est une conséquence de la réussite, pas un budget plus faible : les trois autres cellules consomment leur budget complet (6 016 à 8 040 évaluations). (2) Le temps machine de R1/PSO est un ordre de grandeur au-dessus des autres cellules (visible dans la sortie du croisement ci-dessus) : il reflète le coût du décodage d’un vecteur de réels à chaque évaluation — un détail d’implémentation, pas un résultat. La métrique du croisement est le conflit, pas la milliseconde.

// === Exemple resolu : qu'est-ce que l'arrondi detruit exactement ? (demonstration de la cause) ===
// Mesure directe : N candidats aleatoires par representation. Pour R1 on regarde la
// proportion de candidats qui tombent HORS de l'espace admissible (au moins une ligne
// avec doublon apres arrondi), et le niveau de conflits au depart. R2 sert de controle :
// par construction, 0 % hors espace, et le depart ne compte que colonnes + blocs.
int N = 200;
var causeRnd = new Random(7);

int outOfSpaceR1 = 0; var initConfR1 = new List<int>();
for (int i = 0; i < N; i++)
{
    var genes = Enumerable.Range(0, empties.Count).Select(_ => causeRnd.NextDouble() * 9 + 1).ToArray();
    var g = Mgs21Host.DecodeR1(genes, Puzzle, empties);
    if (RowDuplicates(g) > 0) outOfSpaceR1++;
    initConfR1.Add(CountConflicts(g));
}
var initConfR2 = new List<int>();
for (int i = 0; i < N; i++) initConfR2.Add(CountConflicts(RandomR2(Puzzle, causeRnd)));

Console.WriteLine($"Candidats aleatoires R1 (N={N}, graine 7) :");
Console.WriteLine($"  hors de l'espace admissible (>= 1 ligne en doublon) : {outOfSpaceR1}/{N} = {100.0 * outOfSpaceR1 / N:F1} %");
Console.WriteLine($"  conflits initiaux : moyenne {initConfR1.Average():F1}, min {initConfR1.Min()}, max {initConfR1.Max()}");
Console.WriteLine($"Candidats aleatoires R2 (N={N}) :");
Console.WriteLine($"  hors de l'espace admissible : 0/{N} = 0 % (lignes valides par construction)");
Console.WriteLine($"  conflits initiaux : moyenne {initConfR2.Average():F1}, min {initConfR2.Min()}, max {initConfR2.Max()}");

Candidats aleatoires R1 (N=200, graine 7) :
  hors de l'espace admissible (>= 1 ligne en doublon) : 200/200 = 100,0 %
  conflits initiaux : moyenne 67,9, min 54, max 83
Candidats aleatoires R2 (N=200) :
  hors de l'espace admissible : 0/200 = 0 % (lignes valides par construction)
  conflits initiaux : moyenne 37,4, min 21, max 50

Lecture de la cause — l’arrondi n’ajoute pas du bruit, il expulse de l’espace

La mesure est sans appel : 200 candidats R1 sur 200 (100 %) tombent hors de l’espace admissible (au moins une ligne en double après arrondi), contre 0 sur 200 pour R2 par construction. Et l’écart de départ est massif : 67,9 conflits en moyenne (de 54 à 83) pour un candidat R1 aléatoire, contre 37,4 (de 21 à 50) pour un candidat R2 — les conflits de lignes que R2 ne peut pas avoir, R1 les porte presque tous dès le tirage initial.

La cause est structurelle, pas dynamique. Le décodage par arrondi n’est pas une « imprécision » qui s’atténuerait avec la convergence : c’est une projection discontinue de \([1,10)^{36}\) vers l’ensemble (minuscule dans le volume continu) des grilles admissibles. Trois conséquences pour n’importe quel moteur :

1. La quasi-totalité du volume continu décode hors espace — le moteur R1 dépense son budget à chercher dans une région dont les points sont presque tous invalides, et l’information « tu es proche d’une solution » n’existe plus : deux vecteurs proches peuvent décoder vers des grilles sans rapport, et deux vecteurs distincts peuvent décoder vers la même grille (c’est l’objet de l’exercice 3).
2. Une dimension entière du problème est perdue : en R2, les conflits de lignes sont impossibles — la contrainte est vérifiée par les opérateurs, pas apprise par la recherche. R1 doit résoudre 3 familles de contraintes ; R2 n’en résout que 2.
3. Le gradient continu que le PSO est censé suivre (attiré par gbest) ne survit pas au décodage — d’où la colonne PSO du croisement : le moteur le plus dépendant d’une notion de proximité continue est le premier sacrifié.

C’est la version mesurée du geste « changer de représentation plutôt qu’insister » : avant de régler w, c1 ou c2, demander ce que l’arrondi détruit.

3. Exercices

Les trois exercices étendent l’expérience. Chaque stub s’exécute sans erreur (rendez result non nul quand vous traitez l’exercice).

Exercice 1 — Changer la grille. Relancez le croisement complet sur la deuxième grille facile de Sudoku_Easy51.txt (ligne : 100063025508407060026309001057010290090670530240530600705200304080041950). Le verdict « la représentation domine » survit-il au changement de problème ?

Indice : remplacez PuzzleLine par la nouvelle chaîne, regénérez Puzzle et empties, puis copiez la boucle de la cellule du croisement. Comparez le tableau obtenu au tableau de référence ligne par ligne.

Étape 1 : constatez que seuls Puzzle et empties changent — les moteurs sont déjà paramétrés par le problème. Étape 2 : faites tourner les 16 runs. Étape 3 : confrontez les deux médianes de chaque colonne.

// EXERCICE 1 : refaire le croisement sur la deuxieme grille facile.
// TODO etudiant : reassigner PuzzleLine puis relancer les 4 cellules x 4 graines.
// Etape 1 : nouvelle grille (deuxieme ligne de Sudoku_Easy51.txt)
// string Mgs21Host.PuzzleRef = ... ;
// Etape 2 : relancer les 4 moteurs sur SEEDS
// Etape 3 : comparer medianes et dispersions au tableau de reference
var resultExo1 = null as List<string>;
Console.WriteLine("Exercice a completer : croisement sur la deuxieme grille facile.");

Exercice a completer : croisement sur la deuxieme grille facile.

Exercice 2 — Troisième algorithme. Ajoutez un recuit simulé (température décroissante, mouvement = un échange intra-ligne) aux DEUX représentations et complétez le plan en 2 × 3. Le recuit, qui n’est ni un essaim ni une population, réagit-il à la représentation comme PSO et GA ?

Indice : le mouvement R2 est un RowSwap appliqué par SwapAlgebra21.Move ; en R1, le « voisin » d’un vecteur est le même vecteur avec une coordonnée bruitée — pensez à la probabilité qu’un bruit d’amplitude modeste survive à l’arrondi (amplitude < 0,5 : le candidat décodé ne change pas).

Étape 1 : écrivez RunAnnealR2 (boucle température, acceptation de Metropolis sur CountConflicts). Étape 2 : écrivez RunAnnealR1 sur le même gabarit, bruit gaussien ou uniforme. Étape 3 : même budget (≈ 8 000 évaluations), mêmes graines, même tableau.

// EXERCICE 2 : recuit simule sur les deux representations.
// TODO etudiant : RunAnnealR2 et RunAnnealR1, budget ~8000 evals, graines 0/1/7/42.
// Etape 1 : RunAnnealR2 (temperature decroissante, mouvement = RowSwap)
// Etape 2 : RunAnnealR1 (voisin = coordonnee bruitee, meme acceptation Metropolis)
// Etape 3 : prolonger le tableau croise avec la colonne "recuit"
var resultExo2 = null as List<string>;
Console.WriteLine("Exercice a completer : recuit simule sur R1 et R2.");

Exercice a completer : recuit simule sur R1 et R2.

Exercice 3 — Diversité effective. La cause mesurée en §2 est structurelle (proportion de candidats hors espace). Une seconde cause possible est dynamique : la diversité des candidats décodés. Mesurez, au fil des générations d’un run PSO-R1, le nombre de grilles distinctes produites par le décodage de la population, et comparez-le au nombre de grilles distinctes d’un essaim swap-PSO de même taille.

Indice : sérialisez chaque grille décodée en chaîne (string.Join sur les 81 cellules) et comptez les chaînes distinctes par génération. Si deux vecteurs R1 différents décodent vers la même grille, la population effective de R1 est plus petite que sa population nominale — le moteur croit explorer 40 candidats, il en explore moins.

Étape 1 : instrumentez RunR1/RunSwapPso pour échantillonner la population toutes les 25 générations. Étape 2 : tracez ou imprimez la diversité distincte par échantillon. Étape 3 : reliez au constat de l’Exemple résolu du §2 (l’arrondi colle des candidats distincts sur la même grille).

// EXERCICE 3 : diversite effective des candidats decodes (R1 vs R2).
// TODO etudiant : compter les grilles distinctes par generation dans un run PSO de chaque representation.
// Etape 1 : string GrilleCle(int[,] g) => string.Join(",", g.Cast<int>());
// Etape 2 : echantillonner toutes les 25 generations dans RunR1 et RunSwapPso
// Etape 3 : comparer les deux series et conclure sur la population effective
var resultExo3 = null as List<string>;
Console.WriteLine("Exercice a completer : diversite effective R1 vs R2.");

Exercice a completer : diversite effective R1 vs R2.

Résumé et perspectives

Ce que le croisement a établi (budget ~8 000 évaluations, graines {0, 1, 7, 42}, même fonction de coût) :

• changer d’algorithme à représentation fixée rapporte au mieux un facteur ×4,3 (R1 : PSO 45,0 → GA 10,5) et fait passer R2 de 6,0 à la résolution ;
• changer de représentation à algorithme fixé rapporte ×7,5 au PSO (45,0 → 6,0) et la résolution 4/4 au GA (10,5 → 0) ;
• aucune cellule R1 ne résout (minimum observé : 4 conflits) — à ce budget, aucun algorithme ne compense la relaxation continue + arrondi, et la mesure de cause l’explique : 100 % des candidats décodés tombent hors de l’espace admissible.

La formule de l’introduction est donc démontrée au sens strict sur la colonne PSO (l’effet représentation, 39 conflits, dépasse les deux effets algorithme, 34,5 et 6) et atténuée sur la colonne GA (effets comparables) — le verdict complet est dans la lecture du croisement, avec ses deux temps.

Ce que ce notebook a ajouté au dépôt : la première écriture croisée (représentation × algorithme) d’une expérience que Sudoku-05 avait menée par morceaux (Tranches 3 et 4) sans pouvoir en attribuer l’effet. Le tableau, les graines et le critère de verdict sont pré-enregistrés — l’exercice 1 vérifie sa survie au changement de grille.

La prochaine étape de la série (MGS-20, langage de composition) change encore de niveau : au lieu de choisir la représentation ET l’algorithme à la main, exprimer une intention et laisser le moteur composer les primitives — la direction vient de la spécification, pas de l’assemblage.