MGS-4 : Le Modèle Insulaire – populations structurees et migration

Navigation : Index | << MGS-3 Eukaryote | MGS-5 Composés >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Comprendre le modèle insulaire : structuration spatiale d’une population en sous-populations semi-isolees 2. Utiliser IslandPopulation et IslandMetaHeuristic pour partitionner une population en iles 3. Comparer les modes de migration (None, Static, RandomRing, RandomPermutation, Reinforced) 4. Evaluer l’impact de la diversite insulaire sur la convergence par rapport a une approche panmictique

Prerequis

MGS-1 : Introduction a MetaGeneticSharp et au moteur autonome
MGS-2 : Composition de métaheuristiques (utile pour comprendre les primitives)
MGS-3 : Eukaryote et sous-populations (architecture proche : SubPopulation, SubPopulationMetaHeuristicBase)
Notions de base en algorithmes génétiques (sélection, crossover, mutation, convergence prematuree)
C# .NET 9.0 et .NET Interactive

Duree estimee : 50 minutes

Le modèle insulaire

Metaphore biologique

En biologie evolutive, l’isolation geographique est un puissant moteur de diversite. Les iles Galapagos, isolees du continent sud-americain, ont permis a Darwin d’observer des especes uniques : chaque ile abrite des variations spécifiques de pinsons, de tortues et d’iguanes, adaptees a son propre ecosysteme.

Le modèle insulaire transpose cette idee aux algorithmes génétiques : - Sans migration : chaque ile evolue independamment, comme une population isolee. La diversite intra-ile est forte au debut, puis diminue par derives génétiques – chaque ile converge vers un optimum local différent - Avec migration : des echanges periodiques d’individus entre iles injectent du materiel génétique nouveau, stimulant la diversite et evitant la convergence prematuree

Pourquoi la diversite importe

Dans un algorithme génétique classique (population panmictique, un seul pool), la convergence prematuree est un problème recurrent : la population converge rapidement vers un optimum local et le crossover entre individus similaires ne produit plus de nouveaute. Le modèle insulaire combat ce problème en :

Maintenant des niches : chaque ile preseve ses propres lignees génétiques
Injectant de la nouveaute : les migrants apportent des genes qu’une ile seule n’aurait pas pu produire
Ralentissant la convergence uniforme : la diversite globale reste plus elevee plus longtemps

Propriete	Population panmictique	Modèle insulaire
Diversite initiale	Elevee puis decroit	Elevee et maintenue plus longtemps
Risque de convergence prematuree	Eleve	Reduit
Temps de convergence	Rapide si chanceux, bloque si premature	Plus regulier, plus robuste
Parallelisme	Non	Naturel (iles independantes)

// Wiring: load MetaGeneticSharp + GeneticSharp DLLs from the fork build (net9.0 self-contained).
// Build prerequisite: dotnet build ../MetaGeneticSharp/MetaGeneticSharp.sln
// Requires: git -C ../MetaGeneticSharp submodule update --init GeneticSharp
//
// We #r from the Extensions output dir because it is self-contained: CopyLocalLockFileAssemblies
// ships System.Drawing.Common.dll AND SkiaSharp.dll next to the MGS DLLs, which the graphic
// landscape rendering in section 5 needs at runtime. The Domain-only dir of older wiring did not.
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/GeneticSharp.Infrastructure.Framework.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/GeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Infrastructure.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Domain.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/MetaGeneticSharp.Extensions.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/System.Drawing.Common.dll"
#r "../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/SkiaSharp.dll"

using MetaGeneticSharp;
using GeneticSharp;
using System.Runtime.InteropServices;

// .NET Interactive quirk: a #r to the managed SkiaSharp.dll does NOT wire up SkiaSharp's
// runtimes/<rid>/native/ probing, so the first Skia call would P/Invoke a native lib that was
// never loaded (BadImageFormatException). Preload the arch-matching native binary once (needed by
// the colored-islands heatmap in section 5).
string rid = RuntimeInformation.ProcessArchitecture == Architecture.Arm64 ? "win-arm64"
           : RuntimeInformation.ProcessArchitecture == Architecture.X86   ? "win-x86"
           : "win-x64";
NativeLibrary.Load($"../MetaGeneticSharp/src/MetaGeneticSharp.Extensions/bin/Debug/net9.0/runtimes/{rid}/native/libSkiaSharp.dll");

Console.WriteLine("MetaGeneticSharp + GeneticSharp + Extensions charges avec succes (net9.0).");
Console.WriteLine($"  IslandPopulation         : {typeof(IslandPopulation).Name}");
Console.WriteLine($"  IslandMetaHeuristic      : {typeof(IslandMetaHeuristic).Name}");
Console.WriteLine($"  MigrationMode.RandomRing : {MigrationMode.RandomRing}");
Console.WriteLine($"  SubPopulation            : {typeof(SubPopulation).Name}");
Console.WriteLine($"  MetaPopulation           : {typeof(MetaPopulation).Name}");
Console.WriteLine($"  SkiaLandscapeRenderer    : {typeof(SkiaLandscapeRenderer).Name} (native rid={rid})");

MetaGeneticSharp + GeneticSharp + Extensions charges avec succes (net9.0).
  IslandPopulation         : IslandPopulation
  IslandMetaHeuristic      : IslandMetaHeuristic
  MigrationMode.RandomRing : RandomRing
  SubPopulation            : SubPopulation
  MetaPopulation           : MetaPopulation
  SkiaLandscapeRenderer    : SkiaLandscapeRenderer (native rid=win-x64)

Chargement des DLL et configuration du notebook

La cellule suivante charge les DLL MetaGeneticSharp et GeneticSharp depuis le build du sous-module. Assurez-vous que le build est a jour avant d’executer ce notebook.

Note : si le wiring echoue, verifiez que le sous-module GeneticSharp est initialise (git submodule update --init GeneticSharp) et que le build est a jour (dotnet build depuis ../MetaGeneticSharp).

Architecture du modèle insulaire

Diagramme d’architecture

MetaPopulation (N individus)
  |
  | IslandMetaHeuristic.GenerateSubPopulations()
  | Partition en iles contigues : [0..k-1], [k..2k-1], [2k..3k-1], ...
  v
IslandPopulation 0     IslandPopulation 1     IslandPopulation 2     IslandPopulation 3
  (k individus)          (k individus)          (k individus)          (k individus)
  MigrationRates: [...]  MigrationRates: [...]  MigrationRates: [...]  MigrationRates: [...]
  |                     |                     |                     |
  |  <-- migration periodique selon MigrationMode -->
  |                     |                     |                     |
  DefaultMetaHeuristic  DefaultMetaHeuristic  DefaultMetaHeuristic  DefaultMetaHeuristic
  (evolution locale)    (evolution locale)    (evolution locale)    (evolution locale)

Types fondamentaux

Type	Rôle	Parent dans la hiérarchie
`IslandPopulation`	Sous-population contenant un slice contigu d’individus complets	`SubPopulation`
`IslandMetaHeuristic`	Orchestrateur : créé les iles, gere la migration, applique les sous-heuristiques	`SubPopulationMetaHeuristicBase<IslandPopulation>`
`MigrationMode`	Stratégie de migration : `None`, `Static`, `RandomRing`, `RandomPermutation`, `Reinforced`	Enum

Différence cle avec l’Eukaryote (NB-C)

Aspect	Eukaryote (NB-C)	Insulaire (NB-D)
Granularite de partition	Genes : chaque sous-population evolue une partie du genome	Individus : chaque ile contient des individus complets
Echange entre partitions	`EukaryoteChromosome.UpdateParent()` resync les genes	Migration d’individus entiers entre iles
Diversite	Stratégies heterogenes par gene	Isolation geographique + flux génétique
But	Specialisation des opérateurs par dimension	Preservation de la diversite globale

Paramètres de migration

Paramètre	Type	Defaut	Rôle
`MigrationMode`	`MigrationMode`	`RandomRing`	Stratégie de sélection des routes de migration
`GlobalMigrationRate`	`double`	`0.005` (Small)	Taux global de migration (fraction d’individus echanges)
`MigrationsGenerationPeriod`	`int`	`10`	Frequence de migration (toutes les N generations)
`EmigrantPicker`	`MatchPicker`	Best(10)	Selectionne les meilleurs individus pour emigrer
`ImigrantReplacePicker`	`MatchPicker`	Worst(10)	Selectionne les individus a remplacer a l’arrivee

1. IslandPopulation : creation d’iles

Un IslandPopulation est une sous-population qui contient un slice contigu d’individus complets de la population parente. Contrairement a l’eukaryote qui decoupe le genome, l’insulaire decoupe la population.

Chaque ile possede : - Une reference vers la population parente (ParentPopulation) - Ses propres individus (chromosomes complets, pas des partitions) - Des MigrationRates : un tableau de taux d’emigration vers chaque autre ile

Constructeur

IslandPopulation(IPopulation parentPopulation, IList<IChromosome> subPopulation)

