MGS-7 : TSP combinatoire – la grammaire de composition est agnostique à la représentation

← MGS-6 Benchmarks | ↑ Série MGS

Question centrale. MGS-5 a montré que les métaheuristiques composées géométriques (WOA) se reconstruisent depuis des primitives sur des surfaces continues (gènes en double). Mais la grammaire de composition (Match, Container, Scoped, Islands) vit sous la couche géométrique. Cette couche fait-elle une hypothèse sur le type des gènes ?

Ce notebook le vérifie : la même grammaire structure la recherche sur un problème de permutation — le Voyageur de Commerce (TSP), où les gènes sont des index de villes entiers — sans aucune adaptation. Si les primitives de composition n’avaient pas été conçues de façon agnostique à la représentation (comme le sont les opérateurs de GeneticSharp : bit, permutation, arbre, flottant), on ne pourrait pas réutiliser IslandMetaHeuristic tel quel sur TSP. C’est « components over metaphors » en pratique : les briques ne présument pas du domaine.

// Wiring : charge MetaGeneticSharp + GeneticSharp + GeneticSharp.Extensions (TSP).
// Prérequis : dotnet build ..\MetaGeneticSharp\MetaGeneticSharp.sln
#r "..\MetaGeneticSharp\src\MetaGeneticSharp.Domain\bin\Debug\net9.0\GeneticSharp.Infrastructure.Framework.dll"
#r "..\MetaGeneticSharp\src\MetaGeneticSharp.Domain\bin\Debug\net9.0\GeneticSharp.Domain.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"
#r "..\MetaGeneticSharp\src\MetaGeneticSharp.Extensions\bin\Debug\net9.0\MetaGeneticSharp.Extensions.dll"
#r "..\MetaGeneticSharp\src\MetaGeneticSharp.Extensions\bin\Debug\net9.0\GeneticSharp.Extensions.dll"

using MetaGeneticSharp;
using GeneticSharp;
using GeneticSharp.Extensions;

Console.WriteLine("DLLs chargées (incluant GeneticSharp.Extensions = TSP).");
Console.WriteLine($"  TspFitness          : {typeof(TspFitness).Name}");
Console.WriteLine($"  TspChromosome       : {typeof(TspChromosome).Name}");
Console.WriteLine($"  IslandMetaHeuristic : {typeof(IslandMetaHeuristic).Name}");
Console.WriteLine($"  MigrationMode       : {typeof(MigrationMode).Name}");
DLLs chargées (incluant GeneticSharp.Extensions = TSP).
  TspFitness          : TspFitness
  TspChromosome       : TspChromosome
  IslandMetaHeuristic : IslandMetaHeuristic
  MigrationMode       : MigrationMode

Le problème : 20 villes, gènes = index entiers

TspFitness génère N villes dans un carré et mesure la longueur totale du tour — les gènes sont l’ordre de visite, c’est-à-dire une permutation des index 0..N-1. GeneticSharp maximise le fitness, donc TspFitness.Evaluate renvoie 1 - longueur/(N*1000) (tour court ⇒ fitness élevé). La métrique qu’on surveille est la longueur du tour (TspChromosome.Distance), qu’on minimise.

On fixe le générateur aléatoire (FastRandomRandomization.ResetSeed) pour que les villes et les populations initiales soient reproductibles d’une configuration à l’autre — comparaison équitable.

// Reproductibilité : graine fixe. Les villes sont générées une fois (partagées entre configs).
void ResetRng(int seed) => FastRandomRandomization.ResetSeed(seed);

const int N = 20;
ResetRng(42);
var fitness = new TspFitness(N, 0, 100, 0, 100);
Console.WriteLine($"TSP : {N} villes chargées dans [0,100]².");
TSP : 20 villes chargées dans [0,100]².

Un harness commun

Les trois configurations (baseline, îles, exercices) partagent le même moteur MetaGeneticAlgorithm. On factorise l’exécution dans un helper qui enregistre, à chaque génération, la longueur du meilleur tour. C’est ici que l’agnosticité se manifeste concrètement : le helper ne sait pas que les gènes sont des permutations — il pilote le moteur sur des IChromosome génériques et ne lit le type concret (TspChromosome) que pour extraire la métrique métier.

