MGS-2 : Composition de métaheuristiques – Match et primitives de contrôle

Navigation : Index | << MGS-1 Introduction | MGS-3 Eukaryote >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Configurer le mécanisme de match (MatchMetaHeuristic, MatchingKind) pour contrôler la sélection des parents lors du crossover 2. Utiliser les primitives de contrôle de flux (SwitchMetaHeuristic, SizeBasedMetaHeuristic, GenerationMetaHeuristic, StageSwitchMetaHeuristic) pour adapter le comportement en cours d’évolution 3. Composer ces primitives en stratégies multi-phases qui combinent plusieurs comportements 4. Comparer les performances de différentes stratégies sur un même problème d’optimisation

Prerequis

  • MGS-1 : Introduction a MetaGeneticSharp et au moteur autonome
  • Notions de base en algorithmes génétiques (sélection, crossover, mutation)
  • C# .NET 9.0 et .NET Interactive

Duree estimee : 60 minutes

1. Pourquoi composer des métaheuristiques ?

Dans MGS-1, nous avons utilise DefaultMetaHeuristic et NoOpMetaHeuristic comme des blocs monolithiques. En pratique, une stratégie d’évolution efficace s’adapte au contexte :

  • En debut d’évolution, on favorise l’exploration (mutation forte, match aleatoire)
  • En fin d’évolution, on favorise l’exploitation (crossover entre les meilleurs, mutation faible)
  • Selon la taille de la population, on ajuste la pression de sélection
  • Selon l’étape (crossover vs mutation), on applique des logiques différentes

MetaGeneticSharp fournit un ensemble de primitives de contrôle de flux pour exprimer ces adaptations, a la maniere des structures de contrôle d’un langage de programmation :

Primitive Analogie Rôle
MatchMetaHeuristic Appariement Contrôle la sélection des partenaires de crossover
SwitchMetaHeuristic<T> switch Dispatch vers une sous-métaheuristique selon un index
IfElseMetaHeuristic if/else Branchement booléen (cas particulier de Switch)
SizeBasedMetaHeuristic switch par plage Dispatch selon des plages contigues d’indices
GenerationMetaHeuristic Boucle par phase Alterne les phases selon le numéro de génération
StageSwitchMetaHeuristic switch par étape Dispatch selon l’étape d’évolution (Crossover, Mutation, Sélection…)
ContainerMetaHeuristic Englobant Delegue tout a une sous-métaheuristique
ScopedMetaHeuristic if par étape N’intercepte que les étapes specifiees

Ces primitives se combinent librement : une GenerationMetaHeuristic peut contenir des StageSwitchMetaHeuristic, qui elles-mêmes contiennent des MatchMetaHeuristic.

// Wiring: load MetaGeneticSharp + GeneticSharp DLLs from submodule build
// Build prerequisite: dotnet build ../MetaGeneticSharp/MetaGeneticSharp.sln
// Requires: git -C ../MetaGeneticSharp submodule update --init GeneticSharp
#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"

using MetaGeneticSharp;
using GeneticSharp;

Console.WriteLine("MetaGeneticSharp + GeneticSharp charges avec succes.");
Console.WriteLine("  MatchMetaHeuristic      : " + typeof(MatchMetaHeuristic).Name);
Console.WriteLine("  SwitchMetaHeuristic<int>: " + typeof(SwitchMetaHeuristic<int>).Name);
Console.WriteLine("  GenerationMetaHeuristic : " + typeof(GenerationMetaHeuristic).Name);
Console.WriteLine("  StageSwitchMetaHeuristic: " + typeof(StageSwitchMetaHeuristic).Name);
Console.WriteLine("  MatchingKind.Best       : " + MatchingKind.Best);
Console.WriteLine("  EvolutionStage.Crossover: " + EvolutionStage.Crossover);
MetaGeneticSharp + GeneticSharp charges avec succes.
  MatchMetaHeuristic      : MatchMetaHeuristic
  SwitchMetaHeuristic<int>: SwitchMetaHeuristic`1
  GenerationMetaHeuristic : GenerationMetaHeuristic
  StageSwitchMetaHeuristic: StageSwitchMetaHeuristic
  MatchingKind.Best       : Best
  EvolutionStage.Crossover: Crossover

2. Le mécanisme de Match

Comment les parents sont apparies lors du crossover

Dans un GA standard, le crossover apparie les parents sequentiellement (parent 0 avec parent 1, parent 2 avec parent 3, etc.). MatchMetaHeuristic généralise ce mécanisme : pour chaque individu de référence, elle selectionne un ou plusieurs partenaires selon une stratégie de match.

Le composant central est le MatchPicker, qui contient une liste de directives de pick (MatchingSettings). Chaque directive specifie : - MatchingKind : la technique de sélection (Current, Neighbor, Random, Best, Worst, RouletteWheel…) - AdditionalPicks : nombre de picks supplementaires (0 = 1 seul partenaire) - CachingScope : la porte de cache du résultat (None, Génération, MetaHeuristic…)

Les stratégies de MatchingKind

MatchingKind Description Cas d’usage typique
Current L’individu de référence lui-même Self-crossover, clonage
Neighbor Le voisin suivant dans la population Appariement adjacent (defaut GA standard)
Random Un individu aleatoire Exploration, diversite
Best Le meilleur chromosome de la population Exploitation, intensification
Worst Le pire chromosome Exploration inverse, diversification
RouletteWheel Sélection proportionnelle au fitness Pression de sélection graduee

Utilisation via DefaultMetaHeuristic

La propriete MatchMetaHeuristic de DefaultMetaHeuristic active le mécanisme de match avec la configuration Current + Random par defaut. L’extension WithMatches() permet de personnaliser les directives.

// Shared setup: fitness function and helper methods for all demonstrations in this notebook

// Fitness: minimize f(x) = sum(x_i^2) (Sphere function)
public class QuadraticFitness : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        var fc = (FloatingPointChromosome)chromosome;
        var genes = fc.ToFloatingPoints();
        double sum = 0.0;
        foreach (var g in genes) sum += g * g;
        return 1.0 / (1.0 + sum);
    }
}

// Diagnostic trajectoires (review #17924) : vecteur x du meilleur chromosome du dernier run.
// Sert a verifier que deux configurations distinctes divergent a seed egal : une egalite
// exacte de f(x) entre configurations n'est interpretable qu'accompagnee des vecteurs x.
public static double[] LastBestX;

// Helper: run GA with any IMetaHeuristic as the top-level metaheuristic
double RunWithMetaHeuristic(IMetaHeuristic mh, string label, int popSize = 50, int generations = 50, List<double> trace = null, int seed = 42)
{
// Codage 64 bits + 4 decimales (diagnostic #17924) : fractionDigits=0 reduisait chaque
// dimension a 21 entiers (Rastrigin = Sphere exactement, cf section 5) ; les 4 decimales
// restaurent un paysage continu. NB : un codage serre (20 bits) est refuse par
// GeneticSharp (l'aller-retour interne ToFloatingPoints/ToRepresentation exige 64 bits),
// la redondance reste donc elevee (18 bits utiles sur 64) -- voir la lecture du
// resultat de la section 2 pour ce que ce banc peut et ne peut pas etablir.
    var adam = new FloatingPointChromosome(
        new double[] { -10, -10, -10, -10 },
        new double[] {  10,  10,  10,  10 },
        new int[] { 64, 64, 64, 64 },
        new int[] { 4, 4, 4, 4 });

// Reproductibilite du banc : le moteur tire son alea de RandomizationProvider.Current,
// un FastRandomRandomization NON seede par defaut. Sans cet appel, chaque execution
// produit d'autres valeurs. (cf #12071, #17863, #17864 pour MGS-05, #17919 pour MGS-01.)
// Seed PAR APPEL : chaque configuration repart du meme tirage initial -- comparaison
// equitable entre strategies. Le parametre optionnel trace collecte le meilleur f(x)
// a chaque generation : deux configurations differentes doivent y produire des
// trajectoires differentes malgre ce seed commun, sinon le match n'est pas branche
// (diagnostic de la section 2, review #17924).
    FastRandomRandomization.ResetSeed(seed);
    var pop = new MetaPopulation(popSize, popSize, adam);
    var ga = new MetaGeneticAlgorithm(
        pop,
        new QuadraticFitness(),
        new TournamentSelection(3),
// Operateurs NON degeneres (cf #17997). Les deux valeurs par defaut rendaient ce banc
// inerte : `new OnePointCrossover()` vaut `OnePointCrossover(0)`, donc la coupe tombe
// toujours apres le bit 0 et un enfant n'echange qu'un seul bit sur 256 avec l'autre
// parent (les enfants observes sont des clones ou des quasi-clones) ; `new
// UniformMutation()` vaut `UniformMutation(false)`, dont l'index mutable est tire UNE
// fois puis mis en cache pour toute la duree de vie de l'operateur -- un seul bit est
// donc mutable du debut a la fin du run. UniformCrossover recombine tous les bits,
// FlipBitMutation retire un bit au hasard A CHAQUE APPEL.
        new UniformCrossover(),
        new FlipBitMutation(),
        mh);

    ga.Termination = new GenerationNumberTermination(generations);
    ga.CrossoverProbability = 0.75f;
    ga.MutationProbability = 0.2f;

    if (trace != null)
    {
        ga.GenerationRan += (sender, args) => trace.Add(1.0 / ga.BestChromosome.Fitness.Value - 1.0);
    }

    ga.Start();
    LastBestX = ((FloatingPointChromosome)ga.BestChromosome).ToFloatingPoints();
    return (1.0 / ga.BestChromosome.Fitness.Value) - 1.0;
}