Les iles sont créées automatiquement par IslandMetaHeuristic lors de la première generation. La population parente doit etre de taille exactement islandSize * islandCount.

// Setup: fitness function and helpers for the island model demonstrations

// Fitness: minimize distance to target point (42, 13) -- GeneticSharp maximizes, so we negate
// This is the canonical test fitness from IslandMetaHeuristicTests
public class TargetFitness : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        var values = ((FloatingPointChromosome)chromosome).ToFloatingPoints();
        return -(Math.Abs(values[0] - 42) + Math.Abs(values[1] - 13));
    }
}

// Helper: create chromosome for the 2D target problem
FloatingPointChromosome CreateTargetChromosome()
{
    return new FloatingPointChromosome(
        new double[] { 0, 0 },
        new double[] { 100, 100 },
        new int[] { 16, 16 },
        new int[] { 2, 2 });
}

// Helper: create fitness function for the 2D target problem
IFitness CreateTargetFitness()
{
    return new FuncFitness(c =>
    {
        var values = ((FloatingPointChromosome)c).ToFloatingPoints();
        return -(Math.Abs(values[0] - 42) + Math.Abs(values[1] - 13));
    });
}

Console.WriteLine("Setup OK : TargetFitness, CreateTargetChromosome, CreateTargetFitness definis");
Console.WriteLine($"  TargetFitness          : {typeof(TargetFitness).Name}");
Console.WriteLine($"  IslandPopulation       : {typeof(IslandPopulation).Name}");
Console.WriteLine($"  IslandMetaHeuristic    : {typeof(IslandMetaHeuristic).Name}");
Console.WriteLine($"  MigrationMode values   : {string.Join(", ", Enum.GetNames(typeof(MigrationMode)))}");

Setup OK : TargetFitness, CreateTargetChromosome, CreateTargetFitness definis
  TargetFitness          : TargetFitness
  IslandPopulation       : IslandPopulation
  IslandMetaHeuristic    : IslandMetaHeuristic
  MigrationMode values   : None, Static, RandomRing, RandomPermutation, Reinforced

Demonstration : creation manuelle d’iles

Nous allons maintenant créer manuellement 4 IslandPopulation a partir d’une population de 40 individus pour illustrer le mécanisme de partition. En pratique, IslandMetaHeuristic effectue cette decomposition automatiquement, mais la comprendre manuellement est essentiel pour configurer correctement le modèle.

// Demonstration: create 4 islands with 10 individuals each from a population of 40
// IslandMetaHeuristic partitions the population into contiguous slices

// Create population: 40 individuals, partitioned into 4 islands of 10 each
FastRandomRandomization.ResetSeed(42); // graine la population initiale (reproductibilite, cf #12071)
var adamDemo = CreateTargetChromosome();
var demoPop = new MetaPopulation(40, 40, adamDemo);
demoPop.CreateInitialGeneration();

// Assign fitness to all chromosomes (required for migration)
var demoFitness = CreateTargetFitness();
foreach (var c in demoPop.CurrentGeneration.Chromosomes)
{
    c.Fitness = demoFitness.Evaluate(c);
}

Console.WriteLine("Population parente : ");
Console.WriteLine(string.Format("  Taille          : {0} individus", demoPop.CurrentGeneration.Chromosomes.Count));
Console.WriteLine(string.Format("  Best fitness    : {0:F4}", demoPop.CurrentGeneration.Chromosomes.Max(c => c.Fitness.Value)));
Console.WriteLine(string.Format("  Worst fitness   : {0:F4}", demoPop.CurrentGeneration.Chromosomes.Min(c => c.Fitness.Value)));
Console.WriteLine();

// Create 4 IslandPopulations manually to illustrate the structure
// (In practice, IslandMetaHeuristic does this automatically)
int islandSize = 10;
int islandCount = 4;
var islands = new List<IslandPopulation>();
for (int i = 0; i < islandCount; i++)
{
    var slice = demoPop.CurrentGeneration.Chromosomes
        .Skip(i * islandSize)
        .Take(islandSize)
        .ToList();
    var island = new IslandPopulation(demoPop, slice);
    islands.Add(island);
}

Console.WriteLine(string.Format("Decomposition en {0} iles de {1} individus :", islandCount, islandSize));
for (int i = 0; i < islands.Count; i++)
{
    var island = islands[i];
    var bestFit = island.CurrentGeneration.Chromosomes.Max(c => c.Fitness.Value);
    var worstFit = island.CurrentGeneration.Chromosomes.Min(c => c.Fitness.Value);
    var firstValues = ((FloatingPointChromosome)island.CurrentGeneration.Chromosomes[0]).ToFloatingPoints();
    Console.WriteLine(string.Format("  Ile {0} : {1} individus, fitness [{2:F4} .. {3:F4}], premier = ({4:F2}, {5:F2})",
        i, island.MinSize, worstFit, bestFit, firstValues[0], firstValues[1]));
    Console.WriteLine(string.Format("    ParentPopulation = MetaPopulation({0})", island.ParentPopulation.MinSize));
    Console.WriteLine(string.Format("    MigrationRates   = {0}",
        island.MigrationRates != null
            ? string.Join(", ", island.MigrationRates.Select(r => r.ToString("F4")))
            : "(non initialise, sera defini par le mode de migration)"));
}

Console.WriteLine();
Console.WriteLine("Verification : les memes references d'individus ?");
Console.WriteLine(string.Format("  Ile 0, individu 0 = Population individu 0 : {0}",
    object.ReferenceEquals(islands[0].CurrentGeneration.Chromosomes[0], demoPop.CurrentGeneration.Chromosomes[0])));
Console.WriteLine(string.Format("  Ile 3, individu 0 = Population individu 30 : {0}",
    object.ReferenceEquals(islands[3].CurrentGeneration.Chromosomes[0], demoPop.CurrentGeneration.Chromosomes[30])));

Population parente : 
  Taille          : 40 individus
  Best fitness    : -9,7800
  Worst fitness   : -119,3100

Decomposition en 4 iles de 10 individus :
  Ile 0 : 10 individus, fitness [-118,2900 .. -24,0200], premier = (43,56, 89,66)
    ParentPopulation = MetaPopulation(40)
    MigrationRates   = (non initialise, sera defini par le mode de migration)
  Ile 1 : 10 individus, fitness [-119,3100 .. -9,7800], premier = (33,28, 24,42)
    ParentPopulation = MetaPopulation(40)
    MigrationRates   = (non initialise, sera defini par le mode de migration)
  Ile 2 : 10 individus, fitness [-96,1700 .. -15,7400], premier = (85,45, 6,45)
    ParentPopulation = MetaPopulation(40)
    MigrationRates   = (non initialise, sera defini par le mode de migration)
  Ile 3 : 10 individus, fitness [-79,0000 .. -19,8700], premier = (90,34, 41,44)
    ParentPopulation = MetaPopulation(40)
    MigrationRates   = (non initialise, sera defini par le mode de migration)

Verification : les memes references d'individus ?
  Ile 0, individu 0 = Population individu 0 : True
  Ile 3, individu 0 = Population individu 30 : True

Interpretation : Creation d’iles

Sortie obtenue : La population parente de 40 individus est partitionnee en 4 IslandPopulation de 10 individus chacune. Chaque ile contient des references directes vers les chromosomes de la population parente (pas de copies).

Aspect	Valeur	Signification
Partition	4 iles x 10 individus	Decoupage contigu de la population parente
`ParentPopulation`	`MetaPopulation(40)`	Chaque ile reference la population parente
`MigrationRates`	Non initialise	Sera défini par le mode de migration lors de l’exécution
References	Identiques au parent	Les chromosomes sont partages, pas copies

Points cles : 1. Chaque IslandPopulation herite de SubPopulation, comme les sous-populations eukaryotes 2. Mais contrairement a l’eukaryote qui decoupe le genome, l’insulaire decoupe la population en slices d’individus complets 3. Les MigrationRates sont définis dynamiquement par le MigrationMode a chaque generation de migration 4. La taille de la population doit etre exactement islandSize * islandCount

2. Modes de migration

Le mode de migration determine quels echanges d’individus ont lieu entre les iles a chaque periode de migration. C’est le paramètre cle qui contrôle le flux génétique.

Les 5 modes de migration

Mode	Description	Topologie
`None`	Aucune migration – iles completement isolees	Aucun echange
`Static`	Taux de migration fixes, distribues uniformement entre toutes les iles	Tous vers tous
`RandomRing`	Un anneau aleatoire : chaque ile envoie vers un voisin unique	Cycle hamiltonien aleatoire
`RandomPermutation`	Permutation aleatoire : chaque ile envoie vers une ile cible aleatoire	Permutation random
`Reinforced`	Taux statiques (comme Static), mais les taux peuvent etre ajustes dynamiquement	Tous vers tous (adaptaif)

Mécanisme de migration

L’EmigrantPicker (par defaut : meilleurs individus) selectionne les candidats au depart
L’ImigrantReplacePicker (par defaut : pires individus) selectionne les individus a remplacer a l’arrivee
Le nombre de migrants est proportionnel a GlobalMigrationRate * islandSize