record RunResult(string Label, double FinalTourLength, double[] BestPerGen);

RunResult Run(string label, int generations, int popSize,
              ICrossover crossover, IMutation mutation, IMetaHeuristic meta)
{
    ResetRng(7); // population initiale reproductible : mêmes villes, même départ pour chaque config.
    var adam = new TspChromosome(N);
    var population = new MetaPopulation(popSize, popSize, adam);
    var ga = new MetaGeneticAlgorithm(population, fitness,
        new EliteSelection(), crossover, mutation, meta)
    {
        Termination = new GenerationNumberTermination(generations)
    };

    var best = new List<double>();
    ga.GenerationRan += (_, _) =>
    {
        // MetaPopulation est order-preserving : BestChromosome n'est pas peuplé au moment de l'event.
        // On déduit le meilleur depuis Chromosomes par fitness (toujours fixé par Evaluate).
        // Fitness max <=> tour le plus court ; ce chromosome a son .Distance fixé (même Evaluate).
        var bestChrom = ga.Population.CurrentGeneration.Chromosomes
            .OrderByDescending(c => c.Fitness).First();
        best.Add(((TspChromosome)bestChrom).Distance);
    };
    ga.Start();

    double final = best.Count > 0 ? best[^1] : double.NaN;
    return new RunResult(label, final, best.ToArray());
}

Console.WriteLine("Helper Run prêt.");
Helper Run prêt.

Config 1 — baseline : GA classique

La DefaultMetaHeuristic reproduit le comportement GA standard : sélection élitiste → croisement (OrderedCrossover, OX1) → mutation (ReverseSequenceMutation) → réinsertion élitiste. Population panmictique : aucun partitionnement, tous les chromosomes interagissent.

var baseline = Run("Baseline (panmictic)", 100, 40,
    new OrderedCrossover(), new ReverseSequenceMutation(),
    new DefaultMetaHeuristic());
Console.WriteLine($"{baseline.Label,-26} tour final = {baseline.FinalTourLength:F1}");
Baseline (panmictic)       tour final = 455,3

Config 2 — modèle insulaire sur permutations

Mêmes opérateurs, mais IslandMetaHeuristic(10, 4, ...) partitionne les 40 chromosomes en 4 îles de 10. Chaque île évolue indépendamment ; la migration (mode Static, période 5) échange des chromosomes entiers entre îles. Point clé : aucune arithmétique sur les gènes — la migration déplace des permutations complètes, pas des positions réinterpolées. C’est précisément pourquoi le modèle fonctionne aussi bien sur des permutations que sur des vecteurs continus (MGS-4).

var islandMeta = new IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic())
{
    MigrationMode = MigrationMode.Static,
    MigrationsGenerationPeriod = 5,
};
var island = Run("Islands (4 x 10, Static)", 100, 40,
    new OrderedCrossover(), new ReverseSequenceMutation(),
    islandMeta);
Console.WriteLine($"{island.Label,-26} tour final = {island.FinalTourLength:F1}");
Islands (4 x 10, Static)   tour final = 512,1

Config 3 — un crossover géométrique sur les permutations (Moraglio)

La Lecture précédente (et MGS-5) présente les composés géométriques comme typés : WOA, EO font de l’arithmétique sur des double. C’est vrai pour leurs opérateurs continus. Mais la théorie du crossover géométrique (Moraglio & Poli, GECCO 2004 ; thèse Moraglio 2007) est plus générale : un crossover est géométrique si la progéniture se situe sur le segment métrique entre ses parents — et ce, dans n’importe quel espace métrique, pas seulement euclidien.

Pour les permutations, la métrique naturelle est la distance de swap (combien de transpositions séparent deux ordres). Le GeometricCrossover<int> du fork, muni de son OrderedEmbedding<int> (IsOrdered = true), réalise cela concrètement :

  1. il mappe les parents (permutations d’indices de villes) vers l’espace métrique ;
  2. applique l’opérateur géométrique (ici le centroïde par position) → une cible métrique ;
  3. remappe vers une permutation valide en partant d’un clone du premier parent et en marchant par swaps vers la cible (FlipGene) — chaque transposition rapproche de la cible, la progéniture reste une permutation à chaque pas.