// Helper: build a MatchMetaHeuristic with the given MatchingKinds, wired for crossover
MatchMetaHeuristic BuildMatch(params MatchingKind[] kinds)
{
    var match = new MatchMetaHeuristic();
    foreach (var kind in kinds)
    {
        match.Picker.MatchPicks.Add(new MatchingSettings
        {
            MatchingKind = kind,
            CachingScope = MatchingSettings.GetDefaultScope(kind)
        });
    }
    match.CrossMetaHeuristic = new DefaultMetaHeuristic();
    match.SubMetaHeuristic = new DefaultMetaHeuristic();
    return match;
}

var matchKinds = string.Join(", ", Enum.GetNames(typeof(MatchingKind)));
Console.WriteLine("Setup OK : QuadraticFitness, RunWithMetaHeuristic, BuildMatch definis");
Console.WriteLine("  MatchMetaHeuristic  : " + typeof(MatchMetaHeuristic).Name);
Console.WriteLine("  MatchingKind values : " + matchKinds);
Setup OK : QuadraticFitness, RunWithMetaHeuristic, BuildMatch definis
  MatchMetaHeuristic  : MatchMetaHeuristic
  MatchingKind values : Current, Neighbor, Random, RouletteWheel, Best, Worst, Child, Custom

Demonstration : Stratégie de match

Nous allons maintenant comparer trois stratégies de match sur le problème de la fonction Sphere (\(f(x) = \sum x_i^2\)) :

  1. Current + Neighbor : appariement adjacent (proche du GA standard)
  2. Current + Random : partenaire aleatoire (diversification)
  3. Current + Best : croisement systématique avec le meilleur (intensification)

Approche : pour chaque configuration, nous lancons le GA avec une population de 50 individus pendant 50 générations, puis nous mesurons la valeur objectif \(f(x)\) (0 = optimal).

// Demonstration: Match strategies comparison
// We compare three match strategies on the quadratic (Sphere) problem:
// 1. Current + Neighbor  (adjacent, closest to standard GA)
// 2. Current + Random    (diversified matching)
// 3. Current + Best      (elitist matching -- always cross with the best)

Console.WriteLine("Comparaison des strategies de match (50 generations, population=50)");
Console.WriteLine("======================================================================");
Console.WriteLine(string.Format("{0,-30} {1,-15} {2,-15}", "Configuration", "f(x)", "Match picks"));
Console.WriteLine("----------------------------------------------------------------------");

var matchConfigs = new[]
{
    (Name: "Current + Neighbor (adjacent)",   Match: BuildMatch(MatchingKind.Current, MatchingKind.Neighbor)),
    (Name: "Current + Random (diversifie)",   Match: BuildMatch(MatchingKind.Current, MatchingKind.Random)),
    (Name: "Current + Best (elitiste)",       Match: BuildMatch(MatchingKind.Current, MatchingKind.Best)),
};

var traces = new List<List<double>>();
var finales = new List<(string nom, double fx)>();
foreach (var config in matchConfigs)
{
    var trace = new List<double>();
    var obj = RunWithMetaHeuristic(config.Match, config.Name, trace: trace);
    traces.Add(trace);
    finales.Add((config.Name, obj));
    Console.WriteLine(string.Format("{0,-30} {1,-15:F4} {2,-15}",
        config.Name, obj, config.Name.Split('+')[1].Trim()));
    Console.WriteLine(string.Format("    trace f(x) : gen10={0,8:F3}  gen25={1,8:F3}  gen50={2,8:F3}   x=[{3}]",
        trace[9], trace[24], trace[49], string.Join(", ", LastBestX.Select(v => v.ToString("F3")))));
}

Console.WriteLine("======================================================================");
var t10 = traces.Select(t => t[9]).ToArray();
Console.WriteLine("Diagnostic de branchement (seed=42 pour les trois) -- f(x) a la 10e generation : "
    + string.Join(" / ", t10.Select(v => v.ToString("F3"))));
bool divergent = t10.Distinct().Count() > 1;
Console.WriteLine(divergent
    ? "Trajectoires divergentes des la 10e generation : le match modifie bien les tirages."
    : "Trajectoires identiques a la 10e generation : a seed egal le match ne modifie pas les tirages -- branchement a diagnostiquer (review #17924).");
// Controle positif du banc (cf #17997) : la meilleure valeur FINALE depasse-t-elle le meilleur
// individu de la population INITIALE ? Sans ce controle, une egalite de f(x) entre
// configurations est ininterpretable -- elle peut venir d'un banc qui n'evolue pas du tout.
FastRandomRandomization.ResetSeed(42);
var qfDiag = new QuadraticFitness();
var adamDiag = new FloatingPointChromosome(
    new double[] { -10, -10, -10, -10 },
    new double[] {  10,  10,  10,  10 },
    new int[] { 64, 64, 64, 64 },
    new int[] { 4, 4, 4, 4 });
var popDiag = new MetaPopulation(50, 50, adamDiag);
popDiag.CreateInitialGeneration();   // ce tirage (50 chromosomes) est celui que le GA consomme juste apres le seed
var scoredDiag = popDiag.CurrentGeneration.Chromosomes
    .Select(c => (x: ((FloatingPointChromosome)c).ToFloatingPoints(), fx: 1.0 / qfDiag.Evaluate(c) - 1.0))
    .OrderBy(p => p.fx)
    .ToList();
var best0Diag = scoredDiag.First();
var meilleurFinal = finales.Min(f => f.fx);
Console.WriteLine($"Meilleur f(x) de la population INITIALE (seed 42, pop=50) : {best0Diag.fx:F4}");
Console.WriteLine($"Meilleur f(x) FINAL sur les trois configurations           : {meilleurFinal:F4}");
bool leBancProgresse = meilleurFinal < best0Diag.fx - 1e-9;
Console.WriteLine(leBancProgresse
    ? "  => des generations ont depasse le meilleur individu initial : le banc evolue."
    : "  => AUCUNE generation n'a depasse le meilleur individu initial : l'egalite des");
if (!leBancProgresse)
{
    Console.WriteLine("     configurations est un plancher de stagnation, pas une propriete du paysage.");
}
Console.WriteLine("Objectif optimal : f(x) = 0.0");
Comparaison des strategies de match (50 generations, population=50)
======================================================================
Configuration                  f(x)            Match picks    
----------------------------------------------------------------------
Current + Neighbor (adjacent)  0,0000          Neighbor (adjacent)
    trace f(x) : gen10=   0,209  gen25=   0,043  gen50=   0,000   x=[0,000, -0,000, 0,000, 0,000]