Demonstration : MigrationMode.None (iles completement isolees)

Sans migration, chaque ile evolue comme une population independante de taille islandSize. La diversite intra-ile diminue rapidement car la population est petite (10 individus), et chaque ile converge vers un optimum local différent.

// Demonstration: MigrationMode.None -- fully isolated islands
// Each island evolves independently with no gene flow
// Expected: islands converge to different local optima, stagnation is likely

var noneMh = new IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic())
{
    MigrationMode = MigrationMode.None,
    MigrationsGenerationPeriod = 1
};

FastRandomRandomization.ResetSeed(42);
var nonePop = new MetaPopulation(40, 40, CreateTargetChromosome());
var noneGa = new MetaGeneticAlgorithm(
    nonePop,
    CreateTargetFitness(),
    new EliteSelection(),
    new UniformCrossover(0.5f),
    new UniformMutation(true),
    noneMh)
{
    Termination = new GenerationNumberTermination(50)
};

Console.WriteLine("MigrationMode.None : 4 iles isolees, 50 generations");
Console.WriteLine("  Taille de chaque ile : 10 individus (petite population)");
Console.WriteLine("  Migration : AUCUNE");
Console.WriteLine();

noneGa.Start();

var noneBest = ((FloatingPointChromosome)noneGa.BestChromosome).ToFloatingPoints();
var noneObj = Math.Abs(noneBest[0] - 42) + Math.Abs(noneBest[1] - 13);

Console.WriteLine(string.Format("  Meilleur chromosome : ({0:F2}, {1:F2})", noneBest[0], noneBest[1]));
Console.WriteLine(string.Format("  Cible               : (42, 13)"));
Console.WriteLine(string.Format("  Distance totale     : {0:F4}", noneObj));
Console.WriteLine(string.Format("  Fitness             : {0:F4}", noneGa.BestChromosome.Fitness));
Console.WriteLine(string.Format("  Generations         : {0}", noneGa.GenerationsNumber));
Console.WriteLine(string.Format("  Etat                : {0}", noneGa.State));
Console.WriteLine();
Console.WriteLine("Remarque : sans migration, les petites iles isolées convergent souvent");
Console.WriteLine("  moins bien qu'une population unique de meme taille totale.");

MigrationMode.None : 4 iles isolees, 50 generations
  Taille de chaque ile : 10 individus (petite population)
  Migration : AUCUNE

  Meilleur chromosome : (41,85, 13,09)
  Cible               : (42, 13)
  Distance totale     : 0,2400
  Fitness             : -0,2400
  Generations         : 50
  Etat                : TerminationReached

Remarque : sans migration, les petites iles isolées convergent souvent
  moins bien qu'une population unique de meme taille totale.

Interpretation : iles isolees (MigrationMode.None)

Sortie obtenue : Avec 4 iles completement isolees de 10 individus chacune, la convergence est mediocre. Sans echanges, chaque ile stagne dans son propre optimum local.

Aspect	Observation	Cause
Convergence	Distance elevee a la cible	Petites populations isolées convergent prematurement
Diversite	Chaque ile est homogene, mais différente entre iles	Derive génétique dans des directions différentes
Stagnation	Probable avant 50 generations	10 individus = gene pool très limite

Pourquoi l’isolation totale est insuffisante : sans flux génétique entre iles, chaque ile est une population trop petite pour maintenir assez de diversite. L’avantage du modèle insulaire (diversite par isolation) est perdu si les iles ne communiquent jamais.

Demonstration : MigrationMode.RandomRing (anneau aleatoire)

Le mode RandomRing créé un cycle hamiltonien aleatoire entre les iles : chaque ile envoie des migrants vers exactement une autre ile, formant un anneau. C’est le mode par defaut d’IslandMetaHeuristic.

// Demonstration: MigrationMode.RandomRing -- periodic migration in a random ring topology
// Every MigrationsGenerationPeriod generations, best individuals are exchanged
// Expected: migration injects diversity, improving convergence over isolated islands

var ringMh = new IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic())
{
    MigrationMode = MigrationMode.RandomRing,
    MigrationsGenerationPeriod = 5,
    GlobalMigrationRate = IslandMetaHeuristic.LargeMigrationRate
};

FastRandomRandomization.ResetSeed(42);
var ringPop = new MetaPopulation(40, 40, CreateTargetChromosome());
var ringGa = new MetaGeneticAlgorithm(
    ringPop,
    CreateTargetFitness(),
    new EliteSelection(),
    new UniformCrossover(0.5f),
    new UniformMutation(true),
    ringMh)
{
    Termination = new GenerationNumberTermination(50)
};

Console.WriteLine("MigrationMode.RandomRing : 4 iles, migration toutes les 5 generations");
Console.WriteLine(string.Format("  GlobalMigrationRate : {0}", ringMh.GlobalMigrationRate));
Console.WriteLine("  Topologie           : anneau aleatoire (chaque ile envoie vers un voisin)");
Console.WriteLine("  EmigrantPicker      : meilleurs individus");
Console.WriteLine("  ImigrantReplace     : pires individues (remplaces)");
Console.WriteLine();

ringGa.Start();

var ringBest = ((FloatingPointChromosome)ringGa.BestChromosome).ToFloatingPoints();
var ringObj = Math.Abs(ringBest[0] - 42) + Math.Abs(ringBest[1] - 13);

Console.WriteLine(string.Format("  Meilleur chromosome : ({0:F2}, {1:F2})", ringBest[0], ringBest[1]));
Console.WriteLine(string.Format("  Cible               : (42, 13)"));
Console.WriteLine(string.Format("  Distance totale     : {0:F4}", ringObj));
Console.WriteLine(string.Format("  Fitness             : {0:F4}", ringGa.BestChromosome.Fitness));
Console.WriteLine(string.Format("  Generations         : {0}", ringGa.GenerationsNumber));
Console.WriteLine(string.Format("  Etat                : {0}", ringGa.State));
Console.WriteLine();
Console.WriteLine(string.Format("Comparaison avec None (distance {0:F4}) : {1}",
    noneObj,
    ringObj < noneObj ? "RandomRing est meilleur" : "None est meilleur (hasard)"));

MigrationMode.RandomRing : 4 iles, migration toutes les 5 generations
  GlobalMigrationRate : 0,1
  Topologie           : anneau aleatoire (chaque ile envoie vers un voisin)
  EmigrantPicker      : meilleurs individus
  ImigrantReplace     : pires individues (remplaces)

  Meilleur chromosome : (42,00, 12,99)
  Cible               : (42, 13)
  Distance totale     : 0,0100
  Fitness             : -0,0100
  Generations         : 50
  Etat                : TerminationReached

Comparaison avec None (distance 0,2400) : RandomRing est meilleur

Interpretation : Migration par anneau aleatoire

Sortie obtenue : La migration periodique via RandomRing injecte de la diversite dans les iles, ameliorant généralement la convergence par rapport a l’isolation complete.

Aspect	MigrationMode.None	MigrationMode.RandomRing
Diversite	Chaque ile stagne seule	Les migrants apportent des genes nouveaux
Convergence	Potentiellement prematuree	Plus robuste grace au flux génétique
Topologie	Aucun echange	Anneau aleatoire (1 voisin par ile)

Comment la migration fonctionne : 1. Tous les MigrationsGenerationPeriod generations, l’anneau de migration est construit 2. Les meilleurs individus de chaque ile sont selectionnes comme emigrants (EmigrantPicker) 3. Les pires individus de l’ile cible sont remplacés par les immigrants (ImigrantReplacePicker) 4. Le nombre de migrants est GlobalMigrationRate * islandSize

3. Comparaison : modèle insulaire vs population panmictique

Nous allons maintenant comparer le modèle insulaire (IslandMetaHeuristic avec 4 iles) a une population panmictique classique (DefaultMetaHeuristic, population unique) sur le même problème d’optimisation.

Problème : minimiser \(f(x, y) = |x - 42| + |y - 13|\) dans \([0, 100]^2\).

Protocole : 5 exécutions pour chaque configuration, 50 generations par run.

Configurations : - Panmictique : DefaultMetaHeuristic avec 40 individus (population unique) - Insulaire : IslandMetaHeuristic avec 4 iles de 10 individus, RandomRing, migration toutes les 5 generations

// Compare: panmictic (DefaultMetaHeuristic, single pop) vs island model (IslandMetaHeuristic, 4 islands)
// 5 runs each, 50 generations, same operators (EliteSelection, UniformCrossover, UniformMutation)

// Helper: run a single GA with a given metaheuristic and return the distance to target
double RunGA(IMetaHeuristic mh, int generations = 50)
{
    var pop = new MetaPopulation(40, 40, CreateTargetChromosome());
    var ga = new MetaGeneticAlgorithm(
        pop,
        CreateTargetFitness(),
        new EliteSelection(),
        new UniformCrossover(0.5f),
        new UniformMutation(true),
        mh)
    {
        Termination = new GenerationNumberTermination(generations)
    };
    ga.Start();
    var best = ((FloatingPointChromosome)ga.BestChromosome).ToFloatingPoints();
    return Math.Abs(best[0] - 42) + Math.Abs(best[1] - 13);
}