C’est l’incarnation du geodesic crossover de Moraglio : la progéniture est un point du segment swap-distance entre les parents. Le même GeometricCrossover qui servait aux composés continus (DE/WOA/EO/FBI) s’applique donc aux permutations via l’embedding — c’est l’embedding (la métrique), pas l’opérateur, qui porte la géométrie.

Pivot deep learning géométrique. Les indices de villes sont des étiquettes arbitraires, pas des coordonnées ordinales : le centroïde (v₁ + v₂) / 2 n’a aucun sens géographique. Le deep learning géométrique (Bronstein et al., Geometric Deep Learning) formalise cette intuition — un bon embedding doit être équivariant par permutation (aucun ordre de ville n’est privilégié) et refléter la structure du problème (ici, la géométrie euclidienne des villes dans [0, 100]²). Un embedding appris ou positionnel ferait mieux ; le centroïde naïf sur étiquettes est la baseline qui mesure précisément la limite que la théorie prédit. C’est l’angle mort signalé par le user (« on touche aux limites de ce que je comprenais à l’époque ») et que les insights récents du geometric DL permettent désormais de nommer.

// Config 3 : crossover géométrique de Moraglio sur permutations (OrderedEmbedding swap-walking).
// GeometricCrossover<int>(ordered:true, 2) auto-câble un OrderedEmbedding{IsOrdered=true} :
// la progéniture marche par swaps vers le centroïde métrique -> permutation valide à chaque pas.
// Mêmes parents initiaux reproductibles (ResetRng(7) dans Run) que baseline + îles -> comparaison équitable.
var geometric = Run("Geometric (Moraglio)", 100, 40,
    new GeometricCrossover<int>(ordered: true),
    new ReverseSequenceMutation(),
    new DefaultMetaHeuristic());
Console.WriteLine($"{geometric.Label,-26} tour final = {geometric.FinalTourLength:F1}");
Geometric (Moraglio)       tour final = 596,9

Config 4 — une seconde géométrie : la distance d’insertion (Ulam)

La Config 3 a choisi la métrique de swap (distance de Cayley : combien de transpositions séparent deux ordres). Mais une permutation admet plusieurs métriques naturelles. La distance d’insertion (ou distance d’Ulam) compte combien d’éléments il faut déplacer — en décalant les autres — pour passer d’un ordre à l’autre : un seul déplacement peut faire progresser un élément de plusieurs positions d’un coup, là où un swap n’échange que deux éléments voisins en positions.

Le fork expose un second embedding, InsertionEmbedding<int>, qui réalise cette autre géométrie : la progéniture marche vers le centroïde métrique non plus par FlipGene (transposition de deux positions) mais par InsertAt (extraction d’un élément + décalage du segment intermédiaire + repose à la destination).

C’est le point central du deep learning géométrique. La « géométrie » d’un crossover n’est pas unique : elle est déterminée par le choix de la métrique. Deux métriques distinctes (swap vs insertion) définissent deux espaces métriques distincts, donc deux segments géodésiques distincts entre les mêmes parents, donc des descendants différents atteignables en un seul pas de crossover. Changer d’embedding change le paysage exploré, sans toucher au moteur (GeometricCrossover) ni à l’opérateur géométrique (le centroïde) — c’est l’embedding qui porte la géométrie, pas l’inverse.

Démonstration directe. Avant le run, montrons sur un petit exemple que swap et insertion, partant du même parent vers la même cible (une permutation), n’atteignent pas le même descendant en un pas. La subtilité : l’opérateur centroïde à deux parents produit une cible qui n’est pas une permutation (le milieu de [0,1,2] et [2,0,1] est [1,0.5,1.5]), et les deux walks dégradent alors symétriquement — c’est précisément la limite du centroïde naïf signalée plus haut. La distinction géométrique n’est nette que vers une cible qui est elle-même une permutation, ce que l’on fixe ci-dessous.

// Config 4 : crossover géométrique sous la métrique d'insertion (Ulam).
// GeometricCrossover<int>(ordered:true) câble par DÉFAUT OrderedEmbedding (swap/Cayley = Config 3).
// Pour la métrique d'insertion on INJECTE InsertionEmbedding : la progéniture marche vers le
// centroïde par InsertAt (déplacement+décalage), pas par FlipGene (swap).