Current + Random (diversifie)  0,0000          Random (diversifie)
    trace f(x) : gen10=   0,308  gen25=   0,046  gen50=   0,000   x=[0,000, -0,000, 0,000, 0,000]
Current + Best (elitiste)      0,0000          Best (elitiste)
    trace f(x) : gen10=   2,303  gen25=   1,546  gen50=   0,000   x=[-0,000, 0,000, -0,000, -0,000]
======================================================================
Diagnostic de branchement (seed=42 pour les trois) -- f(x) a la 10e generation : 0,209 / 0,308 / 2,303
Trajectoires divergentes des la 10e generation : le match modifie bien les tirages.
Meilleur f(x) de la population INITIALE (seed 42, pop=50) : 21,9997
Meilleur f(x) FINAL sur les trois configurations           : 0,0000
  => des generations ont depasse le meilleur individu initial : le banc evolue.
Objectif optimal : f(x) = 0.0

Interprétation : Stratégie de match

Sortie obtenue : les trois stratégies atteignent f(x) = 0,0000, l’optimum de Sphere, et la trace par génération montre qu’elles y convergent par des chemins différents : à la 10e génération la meilleure valeur vaut 0,209 (Neighbor), 0,308 (Random) et 2,303 (Best), et les trois sont à 0,000 à la 50e. Le diagnostic de branchement imprimé par la cellule le confirme : « Trajectoires divergentes dès la 10e génération : le match modifie bien les tirages ».

Ce que cela établit (et ce que cela n’établit pas) : le match contrôle bien la trajectoire – trois règles d’appariement menées au même seed produisent trois suites de populations distinctes, donc MatchMetaHeuristic est effectivement branché sur le crossover. En revanche, sur Sphere (convexe, 4 dimensions), le choix de la règle ne change pas le résultat final : les trois convergent vers l’optimum au budget de 50 générations. L’égalité des f(x) finaux n’est donc pas un plancher de stagnation – c’est la conséquence normale d’un paysage assez facile pour que le moteur y arrive quelle que soit la règle d’appariement. C’est précisément pourquoi la section 5 rejoue la comparaison sur un paysage multimodal.

Stratégie Comportement Forces Limites
Current + Neighbor Appariement adjacent (proche du GA standard) Simple, déterministe dans l’ordre Diversité limitée
Current + Random Partenaire aléatoire Exploration maximale Peu de pression vers les meilleurs
Current + Best Toujours croiser avec le meilleur Intensification forte Risque de convergence prématurée

Points clés : 1. Le match contrôle qui croise avec qui – une dimension d’adaptation indépendante des probabilités 2. MatchMetaHeuristic encapsule un MatchPicker qui peut combiner plusieurs directives en pipeline 3. Sur Sphere les trois règles convergent vers l’optimum : un paysage convexe ne les départage pas, même quand il les fait diverger en chemin – la comparaison sur paysage multimodal fait l’objet de la section 5 4. Les picks Best et Worst sont mis en cache par génération (ParamScope.Generation | ParamScope.MetaHeuristic) pour éviter les recalculs

3. Primitives de contrôle de flux

Les primitives de contrôle de flux permettent de changer de comportement en cours d’évolution, en fonction du contexte. Elles heritent toutes de ScopedMetaHeuristic (interception par étape) et PhaseMetaHeuristicBase<TIndex> (dispatch par phase).

Hiérarchie d’heritage

