MGS-25 : WhaleOptimisation MGS contre mealpy — le WOA canonique face à son jumeau exact

Navigation : << MGS-24 (SA vs mealpy) | Index

Kernel : .NET (C#) — pont PythonNet vers mealpy dans la même exécution

---

Introduction

Trois paires mesurées, trois visages de l’écart : PSO dominé par mealpy (MGS-22), DE quasi-ex-aequo en qualité avec vitesse inversée (MGS-23), SA doublé qualité-vitesse par MGS (MGS-24). La paire Whale Optimization Algorithm apporte deux choses neuves à l’Epic #12373 :

• c’est la paire la plus canonique depuis DE : les deux implémentations suivent Mirjalili & Lewis (2016) avec le même refroidissement linéaire a = 2 → 0 et le même partage 50/50 encerclement/spirale — aucun paramètre propre à aligner, le confond paramétrique est quasi nul ;
• MGS expose une seconde variante du même moteur : WhaleOptimisationNaive, dont l’opérateur bubble-net spiral est remplacé par une simple combinaison convexe 0,5·X + 0,5·X*. C’est la simplification que MGS-19 démontait pièce par pièce ; la mesurer ici face au mealpy canonique dit si la forme de l’opérateur spiral porte de la qualité ou si la moyenne suffit.

Le croisement a donc trois colonnes : MGS standard (spirale), MGS naive (convexe) et mealpy OriginalWOA (spirale, NumPy). Même substrat, même budget, mêmes graines.

---

1. Le protocole apparié, pré-enregistré — hérité de MGS-22, non renégocié

Le protocole est celui de MGS-22 (#12302), repris intégralement pour que les paires de l’Epic soient comparables entre elles :

• même substrat : grille Easy[0] de Sudoku_Easy51.txt, représentation R1 (continu + arrondi), fonction de coût = conflits totaux d’une grille pleine ;
• budget d’évaluations égalisé — mesuré, pas supposé : WOA est population-based des deux côtés, structure identique au DE de MGS-23 (population 50 × 160 générations côté MGS, 160 epochs côté mealpy) ;
• 4 graines nommées {0, 1, 7, 42}, médiane + min/max, jamais un run isolé ;
• contre-vérification croisée du coût : le vainqueur mealpy est décodé et coûté côté C# — sans elle on compare deux fonctions de coût, pas deux moteurs ;
• ms/éval séparé du temps total ;
• graines passées explicitement aux deux moteurs : solve(prob, seed=N) côté mealpy (le paramètre du constructeur est silencieusement ignoré en 3.x), ResetSeed(N) côté MGS ;
• déterminisme vérifié (répétition, conflits identiques exigés) avant de publier le moindre chiffre.

Paramètres par défaut de chaque bibliothèque, mesurés et déclarés (c’est le protocole MGS-22 : on compare les bibliothèques telles que leurs auteurs les livrent) :

moteur	équations	refroidissement	opérateur bubble-net
MGS WhaleOptimisation	Mirjalili & Lewis 2016, Eq. (2.3)-(2.5)	a : 2 → 0 linéaire (a2 : −1 → −2 pour l)	spirale \|X*−X\|·e^{bl}·cos(2πl) + X*, b = 1
MGS WhaleOptimisationNaive	idem	idem	combinaison convexe 0,5·X + 0,5·X*
mealpy OriginalWOA	Mirjalili & Lewis 2016	a = 2 − 2·epoch/epochs (idem)	spirale canonique

Les deux WOA canoniques partagent donc les équations ET le schedule — la différence mesurée ne pouvait pas être plus proche d’un pur effet d’implémentation (composé génétique MGS contre update vectoriel NumPy). La colonne naive, elle, isole la question de l’opérateur : c’est l’exercice 2 qui la pousse plus loin (mixCoef ≠ 0,5).

// === MGS-25 : socle commun — DLLs MGS, grille de référence, fonction de coût ===
// Même socle que MGS-22/23/24 : la représentation R1 (continu + arrondi) est le substrat du bench.
#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 MÊME que MGS-21/22/23/24.
public static string PuzzleLine25 = "902005403100063025508407060026309001057010290090670530240530600705200304080041950";

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

// Fonction de coût du bench : conflits totaux (lignes + colonnes + blocs) sur grille PLEINE.
// Renvoie 0 ssi résolu. Le côté Python réimplémente exactement ce comptage.
public static int CountConflicts25(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;
}

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

public static List<(int r, int c)> EmptyCells25(int[,] p)
{
    var l = new List<(int, int)>();
    for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (p[r, c] == 0) l.Add((r, c));
    return l;
}

// Décodage R1 : arrondi + clamp vers 1..9 sur les cellules vides, ordre de lecture.
public static int[,] DecodeR1_25(double[] genes)
{
    var Puzzle = ParsePuzzle25();
    var empties = EmptyCells25(Puzzle);
    var g = (int[,])Puzzle.Clone();
    for (int k = 0; k < empties.Count; k++)
        g[empties[k].r, empties[k].c] = Math.Max(1, Math.Min(9, (int)Math.Round(genes[k])));
    return g;
}

var Puzzle25 = ParsePuzzle25();
Console.WriteLine($"Grille de référence : {CountEmpty25(Puzzle25)} cellules vides, " +
                  $"{81 - CountEmpty25(Puzzle25)} indices fixes, {EmptyCells25(Puzzle25).Count} gènes R1.");

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

Grille de référence : 36 cellules vides, 45 indices fixes, 36 gènes R1.

Lecture. Le socle est posé, identique à MGS-22/23/24 au nom près — c’est voulu : la comparabilité de l’Epic #12373 tient à ce que chaque paire courre sur exactement le même substrat. 36 cellules vides = 36 gènes continus dans [1, 10), la fonction de coût compte les doublons ligne/colonne/bloc d’une grille pleine et vaut 0 ssi résolue.

// === Moteur MGS : chromosome R1, fitness instrumentée, composés WhaleOptimisation (+ Naive) ===
// WOA canonique Mirjalili & Lewis (2016) en composé géométrique MGS : a décroît 2 -> 0,
// p < 0,5 -> encerclement (|A|>1 : cible aléatoire, sinon meilleure), p >= 0,5 -> bubble-net
// spiral ; la variante Naive remplace la spirale par une combinaison convexe 0,5*X + 0,5*X*.
public class SudokuR1Chromosome25 : ChromosomeBase
{
    private const double LO = 1.0, HI = 10.0;
    public SudokuR1Chromosome25() : base(EmptyCells25(ParsePuzzle25()).Count) { CreateGenes(); }
    public override Gene GenerateGene(int index)
        => new Gene(RandomizationProvider.Current.GetDouble(LO, HI));
    public override IChromosome CreateNew() => new SudokuR1Chromosome25();
    public double[] ToGenes() { var v = new double[Length]; for (int i = 0; i < Length; i++) v[i] = (double)GetGene(i).Value; return v; }
    public int[,] ToGrid() => DecodeR1_25(ToGenes());
}

// Fitness instrumentée : chaque évaluation est comptée — le budget se mesure, il ne se suppose pas.
public class SudokuR1Fitness25 : IFitness
{
    public static int Evals;
    public double Evaluate(IChromosome chromosome)
    {
        Evals++;
        return -CountConflicts25(((SudokuR1Chromosome25)chromosome).ToGrid());
    }
}

public static class Mgs25Host
{
    // Variante custom (exercice 2) : construire l'algorithme à la main pour un mixCoef libre,
    // avec le même converter double-identity que le service utilise par défaut.
    public static IMetaHeuristic BuildWoa(int maxGens, bool naive, double? mixCoef = null)
    {
        if (!naive && mixCoef == null)
            return MetaHeuristicsService.CreateMetaHeuristicByName("WhaleOptimisation", maxGens, 50);
        var conv = new TypedGeometricConverter();
        conv.SetTypedConverter(new GeometricConverter<double>
        {
            IsOrdered = false,
            DoubleToGeneConverter = (geneIndex, geomValue) => geomValue,
            GeneToDoubleConverter = (geneIndex, geneValue) => geneValue
        });
        var woa = new WhaleOptimisationAlgorithm()
        {
            MaxGenerations = maxGens,
            GeometricConverter = conv,
            NoMutation = true
        };
        woa.BubbleOperator = WhaleOptimisationAlgorithm.GetSimpleBubbleNetOperator(
            mixCoef ?? 0.5);
        return woa.Build();
    }

    public static (int conflicts, int evals, double ms, double[] genes) RunWoa(
        int seed, int popSize, int maxGens, bool naive = false, double? mixCoef = null)
    {
        // Seeding AVANT création de population : le RNG est consommé par CreateNew()
        // de chaque individu initial (leçon #12071 / MGS-21).
        FastRandomRandomization.ResetSeed(seed);
        var compound = BuildWoa(maxGens, naive, mixCoef);
        var adam = new SudokuR1Chromosome25();
        var pop = new MetaPopulation(popSize, popSize, adam);
        var ga = new MetaGeneticAlgorithm(
            pop, new SudokuR1Fitness25(),
            new EliteSelection(), new UniformCrossover(0.5f), new UniformMutation(true),
            compound);
        ga.Termination = new GenerationNumberTermination(maxGens);
        SudokuR1Fitness25.Evals = 0;
        var sw = Stopwatch.StartNew();
        ga.Start();
        sw.Stop();
        var best = (SudokuR1Chromosome25)ga.BestChromosome;
        return (CountConflicts25(best.ToGrid()), SudokuR1Fitness25.Evals,
                sw.Elapsed.TotalMilliseconds, best.ToGenes());
    }
}

// Échauffement JIT (courses jetées), puis courses témoins graine 7 : standard ET naive.
var warmupMgs = Mgs25Host.RunWoa(123, 50, 10);
var demoStd = Mgs25Host.RunWoa(7, 50, 160);
var demoNaive = Mgs25Host.RunWoa(7, 50, 160, naive: true);
Console.WriteLine($"MGS WOA spirale (graine 7, témoin) : {demoStd.Item1} conflits, " +
                  $"{demoStd.Item2} évaluations, {demoStd.Item3:F0} ms.");
Console.WriteLine($"MGS WOA naive convexe (graine 7, témoin) : {demoNaive.Item1} conflits, " +
                  $"{demoNaive.Item2} évaluations, {demoNaive.Item3:F0} ms.");

MGS WOA spirale (graine 7, témoin) : 51 conflits, 8000 évaluations, 441 ms.
MGS WOA naive convexe (graine 7, témoin) : 49 conflits, 8000 évaluations, 438 ms.

Lecture. Les deux composés MGS sont branchés sur le même harnais que les paires précédentes : chromosome R1, fitness comptée, seeding avant création de population. Les courses témoins graine 7 donnent les premiers chiffres — spirale 51 conflits contre naive 49 pour 8 000 évaluations chacune — l’échauffement JIT les précède pour que la course mesurée ne paie pas la compilation. Premier indice déjà : la simplification convexe n’est pas écrasée par la spirale canonique.

// === Le pont PythonNet : mealpy dans le même kernel, la même exécution ===
// Recette validée MGS-22 (#12356) : pythonnet 3.1.0, DLL résolue par probe
// (PYTHONNET_PYDLL d'abord, sinon installs standards par OS — aucun chemin machine en dur).
// NB : pythonnet 3.1.0 exige CPython >= 3.13 (symbole PyThreadState_GetUnchecked absent
// de python311.dll) — le probe résout la version la plus HAUTE disponible, et prend la
// DLL au nom le plus long (le stub ABI "python3.dll" ne forwarde pas ce symbole).
#r "nuget: pythonnet,3.1.0"
using Python.Runtime;
static string ResolvePythonDll25()
{
    var env = Environment.GetEnvironmentVariable("PYTHONNET_PYDLL");
    if (!string.IsNullOrEmpty(env) && System.IO.File.Exists(env)) return env;
    if (OperatingSystem.IsWindows())
    {
        // Installs CPython.org standards d'abord (les plus récentes portent les packages récents
        // comme mealpy), ensuite le scan LOCALAPPDATA — un Python périmé qui n'a pas mealpy
        // ne doit pas masquer une install plus récente (pb 2026-08-25 : Python310 2023 devant Python313).
        foreach (var c in new[] { @"C:\Python313\python313.dll", @"C:\Python312\python312.dll" })
            if (System.IO.File.Exists(c)) return c;
        var local = Environment.GetEnvironmentVariable("LOCALAPPDATA");
        if (!string.IsNullOrEmpty(local))
        {
            var pyDir = System.IO.Path.Combine(local, "Programs", "Python");
            if (System.IO.Directory.Exists(pyDir))
            {
                var dirs = System.IO.Directory.GetDirectories(pyDir, "Python3*")
                    .OrderByDescending(d => System.IO.Path.GetFileName(d).Replace("Python", ""))
                    .ToList();
                foreach (var d in dirs)
                {
                    var hit = System.IO.Directory.GetFiles(d, "python3*.dll");
                    if (hit.Length == 0) continue;
                    // python3.dll (stub ABI stable, 10 chars) ne forwarde PAS
                    // PyThreadState_GetUnchecked : preferer la DLL versionnee la
                    // plus longue (ex. python313.dll), comme la branche miniconda.
                    return hit.OrderByDescending(h => System.IO.Path.GetFileName(h).Length).First();
                }
            }
        }
        var home = Environment.GetFolderPath(Environment.SpecialFolder.UserProfile);
        foreach (var root in new[] {
                     System.IO.Path.Combine(home, "miniconda3"),
                     System.IO.Path.Combine(home, "anaconda3"),
                     @"C:\ProgramData\miniconda3",
                     @"C:\ProgramData\anaconda3" })
        {
            if (!System.IO.Directory.Exists(root)) continue;
            var hits = System.IO.Directory.GetFiles(root, "python3*.dll");
            var pick = "";
            foreach (var h in hits)
                if (System.IO.Path.GetFileName(h).Length > 11) pick = h;
            if (pick == "" && hits.Length > 0) pick = hits[0];
            if (pick != "")
            {
                var dirs = new[] { root,
                    System.IO.Path.Combine(root, "Library", "mingw-w64", "bin"),
                    System.IO.Path.Combine(root, "Library", "bin"),
                    System.IO.Path.Combine(root, "Scripts") };
                var path = Environment.GetEnvironmentVariable("PATH") ?? "";
                var toAdd = "";
                foreach (var d in dirs)
                    if (System.IO.Directory.Exists(d) && !path.Contains(d + ";"))
                        toAdd += d + ";";
                if (toAdd != "")
                    Environment.SetEnvironmentVariable("PATH", toAdd + path);
                return pick;
            }
        }
    }
    else
    {
        var libs = new[] { "/usr/lib/x86_64-linux-gnu", "/usr/lib", "/usr/local/lib", "/opt/homebrew/lib" };
        foreach (var dir in libs)
            if (System.IO.Directory.Exists(dir))
            {
                var hit = System.IO.Directory.GetFiles(dir, "libpython3.*");
                foreach (var h in hit)
                    if (h.EndsWith(".so") || h.EndsWith(".dylib")) return h;
            }
    }
    throw new System.IO.FileNotFoundException(
        "DLL Python introuvable : definir PYTHONNET_PYDLL ou installer Python 3.10+ (mealpy requis).");
}
Runtime.PythonDLL = ResolvePythonDll25();
PythonEngine.Initialize();

// Le problème Python : decode + coût réimplémentés à l'identique, compteur d'évals,
// solveur mealpy OriginalWOA avec seed EXPLICITE en solve() (API 3.x — le seed du
// constructeur est ignoré) et journal muet (log_to='nothing').
public static PyModule S25;
using (Py.GIL())
{
    S25 = Py.CreateScope();
    S25.Set("puzzle_line25", PuzzleLine25);
    S25.Exec(@"import sys
import mealpy
from mealpy.swarm_based.WOA import OriginalWOA
from mealpy import Problem, FloatVar
import json as _json

puzzle = [int(ch) for ch in puzzle_line25]
empties = [(i // 9, i % 9) for i in range(81) if puzzle[i] == 0]

def decode(vec):
    g = [puzzle[r * 9:(r + 1) * 9] for r in range(9)]
    for k in range(len(empties)):
        r, c = empties[k]
        v = int(round(float(vec[k])))
        g[r][c] = max(1, min(9, v))
    return g

def cost(g):
    conflicts = 0
    for i in range(9):
        units = ([g[i][j] for j in range(9)],
                 [g[j][i] for j in range(9)],
                 [g[3 * (i // 3) + j // 3][3 * (i % 3) + j % 3] for j in range(9)])
        for unit in units:
            seen = set()
            for v in unit:
                if v in seen:
                    conflicts += 1
                seen.add(v)
    return conflicts

def cost_of_vector(vec):
    return cost(decode(vec))

PY_EVALS = [0]

class SudokuProblem(Problem):
    def __init__(self, bounds=None, minmax='min', **kwargs):
        super().__init__(bounds, minmax, log_to='nothing', **kwargs)
    def obj_func(self, x):
        PY_EVALS[0] += 1
        return float(cost(decode(x)))

def run_mealpy_woa(seed, pop_size, epoch):
    import time
    PY_EVALS[0] = 0
    prob = SudokuProblem(bounds=FloatVar(lb=(1.0,) * len(empties), ub=(10.0,) * len(empties), name='genes'), minmax='min')
    model = OriginalWOA(epoch=epoch, pop_size=pop_size)
    t0 = time.perf_counter()
    g_best = model.solve(prob, seed=seed)
    dt = (time.perf_counter() - t0) * 1000.0
    sol = _json.dumps([float(v) for v in g_best.solution])
    return cost(decode(g_best.solution)), PY_EVALS[0], dt, sol

def bench_mealpy_woa(seeds_json, pop_size, epoch, reps=3):
    out = []
    for sd in _json.loads(seeds_json):
        runs = [run_mealpy_woa(sd, pop_size, epoch) for _ in range(reps)]
        cs = [r[0] for r in runs]
        es = [r[1] for r in runs]
        ts = sorted(r[2] for r in runs)
        med = ts[len(ts) // 2] if len(ts) % 2 == 1 else (ts[len(ts) // 2 - 1] + ts[len(ts) // 2]) / 2.0
        out.append({'seed': sd, 'conflicts': cs[0], 'all_same': len(set(cs)) == 1,
                    'evals': es[0], 'ms': med, 'sol': runs[0][3]})
    return _json.dumps(out)

def time_python_evals(vecs_json, reps=5):
    import time
    vecs = _json.loads(vecs_json)
    ts = []
    for _ in range(reps):
        t0 = time.perf_counter()
        for v in vecs:
            cost_of_vector(v)
        ts.append((time.perf_counter() - t0) * 1000.0)
    ts.sort()
    return ts[len(ts) // 2]

# Defaults mealpy OriginalWOA (3.x) : mesures, pas doc — aucun parametre propre,
# le refroidissement a = 2 - 2*epoch/epochs vit dans evolve().
_m = OriginalWOA(epoch=10, pop_size=5)
__defaults__ = 'mealpy OriginalWOA defaults: aucun parametre propre (epoch, pop_size seuls)'
__mealpy_ver__ = 'mealpy ' + mealpy.__version__ + ' sur Python ' + sys.version.split()[0]");
    Console.WriteLine($"Pont PythonNet actif : {S25.Get<string>("__mealpy_ver__")}");
    Console.WriteLine($"Parametres defaut mealpy : {S25.Get<string>("__defaults__")}");
}

// --- Sanity check : la fonction de coût est-elle la MÊME des deux côtés ? ---
// 3 vecteurs témoins DÉTERMINISTES (LCG écrit à la main), décodés et costés des deux côtés.
public static double[] LcgVector25(int seed, int n)
{
    uint state = (uint)seed;
    var v = new double[n];
    for (int i = 0; i < n; i++)
    {
        state = state * 1664525u + 1013904223u;
        v[i] = 1.0 + (state / 4294967296.0) * 9.0; // uniforme dans [1, 10)
    }
    return v;
}

var witnessVectors = new[] { LcgVector25(1, 36), LcgVector25(2, 36), LcgVector25(3, 36) };
using (Py.GIL())
{
    S25.Set("__witness_json__",
        System.Text.Json.JsonSerializer.Serialize(witnessVectors.Select(v => v.ToList()).ToList()));
    S25.Exec(@"__py_costs__ = _json.dumps([cost_of_vector(v) for v in _json.loads(__witness_json__)])");
    var pyCosts = System.Text.Json.JsonSerializer.Deserialize<List<int>>(S25.Get<string>("__py_costs__"));
    var csCosts = witnessVectors.Select(v => CountConflicts25(DecodeR1_25(v))).ToList();
    bool identical = pyCosts.SequenceEqual(csCosts);
    Console.WriteLine($"Sanity check cout : C# {string.Join(",", csCosts)} | Python {string.Join(",", pyCosts)} " +
                      $"-> {(identical ? "IDENTIQUE" : "DIFFERENT")}");
}

Installed Packages

• pythonnet, 3.1.0

Pont PythonNet actif : mealpy 3.0.2 sur Python 3.13.3
Parametres defaut mealpy : mealpy OriginalWOA defaults: aucun parametre propre (epoch, pop_size seuls)
Sanity check cout : C# 67,71,60 | Python 67,71,60 -> IDENTIQUE

Lecture. Le pont PythonNet est actif et la sanity check porte tout le bench : les trois vecteurs témoins LCG, décodés et coûtés indépendamment des deux côtés, donnent exactement les mêmes conflits (67, 71, 60 des deux côtés — IDENTIQUE). Sans cette égalité prouvée, une différence mesurée entre moteurs pourrait n’être qu’une différence entre les deux fonctions de coût. Le WOA mealpy n’expose aucun paramètre propre — le refroidissement vit dans evolve(), vérifié à la source : a = 2 − 2·epoch/epochs, le même schedule que MGS.

// === Moteur mealpy : course témoin + contre-vérification croisée du vainqueur ===
using (Py.GIL())
{
    // Échauffement symétrique (course jetée), puis course témoin graine 7.
    S25.Exec(@"_wu_c, _wu_e, _wu_t, _wu_sol = run_mealpy_woa(123, 50, 10)
__d_c__, __d_e__, __d_t__, __d_sol__ = run_mealpy_woa(7, 50, 160)");
    int dConflicts = S25.Get<int>("__d_c__");
    int dEvals = S25.Get<int>("__d_e__");
    double dMs = S25.Get<double>("__d_t__");
    Console.WriteLine($"mealpy OriginalWOA (graine 7, témoin) : {dConflicts} conflits, " +
                      $"{dEvals} évaluations, {dMs:F0} ms.");

    // Contre-vérification croisée : le vainqueur mealpy, décodé et costé côté C#.
    var solJson = S25.Get<string>("__d_sol__");
    var genes = System.Text.Json.JsonSerializer.Deserialize<double[]>(solJson);
    int csRecheck = CountConflicts25(DecodeR1_25(genes));
    Console.WriteLine($"Contre-vérif croisée : coût C# du meilleur mealpy = {csRecheck} " +
                      $"(Python rapporte {dConflicts}) -> {(csRecheck == dConflicts ? "IDENTIQUE" : "DIFFERENT")}");
}

mealpy OriginalWOA (graine 7, témoin) : 54 conflits, 8050 évaluations, 615 ms.
Contre-vérif croisée : coût C# du meilleur mealpy = 54 (Python rapporte 54) -> IDENTIQUE

---

2. Le croisement — 3 moteurs × 4 graines à budget égal

Population 50, 160 générations (MGS, deux variantes) / 160 epochs (mealpy), graines {0, 1, 7, 42}, trois répétitions par graine côté MGS pour la médiane de temps (amendement anti-pic GC), déterminisme exigé partout. La colonne naive court le même budget que la colonne spirale : l’écart mesuré entre les deux MGS est l’effet opérateur, à budget et graines constants.

// === LE BENCH : 3 moteurs x 4 graines {0,1,7,42} — MGS spirale, MGS naive, mealpy,
// population 50 x 160 générations/epochs : budgets mesurés par les compteurs. ===
public class BenchRow25
{
    public int seed { get; set; }
    public int conflicts { get; set; }
    public bool all_same { get; set; }
    public int evals { get; set; }
    public double ms { get; set; }
    public string sol { get; set; }
}

int[] Seeds25 = { 0, 1, 7, 42 };

// --- Côté MGS (C#), deux variantes : 3 répétitions par graine, ms = médiane ---
var mgsRows = new List<(int seed, int conflicts, int evals, double ms, bool allSame)>();
var naiveRows = new List<(int seed, int conflicts, int evals, double ms, bool allSame)>();
foreach (var sd in Seeds25)
{
    foreach (var (naive, rows) in new[] { (false, mgsRows), (true, naiveRows) })
    {
        var runs3 = new List<(int c, int e, double t)>();
        for (int rep = 0; rep < 3; rep++)
        {
            var r = Mgs25Host.RunWoa(sd, 50, 160, naive: naive);
            runs3.Add((r.Item1, r.Item2, r.Item3));
        }
        var times = runs3.Select(x => x.t).OrderBy(t => t).ToList();
        double med = times[1];
        rows.Add((sd, runs3[0].c, runs3[0].e, med, runs3.All(x => x.c == runs3[0].c)));
    }
}

// --- Côté mealpy (Python, boucle unique dans le scope) ---
string mealpyJson;
using (Py.GIL())
{
    S25.Set("__seeds_json__", System.Text.Json.JsonSerializer.Serialize(Seeds25.ToList()));
    S25.Exec(@"__bench_json__ = bench_mealpy_woa(__seeds_json__, 50, 160)");
    mealpyJson = S25.Get<string>("__bench_json__");
}
var mealpyRows = System.Text.Json.JsonSerializer.Deserialize<List<BenchRow25>>(mealpyJson);

// --- Table ---
static double Median25(List<int> xs)
{
    var s = xs.OrderBy(x => x).ToList();
    return (s.Count % 2 == 1) ? s[s.Count / 2] : (s[s.Count / 2 - 1] + s[s.Count / 2]) / 2.0;
}

Console.WriteLine($"{"moteur",-13} {"graine",6} {"conflits",9} {"evals",7} {"ms",8} {"ms/eval",8}");
foreach (var r in mgsRows)
    Console.WriteLine($"{"MGS spirale",-13} {r.seed,6} {r.conflicts,9} {r.evals,7} {r.ms,8:F0} {r.ms / r.evals,8:F3}");
foreach (var r in naiveRows)
    Console.WriteLine($"{"MGS naive",-13} {r.seed,6} {r.conflicts,9} {r.evals,7} {r.ms,8:F0} {r.ms / r.evals,8:F3}");
foreach (var r in mealpyRows)
    Console.WriteLine($"{"mealpy",-13} {r.seed,6} {r.conflicts,9} {r.evals,7} {r.ms,8:F0} {r.ms / r.evals,8:F3}");

var stdC = mgsRows.Select(r => r.conflicts).ToList();
var nauC = naiveRows.Select(r => r.conflicts).ToList();
var mpC = mealpyRows.Select(r => r.conflicts).ToList();
double stdMsEval = mgsRows.Average(r => r.ms / r.evals);
double nauMsEval = naiveRows.Average(r => r.ms / r.evals);
double mpMsEval = mealpyRows.Average(r => r.ms / r.evals);
Console.WriteLine();
Console.WriteLine($"MGS spirale : médiane conflits {Median25(stdC):F1} (min {stdC.Min()}, max {stdC.Max()}), ms/éval moyen {stdMsEval:F3}");
Console.WriteLine($"MGS naive   : médiane conflits {Median25(nauC):F1} (min {nauC.Min()}, max {nauC.Max()}), ms/éval moyen {nauMsEval:F3}");
Console.WriteLine($"mealpy      : médiane conflits {Median25(mpC):F1} (min {mpC.Min()}, max {mpC.Max()}), ms/éval moyen {mpMsEval:F3}");
Console.WriteLine($"Rapport ms/éval mealpy/MGS spirale : {mpMsEval / stdMsEval:F2}x");
int detAll = mgsRows.Count(r => r.allSame) + naiveRows.Count(r => r.allSame) + mealpyRows.Count(r => r.all_same);
Console.WriteLine($"Déterminisme : conflits identiques sur les 3 répétitions pour {detAll}/12 paires graine-moteur.");

moteur        graine  conflits   evals       ms  ms/eval
MGS spirale        0        46    8000      328    0,041
MGS spirale        1        50    8000      337    0,042
MGS spirale        7        51    8000      297    0,037
MGS spirale       42        49    8000      290    0,036
MGS naive          0        53    8000      320    0,040
MGS naive          1        50    8000      315    0,039
MGS naive          7        49    8000      284    0,035
MGS naive         42        46    8000      461    0,058
mealpy             0        52    8050      535    0,066
mealpy             1        50    8050      582    0,072
mealpy             7        54    8050      535    0,066
mealpy            42        50    8050      584    0,073

MGS spirale : médiane conflits 49,5 (min 46, max 51), ms/éval moyen 0,039
MGS naive   : médiane conflits 49,5 (min 46, max 53), ms/éval moyen 0,043
mealpy      : médiane conflits 51,0 (min 50, max 54), ms/éval moyen 0,069
Rapport ms/éval mealpy/MGS spirale : 1,77x
Déterminisme : conflits identiques sur les 3 répétitions pour 12/12 paires graine-moteur.

// === Coût par évaluation : la fitness seule, hors moteur, 500 vecteurs identiques ===
// Les vecteurs sont générés côté C# (LCG, graines 42..541) et passés en JSON au Python :
// les DEUX côtés chronomètrent decode+coût sur exactement les mêmes 500 points.
int K25 = 500;
var benchVecs = new List<double[]>();
for (int i = 0; i < K25; i++) benchVecs.Add(LcgVector25(42 + i, 36));

var csTimes = new List<double>();
for (int rep = 0; rep < 5; rep++)
{
    var swRep = Stopwatch.StartNew();
    foreach (var v in benchVecs) CountConflicts25(DecodeR1_25(v));
    swRep.Stop();
    csTimes.Add(swRep.Elapsed.TotalMilliseconds);
}
csTimes.Sort();
double csMs = csTimes[2]; // médiane de 5 (amendement §2)

double pyMs;
using (Py.GIL())
{
    S25.Set("__vecs_json__", System.Text.Json.JsonSerializer.Serialize(benchVecs.Select(v => v.ToList()).ToList()));
    S25.Exec(@"__py_ms__ = time_python_evals(__vecs_json__)");
    pyMs = S25.Get<double>("__py_ms__");
}

Console.WriteLine($"Fitness seule, {K25} vecteurs identiques (médiane de 5 répétitions par côté) :");
Console.WriteLine($"  C#     : {csMs:F1} ms total -> {csMs / K25:F3} ms/éval");
Console.WriteLine($"  Python : {pyMs:F1} ms total -> {pyMs / K25:F3} ms/éval");
Console.WriteLine($"  rapport Python/C# : {pyMs / csMs:F2}x");

Fitness seule, 500 vecteurs identiques (médiane de 5 répétitions par côté) :
  C#     : 3,4 ms total -> 0,007 ms/éval
  Python : 21,3 ms total -> 0,043 ms/éval
  rapport Python/C# : 6,24x

Lecture du croisement. La paire la plus canonique de l’Epic donne le croisement le plus serré :

• qualité : les deux MGS sont ex æquo en médiane (49,5 [46-51] spirale, 49,5 [46-53] naive) et mealpy ferme la marche (51,0 [50-54]) — sans gagner une seule graine nettement (ex æquo sur la 1, derrière sur les trois autres). L’écart médian MGS-mealpy est de 1,5 conflits : à la marge du bruit de graine, mais l’ordre des étendues est net (mealpy [50-54] ne touche jamais les 46-48 que les MGS atteignent) ;
• l’opérateur ne paie pas ici : spirale et combinaison convexe sont indiscernables à ce budget sur ce problème (2 graines chacune, étendues quasi identiques) — la forme de l’opérateur bubble-net n’est pas ce qui sépare les moteurs sur Sudoku-R1. C’est la contre-mesure directe de MGS-19, qui démontait le composant : détaché, il « fonctionne » — ici on voit qu’à budget égal la spirale canonique n’apporte pas davantage mesurable non plus ;
• vitesse : l’évaluation MGS est 1,77× moins chère (0,039 contre 0,069 ms/éval ; run original : 1,69×) — entre le coude-à-coude du PSO (0,8×-1,0× selon la machine) et le 2,4×-3,3× du DE/SA (re-exécutions #13407) ;
• le protocole est tenu : 8 000 évaluations MGS contre 8 050 mealpy (la population initiale compte pour 50), déterminisme 12/12, contre-vérification croisée du coût IDENTIQUE (cellule témoin ci-dessus).

À noter aussi : le WOA est le pire moteur de l’Epic sur ce problème, toutes colonnes confondues (médianes ~50 conflits contre 27 pour le SA, 21-25 pour le DE, 28-43 pour le PSO) — la contraction rapide vers le barycentre épuise la diversité avant la résolution ; le Sudoku-R1 n’est pas un terrain qui favorise les baleines.

Lecture du coût par évaluation. La fitness C# isolée reste 6,24× plus rapide (0,007 contre 0,043 ms/éval ; run original : 3,49× — l’amplitude du ratio fitness est sensible à la machine, l’ordre ne l’est pas). L’écart moteur (1,77×) reste sous l’écart fitness, comme sur DE et SA : le composé MGS ne paie qu’une fraction du surcoût de langage.

Verdict de la paire. Sur la paire la plus symétrique de l’Epic — mêmes équations, même schedule, aucun paramètre à aligner — l’implémentation MGS rejoint ou devance mealpy : qualité ex æquo entre variantes MGS, mealpy légèrement derrière et surtout plus lent par évaluation. Quatre paires mesurées, quatre histoires différentes : l’écart constaté sur le PSO n’est ni une propriété systématique des composés (WOA et SA le réfutent) ni un accident isolé (DE le resserre) — c’est la paire PSO qui est l’outlier, hypothèse que la synthèse de l’Epic devra trancher.

---

Exercice 1 : budget ×4 — l’ordre des trois colonnes survit-il ?

MGS-22/23/24 posaient la même question. Un écart qui se referme à budget accru dit « le moteur distillé converge plus lentement mais atteint le même plateau » ; un écart stable dit « plateau différent ». Ici la question a une dimension supplémentaire : la colonne naive, dont l’opérateur convexe ne peut que contracter la population vers le barycentre courant, a-t-elle un déficit que le budget comble — ou est-ce structurel ?

À compléter (décommentez dans la cellule suivante) :
1. Relancez les trois côtés à budget x4 (MGS : 640 générations, les deux variantes ; mealpy : 640 epochs).
2. Comparez les médianes obtenues à celles du croisement.
3. Verdict : l'ordre spirale/naive/mealpy est-il stable à budget accru ?

// EXERCICE 1 : budget x4 — MGS pop 50, 640 générations (spirale + naive) ; mealpy 640 epochs.
// Décommentez et exécutez :
// foreach (var sd in new[] {0, 1, 7, 42})
// {
//     var rs = Mgs25Host.RunWoa(sd, 50, 640);
//     var rn = Mgs25Host.RunWoa(sd, 50, 640, naive: true);
//     Console.WriteLine($"MGS WOA x4 (graine {sd}) : spirale {rs.Item1} conflits ({rs.Item3:F0} ms), " +
//         $"naive {rn.Item1} conflits ({rn.Item3:F0} ms).");
// }
// using (Py.GIL())
// {
//     S25.Set("__seeds_json__", System.Text.Json.JsonSerializer.Serialize(new[] {0, 1, 7, 42}.ToList()));
//     S25.Exec(@"__bench_x4_json__ = bench_mealpy_woa(__seeds_json__, 50, 640)");
//     Console.WriteLine(S25.Get<string>("__bench_x4_json__"));
// }

Console.WriteLine("Exercice a completer (decommentez le bloc ci-dessus).");

Exercice a completer (decommentez le bloc ci-dessus).

Exercice 2 : mixCoef — de combien penche la moyenne du Naive ?

L’opérateur naive écrit mixCoef·X + (1−mixCoef)·X* avec mixCoef = 0,5 : le candidat et la meilleure solution reçoivent le même poids. RunWoa accepte un mixCoef libre (construction directe du composé, même converter que le service) — pencher la moyenne vers X* (0,25) ou vers le candidat (0,75) dit dans quel sens l’asymétrie aide.

// EXERCICE 2 : mixCoef 0.25 (vers X*) et 0.75 (vers le candidat), 4 graines, budget standard.
// Décommentez et exécutez :
// foreach (var mc in new[] {0.25, 0.75})
// {
//     var line = new List<string>();
//     foreach (var sd in new[] {0, 1, 7, 42})
//     {
//         var r = Mgs25Host.RunWoa(sd, 50, 160, mixCoef: mc);
//         line.Add($"graine {sd}: {r.Item1} conflits");
//     }
//     Console.WriteLine($"mixCoef={mc} : {string.Join(" | ", line)}");
// }

Console.WriteLine("Exercice a completer (decommentez le bloc ci-dessus).");

Exercice a completer (decommentez le bloc ci-dessus).

Exercice 3 : profiler la fitness — où va la milliseconde ?

La cellule du coût par évaluation compare déjà le total decode+coût. Pour localiser la différence, séparez les deux étapes côté Python (décoder une fois, coûter N fois) et comparez au profil C# équivalent.

// EXERCICE 3 : profil decode vs cost, 500 vecteurs, deux côtés.
// Décommentez et exécutez (adapté de MGS-23/24 exercice 3) :
// var decSw = Stopwatch.StartNew();
// foreach (var v in benchVecs) DecodeR1_25(v);
// decSw.Stop();
// Console.WriteLine($"C# decode seul : {decSw.Elapsed.TotalMilliseconds / K25:F3} ms/vec " +
//     $"(reste = coût : {(csMs - decSw.Elapsed.TotalMilliseconds) / K25:F3} ms/vec)");
// using (Py.GIL())
// {
//     S25.Set("__vecs_json__", System.Text.Json.JsonSerializer.Serialize(benchVecs.Select(v => v.ToList()).ToList()));
//     S25.Exec(@"import time
// _vecs = _json.loads(__vecs_json__)
// _t0 = time.perf_counter()
// _grids = [decode(v) for v in _vecs]
// _t1 = time.perf_counter()
// for g in _grids: cost(g)
// _t2 = time.perf_counter()
// print(f'Python decode seul : {(_t1-_t0)*1000.0/len(_vecs):.3f} ms/vec, coût : {(_t2-_t1)*1000.0/len(_vecs):.3f} ms/vec')");
// }

Console.WriteLine("Exercice a completer (decommentez le bloc ci-dessus).");

Exercice a completer (decommentez le bloc ci-dessus).