// (A) Démonstration RÉELLE : swap vs insertion vers une MÊME cible-permutation, en un pas.
// Un chromosome de permutation minimal (sous-classe de ChromosomeBase) pour l'illustration.
public sealed class IntPerm : ChromosomeBase
{
    private readonly int[] _init;
    public IntPerm(int[] values) : base(values.Length)
    {
        _init = values;
        for (int i = 0; i < values.Length; i++) ReplaceGene(i, new Gene(values[i]));
    }
    public override IChromosome CreateNew() => new IntPerm(_init);
    public override Gene GenerateGene(int geneIndex) => new Gene(_init[geneIndex]);
    public int[] ToArray() => GetGenes().Select(g => (int)g.Value).ToArray();
}

var permParent = new IntPerm(new[] { 0, 1, 2, 3, 4 });
var permTarget = new[] { 2, 0, 1, 3, 4 };   // une permutation valide (= la cible métrique)

// SingleFirstAllowed : UN seul pas accepté vers la cible, puis retour.
var swapEmb = new OrderedEmbedding<int>
{
    IsOrdered = true,
    GeneSelectionMode = GeneSelectionMode.SingleFirstAllowed,
};
var insertionEmb = new InsertionEmbedding<int>
{
    IsOrdered = true,
    GeneSelectionMode = GeneSelectionMode.SingleFirstAllowed,
};

var swapOffspring      = ((IntPerm)swapEmb.MapFromGeometry(
    new List<IChromosome> { permParent }, permTarget)).ToArray();
var insertionOffspring = ((IntPerm)insertionEmb.MapFromGeometry(
    new List<IChromosome> { permParent }, permTarget)).ToArray();

Console.WriteLine($"  parent             = [{string.Join(", ", permParent.ToArray())}]");
Console.WriteLine($"  cible (permutation)= [{string.Join(", ", permTarget)}]");
Console.WriteLine($"  1 pas swap (Cayley)    = [{string.Join(", ", swapOffspring)}]   (transposition)");
Console.WriteLine($"  1 pas insertion (Ulam) = [{string.Join(", ", insertionOffspring)}]   (déplacement+décalage)");
Console.WriteLine($"  -> distincts en un pas ? {(!swapOffspring.SequenceEqual(insertionOffspring))}");
Console.WriteLine();

// (B) Run GA sous la métrique d'insertion : mêmes parents initiaux (ResetRng(7) dans Run)
// que baseline + îles + géométrique(swap) -> seul le choix de la métrique diffère.
var insertionGeo = new GeometricCrossover<int>(ordered: true);
insertionGeo.GeometryEmbedding = new InsertionEmbedding<int> { IsOrdered = true };
var insertion = Run("Geometric (insertion/Ulam)", 100, 40,
    insertionGeo,
    new ReverseSequenceMutation(),
    new DefaultMetaHeuristic());
Console.WriteLine($"{insertion.Label,-26} tour final = {insertion.FinalTourLength:F1}");
  parent             = [0, 1, 2, 3, 4]
  cible (permutation)= [2, 0, 1, 3, 4]
  1 pas swap (Cayley)    = [2, 1, 0, 3, 4]   (transposition)
  1 pas insertion (Ulam) = [2, 0, 1, 3, 4]   (déplacement+décalage)
  -> distincts en un pas ? True

Geometric (insertion/Ulam) tour final = 614,3

Config 5 — une troisième géométrie : la distance des arêtes (la métrique du TSP)

La Config 3 (swap/Cayley) et la Config 4 (insertion/Ulam) mesurent les permutations sur leurs positions d’index. Mais le TSP se mesure naturellement en arêtes — les paires de villes adjacentes dans le tour. Deux tours sont proches quand ils partagent beaucoup d’arêtes, peu importe où se trouve chaque ville : c’est la métrique pour laquelle un crossover géométrique coïncide avec la recombinaison par arêtes (edge-recombination de Whitley, Edge-Assembly Crossover).