MetaHeuristicBase
  -> CustomProbabilityMetaHeuristic (contrôle des probabilites)
    -> ContainerMetaHeuristic (delegue a une sous-métaheuristique)
      -> ScopedMetaHeuristic (interception par EvolutionStage)
        -> PhaseMetaHeuristicBase<TIndex> (dispatch par cle de phase)
          -> SwitchMetaHeuristic<TIndex> (switch generique)
            -> IfElseMetaHeuristic (switch booléen)
            -> SizeBasedMetaHeuristic (switch par plages)
              -> GenerationMetaHeuristic (switch par génération)
            -> StageSwitchMetaHeuristic (switch par étape d'évolution)
      -> MatchMetaHeuristic (appariement pour le crossover)
      -> DefaultMetaHeuristic (comportement GA standard)
      -> NoOpMetaHeuristic (neutre)

Principe commun : PhaseHeuristics

Toutes les primitives de dispatch stockent leurs sous-métaheuristiques dans un dictionnaire PhaseHeuristics<TKey, IMetaHeuristic>. La cle determine quelle sous-métaheuristique est active :

  • SwitchMetaHeuristic<int> : cle = entier (numéro de phase)
  • IfElseMetaHeuristic : cle = booléen (true/false)
  • StageSwitchMetaHeuristic : cle = EvolutionStage (Crossover, Mutation, Sélection, Reinsertion)
// Demonstration: SizeBasedMetaHeuristic
// Switches between two strategies based on the local individual index:
// Phase 0 (first 25 individuals): aggressive crossover (high probability)
// Phase 1 (remaining individuals): conservative crossover (low probability)

// Phase 0: aggressive crossover (p_c = 0.95)
var aggressiveMh = new DefaultMetaHeuristic();
aggressiveMh.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
aggressiveMh.ProbabilityConfig.Crossover.StaticProbability = 0.95f;

// Phase 1: conservative crossover (p_c = 0.30)
var conservativeMh = new DefaultMetaHeuristic();
conservativeMh.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
conservativeMh.ProbabilityConfig.Crossover.StaticProbability = 0.3f;

// Helper: build a SizeBased with DynamicParameter set (required for dispatch)
SizeBasedMetaHeuristic BuildSizeBased(int phaseSize, params IMetaHeuristic[] phaseHeuristics)
{
    var sb = new SizeBasedMetaHeuristic(phaseSize, phaseHeuristics);
    sb.DynamicParameter = new MetaHeuristicParameter<int>
    {
        Scope = ParamScope.None,
        Generator = (h, ctx) => ctx.LocalIndex
    };
    return sb;
}

Console.WriteLine("SizeBasedMetaHeuristic : deux zones de crossover");
Console.WriteLine("=================================================================");

// Discrimination inter-strategies sur N >= 4 runs independants (seed 42+run).
// Le banc devient un banc de mesure reelle : moyenne et ecart-type par strategie,
// pas seulement un point unique sur un seul seed.
const int N_RUNS_9 = 5;
var baselineResults = new List<double>(N_RUNS_9);
var sizeBasedResults = new List<double>(N_RUNS_9);
for (int run = 0; run < N_RUNS_9; run++)
{
    int runSeed = 42 + run;
    baselineResults.Add(RunWithMetaHeuristic(new DefaultMetaHeuristic(), "Baseline", seed: runSeed));
    var agg = new DefaultMetaHeuristic();
    agg.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
    agg.ProbabilityConfig.Crossover.StaticProbability = 0.95f;
    var cons = new DefaultMetaHeuristic();
    cons.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
    cons.ProbabilityConfig.Crossover.StaticProbability = 0.3f;
    sizeBasedResults.Add(RunWithMetaHeuristic(BuildSizeBased(25, agg, cons), "SizeBased", seed: runSeed));
}

double BaseMean = baselineResults.Average();
double BaseStd  = System.Math.Sqrt(baselineResults.Sum(r => (r - BaseMean) * (r - BaseMean)) / N_RUNS_9);
double SbMean   = sizeBasedResults.Average();
double SbStd    = System.Math.Sqrt(sizeBasedResults.Sum(r => (r - SbMean) * (r - SbMean)) / N_RUNS_9);

Console.WriteLine(string.Format("{0,-20} {1,-12}", "Configuration", "Valeur"));
Console.WriteLine("-------------------------------------------------");
Console.WriteLine(string.Format("{0,-20} {1,-12:F4}", "Default (baseline)", BaseMean));
Console.WriteLine(string.Format("{0,-20} {1,-12:F4}", "SizeBased(25/25)", SbMean));

Console.WriteLine("-------------------------------------------------");
Console.WriteLine(string.Format("  Default  moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", BaseMean, BaseStd, N_RUNS_9));
Console.WriteLine(string.Format("  SizeBased moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", SbMean, SbStd, N_RUNS_9));
Console.WriteLine("=================================================================");
Console.WriteLine("Objectif optimal : f(x) = 0.0");
SizeBasedMetaHeuristic : deux zones de crossover
=================================================================
Configuration        Valeur      
-------------------------------------------------
Default (baseline)   1,9269      
SizeBased(25/25)     7,6525      
-------------------------------------------------
  Default  moyenne = 1,9269 (ecart-type = 1,9932, N = 5)
  SizeBased moyenne = 7,6525 (ecart-type = 11,8058, N = 5)
=================================================================
Objectif optimal : f(x) = 0.0

Interpretation : SizeBasedMetaHeuristic

Sortie obtenue : La stratégie SizeBased divise la population en deux zones avec des probabilites de crossover différentes.

Aspect Description
Phase 0 (index 0-24) Crossover agressif (\(p_c = 0.95\)) : beaucoup de recombinaison
Phase 1 (index 25-49) Crossover conservateur (\(p_c = 0.30\)) : preservation des solutions
EnumeratedPhases Mappe un index lineaire vers une phase via la taille de chaque phase

Points cles : 1. SizeBasedMetaHeuristic herite de SwitchMetaHeuristic<int> et ajoute la logique de plages contigues 2. Le DynamicParameter calcule automatiquement l’index de phase a partir du contexte 3. L’index reboucle (modulo) si la population est plus grande que la somme des phases 4. Utile pour créer des sous-populations virtuelles avec des comportements différents au sein d’une même population

// Demonstration: GenerationMetaHeuristic
// Cycles through phases based on generation number:
//   Phase A (generations 1-15): exploration  -- high mutation probability
//   Phase B (generations 16-30): exploitation -- low mutation probability
//   Total cycle = 30 generations, wraps around if termination > 30

// Exploration phase: high mutation probability
var exploreMh = new DefaultMetaHeuristic();
exploreMh.ProbabilityConfig.Mutation.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
exploreMh.ProbabilityConfig.Mutation.StaticProbability = 0.5f;

// Exploitation phase: low mutation probability
var exploitMh = new DefaultMetaHeuristic();
exploitMh.ProbabilityConfig.Mutation.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
exploitMh.ProbabilityConfig.Mutation.StaticProbability = 0.05f;

Console.WriteLine("GenerationMetaHeuristic : exploration (gen 1-15) vs exploitation (gen 16-30)");
Console.WriteLine("=================================================================");

// Discrimination inter-strategies sur N >= 4 runs independants (seed 42+run).
// Pattern uniformise avec la cellule 9 ci-dessus.
const int N_RUNS_11 = 5;
var genResults = new List<double>(N_RUNS_11);
var defaultResults = new List<double>(N_RUNS_11);
for (int run = 0; run < N_RUNS_11; run++)
{
    int runSeed = 42 + run;
    genResults.Add(RunWithMetaHeuristic(
        new GenerationMetaHeuristic(15, exploreMh, exploitMh), "Gen",
        generations: 40, seed: runSeed));
    defaultResults.Add(RunWithMetaHeuristic(new DefaultMetaHeuristic(), "Default",
        generations: 40, seed: runSeed));
}

double DMean = defaultResults.Average();
double DStd  = System.Math.Sqrt(defaultResults.Sum(r => (r - DMean) * (r - DMean)) / N_RUNS_11);
double GMean = genResults.Average();
double GStd  = System.Math.Sqrt(genResults.Sum(r => (r - GMean) * (r - GMean)) / N_RUNS_11);

Console.WriteLine(string.Format("{0,-22} {1,-10}", "Config", "Valeur"));
Console.WriteLine("-----------------------------------------------------");
Console.WriteLine(string.Format("{0,-22} {1,-10:F4}", "Default (40 gen)", DMean));
Console.WriteLine(string.Format("{0,-22} {1,-10:F4}", "Gen(15+15 cycle)", GMean));

Console.WriteLine("-----------------------------------------------------");
Console.WriteLine(string.Format("  Default moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", DMean, DStd, N_RUNS_11));
Console.WriteLine(string.Format("  Gen     moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", GMean, GStd, N_RUNS_11));
Console.WriteLine("  Phase cycle      : 15 explore (p_m=0.5) + 15 exploit (p_m=0.05)");
Console.WriteLine("=================================================================");
Console.WriteLine("Objectif optimal : f(x) = 0.0");
GenerationMetaHeuristic : exploration (gen 1-15) vs exploitation (gen 16-30)
=================================================================
Config                 Valeur    
-----------------------------------------------------
Default (40 gen)       5,4777    
Gen(15+15 cycle)       1,4250    
-----------------------------------------------------
  Default moyenne = 5,4777 (ecart-type = 6,5479, N = 5)
  Gen     moyenne = 1,4250 (ecart-type = 1,4387, N = 5)
  Phase cycle      : 15 explore (p_m=0.5) + 15 exploit (p_m=0.05)
=================================================================
Objectif optimal : f(x) = 0.0

Interpretation : GenerationMetaHeuristic

Sortie obtenue : La stratégie par génération alterne entre exploration et exploitation.

Phase Générations Mutation (\(p_m\)) Objectif
Exploration 1-15 0.50 (elevee) Diversifier la population, eviter les minima locaux
Exploitation 16-30 0.05 (faible) Affiner les meilleures solutions

Points cles : 1. GenerationMetaHeuristic herite de SizeBasedMetaHeuristic et remplace DynamicParameter par un calcul base sur le numéro de génération 2. La formule (GenerationsNumber - 1) % TotalPhaseSize assure un cycle rebouclant : après la génération 30, la phase d’exploration recommence 3. Le cycle est utile pour les évolutions longues : exploration/exploitation alternent naturellement 4. La mise en cache a la porte ParamScope.Generation garantit que la même phase est utilisee pour tous les individus d’une même génération

// Demonstration: StageSwitchMetaHeuristic
// Applies different metaheuristics depending on the evolution stage:
//   Crossover stage: MatchMetaHeuristic with Best matching (elitist)
//   Mutation stage: DefaultMetaHeuristic with low mutation probability
//   Other stages (Selection, Reinsertion): DefaultMetaHeuristic (passthrough)

Console.WriteLine("StageSwitchMetaHeuristic : crossover elitiste + mutation conservatrice");
Console.WriteLine("=================================================================");

// Discrimination inter-strategies sur N >= 4 runs independants (seed 42+run).
// Pattern uniformise avec les cellules 9 et 11.
const int N_RUNS_13 = 5;
var stageResults = new List<double>(N_RUNS_13);
var plainDefault = new List<double>(N_RUNS_13);
for (int run = 0; run < N_RUNS_13; run++)
{
    int runSeed = 42 + run;
    var ss = new StageSwitchMetaHeuristic();
    // Crossover: elitist (Current + Best)
    ss.PhaseHeuristics[EvolutionStage.Crossover] = BuildMatch(MatchingKind.Current, MatchingKind.Best);

    // Mutation: conservative (p_m = 0.1)
    var mut = new DefaultMetaHeuristic();
    mut.ProbabilityConfig.Mutation.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
    mut.ProbabilityConfig.Mutation.StaticProbability = 0.1f;
    ss.PhaseHeuristics[EvolutionStage.Mutation] = mut;

    // Selection + Reinsertion: default passthrough
    ss.PhaseHeuristics[EvolutionStage.Selection] = new DefaultMetaHeuristic();
    ss.PhaseHeuristics[EvolutionStage.Reinsertion] = new DefaultMetaHeuristic();

    stageResults.Add(RunWithMetaHeuristic(ss, "StageSwitch", seed: runSeed));
    plainDefault.Add(RunWithMetaHeuristic(new DefaultMetaHeuristic(), "Default", seed: runSeed));
}

double DMean13 = plainDefault.Average();
double DStd13  = System.Math.Sqrt(plainDefault.Sum(r => (r - DMean13) * (r - DMean13)) / N_RUNS_13);
double SMean   = stageResults.Average();
double SStd    = System.Math.Sqrt(stageResults.Sum(r => (r - SMean) * (r - SMean)) / N_RUNS_13);

Console.WriteLine(string.Format("{0,-22} {1,-10}", "Config", "Valeur"));
Console.WriteLine("-----------------------------------------------------");
Console.WriteLine(string.Format("{0,-22} {1,-10:F4}", "Default", DMean13));
Console.WriteLine(string.Format("{0,-22} {1,-10:F4}", "StageSwitch(CX=Best)", SMean));

Console.WriteLine("-----------------------------------------------------");
Console.WriteLine(string.Format("  Default     moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", DMean13, DStd13, N_RUNS_13));
Console.WriteLine(string.Format("  StageSwitch moyenne = {0:F4} (ecart-type = {1:F4}, N = {2})", SMean, SStd, N_RUNS_13));
Console.WriteLine("=================================================================");
Console.WriteLine("Note : StageSwitch dispatche par EvolutionStage (Crossover/Mutation/Selection/Reinsertion)");
Console.WriteLine("       Le DynamicParameter lit ctx.CurrentStage avec ParamScope.None (pas de cache)");
StageSwitchMetaHeuristic : crossover elitiste + mutation conservatrice
=================================================================
Config                 Valeur    
-----------------------------------------------------
Default                1,9269    
StageSwitch(CX=Best)   0,1904    
-----------------------------------------------------
  Default     moyenne = 1,9269 (ecart-type = 1,9932, N = 5)
  StageSwitch moyenne = 0,1904 (ecart-type = 0,2479, N = 5)
=================================================================
Note : StageSwitch dispatche par EvolutionStage (Crossover/Mutation/Selection/Reinsertion)
       Le DynamicParameter lit ctx.CurrentStage avec ParamScope.None (pas de cache)

Interpretation : StageSwitchMetaHeuristic

Sortie obtenue : Le StageSwitch combine un crossover elitiste (match avec le meilleur) et une mutation conservatrice.

Étape Métaheuristique Comportement
Sélection DefaultMetaHeuristic Sélection par tournoi standard
Crossover MatchMetaHeuristic(Current+Best) Croise toujours avec le meilleur chromosome
Mutation DefaultMetaHeuristic (\(p_m = 0.1\)) Mutation faible pour ne pas detruire les bonnes solutions
Reinsertion DefaultMetaHeuristic Elitisme standard

Points cles : 1. StageSwitchMetaHeuristic utilise ctx.CurrentStage comme cle de dispatch – le moteur renseigne cette propriete a chaque étape 2. Le DynamicParameter a ParamScope.None (pas de cache) car l’étape change a chaque appel au sein d’une même génération 3. Cette primitive est la plus granulaire : elle permet de specialiser independamment chaque étape de la boucle d’évolution 4. Le crossover elitiste (Best) couplie a une mutation faible favorise une convergence rapide mais peut reduire la diversite

4. Composition en action

La puissance de MetaGeneticSharp reside dans la composition libre des primitives. Nous allons construire une stratégie multi-niveaux qui combine :

  1. Niveau génération : alterner exploration (gen 1-20) et exploitation (gen 21-40)
  2. Niveau étape : pendant l’exploration, utiliser un crossover diversifie ; pendant l’exploitation, utiliser un crossover elitiste
  3. Niveau mutation : probabilité adaptative selon la phase

Architecture de la stratégie composee

GenerationMetaHeuristic(20, [explorePhase, exploitPhase])
  |
  +-- explorePhase (gen 1-20):
  |     StageSwitchMetaHeuristic
  |       Crossover -> MatchMetaHeuristic(Current + Random)  [diversifie]
  |       Mutation  -> DefaultMetaHeuristic (p_m = 0.4)      [agressive]
  |
  +-- exploitPhase (gen 21-40):
        StageSwitchMetaHeuristic
          Crossover -> MatchMetaHeuristic(Current + Best)    [elitiste]
          Mutation  -> DefaultMetaHeuristic (p_m = 0.05)    [conservatrice]
// Composed strategy: GenerationMetaHeuristic containing StageSwitchMetaHeuristic
// containing MatchMetaHeuristic

IMetaHeuristic BuildExplorePhase()
{
    var stageSwitch = new StageSwitchMetaHeuristic();
    // Crossover: diversified (Current + Random)
    stageSwitch.PhaseHeuristics[EvolutionStage.Crossover] = BuildMatch(MatchingKind.Current, MatchingKind.Random);

    // Mutation: aggressive (p_m = 0.4)
    var mutExplore = new DefaultMetaHeuristic();
    mutExplore.ProbabilityConfig.Mutation.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
    mutExplore.ProbabilityConfig.Mutation.StaticProbability = 0.4f;
    stageSwitch.PhaseHeuristics[EvolutionStage.Mutation] = mutExplore;

    stageSwitch.PhaseHeuristics[EvolutionStage.Selection] = new DefaultMetaHeuristic();
    stageSwitch.PhaseHeuristics[EvolutionStage.Reinsertion] = new DefaultMetaHeuristic();
    return stageSwitch;
}

IMetaHeuristic BuildExploitPhase()
{
    var stageSwitch = new StageSwitchMetaHeuristic();
    // Crossover: elitist (Current + Best)
    stageSwitch.PhaseHeuristics[EvolutionStage.Crossover] = BuildMatch(MatchingKind.Current, MatchingKind.Best);

    // Mutation: conservative (p_m = 0.05)
    var mutExploit = new DefaultMetaHeuristic();
    mutExploit.ProbabilityConfig.Mutation.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
    mutExploit.ProbabilityConfig.Mutation.StaticProbability = 0.05f;
    stageSwitch.PhaseHeuristics[EvolutionStage.Mutation] = mutExploit;

    stageSwitch.PhaseHeuristics[EvolutionStage.Selection] = new DefaultMetaHeuristic();
    stageSwitch.PhaseHeuristics[EvolutionStage.Reinsertion] = new DefaultMetaHeuristic();
    return stageSwitch;
}

Console.WriteLine("Strategie composee : Generation + StageSwitch + Match");
Console.WriteLine("=================================================================");
Console.WriteLine("Explore (gen 1-20)  : CX=Current+Random, p_m=0.4");
Console.WriteLine("Exploit (gen 21-40) : CX=Current+Best,   p_m=0.05");
Console.WriteLine("-----------------------------------------------------------------");

var composedResults = new List<double>();
var simpleResults = new List<double>();

for (int run = 0; run < 5; run++)
{
    composedResults.Add(RunWithMetaHeuristic(
        new GenerationMetaHeuristic(20, BuildExplorePhase(), BuildExploitPhase()),
        "Composed", generations: 40, seed: 42 + run));
    simpleResults.Add(RunWithMetaHeuristic(new DefaultMetaHeuristic(), "Default", generations: 40, seed: 42 + run));
}

Console.WriteLine("Config                   Run1        Run2        Run3        Run4        Run5");
Console.WriteLine("-----------------------------------------------------------------");

Console.Write("Default (40 gen)        ");
foreach (var r in simpleResults) Console.Write(string.Format(" {0,-10:F4}", r));
Console.WriteLine();

Console.Write("Composed(20+20)         ");
foreach (var r in composedResults) Console.Write(string.Format(" {0,-10:F4}", r));
Console.WriteLine();

Console.WriteLine("-----------------------------------------------------------------");
Console.WriteLine(string.Format("  Default moyenne   : {0:F4}", simpleResults.Average()));
Console.WriteLine(string.Format("  Composed moyenne  : {0:F4}", composedResults.Average()));
Console.WriteLine(string.Format("  Amelioration      : {0:F1}%",
    (simpleResults.Average() - composedResults.Average()) / simpleResults.Average() * 100));
Console.WriteLine("=================================================================");
Console.WriteLine("La strategie composee combine 3 niveaux de primitives :");
Console.WriteLine("  1. GenerationMetaHeuristic -> exploration/exploitation par generation");
Console.WriteLine("  2. StageSwitchMetaHeuristic -> comportement different par etape (CX vs M)");
Console.WriteLine("  3. MatchMetaHeuristic -> selection des partenaires de crossover");
Strategie composee : Generation + StageSwitch + Match
=================================================================
Explore (gen 1-20)  : CX=Current+Random, p_m=0.4
Exploit (gen 21-40) : CX=Current+Best,   p_m=0.05
-----------------------------------------------------------------
Config                   Run1        Run2        Run3        Run4        Run5
-----------------------------------------------------------------
Default (40 gen)         4,9620     4,4870     0,0057     17,8785    0,0553    
Composed(20+20)          0,0001     0,6942     0,0002     2,8009     0,0002    
-----------------------------------------------------------------
  Default moyenne   : 5,4777
  Composed moyenne  : 0,6991
  Amelioration      : 87,2%
=================================================================
La strategie composee combine 3 niveaux de primitives :
  1. GenerationMetaHeuristic -> exploration/exploitation par generation
  2. StageSwitchMetaHeuristic -> comportement different par etape (CX vs M)
  3. MatchMetaHeuristic -> selection des partenaires de crossover

Interprétation : Stratégie composée

Sortie obtenue : les 5 runs (seeds 42 à 46) produisent des valeurs distinctes et reproductibles, et la stratégie composée devance la baseline sur chacun des 5 runs :

Run Default (40 gen) Composée (20+20)
1 4,9620 0,0001
2 4,4870 0,6942
3 0,0057 0,0002
4 17,8785 2,8009
5 0,0553 0,0002
moyenne 5,4777 0,6991

Soit 87,2 % d’amélioration de la moyenne. La composition atteint la quasi-optimalité (<= 0,0002) sur 3 runs sur 5, alors que la baseline n’en atteint aucun (son minimum est 0,0057).

Ce que cela établit, et sa limite : c’est le premier écart net de ce notebook entre une stratégie composée et sa baseline. Il porte sur 5 runs : l’écart des moyennes (5,48 contre 0,70) reste inférieur à l’étendue inter-runs de la baseline (0,0057 à 17,88), mais cinq tirages n’établissent pas une significativité statistique – le dépôt exige ailleurs un test de Diebold-Mariano sur des séries longues. Le résultat se lit donc comme un indice fort et reproductible, pas comme une preuve de supériorité générale.

Note historique : les versions précédentes de cet output affichaient « amélioration 0,0 % » avec des moyennes identiques, et attribuaient à juste titre ce plat au banc. La cause est désormais identifiée et corrigée (issue #17997) : new OnePointCrossover() vaut OnePointCrossover(0) et fige la coupe après le bit 0, new UniformMutation() vaut UniformMutation(false) et ne rend qu’un seul bit mutable pour toute la durée de vie de l’opérateur – les enfants du crossover étaient des clones phénotypiques de leurs parents.

Niveau Primitive Paramètres Effet
Génération GenerationMetaHeuristic(20, ...) Cycle de 40 générations Alterne exploration et exploitation
Étape StageSwitchMetaHeuristic Crossover vs Mutation Spécifique à chaque opérateur
Match MatchMetaHeuristic Random ou Best Diversifie ou intensifie le crossover

Points clés : 1. La composition est hiérarchique : chaque niveau délègue aux niveaux inférieurs 2. Le moteur appelle RegisterParameters() récursivement sur toute la hiérarchie, garantissant que les caches de chaque niveau sont initialisés 3. La stratégie composée est un objet C# ordinaire – elle peut être paramétrée, sérialisée, testée unitairement 4. La composition produit ici un avantage mesurable et reproductible sur Sphere à 40 générations (+87,2 % de moyenne sur 5 seeds) ; savoir si elle en produit un sur un paysage multimodal est l’objet de la section 5

Note technique : GenerationMetaHeuristic wrappe l’index avec (GenerationsNumber - 1) % TotalPhaseSize, donc le cycle se répète au-delà de 40 générations. Pour une évolution de 80 générations, on aurait deux cycles complets exploration -> exploitation.

5. Resume

Ce notebook a introduit les mécanismes de composition de MetaGeneticSharp :

Concept Rôle Paramètres cles
MatchMetaHeuristic Contrôle l’appariement des parents lors du crossover MatchingKind (Current, Random, Best, Worst, Neighbor, RouletteWheel)
MatchPicker Pipeline de directives de sélection MatchingSettings (kind, picks, caching)
SwitchMetaHeuristic<T> Dispatch generique par cle DynamicParameter, PhaseHeuristics
SizeBasedMetaHeuristic Dispatch par plages d’indices contigues EnumeratedPhases (tailles de phases)
GenerationMetaHeuristic Alternance par numéro de génération Taille de phase, sous-métaheuristiques
StageSwitchMetaHeuristic Dispatch par étape d’évolution EvolutionStage comme cle
Composition Combinaison hiérarchique des primitives Imbriquer les niveaux librement

Principes de conception

  1. Separation des preoccupations : chaque primitive contrôle un seul aspect (génération, étape, match)
  2. Composition ouverte : les primitives s’imbriquent librement, sans restriction d’arbre
  3. Cache par porte : les valeurs calculees sont mises en cache selon ParamScope (None, Generation, MetaHeuristic…)
  4. Rebouclage : les phases cyclent naturellement via modulo

Pour aller plus loin

  • Notebook suivant : MGS-3 Eukaryote – populations structurees (iles, sous-populations)
  • Référence : Sorensen, K. (2015). Metaheuristics – The Metaphor Exposed.
  • Code source : https://github.com/jsboige/MetaGeneticSharp

Exercice 1 : Adapter le match selon le numéro de génération

L’objectif est de créer une stratégie qui utilise un match Random (diversifie) pendant les 10 premières générations, puis un match Best (elitiste) pour les générations suivantes.

Enonce : Utilisez GenerationMetaHeuristic avec deux phases : une phase d’exploration contenant un MatchMetaHeuristic(Current + Random) et une phase d’exploitation contenant un MatchMetaHeuristic(Current + Best).

Indices : - GenerationMetaHeuristic(10, exploreMh, exploitMh) créé un cycle de 20 générations (10+10) - Pour les générations 11-20, le cycle reboucle sur la phase 0 – ce n’est pas ideal. Utilisez une seule phase d’exploration de 10 et une phase d’exploitation de 30 pour couvrir 40 générations - Utilisez le constructeur SizeBasedMetaHeuristic((int, IMetaHeuristic)[]) pour des phases de tailles différentes - new SizeBasedMetaHeuristic(new[] { (10, exploreMh), (30, exploitMh) }) créé 10+30 = 40

5. La composition se discriminant-elle ? Le test du paysage multimodal

Sur la fonction Sphere (convexe, unimodale), les stratégies des sections précédentes atteignent l’optimum global (0, 0, 0, 0) : les trois règles de match y convergent (section 2, f(x) = 0,0000) et la stratégie composée y arrive sur 3 runs sur 5 (section 4, meilleure valeur 0,0001). Le classement de la section 4 est donc établi – mais sur un paysage qui récompense la convergence : un crossover constant et une mutation faible y suffisent, et un hill-climber ou une simple descente s’en sortirait aussi bien. Un paysage convexe ne départage pas des stratégies dont la valeur ajoutée est de gérer la diversité. C’est le piège classique d’une démonstration dégénérée – montrer un moteur de recherche globale sur un paysage où la recherche globale n’apporte rien de mesurable.

Pour faire valoir la capacité distinctive de la composition (adapter la stratégie selon le contexte pour entretenir la diversité et s’échapper des optima locaux), il faut un paysage multimodal. La fonction de Rastrigin, benchmark canonique, est riche en optima locaux :

\[f(\mathbf{x}) = 10n + \sum_{i=1}^{n} \left[ x_i^2 - 10 \cos(2\pi x_i) \right], \quad x_i \in [-5.12, 5.12]\]

Minimisée en (0,...,0) = 0, mais parsemée d’une forêt d’optima locaux. Sur un tel paysage, une stratégie trop convergente (Default pur, crossover constant) a tendance à stagner dans un bassin local ; une stratégie diversifiée (alternance exploration/exploitation via Génération + StageSwitch) devrait mieux s’échapper des basins. C’est l’hypothèse que le test suivant confronte aux mesures – avec une leçon en retour : un avantage attendu n’est pas un avantage mesuré, et un avantage mesuré n’est pas encore un avantage établi (cf la lecture du résultat ci-dessous).

Comparons, sur Rastrigin 4D (5 runs chacune) : DefaultMetaHeuristic (baseline sans composition), SizeBasedMetaHeuristic (crossover agressif puis conservateur), et la stratégie composée Génération + StageSwitch + Match (réutilisant les helpers de la section 4).

// Section 5 : test du paysage multimodal (Rastrigin) -- la composition devient-elle visible ?
// Sur Sphere (convexe), a 50 generations les strategies des sections precedentes atteignent
// des f(x) disperses (~4 a ~42 selon les runs) qu'aucun ecart fiable ne separe : il faut un
// paysage qui discrimine. Sur Rastrigin (multimodal, riche en optima locaux), l'hypothese a
// tester : une strategy qui entretient la diversite s'echapperait mieux des basins locaux.
// f(x) = 10n + sum( x_i^2 - 10*cos(2*pi*x_i) ), x_i in [-5.12, 5.12].

public class RastriginFitness : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        var fc = (FloatingPointChromosome)chromosome;
        var g = fc.ToFloatingPoints();
        double s = 10.0 * g.Length;
        for (int i = 0; i < g.Length; i++) s += g[i] * g[i] - 10.0 * Math.Cos(2.0 * Math.PI * g[i]);
        return 1.0 / (1.0 + s);   // GeneticSharp maximise => on inverse (optimum f=0 -> fitness=1)
    }
}