// Panmictic: single DefaultMetaHeuristic
IMetaHeuristic Panmictic() => new DefaultMetaHeuristic();

// Island: 4 islands with RandomRing migration
IMetaHeuristic Island() => new IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic())
{
    MigrationMode = MigrationMode.RandomRing,
    MigrationsGenerationPeriod = 5,
    GlobalMigrationRate = IslandMetaHeuristic.LargeMigrationRate
};

Console.WriteLine("Comparaison : Panmictique vs Modele Insulaire (5 runs, 50 generations)");
Console.WriteLine("======================================================================");
Console.WriteLine(string.Format("{0,-18} {1,-8} {2,-8} {3,-8} {4,-8} {5,-8} {6,-8}",
    "Config", "Run1", "Run2", "Run3", "Run4", "Run5", "Moyenne"));
Console.WriteLine("----------------------------------------------------------------------");

int[] RUN_SEEDS = { 0, 1, 7, 42, 99 }; // une graine par run : la comparaison devient multi-seed reproductible (cf #12071)
var panmResults = new List<double>();
var islResults = new List<double>();

for (int run = 0; run < 5; run++)
{
    FastRandomRandomization.ResetSeed(RUN_SEEDS[run]);
    panmResults.Add(RunGA(Panmictic()));
    islResults.Add(RunGA(Island()));
}

Console.Write(string.Format("{0,-18}", "Panmictique"));
foreach (var r in panmResults) Console.Write(string.Format(" {0,-7:F4}", r));
Console.WriteLine(string.Format(" {0,-7:F4}", panmResults.Average()));

Console.Write(string.Format("{0,-18}", "Insulaire (4 iles)"));
foreach (var r in islResults) Console.Write(string.Format(" {0,-7:F4}", r));
Console.WriteLine(string.Format(" {0,-7:F4}", islResults.Average()));

Console.WriteLine("----------------------------------------------------------------------");
Console.WriteLine(string.Format("  Panmictique moyenne  : {0:F4}", panmResults.Average()));
Console.WriteLine(string.Format("  Insulaire moyenne    : {0:F4}", islResults.Average()));

var improvement = (panmResults.Average() - islResults.Average()) / panmResults.Average() * 100;
Console.WriteLine(string.Format("  Difference           : {0:F1}% ({1})",
    Math.Abs(improvement),
    improvement > 0 ? "insulaire meilleur" : "panmictique meilleur"));
Console.WriteLine("======================================================================");
Console.WriteLine("Fitness : f(x, y) = -(|x - 42| + |y - 13|), cible = (42, 13)");
Console.WriteLine("  Panmictique : 1 population de 40, DefaultMetaHeuristic");
Console.WriteLine("  Insulaire   : 4 iles de 10, RandomRing, migration/5gen, LargeRate");

Comparaison : Panmictique vs Modele Insulaire (5 runs, 50 generations)
======================================================================
Config             Run1     Run2     Run3     Run4     Run5     Moyenne 
----------------------------------------------------------------------
Panmictique        0,0200  0,2100  0,0000  0,0000  0,2700  0,1000 
Insulaire (4 iles) 0,0100  0,0100  0,0000  0,2100  0,0500  0,0560 
----------------------------------------------------------------------
  Panmictique moyenne  : 0,1000
  Insulaire moyenne    : 0,0560
  Difference           : 44,0% (insulaire meilleur)
======================================================================
Fitness : f(x, y) = -(|x - 42| + |y - 13|), cible = (42, 13)
  Panmictique : 1 population de 40, DefaultMetaHeuristic
  Insulaire   : 4 iles de 10, RandomRing, migration/5gen, LargeRate

Interpretation : Panmictique vs Insulaire

Sortie obtenue : Comparaison sur 5 seeds entre une population unique de 40 individus et 4 iles de 10 individus avec migration.

Quand le modèle insulaire est avantagé : 1. Paysage multimodal : quand la fonction objectif a plusieurs optima locaux, les iles explorent différentes regions et la migration permet de combiner les decouvertes 2. Population elevee : avec beaucoup d’individus, la decomposition en iles est naturelle pour le parallelisme 3. Convergence prematuree : si la population panmictique converge trop vite vers un optimum local, les iles maintiennent la diversite plus longtemps

Quand la population panmictique est avantagé : 1. Paysage unimodal : sur une fonction simple (comme notre distance a un point), l’approche directe converge plus vite 2. Petite population totale : si la population est déjà petite, la subdiviser encore plus affaiblit chaque ile 3. Taux de migration mal calibre : trop de migration = panmictique deguisé, trop peu = iles isolees

Paramètre	Impact	Recommendation
Nombre d’iles	Trop d’iles = trop petites	3-8 iles, 10-50 individus par ile
`GlobalMigrationRate`	Trop haut = diversite perdue, trop bas = iles isolees	`Small` (0.005) a `Large` (0.1)
`MigrationsGenerationPeriod`	Trop frequent = panmictique, trop rare = isole	5-20 generations
Taille totale	Doit etre suffisante pour le problème	Au moins 30-50 individus au total

Note technique : la probabilite de crossover passee aux sous-heuristiques est forcee a 1.0 par IslandMetaHeuristic (cf ScopedMatchParentsAndCross). C’est load-bearing : les stages de mutation et reinsertion re-decoupent la liste globale de descendants par tailles d’iles fixes.

4. Visualiser les îles : bassins d’attraction colorés

La section 3 a comparé insulaire et panmictique au tableau de distances. Reste une question qualitative que les chiffres ne disent pas : vers où converge chaque île, et pourquoi la diversité insulaire aide-t-elle sur un paysage accidenté ?