EdgeEmbedding<int> mappe chaque tour vers son vecteur d’indicateurs d’arêtes (1 si la paire de villes est une arête du tour cyclique, 0 sinon). Sous cette métrique, le centroïde par défaut — inchangé — devient l’intersection : une arête présente chez les deux parents a indicateur (1+1)/2 = 1, présente chez un seul (0+1)/2 = 0,5 → 0. La progéniture est réassemblée pour contenir toutes les arêtes communes — le cœur géodésique prouvé.

Lecture honnête. Les arêtes communes sont garanties préservées ; les arêtes qui recousent les blocs en un cycle complet sont heuristiques. Edge atteint un tour novel (≠ des deux parents), là où swap/insertion dégénèrent sur un parent sous le centroïde naïf. Edge ne « gagne » pas systématiquement la course à la longueur du tour — il expose une troisième géométrie où la recombinaison préserve la structure partagée des deux parents.

// Config 5 : crossover géométrique sous la métrique des arêtes (edge/TSP).
// GeometricCrossover<int>(ordered:true) câble par DÉFAUT OrderedEmbedding (swap = Config 3).
// Pour la métrique des arêtes on INJECTE EdgeEmbedding : la progéniture hérite des arêtes
// communes aux deux parents (intersection = centroïde par défaut inchangé).

// (A) Démonstration RÉELLE : deux parents partagent des arêtes ; l'offspring les préserve toutes.
var permEdgeA = new IntPerm(new[] { 0, 1, 2, 3, 4 });
var permEdgeB = new IntPerm(new[] { 0, 2, 1, 3, 4 });
var edgeEmb = new EdgeEmbedding<int>();
var edgeGeom = edgeEmb.MapToGeometry(new List<IChromosome> { permEdgeA, permEdgeB });
// Centroïde = intersection des indicateurs d'arêtes (moyenne puis To<int>, arrondi).
var edgeCentroid = new int[edgeGeom[0].Count];
for (int i = 0; i < edgeCentroid.Length; i++)
{
    double avg = (edgeGeom[0][i] + edgeGeom[1][i]) / 2.0;
    edgeCentroid[i] = (int)Convert.ChangeType(avg, typeof(int));
}
var edgeOffspring = ((IntPerm)edgeEmb.MapFromGeometry(
    new List<IChromosome> { permEdgeA, permEdgeB }, edgeCentroid)).ToArray();

HashSet<(int, int)> TourEdgesOf(int[] t)
{
    var s = new HashSet<(int, int)>();
    for (int k = 0; k < t.Length; k++) { int a = t[k], b = t[(k + 1) % t.Length]; s.Add(a < b ? (a, b) : (b, a)); }
    return s;
}
var edgeCommon = TourEdgesOf(permEdgeA.ToArray()); edgeCommon.IntersectWith(TourEdgesOf(permEdgeB.ToArray()));
Console.WriteLine($"  parent A = [{string.Join(", ", permEdgeA.ToArray())}]");
Console.WriteLine($"  parent B = [{string.Join(", ", permEdgeB.ToArray())}]");
Console.WriteLine($"  arêtes communes = {{{string.Join(", ", edgeCommon.Select(e => $"({e.Item1},{e.Item2})"))}}}");
Console.WriteLine($"  offspring edge = [{string.Join(", ", edgeOffspring)}]");
Console.WriteLine($"  novel vs A ? {(!edgeOffspring.SequenceEqual(permEdgeA.ToArray()))}  novel vs B ? {(!edgeOffspring.SequenceEqual(permEdgeB.ToArray()))}");
Console.WriteLine($"  contient TOUTES les arêtes communes ? {edgeCommon.All(e => TourEdgesOf(edgeOffspring).Contains(e))}");
Console.WriteLine();

// (B) Run GA sous la métrique des arêtes : mêmes parents initiaux (ResetRng(7) dans Run).
var edgeGeo = new GeometricCrossover<int>(ordered: true);
edgeGeo.GeometryEmbedding = new EdgeEmbedding<int>();
var edge = Run("Geometric (edge/TSP)", 100, 40,
    edgeGeo, new ReverseSequenceMutation(), new DefaultMetaHeuristic());