// Variante Rastrigin du helper RunWithMetaHeuristic : borne [-5.12, 5.12]^4, renvoie f(x) moyen (plus bas = meilleur)
double RunRastrigin(IMetaHeuristic mh, List<double> perRun = null, int runs = 5, int generations = 50)
{
    var fx = new List<double>();
    for (int r = 0; r < runs; r++)
    {
// Codage 64 bits + 4 decimales (cf helper section 2) : le reseau entier rendait
// cos(2*pi*x)=1 partout et f_Rastrigin = sum(x_i^2) exactement -- le paysage
// multimodal disparaissait. Les 4 decimales le restaurent.
        var adam = new FloatingPointChromosome(
            new double[] { -5.12, -5.12, -5.12, -5.12 },
            new double[] {  5.12,  5.12,  5.12,  5.12 },
            new int[] { 64, 64, 64, 64 },
            new int[] { 4, 4, 4, 4 });
// Reproductibilite : seed DISTINCT PAR RUN (42 + r), review #17924. Un meme seed
// remis a chaque iteration rendrait les 5 runs identiques (cinq copies du meme
// tirage) et la moyenne sans objet ; 42 + r fait de chaque run un tirage different
// et reproductible. (cf #17863, #17864 pour MGS-05, #17919 pour MGS-01.)
        FastRandomRandomization.ResetSeed(42 + r);
        var pop = new MetaPopulation(60, 60, adam);
        var ga = new MetaGeneticAlgorithm(
            pop, new RastriginFitness(),
            // Operateurs NON degeneres (cf #17997), meme correctif que le helper de la section 2.
            new TournamentSelection(3), new UniformCrossover(), new FlipBitMutation(), mh);
        ga.Termination = new GenerationNumberTermination(generations);
        ga.CrossoverProbability = 0.75f;
        ga.MutationProbability = 0.2f;
        ga.Start();
        var v = (1.0 / ga.BestChromosome.Fitness.Value) - 1.0;   // fitness -> f(x)
        fx.Add(v);
        perRun?.Add(v);
    }
    return fx.Average();
}