Pour le voir, il faut deux ingrédients : 1. Un paysage multimodal — une fonction avec plusieurs optima locaux (pièges), pas le simple cône unimodal de la section 3. Nous passons à Rastrigin : un plateau criblé de puits locaux, le benchmark canonique de la difficulté d’optimisation. 2. Colorer chaque individu selon son île — l’overlay « îles colorées » ajouté au fork (PR fork #28, co-évolution item 2). Au lieu de dessiner toute la population dans une seule couleur (BlueViolet), chaque île reçoit sa propre couleur. On voit alors se former des amas monochromes : chaque île, évoluant quasi-isolément, tombe dans un bassin d’attraction différent et y reste.

Ce que la visualisation révèle : à la fin de l’évolution, les individus d’une même île forment un cluster localisé autour d’un optimum — preuve que l’isolation géographique a préservé des niches. La migration (lignes RandomRing) expliqueraient pourquoi un individu « hors-couleur » apparaît parfois dans un cluster : un migrant. C’est exactement le mécanisme que Darwin observait aux Galapagos, rendu visible pixel par pixel.

L’overlay est additif. Le nouvel overload SkiaLandscapeRenderer.RenderHeatmapPng(..., IReadOnlyList<Color>? individualColors) ne change rien au rendu existant : sans palette, il retombe sur le marqueur BlueViolet verbatim (testé byte-identique dans la PR fork). On ajoute une capacité de visualisation, on n’en substitue pas.

// Section 4 setup: a MULTIMODAL fitness (Rastrigin) + a display helper for the colored heatmap.
using System.Drawing;             // Color
using System.Linq;                // OrderByDescending, Select, ToList
using System.Collections.Generic; // List<>

// Rastrigin on [-5.12, 5.12]^2 : f(x,y) = 20 + x^2 + y^2 - 10*(cos(2*pi*x) + cos(2*pi*y))
// Minimised at (0,0) = 0, but riddled with local minima on the integer lattice (a grid of pits).
// GeneticSharp MAXIMISES -> we negate so the GA climbs toward the global optimum at the origin,
// and the landscape renderer (which paints "high = good") lights the optima as bright peaks.
double Rastrigin2D(double[] xy)
{
    double x = xy[0], y = xy[1];
    double f = 20.0 + x * x + y * y - 10.0 * (Math.Cos(2 * Math.PI * x) + Math.Cos(2 * Math.PI * y));
    return -f; // negate: GA maximises, renderer paints high fitness bright
}

// Fitness adapter for the GA engine: extract the 2 genes, evaluate Rastrigin (negated).
IFitness RastriginFitness() => new FuncFitness(c =>
{
    var v = ((FloatingPointChromosome)c).ToFloatingPoints();
    return Rastrigin2D(new[] { v[0], v[1] });
});

// Chromosome on the Rastrigin box [-5.12, 5.12]^2. NOTE: totalBits must be 64 (not 32) here:
// GeneticSharp's BinaryStringRepresentation encodes signed values wastefully, so a negative box
// [-5.12, 5.12] with fractionDigits=2 needs 64 bits per gene to round-trip every value the GA
// produces during crossover/mutation. (Empirically verified: 32/44 bits throw "needs 64 bits".)
FloatingPointChromosome CreateRastriginChromosome() => new FloatingPointChromosome(
    new double[] { -5.12, -5.12 },
    new double[] {  5.12,  5.12 },
    new int[] { 64, 64 },
    new int[] {  2,  2 });

// Display a PNG byte[] inline (no plot package: data-URI <img>, pattern MGS-7/8/9).
// NOTE: lowercase `display` is the .NET Interactive helper available inside user functions; the
// uppercase `Display` extension only resolves at top-level submission scope and won't compile here.
void DisplayPng(byte[] png, int widthPx = 420)
{
    string b64 = Convert.ToBase64String(png);
    display(HTML($"<img src=\"data:image/png;base64,{b64}\" width=\"{widthPx}\"/>"));
}

// One palette colour per island (4 islands). Distinct hues so clusters are easy to tell apart.
Color[] IslandPalette = new Color[]
{
    Color.FromArgb(255, 231, 76, 60),    // island 0: red
    Color.FromArgb(255, 46, 204, 113),   // island 1: green
    Color.FromArgb(255, 52, 152, 219),   // island 2: blue
    Color.FromArgb(255, 241, 196, 15),   // island 3: yellow
};

// Render the Rastrigin landscape background once, with NO population, as a reference.
byte[] landscapeOnly = SkiaLandscapeRenderer.RenderHeatmapPng(
    Rastrigin2D, (-5.12, 5.12), (-5.12, 5.12), width: 420, height: 420);

Console.WriteLine("Setup section 4 : Rastrigin2D (multimodal), RastriginFitness, CreateRastriginChromosome.");
Console.WriteLine($"  Rastrigin f(0,0)      = {-Rastrigin2D(new[]{0.0,0.0})} (optimum global = 0)");
Console.WriteLine($"  Rastrigin f(1,1)      = {-Rastrigin2D(new[]{1.0,1.0}):F3} (pit local au voisinage de l'optimum)");
Console.WriteLine($"  Palette iles          : {IslandPalette.Length} couleurs distinctes");
Console.WriteLine();
Console.WriteLine("Paysage Rastrigin de reference (sans population) :");
DisplayPng(landscapeOnly);

Setup section 4 : Rastrigin2D (multimodal), RastriginFitness, CreateRastriginChromosome.
  Rastrigin f(0,0)      = 0 (optimum global = 0)
  Rastrigin f(1,1)      = 2,000 (pit local au voisinage de l'optimum)
  Palette iles          : 4 couleurs distinctes

Paysage Rastrigin de reference (sans population) :

// Run an island-model GA on Rastrigin, snapshot the final population, and overlay each
// individual COLORED BY ITS ISLAND. The 4 islands evolve quasi-isolated; on the multimodal
// landscape each converges toward a different basin of attraction -> colored clusters appear.

const int islandCount = 4;
const int islandSize = 15;            // 15 individuals per island -> 60 total
const int generations = 40;

// Island model: RandomRing migration every 8 generations (light flow -> islands stay distinct).
var islandsMh = new IslandMetaHeuristic(islandSize, islandCount, new DefaultMetaHeuristic())
{
    MigrationMode = MigrationMode.RandomRing,
    MigrationsGenerationPeriod = 8,
    GlobalMigrationRate = IslandMetaHeuristic.SmallMigrationRate,
};

FastRandomRandomization.ResetSeed(42);
var pop = new MetaPopulation(islandSize * islandCount, islandSize * islandCount, CreateRastriginChromosome());
var ga = new MetaGeneticAlgorithm(
    pop,
    RastriginFitness(),
    new EliteSelection(),
    new UniformCrossover(0.5f),
    new UniformMutation(true),
    islandsMh)
{
    Termination = new GenerationNumberTermination(generations)
};

// Snapshot the FINAL generation's chromosomes once the GA stops.
List<IChromosome> finalChromosomes = new();
ga.GenerationRan += (s, e) =>
{
    if (ga.GenerationsNumber >= generations)
    {
        finalChromosomes = ga.Population.CurrentGeneration.Chromosomes.ToList();
    }
};

ga.Start();

// Build the per-individual color list: individual i belongs to island floor(i / islandSize).
// IslandMetaHeuristic partitions contiguously (cf. section 1, cell 8), so the slice index is the
// island id -- this is exactly what we color.
List<Color> perIndividual = new();
for (int i = 0; i < finalChromosomes.Count; i++)
{
    int islandId = i / islandSize;
    perIndividual.Add(IslandPalette[islandId % IslandPalette.Length]);
}

// Materialize the population as (x,y) doubles for the renderer.
List<double[]> finalPoints = finalChromosomes
    .Select(c => ((FloatingPointChromosome)c).ToFloatingPoints())
    .Select(v => new[] { v[0], v[1] })
    .ToList();

// Best individual (order-preserving gotcha: BestChromosome may be null mid-run; here the GA
// stopped so it is set, but we deduce it defensively from fitness as in MGS-8/9).
var bestChrom = finalChromosomes.OrderByDescending(c => c.Fitness).First();
double[] bestPoint = ((FloatingPointChromosome)bestChrom).ToFloatingPoints();

byte[] coloredPng = SkiaLandscapeRenderer.RenderHeatmapPng(
    Rastrigin2D,
    (-5.12, 5.12), (-5.12, 5.12),
    width: 420, height: 420,
    population: finalPoints,
    best: bestPoint,
    individualColors: perIndividual);

// Also render the SAME final population in single-color (BlueViolet) for contrast: without the
// per-island palette you cannot tell which individual came from which island.
byte[] monoPng = SkiaLandscapeRenderer.RenderHeatmapPng(
    Rastrigin2D,
    (-5.12, 5.12), (-5.12, 5.12),
    width: 420, height: 420,
    population: finalPoints,
    best: bestPoint);

Console.WriteLine($"GA insulaire sur Rastrigin : {islandCount} iles de {islandSize}, {generations} generations.");
Console.WriteLine($"  Best (x,y) = ({bestPoint[0]:F3}, {bestPoint[1]:F3}), fitness = {bestChrom.Fitness:F3}, Rastrigin = {-bestChrom.Fitness:F3}");
Console.WriteLine($"  Population finale : {finalPoints.Count} individus colores par ile.");
Console.WriteLine();
Console.WriteLine("GAUCHE : population monochrome (on ne distingue pas les iles).");
DisplayPng(monoPng, widthPx: 360);
Console.WriteLine("DROITE : population coloree par ile -- chaque couleur revele un bassin d'attraction.");
DisplayPng(coloredPng, widthPx: 360);

GA insulaire sur Rastrigin : 4 iles de 15, 40 generations.
  Best (x,y) = (0,070, 0,010), fitness = -0,976, Rastrigin = 0,976
  Population finale : 60 individus colores par ile.

GAUCHE : population monochrome (on ne distingue pas les iles).

DROITE : population coloree par ile -- chaque couleur revele un bassin d'attraction.

Interpretation : les iles dessinent leurs bassins

Sortie obtenue : sur le paysage Rastrigin (f(0,0)=0 est l’optimum global, f(1,1)=2 est un pit local typique), le GA insulaire a tourné 40 générations sur 4 îles de 15 individus. Le meilleur individu tombe à (0.070, 0.010) avec une fitness de -0.976 (Rastrigin = 0.976) — dans le bassin de l’optimum global, sans l’atteindre exactement. C’est le piège multimodal que Rastrigin tend, amoindri : les coordonnées x≈0.07 et y≈0.01 sont dans le puits central (où f=0), mais à 40 générations le raffinement fin vers (0,0) n’est pas terminé — la grille des pits voisins (nœuds entiers où f≥2) attend tout individu qui dérive. La population finale (60 individus) est rendue deux fois : monochrome à gauche, colorée par île à droite.

Ce que la couleur révèle que le mono cache : dans le rendu monochrome, les 60 individus forment des tâches BlueViolet dont on ne peut pas dire si elles viennent d’une même île ou de plusieurs. Dès qu’on colore par île, la structure apparaît — chaque couleur s’agglutine dans une région distincte. C’est la signature d’un bassin d’attraction : une île, évoluant quasi-isolément (migration RandomRing toutes les 8 générations seulement), converge vers un optimum — le central pour l’île qui l’a trouvé, des pits locaux pour les autres — et y reste, ses individus convergeant les uns vers les autres.

Pourquoi c’est l’avantage insulaire rendu visible : 1. Niches préservées — chaque couleur occupe son propre bassin. Une population panmictique aurait convergé vers un seul puits (le premier trouvé), perdant les autres. 2. Diversité globale — bien que chaque île soit peu diverse en interne, l’archipel couvre collectivement plusieurs optima. C’est la diversité entre îles que le modèle protège. 3. Le meilleur (marqueur Aqua) — il se trouve à (0.070, 0.010), dans le bassin de l’optimum global, mais il coexiste avec des individus d’autres couleurs installés dans leurs propres bassins. La migration n’a pas encore tout homogénéisé.

Lien avec la section 3 : la comparaison numérique (insulaire bat panmictique sur la moyenne des distances) prenait tout son sens ici. Sur un paysage unimodal (cône de la section 3), les îles n’apportent rien de visible — un seul bassin, un seul optimum. Sur Rastrigin, la multimodalité donne aux îles l’occasion de montrer leur force : explorer en parallèle plusieurs régions prometteuses plutôt que de miser tout sur une seule. Le fait que le meilleur reste à fitness=-0.976 (et non 0) illustre aussi la difficulté résiduelle : les îles aident à explorer, mais le raffinement fin vers (0,0) demande plus de générations ou une mutation plus agressive.

Limite honnête (No-Free-Lunch). Si la migration est trop forte (LargeMigrationRate, période courte), les îles s’homogénéisent et la carte redevient quasi-monochrome — l’effet archipel s’efface. Si elle est nulle (MigrationMode.None), les îles sont si petites (15 individus) qu’elles dérivent fortuitement, parfois vers de mauvais puits. L’overlay coloré est aussi un outil de diagnostic : il montre visuellement si votre taux de migration est bien calibré.

Synergie exploration / exploitation — flipbook de convergence animé

Les instantanés statiques ci-dessus (cellule précédente) figent l’état final : 4 amas colorés, un par bassin d’attraction. Pour voir la synergie entre iles — le bon mélange d’exploration et d’exploitation que cherche le modèle insulaire — il faut animer toute la course.

On capture la population à des générations sélectionnées, on colore chaque individu par son ile courante (même palette que ci-dessus, tranche contiguë i / islandSize), puis on assemble les images PNG par génération en un seul GIF bouclé via SkiaLandscapeRenderer.EncodeAnimatedGif (co-évolution du fork jsboige/MetaGeneticSharp #29/#30, See #1203 — SkiaSharp ne fournit pas d’encodeur GIF animé, donc le conteneur GIF89a + la palette median-cut + le LZW sont écrits dans le fork ; maxColors:64 (#30) bande le dégradé Rastrigin en plages compressibles par le LZW).

Lecture de l’animation : - Frames précoces (exploration) : les 4 sous-populations colorées se dispersent sur la grille de bassins de Rastrigin — chaque ile couvre une région différente, la diversité est préservée par l’isolement parallèle. - Frames tardives (exploitation) : chaque amas coloré se resserre vers un bassin d’attraction — chaque ile exploite localement son optimum. - Migration (RandomRing toutes les 8 générations) : les couleurs se mélangent légèrement aux générations de migration — c’est le « bon mélange » : les iles échangent du matériel sans fusionner prématurément.

C’est la signature visuelle de la synergie insulaire : diversité préservée plus longtemps (exploration parallèle) puis convergence (exploitation), rendue visible dans une seule animation plutôt qu’une série d’images statiques.

// Convergence flipbook du modele insulaire (colore) : capturer la population a des generations
// selectionnees, colorer chaque individu par son ile courante (tranche contigue i/islandSize,
// cf cellule precedente), et assembler les frames PNG par generation en UN seul GIF boucle via
// EncodeAnimatedGif (fork #29/#30, See #1203). L'animation rend visible la synergie exploration ->
// exploitation : frames precoces = 4 nuages colores disperses (exploration parallele), frames
// tardives = chaque cluster se resserre vers un bassin (exploitation). Orchestration pure sur le
// renderer verbatim -- aucun nouveau code de rendu.
List<(int gen, List<double[]> pop, List<Color> colors, double[] best)> RunIslandGaTraced(
    int generations, int islandSize, int islandCount, ISet<int> snapshotGens)
{
    var islandsMh = new IslandMetaHeuristic(islandSize, islandCount, new DefaultMetaHeuristic())
    {
        MigrationMode = MigrationMode.RandomRing,
        MigrationsGenerationPeriod = 8,
        GlobalMigrationRate = IslandMetaHeuristic.SmallMigrationRate,
    };
        FastRandomRandomization.ResetSeed(42); // graine le flipbook : frames reproductibles
    var pop = new MetaPopulation(islandSize * islandCount, islandSize * islandCount, CreateRastriginChromosome());
    var ga = new MetaGeneticAlgorithm(
        pop, RastriginFitness(), new EliteSelection(),
        new UniformCrossover(0.5f), new UniformMutation(true), islandsMh)
    { Termination = new GenerationNumberTermination(generations) };

    var trace = new List<(int, List<double[]>, List<Color>, double[])>();
    int genCount = 0;
    ga.GenerationRan += (s, e) =>
    {
        genCount++;
        if (!snapshotGens.Contains(genCount)) return;
        var chroms = ga.Population.CurrentGeneration.Chromosomes;
        var pts = chroms.Select(c => ((FloatingPointChromosome)c).ToFloatingPoints())
                        .Select(v => new[] { v[0], v[1] }).ToList();
        var cols = new List<Color>(pts.Count);
        for (int i = 0; i < pts.Count; i++)
            cols.Add(IslandPalette[(i / islandSize) % IslandPalette.Length]);
        var bestPts = ((FloatingPointChromosome)chroms.OrderByDescending(c => c.Fitness).First()).ToFloatingPoints();
        trace.Add((genCount, pts, cols, new[] { bestPts[0], bestPts[1] }));
    };
    ga.Start();
    return trace;
}

int[] gifGens = { 1, 3, 6, 10, 16, 25, 40 };
var traceGif = RunIslandGaTraced(generations: 40, islandSize: 15, islandCount: 4, snapshotGens: new HashSet<int>(gifGens));

var gifFrames = new List<byte[]>(traceGif.Count);
foreach (var (gen, snap, cols, best) in traceGif)
{
    gifFrames.Add(SkiaLandscapeRenderer.RenderHeatmapPng(
        Rastrigin2D, (-5.12, 5.12), (-5.12, 5.12), width: 320, height: 320,
        population: snap, best: best, individualColors: cols));
}
byte[] islandGif = SkiaLandscapeRenderer.EncodeAnimatedGif(gifFrames, delayCentiseconds: 45, loopCount: 0, maxColors: 64);

display(HTML($"<figure style='margin:6px 0'>"
    + $"<img src='data:image/gif;base64,{Convert.ToBase64String(islandGif)}' style='width:360px;image-rendering:pixelated;border:1px solid #ccc'/>"
    + $"<figcaption style='font:12px sans-serif;color:#555'>Convergence animee du modele insulaire ({gifFrames.Count} generations, 4 iles) : exploration (4 nuages colores disperses sur la grille de bassins) puis exploitation (chaque cluster se resserre vers un bassin d'attraction). Migration RandomRing toutes les 8 generations.</figcaption></figure>"));
Console.WriteLine($"GIF insulaire : {gifFrames.Count} frames, {islandGif.Length / 1024.0:F1} KB (image/gif, lisible sur le viewer statique GitHub).");

Convergence animee du modele insulaire (7 generations, 4 iles) : exploration (4 nuages colores disperses sur la grille de bassins) puis exploitation (chaque cluster se resserre vers un bassin d'attraction). Migration RandomRing toutes les 8 generations.

GIF insulaire : 7 frames, 295,0 KB (image/gif, lisible sur le viewer statique GitHub).

Synergie des métaheuristiques complémentaires — benchmark

Le flipbook ci-dessus montre la convergence insulaire ; cette section la mesure. La question du mandat #3965 : une combinaison de métaheuristiques complémentaires (un explorateur + un exploiteur) dans des îles hétérogènes produit-elle une synergie — mieux que chaque constituant seul, sur un problème où l’exploration compte ?

Protocole (contrôle rigoureux de la structure d’îles) : - Fonction : Rastrigin-5 (fortement multimodale — une grille régulière de minima locaux, où un algorithme qui n’explore pas se fige dans un bassin médiocre). - Structure fixe : 3 îles × 20 individus = 60, 60 générations, migration RandomRing. On ne varie QUE la métaheuristique par île. - Configurations : 3 configurations homogènes (tout-WOA, tout-EO, tout-GA = contrôles) vs 1 île WOA + 1 île EO + 1 île GA (hétérogène). Même structure, mêmes budgets — seul le mix change. WOA = exploration (encerclement + bubble-net en spirale), EO = exploitation (equilibrium pool convergent), GA = défaut équilibré. - ≥4 graines (0, 1, 7, 42, 99) : on rapporte moyenne ± écart-type du meilleur Rastrigin (à minimiser, 0 = optimum global). FastRandomRandomization.ResetSeed amorce le RNG optimiseur à chaque course (reproductibilité multi-seed, cf pr-review-discipline C).

Verdict honnête (pr-review-discipline C) : SYNERGIE si l’hétérogène bat chaque constituant homogène en moyenne ; sinon on le dit (PAS DE SYNERGIE / partiel). Pas de « promising ». Les composés géométriques (WOA/EO/FBI) exigent des gènes double nus → cette section définit DoubleArrayChromosome (cf MGS-6), indépendante du FloatingPointChromosome à bits de la section 4 ci-dessus. La fabrique MetaHeuristicsService.CreateMetaHeuristicByName cale automatiquement un convertisseur d’identité double ↔︎ gene puis appelle .Build() pour WOA/EO/FBI.

// Synergie heterogene vs homogene sur Rastrigin-5D (mandat #3965).
// DoubleArrayChromosome : chromosome a genes double nus. Les composes geometriques (WOA/EO/FBI)
// exigent une representation continue transparente (identite gene<->double), impossible avec le
// FloatingPointChromosome a bits de la section 4. Meme definition qu'en MGS-6 (cell-003) ; le
// CreateNew() randomise dans les bornes -- sinon les 60 individus initiaux sont des clones et le
// GA ne peut pas explorer (diversite nulle, bassin mediocre fige).
public class DoubleArrayChromosome : ChromosomeBase
{
    private readonly double _min;
    private readonly double _max;
    public DoubleArrayChromosome(double[] values, double min, double max) : base(values.Length)
    {
        _min = min;
        _max = max;
        for (int i = 0; i < values.Length; i++) ReplaceGene(i, new Gene(values[i]));
    }
    public override IChromosome CreateNew()
    {
        var r = RandomizationProvider.Current;
        var v = new double[Length];
        for (int i = 0; i < Length; i++) v[i] = r.GetDouble(_min, _max);
        return new DoubleArrayChromosome(v, _min, _max);
    }
    public override Gene GenerateGene(int geneIndex)
        => new Gene(RandomizationProvider.Current.GetDouble(_min, _max));
    public double[] GetDoubleValues() => GetGenes().Select(g => (double)g.Value).ToArray();
}

const int SYN_DIM = 5;
const double SYN_LO = -5.12, SYN_HI = 5.12;
const int SYN_ISLAND = 20, SYN_NISLAND = 3, SYN_GENS = 60;
int[] SYN_SEEDS = { 0, 1, 7, 42, 99 };

// Rastrigin-5D : f(x) = 10*n + sum(x_i^2 - 10*cos(2*pi*x_i)), minimisée à l'origine (0). GA maximise
// -> on negige (fitness = -Rastrigin), meilleur = plus proche de 0 par valeurs negatives.
double SynRastrigin(double[] x)
{
    double s = 0.0;
    for (int i = 0; i < x.Length; i++) s += x[i] * x[i] - 10.0 * Math.Cos(2 * Math.PI * x[i]);
    return 10.0 * x.Length + s;
}
IFitness SynFitness() => new FuncFitness(c => -SynRastrigin(((DoubleArrayChromosome)c).GetDoubleValues()));

// La fabrique cale automatiquement un convertisseur d'identite double<->gene puis appelle .Build()
// pour WOA/EO/FBI (cf MetaHeuristicsService). "Default" = GA brut. On n'utilise pas DE : absent du
// switch de la fabrique (retournerait une instance non-construite). Trio propre : WOA (exploration)
// + EO (exploitation) + GA (defaut equilibre).
IMetaHeuristic SynMh(string name) => name == "Default"
    ? new DefaultMetaHeuristic()
    : MetaHeuristicsService.CreateMetaHeuristicByName(name, maxGenerations: SYN_GENS, populationSize: SYN_ISLAND);

double SynRun(int seed, string[] perIsland, bool hetero)
{
    FastRandomRandomization.ResetSeed(seed);
    double mid = 0.5 * (SYN_LO + SYN_HI);
    var adam = new DoubleArrayChromosome(Enumerable.Repeat(mid, SYN_DIM).ToArray(), SYN_LO, SYN_HI);
    var pop = new MetaPopulation(SYN_ISLAND * SYN_NISLAND, SYN_ISLAND * SYN_NISLAND, adam);
    IslandMetaHeuristic mh = hetero
        ? new IslandMetaHeuristic(
            (SYN_ISLAND, SynMh(perIsland[0])),
            (SYN_ISLAND, SynMh(perIsland[1])),
            (SYN_ISLAND, SynMh(perIsland[2])))
        : new IslandMetaHeuristic(SYN_ISLAND, SYN_NISLAND, SynMh(perIsland[0]));
    var ga = new MetaGeneticAlgorithm(pop, SynFitness(),
        new EliteSelection(), new UniformCrossover(0.5f), new UniformMutation(true), mh)
    { Termination = new GenerationNumberTermination(SYN_GENS) };
    ga.Start();
    return ga.BestChromosome.Fitness.HasValue ? -ga.BestChromosome.Fitness.Value : double.NaN;
}

(double mean, double std, string detail) SynConfig(string[] names, bool hetero)
{
    var rs = SYN_SEEDS.Select(s => SynRun(s, names, hetero)).ToList();
    double m = rs.Average();
    double sd = Math.Sqrt(rs.Average(r => (r - m) * (r - m)));
    return (m, sd, $"[{string.Join(", ", rs.Select(r => r.ToString("F2")))}]");
}

var homoGA  = SynConfig(new[] { "Default", "", "" }, false);
var homoWOA = SynConfig(new[] { "WhaleOptimisation", "", "" }, false);
var homoEO  = SynConfig(new[] { "EquilibriumOptimizer", "", "" }, false);
var hetero  = SynConfig(new[] { "WhaleOptimisation", "EquilibriumOptimizer", "Default" }, true);

void PrintRow(string label, (double mean, double std, string detail) r)
    => Console.WriteLine(string.Format("  {0,-26} mean={1,8:F3}  std={2,7:F3}  runs={3}", label, r.mean, r.std, r.detail));

Console.WriteLine("Banc synergie insulaire -- Rastrigin-5D, graines {0,1,7,42,99}, 60 generations, 3 iles x 20 indiv.\n");
PrintRow("Homogene GA (3x GA)",   homoGA);
PrintRow("Homogene WOA (3x WOA)", homoWOA);
PrintRow("Homogene EO (3x EO)",   homoEO);
PrintRow("Heterogene WOA+EO+GA",  hetero);
Console.WriteLine();

bool beatsGa  = hetero.mean < homoGA.mean;
bool beatsWoa = hetero.mean < homoWOA.mean;
bool beatsEo  = hetero.mean < homoEO.mean;
Console.WriteLine(string.Format("Heterogene vs homogene-GA  : {0} ({1:+0.000;-0.000}).", beatsGa  ? "GAGNE" : "perd",  homoGA.mean  - hetero.mean));
Console.WriteLine(string.Format("Heterogene vs homogene-WOA : {0} ({1:+0.000;-0.000}).", beatsWoa ? "GAGNE" : "perd",  homoWOA.mean - hetero.mean));
Console.WriteLine(string.Format("Heterogene vs homogene-EO  : {0} ({1:+0.000;-0.000}).", beatsEo  ? "GAGNE" : "perd",  homoEO.mean  - hetero.mean));
string verdict = (beatsGa && beatsWoa && beatsEo)
    ? "SYNERGIE : le mix heterogene exploite le meilleur des 3 regimes (bat chaque constituant seul)."
    : ((beatsGa || beatsWoa || beatsEo)
        ? "PARTIEL : le mix bat certaines configs homogenes, pas toutes (pas de synergie nette a ce budget)."
        : "PAS DE SYNERGIE : aucune config homogene n'est depassee par le mix a ce budget.");
Console.WriteLine("\nVerdict : " + verdict);

Banc synergie insulaire -- Rastrigin-5D, graines {0,1,7,42,99}, 60 generations, 3 iles x 20 indiv.

  Homogene GA (3x GA)        mean=   1,683  std=  0,334  runs=[1,29, 1,50, 1,48, 1,98, 2,17]
  Homogene WOA (3x WOA)      mean=  11,278  std=  6,877  runs=[13,78, 20,06, 3,06, 3,39, 16,11]
  Homogene EO (3x EO)        mean=   0,404  std=  0,495  runs=[0,00, 0,00, 1,00, 0,00, 1,02]
  Heterogene WOA+EO+GA       mean=   1,683  std=  1,136  runs=[3,40, 2,03, 1,99, 1,00, 0,00]

Heterogene vs homogene-GA  : GAGNE (+0,000).
Heterogene vs homogene-WOA : GAGNE (+9,596).
Heterogene vs homogene-EO  : perd (-1,279).

Verdict : PARTIEL : le mix bat certaines configs homogenes, pas toutes (pas de synergie nette a ce budget).

5. Resume et conclusion de la serie

Ce que nous avons appris dans ce notebook

Concept	Rôle	Point cle
IslandPopulation	Sous-population d’individus complets (slice contigu)	Herite de `SubPopulation`, ajoute `MigrationRates`
IslandMetaHeuristic	Orchestrateur insulaire : evolution locale + migration	Herite de `SubPopulationMetaHeuristicBase<IslandPopulation>`
MigrationMode	Stratégie de migration (None, Static, RandomRing, RandomPermutation, Reinforced)	Contrôle la topologie du flux génétique
EmigrantPicker / ImigrantReplacePicker	Sélection des migrants et des remplacants	Par defaut : meilleurs partent, pires sont remplacés
Crossover probability = 1.0	Force dans `ScopedMatchParentsAndCross`	Load-bearing : la mutation et reinsertion re-slicent par tailles fixes
Overlay iles colorees (section 4)	`RenderHeatmapPng(..., individualColors)` colore chaque individu par son ile	Revele les bassins d’attraction sur un paysage multimodal

Conclusion de la serie MetaGeneticSharp

En quatre notebooks, nous avons parcouru les primitives fondamentales de MetaGeneticSharp :

Notebook	Concept	Idee centrale
NB-A Introduction	Moteur autonome	`MetaGeneticAlgorithm` : un GA qui s’execute sans callbacks, avec `IMetaHeuristic` comme cerveau
NB-B Composition	Primitives de contrôle	`MatchMetaHeuristic`, `ConditionalMetaHeuristic`, `SequentialMetaHeuristic` : composer des comportements
NB-C Eukaryote	Sous-populations par gene	`EukaryoteChromosome` + `SubPopulation` : decouper le genome et evoluer chaque partie independamment
NB-D Insulaire	Sous-populations par individu	`IslandPopulation` + `IslandMetaHeuristic` : structurer spatialement la population avec migration

Pour aller plus loin

Ces quatre notebooks couvrent les primitives de base du framework. Le ROADMAP.md du depot MetaGeneticSharp decrit les directions suivantes : - Système de paramètres : configuration dynamique des probabilites et taux - Métaheuristiques composees : combinaisons de primitives WOA (Whale Optimization), EO (Equilibrium Optimizer), FBI - Benchmarks : comparaison systématique des configurations sur des problemes de reference

Code source : https://github.com/jsboige/MetaGeneticSharp

Exercice 1 : Comparer 2 iles vs 8 iles sur la vitesse de convergence

L’objectif est d’etudier l’impact du nombre d’iles sur la convergence. Avec 2 iles de 20 individus, chaque ile est grande mais il y a peu de diversite entre iles. Avec 8 iles de 5 individus, chaque ile est très petite mais la diversite globale est maximale.

Enonce : Configurez deux modèles insulaires et comparez leur convergence sur 5 seeds : - Configuration A : 2 iles de 20 individus - Configuration B : 8 iles de 5 individus

Indices : - IslandMetaHeuristic(20, 2, new DefaultMetaHeuristic()) pour 2 iles de 20 - IslandMetaHeuristic(5, 8, new DefaultMetaHeuristic()) pour 8 iles de 5 - Reutilisez la fonction RunGA définie dans la section 3 pour executer les comparaisons - Observez si les petites iles convergent mieux (plus de diversite) ou moins bien (taille insuffisante)

// Exercice 1 : Comparer 2 iles vs 8 iles sur la vitesse de convergence
// TODO: Configurer deux IslandMetaHeuristic avec des nombres d'iles differents
// TODO: Executer 5 seeds pour chaque configuration et comparer les moyennes
// Indice: IslandMetaHeuristic(islandSize, islandCount, new DefaultMetaHeuristic())
// Indice: Taille totale = 40 dans les deux cas (2*20 = 8*5 = 40)

// Etape 1 : Configurer 2 iles de 20
// var mh2Islands = new IslandMetaHeuristic(20, 2, new DefaultMetaHeuristic())
// {
//     MigrationMode = MigrationMode.RandomRing,
//     MigrationsGenerationPeriod = 5,
//     GlobalMigrationRate = IslandMetaHeuristic.LargeMigrationRate
// };

// Etape 2 : Configurer 8 iles de 5
// var mh8Islands = new IslandMetaHeuristic(5, 8, new DefaultMetaHeuristic())
// {
//     MigrationMode = MigrationMode.RandomRing,
//     MigrationsGenerationPeriod = 5,
//     GlobalMigrationRate = IslandMetaHeuristic.LargeMigrationRate
// };

// Etape 3 : Comparer sur 5 seeds avec RunGA

object result = null; // TODO etudiant : lancer les comparaisons et afficher les resultats
Console.WriteLine("Exercice a completer : 2 iles vs 8 iles");

Exercice a completer : 2 iles vs 8 iles

Exercice 2 : Implementer un mode de migration bias vers l’ile la moins performante

L’objectif est de créer une variante de migration qui envoie les meilleurs individus vers l’ile ayant la pire performance (inverse de l’approche elitiste par defaut). L’idee est de “sauver” les iles en difficulté en leur injectant du bon materiel génétique.

Enonce : Utilisez le mode Static et ajustez manuellement les MigrationRates pour biaiser la migration vers l’ile la moins performante.

Indices : - Le mode Static utilise StaticMigrationRates : une matrice islandCount x islandCount de taux fixes - StaticMigrationRates[i][j] = taux de migration de l’ile i vers l’ile j - Pour biaiser vers la pire ile : identifiez l’ile avec le fitness moyen le plus bas, et augmentez les taux vers cette ile - IslandMetaHeuristic expose StaticMigrationRates en propriete publique - Vous pouvez modifier les MigrationRates de chaque IslandPopulation après la première generation

// Exercice 2 : Mode de migration bias vers l'ile la moins performante
// TODO: Configurer un IslandMetaHeuristic avec MigrationMode.Static
// TODO: Apres chaque generation de migration, ajuster les MigrationRates
//   pour envoyer plus d'individus vers l'ile la moins performante
// Indice: Utilisez StaticMigrationRates comme base, puis augmentez le taux
//   vers l'ile avec le fitness moyen le plus bas
// Indice: GenerationNumberTermination + GenerationRan event pour intercepter

// Etape 1 : Configurer le modele insulaire en mode Static
// var mh = new IslandMetaHeuristic(10, 4, new DefaultMetaHeuristic())
// {
//     MigrationMode = MigrationMode.Static,
//     MigrationsGenerationPeriod = 5
// };

// Etape 2 : S'abonner a l'evenement GenerationRan pour ajuster les taux
// var ga = new MetaGeneticAlgorithm(...);
// ga.GenerationRan += (s, e) => { /* ajuster les taux */ };

// Etape 3 : Executer et comparer avec le mode RandomRing standard

object result = null; // TODO etudiant : implementer et tester
Console.WriteLine("Exercice a completer : migration vers l'ile la moins performante");

Exercice a completer : migration vers l'ile la moins performante

Exercice 3 : Combiner EukaryoteMetaHeuristic (NB-C) avec IslandMetaHeuristic

L’objectif est de combiner les deux approches de sous-population : des iles (partition par individu) contenant chacune un eukaryote (partition par gene). C’est l’architecture la plus riche de MetaGeneticSharp.

Enonce : Utilisez IslandMetaHeuristic avec comme sous-heuristiques des EukaryoteMetaHeuristic. Chaque ile contient une population eukaryote qui decompose le genome en sous-chromosomes.

Indices : - IslandMetaHeuristic accepte des IMetaHeuristic quelconques comme sous-heuristiques, pas seulement DefaultMetaHeuristic - Utilisez un chromosome a 2 genes (position, vitesse) avec un EukaryoteMetaHeuristic dans chaque ile - IslandMetaHeuristic(20, 2, eukaryoteMh, eukaryoteMh) : 2 iles de 20, chacune eukaryote - L’Eukaryote decompose le genome (NB-C), l’insulaire decompose la population (NB-D) - Les deux niveaux sont orthogonaux : partition par gene x partition par individu

// Exercice 3 : Combiner EukaryoteMetaHeuristic avec IslandMetaHeuristic
// TODO: Creer un EukaryoteMetaHeuristic pour la decomposition par gene
// TODO: L'utiliser comme sous-heuristique d'un IslandMetaHeuristic
// TODO: Comparer avec un IslandMetaHeuristic + DefaultMetaHeuristic seul
// Indice: IslandMetaHeuristic(islandSize, islandCount, eukaryoteMh1, eukaryoteMh2)
// Indice: EukaryoteMetaHeuristic(16, active, noOp) { Scope = Crossover | Mutation }
// Indice: Le chromosome doit avoir 2 genes (32 bits total, 16 par sous-chromosome)

// Etape 1 : Creer le chromosome et le fitness
// var adam = new FloatingPointChromosome(
//     new double[] { 0, 0 }, new double[] { 100, 100 },
//     new int[] { 16, 16 }, new int[] { 2, 2 });

// Etape 2 : Creer les EukaryoteMetaHeuristic (un par ile)
// var eukaryoteMh = new EukaryoteMetaHeuristic(16, new DefaultMetaHeuristic(), new DefaultMetaHeuristic())
// {
//     Scope = EvolutionStage.Crossover | EvolutionStage.Mutation
// };

// Etape 3 : Creer l'IslandMetaHeuristic avec les EukaryoteMetaHeuristic
// var islandWithEukaryote = new IslandMetaHeuristic(20, 2, eukaryoteMh, eukaryoteMh)
// {
//     MigrationMode = MigrationMode.RandomRing,
//     MigrationsGenerationPeriod = 5
// };

// Etape 4 : Executer et comparer avec Island + Default

object result = null; // TODO etudiant : implementer et tester la combinaison
Console.WriteLine("Exercice a completer : Eukaryote + Island");

Exercice a completer : Eukaryote + Island

Navigation : Index | << MGS-3 Eukaryote | MGS-5 Composés >>

Retour au sommet