Console.WriteLine($"{edge.Label,-26} tour final = {edge.FinalTourLength:F1}");
  parent A = [0, 1, 2, 3, 4]
  parent B = [0, 2, 1, 3, 4]
  arêtes communes = {(1,2), (3,4), (0,4)}
  offspring edge = [0, 4, 3, 1, 2]
  novel vs A ? True  novel vs B ? True
  contient TOUTES les arêtes communes ? True

Geometric (edge/TSP)       tour final = 580,5

Comparaison

On rapporte la longueur finale du meilleur tour (plus court = meilleur) et la dynamique de convergence échantillonnée. Attendu : les îles convergent plus lentement par génération (sous-populations plus petites) mais maintiennent la diversité plus longtemps, ce qui peut éviter des optima locaux. Le résultat exact dépend du tirage des villes et de la taille du problème — on le rapporte honnêtement, sans trier les victoires.

var results = new[] { baseline, island, geometric, insertion, edge };
Console.WriteLine($"{"Config",-26} | {"Tour final",10} | {"vs baseline",12}");
Console.WriteLine(new string('-', 54));
double refLen = baseline.FinalTourLength;
foreach (var r in results)
{
    double impr = refLen > 0 ? (refLen - r.FinalTourLength) / refLen * 100.0 : 0.0;
    Console.WriteLine($"{r.Label,-26} | {r.FinalTourLength,10:F1} | {impr,+10:F1} %");
}

Console.WriteLine();
Console.WriteLine("Convergence (longueur du meilleur tour, échantillonnée) :");
foreach (var r in results)
{
    var samples = Enumerable.Range(0, r.BestPerGen.Length)
        .Where(i => i % 25 == 0 || i == r.BestPerGen.Length - 1)
        .Select(i => "g" + (i + 1) + "=" + r.BestPerGen[i].ToString("F0"));
    Console.WriteLine("  " + r.Label.PadRight(24) + string.Join("  ", samples));
}
Config                     | Tour final |  vs baseline
------------------------------------------------------
Baseline (panmictic)       |      455,3 |        0,0 %
Islands (4 x 10, Static)   |      512,1 |      -12,5 %
Geometric (Moraglio)       |      596,9 |      -31,1 %
Geometric (insertion/Ulam) |      614,3 |      -34,9 %
Geometric (edge/TSP)       |      580,5 |      -27,5 %

Convergence (longueur du meilleur tour, échantillonnée) :
  Baseline (panmictic)    g1=1011  g26=633  g51=543  g76=491  g100=455
  Islands (4 x 10, Static)g1=1011  g26=672  g51=577  g76=577  g100=512
  Geometric (Moraglio)    g1=1011  g26=725  g51=665  g76=636  g100=597
  Geometric (insertion/Ulam)g1=1011  g26=889  g51=767  g76=713  g100=614
  Geometric (edge/TSP)    g1=1011  g26=843  g51=705  g76=594  g100=581

Lecture

La grammaire de composition (IslandMetaHeuristic ici) s’est appliquée à un chromosome de permutation sans aucune adaptation. C’est la preuve que la couche de composition est agnostique à la représentation : elle opère sur IChromosome, ne lit jamais Gene.Value, et n’a donc pas besoin de savoir si les gènes sont des double (MGS-5) ou des index de villes (int, ici).

Les métaheuristiques géométriques (WOA, EO), elles, nécessitent un GeometricConverter<double> précisément parce qu’elles font de l’arithmétique sur les gènes — c’est leur travail (centroïde, spirale, opérateur géométrique), pas celui de la couche de composition. La séparation est nette : la composition est agnostique, les composés géométriques sont typés. Composer ne présuppose pas le domaine.

Le fait que le modèle insulaire batte, égalise ou perde sur ce TSP de taille 20 est secondaire ; le point est ailleurs : la même brique structure des recherches sur des représentations disjointes. C’est ce qui distingue un composant réutilisable d’une métaphore monolithique attachée à un type de problème.

Nuance apportée par le crossover géométrique (Config 3). Le constat « les composés géométriques sont typés » vaut pour leurs opérateurs continus (centroïde, spirale sur double). Mais la Config 3 montre que le crossover géométrique lui-même s’étend aux permutations dès qu’on lui fournit un embedding métrique (OrderedEmbedding, distance de swap). Ce n’est donc pas la composition géométrique qui est cantonnée aux double, c’est l’espace métrique choisi : un opérateur géométrique n’est pertinent que si son embedding reflète la structure du problème. Le centroïde naïf sur étiquettes d’indice en est la limite — d’où l’intérêt des embeddings permutation-équivariants (deep learning géométrique).