Console.WriteLine("Rastrigin 4D (multimodal) -- meilleur f(x) moyen sur 5 runs (optimum = 0.0)");
Console.WriteLine(new string('=', 74));

// (a) Default sans composition
var runsDefault = new List<double>();
double fDefault = RunRastrigin(new DefaultMetaHeuristic(), perRun: runsDefault);

// (b) SizeBased : crossover aggressif (25 premiers individus) puis conservateur
var aggR = new DefaultMetaHeuristic();
aggR.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
aggR.ProbabilityConfig.Crossover.StaticProbability = 0.95f;
var consR = new DefaultMetaHeuristic();
consR.ProbabilityConfig.Crossover.Strategy = ProbabilityStrategy.TestProbability | ProbabilityStrategy.OverwriteProbability;
consR.ProbabilityConfig.Crossover.StaticProbability = 0.3f;
var sbR = new SizeBasedMetaHeuristic(25, aggR, consR);
sbR.DynamicParameter = new MetaHeuristicParameter<int> { Scope = ParamScope.None, Generator = (h, ctx) => ctx.LocalIndex };
var runsSize = new List<double>();
double fSize = RunRastrigin(sbR, perRun: runsSize);

// (c) Composee : Generation(explore/exploit) x StageSwitch x Match (reutilise BuildExplorePhase/BuildExploitPhase de la section 4)
var runsComposed = new List<double>();
double fComposed = RunRastrigin(new GenerationMetaHeuristic(20, BuildExplorePhase(), BuildExploitPhase()), perRun: runsComposed);