Une géométrie, ou l’autre ? (Config 4). La Config 3 et la Config 4 partagent tout sauf un choix : la métrique. Même moteur (GeometricCrossover), même opérateur (centroïde), mêmes parents initiaux. Seul l’embedding diffère (OrderedEmbedding en swap-distance vs InsertionEmbedding en insertion/Ulam-distance). La théorie prédit — et la démonstration directe le confirme — que les deux n’atteignent pas le même descendant en un pas : un swap et une insertion, depuis le même parent vers la même cible-permutation, empruntent des géodésiques distinctes. Le deep learning géométrique pousse plus loin : il n’y a pas de métrique « correcte » dans l’absolu, seulement un embedding adapté à la structure du problème. Sur TSP, ni swap ni insertion n’ont de privilège géographique (ce sont des distances sur les étiquettes d’indice) ; les deux sont des baselines, et un embedding appris équivariant par permutation ferait mieux que les deux.

Une troisième géométrie : les arêtes (Config 5). La Config 5 change de catégorie : au lieu de mesurer les permutations sur leurs positions (swap, insertion), elle les mesure sur leurs arêtes — les paires de villes adjacentes, la métrique naturelle du TSP. Sous cette métrique, le centroïde par défaut devient l’intersection des arêtes communes, et l’offspring préserve ces arêtes (le cœur géodésique). C’est la lecture géométrique des crossovers TSP classiques (edge-recombination, EAX). Edge atteint un tour novel — distinct des deux parents — là où swap/insertion dégénèrent sur un parent sous le centroïde naïf. La métrique des arêtes distingue aussi ce que swap/insertion confondent : un tour et son renversement partagent toutes leurs arêtes (distance 0), car les arêtes d’un tour cyclique sont non-dirigées.

Exercice 1 — Changer d’opérateur de croisement

OrderedCrossover (OX1) est l’opérateur canonique du TSP. GeneticSharp en fournit d’autres pour permutations : PartiallyMappedCrossover (PMX), CycleCrossover (CX), OrderBasedCrossover (OX2). Relancez le baseline avec PartiallyMappedCrossover et comparez la longueur finale du tour. La performance relative dépend-elle de la taille du problème ?

// Exercice 1 : comparez OrderedCrossover (OX1) vs PartiallyMappedCrossover (PMX).
// # Indice : remplacez new OrderedCrossover() par new PartiallyMappedCrossover() dans l'appel Run(...).
// # Étape 1 : appelez Run("Baseline (PMX)", 100, 40, new PartiallyMappedCrossover(), new ReverseSequenceMutation(), new DefaultMetaHeuristic()).
// # Étape 2 : affichez la longueur finale et comparez à baseline-OX1.
// TODO étudiant
Console.WriteLine($"[Exercice 1] À compléter. Référence : baseline-OX1 = {baseline.FinalTourLength:F1}.");
[Exercice 1] À compléter. Référence : baseline-OX1 = 455,3.

Exercice 2 — Mode de migration

Le modèle insulaire supporte plusieurs MigrationMode : Static, RandomRing, RandomPermutation, Reinforced. Chaque mode détermine quelles îles échangent des chromosomes. Relancez la configuration îles avec MigrationMode.RandomRing et comparez la longueur finale à Static.

// Exercice 2 : comparez MigrationMode.Static vs MigrationMode.RandomRing.
// # Indice : recréez IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic()) avec MigrationMode = MigrationMode.RandomRing.
// TODO étudiant
Console.WriteLine($"[Exercice 2] À compléter. Référence : islands-Static = {island.FinalTourLength:F1}.");
[Exercice 2] À compléter. Référence : islands-Static = 512,1.

Exercice 3 — Topologie des îles

La partition (islandSize, islandNb) doit satisfaire islandSize × islandNb = popSize. Pour une population de 40, les partitions valides incluent (20, 2), (10, 4), (5, 8), (4, 10). Testez l’effet de la granularité — peu d’îles grandes vs beaucoup de petites — sur la diversité maintenue et la qualité de la convergence. Quelle granularité évite le mieux la convergence prématurée ?