Console.WriteLine($"  Default (sans composition)   f(x) = {fDefault,7:F3}");
Console.WriteLine($"  SizeBased(25/25 crossover)   f(x) = {fSize,7:F3}");
Console.WriteLine($"  Composee (Gen+Stage+Match)   f(x) = {fComposed,7:F3}");
Console.WriteLine(new string('=', 74));
var classement = new[] { ("Default", fDefault), ("SizeBased", fSize), ("Composee", fComposed) }
    .OrderBy(p => p.Item2).ToArray();
int rangComposee = 1 + classement.Count(p => p.Item2 < fComposed);
Console.WriteLine($"Classement observe (meilleure d'abord) : {string.Join("  <  ", classement.Select(p => $"{p.Item1} {p.Item2:F1}"))}");
Console.WriteLine("Detail par run (seed 42+r, r=0..4) :");
Console.WriteLine("  Default   : " + string.Join("  ", runsDefault.Select(v => v.ToString("F3"))));
Console.WriteLine("  SizeBased : " + string.Join("  ", runsSize.Select(v => v.ToString("F3"))));
Console.WriteLine("  Composee  : " + string.Join("  ", runsComposed.Select(v => v.ToString("F3"))));
double ecartMax = new[] { fDefault, fSize, fComposed }.Max() - new[] { fDefault, fSize, fComposed }.Min();
Console.WriteLine($"Ecart max entre configurations (moyennes) : {ecartMax:F3}");
double ecartSD = fSize - fDefault;
double ecartCD = fComposed - fDefault;
Console.WriteLine($"Ecarts signes a Default (negatif = meilleur que Default) : SizeBased {ecartSD:+0.000;-0.000}   Composee {ecartCD:+0.000;-0.000}");
Console.WriteLine($"Composee au rang {rangComposee}/3.");
Rastrigin 4D (multimodal) -- meilleur f(x) moyen sur 5 runs (optimum = 0.0)
==========================================================================
  Default (sans composition)   f(x) =  17,218
  SizeBased(25/25 crossover)   f(x) =  15,576
  Composee (Gen+Stage+Match)   f(x) =  15,479
==========================================================================
Classement observe (meilleure d'abord) : Composee 15,5  <  SizeBased 15,6  <  Default 17,2
Detail par run (seed 42+r, r=0..4) :
  Default   : 22,711  12,208  16,328  10,565  24,280
  SizeBased : 12,774  14,772  13,494  17,955  18,885
  Composee  : 16,464  15,433  13,985  9,951  21,560
Ecart max entre configurations (moyennes) : 1,740
Ecarts signes a Default (negatif = meilleur que Default) : SizeBased -1,643   Composee -1,740
Composee au rang 1/3.

Lecture du résultat : ce que le test établit (et ce qu’il ne dit pas)

Ce que le run semé montre : les cinq runs (seeds 42+r) donnent des valeurs distinctes et reproductibles, et avec 4 décimales par gène le paysage Rastrigin est réellement multimodal (sur le codage entier d’origine, cos(2pix) = 1 partout et Rastrigin se réduisait exactement à Sphere). Les trois stratégies se classent cette fois :

Stratégie moyenne (5 runs) détail par run
Composée (Gen+Stage+Match) 15,479 16,464 / 15,433 / 13,985 / 9,951 / 21,560
SizeBased(25/25) 15,576 12,774 / 14,772 / 13,494 / 17,955 / 18,885
Default 17,218 22,711 / 12,208 / 16,328 / 10,565 / 24,280

La Composée est au rang 1 sur 3, conformément à l’hypothèse de la section 5.

Ce que ce classement ne dit pas : l’écart entre les trois moyennes (1,740) est plus petit que la dispersion d’une seule configuration d’un run à l’autre – la Default va de 10,565 à 24,280, soit 13,7 d’amplitude. Le banc discrimine désormais, mais à ce budget et avec 5 runs l’ordre observé reste dans le bruit : il ne permet pas de conclure que la composition est supérieure sur Rastrigin, seulement qu’elle n’y est pas désavantagée. Trancher exigerait davantage de runs et un test de significativité, pas un classement de moyennes.

Ce que le notebook établit : le mécanisme de composition fonctionne – les trois niveaux (génération -> étape -> match) s’enchaînent, s’exécutent sans erreur et produisent un GA complet sur deux paysages différents – et le banc est désormais capable de mesurer : seeds distincts par run, détail par run imprimé, diagnostic de branchement automatique, et deux défauts moteur corrigés (le codage entier qui effacait le paysage multimodal, et les opérateurs dégénérés qui clonaient les enfants).

Ce qu’il ne dit pas : si la composition est supérieure sur Rastrigin au-delà du bruit de 5 runs.

Piège pédagogique évacué : les versions précédentes de cette cellule ont affirmé successivement que la Composée « échappe mieux aux optima locaux » alors que leurs propres chiffres la plaçaient dernière, puis que « le paysage ne discrimine pas » alors que c’était le banc. Un récit plausible ne remplace pas la mesure – et la mesure, ici, a d’abord renvoyé au moteur (issue #17997).

// Exercice 1 : Adapter le match selon le numero de generation
// TODO: Creez une strategie GenerationMetaHeuristic qui utilise
//       - Phase explore (10 gen) : MatchMetaHeuristic(Current + Random)
//       - Phase exploit (30 gen) : MatchMetaHeuristic(Current + Best)
// Indice: GenerationMetaHeuristic herite de SizeBasedMetaHeuristic
// Indice: new SizeBasedMetaHeuristic(new[] { (10, exploreMh), (30, exploitMh) })

// Etape 1 : Definir la phase d'exploration
// var exploreMh = ... (MatchMetaHeuristic avec Current + Random)

// Etape 2 : Definir la phase d'exploitation
// var exploitMh = ... (MatchMetaHeuristic avec Current + Best)

// Etape 3 : Composez avec SizeBasedMetaHeuristic pour des phases asymetriques
// var strategy = new SizeBasedMetaHeuristic(new[] { (10, exploreMh), (30, exploitMh) });

// Etape 4 : Executez et comparez avec DefaultMetaHeuristic
// var result = RunWithMetaHeuristic(strategy, "GenMatch", generations: 40);

object result = null; // TODO etudiant : lancer la strategie et afficher le resultat
Console.WriteLine("Exercice a completer : Match adaptatif par generation");
Exercice a completer : Match adaptatif par generation

Exercice 2 : Combiner SizeBased et Match pour une stratégie hybride

L’objectif est de créer une stratégie qui traite differemment les premiers individus de la population (index 0-19) et les suivants (index 20-49).

Enonce : Utilisez SizeBasedMetaHeuristic(20, ...) avec deux sous-métaheuristiques : - Zone 1 (index 0-19) : MatchMetaHeuristic(Current + Best) pour intensifier - Zone 2 (index 20-49) : MatchMetaHeuristic(Current + Random) pour diversifier

Indices : - SizeBasedMetaHeuristic(20, zone1Mh, zone2Mh) divise en phases de 20 chacune - Pour une population de 50, les index 40-49 rebouclent sur la zone 1 (modulo 40) - Ajustez la taille de phase si vous voulez couvrir exactement 50 : SizeBasedMetaHeuristic(new[] { (20, zone1), (30, zone2) }) - Observez comment les deux zones interagissent dans la population globale

// Exercice 2 : Combiner SizeBased et Match pour une strategie hybride
// TODO: Creez une SizeBasedMetaHeuristic avec deux zones:
//       - Zone 1 (index 0-19) : Match(Current + Best) -- intensification
//       - Zone 2 (index 20-49) : Match(Current + Random) -- diversification
// Indice: new SizeBasedMetaHeuristic(new[] { (20, zone1Mh), (30, zone2Mh) })

// Etape 1 : Definir la zone d'intensification
// var zone1Mh = ... (MatchMetaHeuristic avec Current + Best)

// Etape 2 : Definir la zone de diversification
// var zone2Mh = ... (MatchMetaHeuristic avec Current + Random)

// Etape 3 : Composez avec SizeBasedMetaHeuristic
// var strategy = new SizeBasedMetaHeuristic(new[] { (20, zone1Mh), (30, zone2Mh) });

// Etape 4 : Executez et comparez
// var result = RunWithMetaHeuristic(strategy, "Hybrid", popSize: 50, generations: 50);

object result = null; // TODO etudiant : lancer la strategie et afficher le resultat
Console.WriteLine("Exercice a completer : SizeBased + Match hybride");
Exercice a completer : SizeBased + Match hybride

Exercice 3 : Stratégie multi-phases avec Génération + StageSwitch

L’objectif est de créer une stratégie en trois phases avec un comportement différent pour le crossover et la mutation a chaque phase.

Enonce : Construisez une stratégie avec trois phases de 15 générations chacune : - Phase 1 (gen 1-15) – Exploration : crossover diversifie (Random), mutation agressive (\(p_m = 0.5\)) - Phase 2 (gen 16-30) – Equilibrage : crossover par tour de roulette (RouletteWheel), mutation moderee (\(p_m = 0.2\)) - Phase 3 (gen 31-45) – Exploitation : crossover elitiste (Best), mutation conservatrice (\(p_m = 0.02\))

Indices : - Utilisez GenerationMetaHeuristic(15, phase1, phase2, phase3) pour un cycle de 45 générations - Chaque phase est un StageSwitchMetaHeuristic avec un MatchMetaHeuristic différent pour le crossover - MatchingKind.RouletteWheel utilise la sélection proportionnelle au fitness pour choisir le partenaire - Executez avec 45 générations pour couvrir exactement un cycle - Comparez avec la stratégie composee de la section 4 (qui n’a que 2 phases)

// Exercice 3 : Strategie multi-phases avec Generation + StageSwitch
// TODO: Construisez 3 phases de 15 generations chacune
// Indice: GenerationMetaHeuristic(15, phase1, phase2, phase3)
// Indice: chaque phase = StageSwitchMetaHeuristic avec Match + mutation custom

// Etape 1 : Phase exploration (gen 1-15)
//   Crossover: MatchMetaHeuristic(Current + Random)
//   Mutation: p_m = 0.5 (agressive)
// var phase1 = ... ;

// Etape 2 : Phase equilibrage (gen 16-30)
//   Crossover: MatchMetaHeuristic(Current + RouletteWheel)
//   Mutation: p_m = 0.2 (moderee)
// var phase2 = ... ;

// Etape 3 : Phase exploitation (gen 31-45)
//   Crossover: MatchMetaHeuristic(Current + Best)
//   Mutation: p_m = 0.02 (conservatrice)
// var phase3 = ... ;

// Etape 4 : Composez et executez
// var strategy = new GenerationMetaHeuristic(15, phase1, phase2, phase3);
// var result = RunWithMetaHeuristic(strategy, "ThreePhase", generations: 45);

object result = null; // TODO etudiant : lancer la strategie et afficher le resultat
Console.WriteLine("Exercice a completer : Strategie trois phases (Generation + StageSwitch)");
Exercice a completer : Strategie trois phases (Generation + StageSwitch)

Navigation : Index | << MGS-1 Introduction | MGS-3 Eukaryote >>

Retour au sommet