// Exercice 3 : testez plusieurs partitions (islandSize, islandNb) de produit 40.
// # Indice : (20,2), (10,4), (5,8), (4,10). Relancez Run(...) avec un IslandMetaHeuristic par partition.
// # Étape 1 : bouclez sur les partitions et appelez Run pour chacune.
// # Étape 2 : affichez la longueur finale de chaque partition.
// TODO étudiant
Console.WriteLine("[Exercice 3] À compléter. Comparez les longueurs finales selon la granularité.");
[Exercice 3] À compléter. Comparez les longueurs finales selon la granularité.

Conclusion

Le même moteur MetaGeneticAlgorithm et les mêmes primitives de composition (IslandMetaHeuristic) ont structuré une recherche sur des permutations, alors que MGS-5 les utilisait sur des surfaces continues. La couche de composition ne fait aucune hypothèse sur le type des gènes : elle orchestre des IChromosome. C’est l’agnosticité de représentation héritée de GeneticSharp (bit, permutation, arbre, flottant), étendue à la couche métaheuristique.

Les métaheuristiques géométriques (WOA, EO) restent attachées aux gènes double — non par limitation de la composition, mais parce que leur mécanisme (opérateur géométrique, centroïde, spirale) est de l’arithmétique sur des positions continues. La séparation est nette : la composition est agnostique, les composés géométriques sont typés.

Suite logique : combiner cette agnosticité avec la structuration — un modèle insulaire où chaque île utiliserait un opérateur différent (configuration hétérogène), via la surcharge IslandMetaHeuristic(params (int, IMetaHeuristic)[]).

Extension : crossover géométrique de Moraglio. La Config 3 (GeometricCrossover<int> + OrderedEmbedding) étend la géométrie aux permutations : la progéniture marche par swaps sur le segment métrique entre parents. Le résultat empirique (tour final reporté dans la comparaison ci-dessus) se lit à l’aune de la théorie — l’opérateur centroïde agit sur des étiquettes d’indice sans signification géographique, ce qui borne ce qu’un crossover géométrique naïf peut atteindre et motive les embeddings permutation-équivariants du deep learning géométrique.

Extension : seconde métrique géométrique (Config 4). Le InsertionEmbedding<int> (métrique d’insertion/Ulam) le confirme par contraste : changer uniquement d’embedding — sans toucher au moteur GeometricCrossover ni à l’opérateur centroïde — change le paysage exploré, car swap-distance et insertion-distance sont deux métriques distinctes qui définissent deux segments géodésiques distincts entre les mêmes parents. Deux descendants différents deviennent atteignables en un seul pas de crossover : c’est l’embedding (le choix de la métrique), et non le moteur, qui porte la géométrie.

Extension : troisième métrique géométrique, les arêtes (Config 5). Le EdgeEmbedding<int> (métrique des arêtes) porte la géométrie au cœur du TSP : deux tours sont proches s’ils partagent des arêtes, peu importe la position des villes. Sous cette métrique, le centroïde par défaut — inchangé — devient l’intersection des arêtes communes : l’opérateur existant produit le cœur commun sans adaptation, parce que la géométrie vit dans l’embedding, pas le moteur. L’offspring préserve ces arêtes communes et atteint un tour novel ; les arêtes de complétion (recousent les blocs) sont heuristiques. Edge ne bat pas systématiquement swap sur la longueur du tour — il expose une troisième géométrie, et rappelle que la bonne métrique est celle qui reflète la structure du problème.

Références. - A. Moraglio & R. Poli, Topological Interpretation of Crossover, GECCO 2004 ; A. Moraglio, Towards a Geometric Unification of Evolutionary Algorithms, thèse 2007 — le cadre du crossover géométrique (segment métrique entre parents, valide en toute métrique, dont la distance de swap). - M. Bronstein, J. Bruna, T. Cohen, P. Veličković, Geometric Deep Learning — https://geometricdeeplearning.com — équivariance par permutation et embeddings structurés.

← MGS-6 Benchmarks | ↑ Série MGS | Fork jsboige/MetaGeneticSharp →

Retour au sommet