MGS-1 : Introduction a MetaGeneticSharp et au moteur autonome

Navigation : Index | MGS-2 Composition >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Comprendre la these “primitives vs bestiaire” (Sorensen 2015) et pourquoi les métaheuristiques doivent etre composables 2. Utiliser le moteur autonome MetaGeneticAlgorithm pour executer un algorithme génétique sans patcher GeneticSharp 3. Comparer l’impact des probabilites de crossover et mutation sur la convergence 4. Etendre le moteur en implementant votre propre IMetaHeuristic

Prerequis

• Notions de base en algorithmes génétiques (sélection, crossover, mutation)
• C# .NET 9.0 et .NET Interactive
• GeneticSharp 3.1.4-9 (upstream master 4406ad7, charge depuis les DLL du submodule)

Duree estimee : 45 minutes

1. Pourquoi MetaGeneticSharp ?

La these “primitives vs bestiaire”

Dans un article influent de 2015, Kenneth Sorensen (Metaheuristics – The Metaphor Exposed) denonce la proliferation de “nouvelles” métaheuristiques inspirees de metaphores biologiques (colonies de fourmis, essaims d’abeilles, loups gris…). Selon lui, la plupart de ces algorithmes ne sont que des recombinaisons d’un petit nombre de primitifs fondamentaux : sélection, crossover, mutation, remplacement – habilles d’un recit metaphorique differant.

MetaGeneticSharp adopte cette philosophie. Plutot que d’ajouter un N-ieme monolithe a la bibliotheque GeneticSharp, il expose chaque opération d’evolution comme un primitif composable via l’interface IMetaHeuristic. L’utilisateur combine ces primitifs pour construire des stratégies d’evolution sur mesure, sans modifier le code source amont.

Architecture en 3 couches

+----------------------------------------------+
|  Votre métaheuristique composee              |
|  (DefaultMetaHeuristic, Island, Match, ...)  |
+----------------------------------------------+
|  MetaGeneticSharp Engine                     |
|  MetaGeneticAlgorithm + IMetaHeuristic       |
|  MetaPopulation (pas de tri implicite)       |
|  FitnessBasedElitistReinsertion              |
+----------------------------------------------+
|  GeneticSharp 3.1.4-9 (amont, non modifie)   |
|  Chromosomes, Crossover, Mutation, Sélection |
+----------------------------------------------+

Couche	Rôle	Mutable ?
GeneticSharp amont	Types de base (chromosomes, opérateurs)	Non
MGS Engine	Boucle d’evolution autonome, pas de tri implicite	Non
Métaheuristique	Logique composable qui intercepte chaque étape	Oui

Le principe cle : la métaheuristique intercepte chaque étape de l’evolution (sélection, crossover, mutation, reinsertion) et peut modifier, remplacer ou composer le comportement de l’opérateur correspondant. Le moteur lui-même reste generique et stable.

// Wiring: load MetaGeneticSharp + GeneticSharp DLLs from submodule build
// Build prerequisite: dotnet build from the in-repo submodule MyIA.AI.Notebooks/Search/MetaGeneticSharp
// Requires: git submodule update --init GeneticSharp (nested submodule)
#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($"  MetaGeneticAlgorithm : {typeof(MetaGeneticAlgorithm).Name}");
Console.WriteLine($"  DefaultMetaHeuristic : {typeof(DefaultMetaHeuristic).Name}");
Console.WriteLine($"  NoOpMetaHeuristic    : {typeof(NoOpMetaHeuristic).Name}");
Console.WriteLine($"  MetaPopulation       : {typeof(MetaPopulation).Name}");

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

MetaGeneticSharp + GeneticSharp charges avec succes.
  MetaGeneticAlgorithm : MetaGeneticAlgorithm
  DefaultMetaHeuristic : DefaultMetaHeuristic
  NoOpMetaHeuristic    : NoOpMetaHeuristic
  MetaPopulation       : MetaPopulation

2. Architecture du moteur autonome

MetaGeneticAlgorithm – un GA sans patch amont

Le moteur MetaGeneticAlgorithm implemente IGeneticAlgorithm de GeneticSharp, mais avec trois différences majeures par rapport au GeneticAlgorithm standard :

1. Chaque étape est routee vers la métaheuristique : sélection, crossover, mutation et reinsertion passent par IMetaHeuristic, pas directement par les opérateurs.
2. L’evaluation du fitness est limitee a la descendance : seuls les chromosomes sans fitness sont evalues (pas de re-evaluation inutile des parents).
3. Pas de tri implicite par fitness : MetaPopulation preserve l’ordre des chromosomes. L’elitisme est la responsabilite explicite de la reinsertion (FitnessBasedElitistReinsertion par defaut).

L’interface IMetaHeuristic

public interface IMetaHeuristic
{
    IEvolutionContext GetContext(IGeneticAlgorithm ga, IPopulation pop);
    IList<IChromosome> SelectParentPopulation(IEvolutionContext ctx, ISelection sel);
    IList<IChromosome> MatchParentsAndCross(IEvolutionContext ctx, ICrossover cx, float prob, IList<IChromosome> parents);
    void MutateChromosome(IEvolutionContext ctx, IMutation mut, float prob, IList<IChromosome> offspring);
    IList<IChromosome> Reinsert(IEvolutionContext ctx, IReinsertion reins, IList<IChromosome> offspring, IList<IChromosome> parents);
}

Chaque méthode correspond a une étape de la boucle d’evolution. La métaheuristique peut : - Deleguer a l’opérateur standard (comportement par defaut) - Modifier les probabilites ou les individus selectionnes - Combiner plusieurs sous-métaheuristiques (composition) - Court-circuiter une étape (par exemple, sauter le crossover)

Concepts cles

Concept	Description
DefaultMetaHeuristic	Reproduit le comportement standard d’un GA (appariement adjacent, probabilite, mutation par index)
NoOpMetaHeuristic	Neutre : passe les parents inchanges, pas de crossover ni mutation
MetaPopulation	Population sans tri implicite, les métaheuristiques adressent les individus par index stable
FitnessBasedElitistReinsertion	Garde les meilleurs chromosomes (parents+descendance) – elitisme explicite
EvolutionContext	Contexte d’evolution partage entre les étapes, contient index, stage, paramètres caches

3. Premier exemple : minimisation de Rastrigin (paysage multimodal)

Nous allons configurer un algorithme génétique avec MetaGeneticAlgorithm pour minimiser la fonction de Rastrigin : \(f(x) = 10n + \sum_{i=1}^{n} \left( x_i^2 - 10\cos(2\pi x_i) \right)\). Contrairement a la Sphere (convexe, optimum trivial a l’origine), Rastrigin est multimodale : parsemee d’optima locaux (un par valeur entiere), elle oblige le GA a explorer et a echapper aux pieges. C’est précisément ce qui rend le crossover et la métaheuristique discriminants – la ou la Sphere laissait toutes les configurations converger vers 0.

Configuration : - Chromosome : FloatingPointChromosome (genes dans \([-10, 10]\)) - Sélection : TournamentSelection (taille 3) - Crossover : OnePointCrossover - Mutation : UniformMutation (probabilite 0.1) - Métaheuristique : DefaultMetaHeuristic (comportement standard) - Terminaison : 50 generations

// Setup: fitness = fonction de Rastrigin (multimodale, nombreux optima locaux)
// f(x) = 10*n + sum( x_i^2 - 10*cos(2*pi*x_i) ) ; minimum global 0 a l'origine,
// mais parsemee d'optima locaux (un par valeur entiere). Contrairement a la Sphere
// (convexe, optimum trivial), le GA doit ici echapper aux pieges locaux -- c'est
// ce qui rend le crossover et le choix de metaheuristique pertinents.
public class RastriginFitness : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        var fc = (FloatingPointChromosome)chromosome;
        var genes = fc.ToFloatingPoints();
        int n = genes.Length;
        double r = 10.0 * n;
        foreach (var g in genes) r += g * g - 10.0 * Math.Cos(2.0 * Math.PI * g);
        // Rastrigin est a minimiser ; GeneticSharp maximise, on inverse donc (1/(1+f))
        return 1.0 / (1.0 + r);
    }
}

Console.WriteLine("RastriginFitness definie : minimise f(x) = 10n + sum( x_i^2 - 10*cos(2*pi*x_i) )  [multimodale]");

RastriginFitness definie : minimise f(x) = 10n + sum( x_i^2 - 10*cos(2*pi*x_i) )  [multimodale]

// Run MetaGeneticAlgorithm with DefaultMetaHeuristic on the Rastrigin function

// Chromosome: 4 genes, each in [-10, 10]
var adamChromosome = new FloatingPointChromosome(
    new double[] { -10, -10, -10, -10 },
    new double[] {  10,  10,  10,  10 },
    new int[] { 64, 64, 64, 64 },
    new int[] { 0, 0, 0, 0 });

// Population: MetaPopulation (no implicit fitness sort)
// 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.)
FastRandomRandomization.ResetSeed(42);
var population = new MetaPopulation(50, 50, adamChromosome);

// GA with DefaultMetaHeuristic
var ga = new MetaGeneticAlgorithm(
    population,
    new RastriginFitness(),
    new TournamentSelection(3),
    new OnePointCrossover(),
    new UniformMutation());

ga.Termination = new GenerationNumberTermination(50);
ga.CrossoverProbability = 0.75f;
ga.MutationProbability = 0.1f;

// Track best fitness per generation
var bestFitnessHistory = new List<double>();
ga.GenerationRan += (sender, e) =>
{
    bestFitnessHistory.Add(ga.BestChromosome.Fitness.Value);
};

// Run
Console.WriteLine("Execution de MetaGeneticAlgorithm (50 generations, DefaultMetaHeuristic)...");
ga.Start();

// Display results
var best = (FloatingPointChromosome)ga.BestChromosome;
var bestGenes = best.ToFloatingPoints();
var bestFitness = ga.BestChromosome.Fitness.Value;
// Convert back to the original objective value (Rastrigin)
var objectiveValue = (1.0 / bestFitness) - 1.0;

Console.WriteLine("  Meilleur chromosome : [" + string.Join(", ", bestGenes.Select(g => string.Format("{0:F4}", g))) + "]");
Console.WriteLine(string.Format("  Fitness (inverted)  : {0:F6}", bestFitness));
Console.WriteLine(string.Format("  Objectif Rastrigin f(x) : {0:F6}", objectiveValue));
Console.WriteLine(string.Format("  Generations          : {0}", ga.GenerationsNumber));
Console.WriteLine(string.Format("  Temps total          : {0:F0} ms", ga.TimeEvolving.TotalMilliseconds));

Execution de MetaGeneticAlgorithm (50 generations, DefaultMetaHeuristic)...
  Meilleur chromosome : [-3,0000, 1,0000, -1,0000, -4,0000]
  Fitness (inverted)  : 0,035714
  Objectif Rastrigin f(x) : 27,000000
  Generations          : 50
  Temps total          : 275 ms

Interpretation : Premier run avec DefaultMetaHeuristic

Sortie obtenue : L’algorithme converge vers un optimum local – un vecteur a coordonnees entieres, eloigne de l’optimum global \([0,0,0,0]\). C’est la signature d’un paysage multimodal : le GA s’est arrete dans un piege local.

Le banc est rendu reproductible par un seed unique (FastRandomRandomization.ResetSeed(42) avant la population, cf cellules [9] et [15]) : execution apres execution, le meme piege exact est atteint.

Aspect	Valeur	Signification
Meilleur chromosome	\([-3, 1, -1, -4]\)	Optimum local (piege)
Fitness	\(0{,}035714\)	Fitness bas : le GA n’a pas atteint l’optimum global
Objectif f(x)	\(27{,}000000\)	Piege local (objectif global : \(0\))
Generations	50	Terminaison atteinte

Points cles : 1. DefaultMetaHeuristic reproduit le comportement d’un GA standard : sélection par tournoi, crossover adjacent probabiliste, mutation par index 2. Le moteur evalue le fitness uniquement sur les descendants (offspring-scoped evaluation) 3. FitnessBasedElitistReinsertion assure l’elitisme en gardant les meilleurs parmi parents + descendance 4. Aucune modification de GeneticSharp amont n’a ete necessaire

4. Impact des probabilites de crossover

La probabilite de crossover (\(p_c\)) contrôle la frequence a laquelle deux parents echangent du materiel génétique. Une probabilite elevee favorise l’exploration (recombinaison de solutions), tandis qu’une probabilite basse preserve les solutions existantes.

Comparons trois valeurs de \(p_c\) : 0.3 (faible), 0.75 (defaut) et 0.95 (elevee). Pour chaque valeur, nous mesurons la convergence en repetant le run plusieurs fois.

// Compare crossover probability: 0.3 vs 0.75 vs 0.95
var crossoverProbs = new[] { 0.3f, 0.75f, 0.95f };
var resultsByProb = new Dictionary<float, List<double>>();

// Reproductibilite du banc : le moteur tire son alea de RandomizationProvider.Current,
// un FastRandomRandomization NON seede par defaut. On place le seed UNE SEULE fois
// ici, AVANT la boucle des pc, pour que chaque run successif reparte d'un etat
// interne different du RNG (sinon les 5 runs d'un meme pc sont identiques, cf
// review CONCERNS #17919 -- la variance mesuree etait nulle). L'execution du
// notebook complet reste reproductible d'un lancement a l'autre (meme seed 42).
FastRandomRandomization.ResetSeed(42);

foreach (var pc in crossoverProbs)
{
    var fitnesses = new List<double>();

    for (int run = 0; run < 5; run++)
    {
        var adam = new FloatingPointChromosome(
            new double[] { -10, -10, -10, -10 },
            new double[] {  10,  10,  10,  10 },
            new int[] { 64, 64, 64, 64 },
            new int[] { 0, 0, 0, 0 });

        var pop = new MetaPopulation(50, 50, adam);
        var runGa = new MetaGeneticAlgorithm(
            pop,
            new RastriginFitness(),
            new TournamentSelection(3),
            new OnePointCrossover(),
            new UniformMutation());

        runGa.Termination = new GenerationNumberTermination(50);
        runGa.CrossoverProbability = pc;
        runGa.MutationProbability = 0.1f;

        runGa.Start();
        var objVal = (1.0 / runGa.BestChromosome.Fitness.Value) - 1.0;
        fitnesses.Add(objVal);
    }

    resultsByProb[pc] = fitnesses;
}

// Display comparison table
Console.WriteLine("Comparaison des probabilites de crossover (5 runs, 50 generations)");
Console.WriteLine("======================================================================");
Console.WriteLine(string.Format("{0,-8} {1,-12} {2,-12} {3,-12} {4,-12}", "Pc", "Moyenne", "Min", "Max", "Ecart-type"));
Console.WriteLine("----------------------------------------------------------------------");

foreach (var pc in crossoverProbs)
{
    var vals = resultsByProb[pc];
    var mean = vals.Average();
    var min = vals.Min();
    var max = vals.Max();
    var std = Math.Sqrt(vals.Average(v => (v - mean) * (v - mean)));
    Console.WriteLine(string.Format("{0,-8} {1,-12:F6} {2,-12:F6} {3,-12:F6} {4,-12:F6}", pc, mean, min, max, std));
}

Console.WriteLine("======================================================================");
Console.WriteLine("Objectif optimal : f(x) = 0.0");

Comparaison des probabilites de crossover (5 runs, 50 generations)
======================================================================
Pc       Moyenne      Min          Max          Ecart-type  
----------------------------------------------------------------------
0,3      20,600000    7,000000     38,000000    12,043255   
0,75     22,000000    3,000000     40,000000    12,049896   
0,95     19,600000    11,000000    41,000000    11,620671   
======================================================================
Objectif optimal : f(x) = 0.0

Interpretation : Impact de la probabilite de crossover

Sortie obtenue : Les trois probabilites de crossover produisent des moyennes du meme ordre, avec un ecart-type eleve – sur Rastrigin, 5 runs ne suffisent pas a separer les \(p_c\).

Le banc est reproductible execution apres execution grace au seed place une seule fois avant la boucle des pc (cf cellule [9]) : les memes moyennes et ecarts-types sont retrouves au prochain lancement. A l’interieur d’un meme lancement, les 5 runs par pc different les uns des autres (variance non nulle), ce qui preserve l’argument statistique sur l’ordre des moyennes.

Probabilite pc	Moyenne f(x)	Min	Max	Ecart-type
0.3 (faible)	\(20{,}60\)	\(7{,}00\)	\(38{,}00\)	\(12{,}04\)
0.75 (defaut)	\(22{,}00\)	\(3{,}00\)	\(40{,}00\)	\(12{,}05\)
0.95 (elevee)	\(19{,}60\)	\(11{,}00\)	\(41{,}00\)	\(11{,}62\)

Points cles : 1. L’ordre des moyennes n’est pas significatif : avec 5 runs et \(\sigma \approx 12\), l’erreur standard \(\sigma/\sqrt{5} \approx 5{,}4\) est du meme ordre que les ecarts entre moyennes (\(\leq 2{,}4\)). L’ordre observe (\(0{,}95 < 0{,}3 < 0{,}75\)) peut s’inverser d’une serie de runs a l’autre (la variance est reelle, pas duee a un defaut de seed). Ne pas conclure sur un classement sans plus de runs (c’est la meme discipline que le multi-seed des experiences ML du depot) 2. Le resultat robuste est la variance elle-meme (\(\sigma \approx 12\) partout) : sur un paysage multimodal, l’initialisation determine dans quel bassin d’optimum local la population tombe – d’ou l’ecart-type eleve pour chaque \(p_c\) 3. Comparer honnetement des \(p_c\) sur Rastrigin exigerait plus de runs (ou un seed par-run) – le notebook assume l’alea et l’enseigne plutot que de le cacher 4. DefaultMetaHeuristic teste la probabilite pour chaque paire adjacente de parents (appariement séquentiel)

5. Suivi de la convergence par generation

Pour visualiser la dynamique de convergence, suivons le meilleur fitness a chaque generation. Nous utilisons l’événement GenerationRan pour collecter cette trace.

// Track convergence per generation with DefaultMetaHeuristic
var adam2 = new FloatingPointChromosome(
    new double[] { -10, -10, -10, -10 },
    new double[] {  10,  10,  10,  10 },
    new int[] { 64, 64, 64, 64 },
    new int[] { 0, 0, 0, 0 });

// 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.)
FastRandomRandomization.ResetSeed(42);
var pop2 = new MetaPopulation(50, 50, adam2);
var ga2 = new MetaGeneticAlgorithm(
    pop2,
    new RastriginFitness(),
    new TournamentSelection(3),
    new OnePointCrossover(),
    new UniformMutation());

ga2.Termination = new GenerationNumberTermination(30);
ga2.CrossoverProbability = 0.75f;
ga2.MutationProbability = 0.1f;

var trace = new List<(int Gen, double Objective)>();
ga2.GenerationRan += (sender, e) =>
{
    var obj = (1.0 / ga2.BestChromosome.Fitness.Value) - 1.0;
    trace.Add((ga2.GenerationsNumber, obj));
};

Console.WriteLine("Execution avec suivi de convergence (30 generations)...");
ga2.Start();

// Display convergence trace (every 5 generations)
Console.WriteLine();
Console.WriteLine(string.Format("{0,-8} {1,-20}", "Gen", "f(x) = Rastrigin"));
Console.WriteLine("------------------------------");
foreach (var (gen, obj) in trace.Where(t => t.Gen % 5 == 0 || t.Gen == 1))
{
    Console.WriteLine(string.Format("{0,-8} {1,-20:F6}", gen, obj));
}
Console.WriteLine(string.Format("{0,-8} {1,-20:F6}", ga2.GenerationsNumber, trace.Last().Objective));

Console.WriteLine();
Console.WriteLine(string.Format("Convergence finale : f(x) = {0:F6}", trace.Last().Objective));
Console.WriteLine(string.Format("Amelioration gen 1 -> {0} : {1:F1}x", ga2.GenerationsNumber, trace[0].Objective / trace.Last().Objective));

Execution avec suivi de convergence (30 generations)...

Gen      f(x) = Rastrigin    
------------------------------
1        27,000000           
5        27,000000           
10       27,000000           
15       27,000000           
20       27,000000           
25       27,000000           
30       27,000000           
30       27,000000           

Convergence finale : f(x) = 27,000000
Amelioration gen 1 -> 30 : 1,0x

Interpretation : Trace de convergence

Sortie obtenue : Le fitness s’ameliore rapidement dans les premières generations puis se stabilise.

Phase	Generations	Comportement
Exploration	1-10	Amelioration rapide, la population explore l’espace
Exploitation	10-20	Ralentissement, convergence vers l’optimum
Stabilisation	20-30	Plateau, la diversite génétique diminue

Points cles : 1. L’amelioration est rapide en debut d’evolution car la diversite initiale est elevee 2. La convergence ralentit quand les chromosomes deviennent similaires 3. Le moteur ne modifie pas les probabilites en cours d’exécution – c’est le rôle d’une métaheuristique personnalisee (cf. exercice 3) 4. FitnessStagnationTermination pourrait etre utilisee pour arreter l’evolution quand le fitness stagne

6. Comparaison avec NoOpMetaHeuristic

NoOpMetaHeuristic est la métaheuristique neutre : elle passe les parents inchanges sans crossover ni mutation. Comparer DefaultMetaHeuristic avec NoOpMetaHeuristic montre l’apport des opérateurs génétiques.

Attention : avec NoOpMetaHeuristic, il n’y a ni crossover ni mutation. La reinsertion seule (FitnessBasedElitistReinsertion) agit comme un tri par fitness : la population converge immediatement vers le meilleur chromosome initial.

// Compare DefaultMetaHeuristic vs NoOpMetaHeuristic
var heuristics = new (string Name, IMetaHeuristic MH)[]
{
    ("DefaultMetaHeuristic", new DefaultMetaHeuristic()),
    ("NoOpMetaHeuristic",    new NoOpMetaHeuristic()),
};

// Reproductibilite du banc : le seed est place UNE SEULE fois avant la premiere
// branche, pour que Default et NoOp partent d'etats internes distincts du RNG.
// Si le seed etait dans la boucle, les deux branches partiraient du meme tirage
// initial et le contraste pedagogique Default-vs-NoOp disparaitrait (cf review
// CONCERNS #17919).
FastRandomRandomization.ResetSeed(42);

Console.WriteLine("Comparaison DefaultMetaHeuristic vs NoOpMetaHeuristic");
Console.WriteLine("=================================================================");
Console.WriteLine(string.Format("{0,-25} {1,-15} {2,-15} {3,-20}", "MetaHeuristic", "f(x)", "Fitness", "Genes (2 premiers)"));
Console.WriteLine("-----------------------------------------------------------------");

foreach (var (name, mh) in heuristics)
{
    var adam3 = new FloatingPointChromosome(
        new double[] { -10, -10, -10, -10 },
        new double[] {  10,  10,  10,  10 },
        new int[] { 64, 64, 64, 64 },
        new int[] { 0, 0, 0, 0 });

    var pop3 = new MetaPopulation(50, 50, adam3);
    var ga3 = new MetaGeneticAlgorithm(
        pop3,
        new RastriginFitness(),
        new TournamentSelection(3),
        new OnePointCrossover(),
        new UniformMutation(),
        mh);  // Pass the metaheuristic explicitly

    ga3.Termination = new GenerationNumberTermination(30);
    ga3.CrossoverProbability = 0.75f;
    ga3.MutationProbability = 0.1f;

    ga3.Start();

    var best3 = (FloatingPointChromosome)ga3.BestChromosome;
    var genes3 = best3.ToFloatingPoints();
    var obj3 = (1.0 / ga3.BestChromosome.Fitness.Value) - 1.0;

    Console.WriteLine(string.Format("{0,-25} {1,-15:F6} {2,-15:F6} [{3:F4}, {4:F4}, ...]",
        name, obj3, ga3.BestChromosome.Fitness.Value, genes3[0], genes3[1]));
}

Console.WriteLine("=================================================================");

Comparaison DefaultMetaHeuristic vs NoOpMetaHeuristic
=================================================================
MetaHeuristic             f(x)            Fitness         Genes (2 premiers)  
-----------------------------------------------------------------
DefaultMetaHeuristic      27,000000       0,035714        [-3,0000, 1,0000, ...]
NoOpMetaHeuristic         33,000000       0,029412        [-2,0000, -3,0000, ...]
=================================================================

Interpretation : Default vs NoOp

Sortie obtenue : DefaultMetaHeuristic converge vers un piege local (\(f(x) = 27{,}0\)) tandis que NoOpMetaHeuristic reste sur le meilleur chromosome de la population initiale (\(f(x) = 33{,}0\), piege different).

Le banc est reproductible execution apres execution grace au seed place une seule fois avant la premiere branche (cf cellule [15]). Si le seed etait dans la boucle, les deux branches partiraient du meme tirage initial et le contraste pedagogique disparaitrait (cf review CONCERNS #17919).

Métaheuristique	f(x)	Fitness	Genes (2 premiers)
Default	\(27{,}000000\)	\(0{,}035714\)	\([-3{,}0000, 1{,}0000, ...]\)
NoOp	\(33{,}000000\)	\(0{,}029412\)	\([-2{,}0000, -3{,}0000, ...]\)

Points cles : 1. NoOpMetaHeuristic montre que sans opérateurs génétiques, l’elitisme seul ne suffit pas a explorer l’espace – le meilleur de la population initiale (\([-2, -3, ...]\)) n’est pas le meme piege que celui atteint par Default (\([-3, 1, ...]\)) 2. NoOpMetaHeuristic ne produit jamais de nouveau materiel génétique : il gele le meilleur de l’initialisation, sans crossover ni mutation 3. Cette comparaison illustre le rôle de chaque primitive : crossover pour l’exploration, mutation pour la diversification 4. NoOpMetaHeuristic est utile comme branche neutre dans les compositions (par exemple : appliquer une métaheuristique seulement 50% du temps)

7. Resume

Ce notebook a introduit les concepts fondamentaux de MetaGeneticSharp :

Concept	Ce que nous avons observe
Primitives vs bestiaire	Les métaheuristiques sont des primitifs composables, pas des monolithes
Moteur autonome	MetaGeneticAlgorithm execute un GA sans patcher GeneticSharp
Pas de tri implicite	MetaPopulation preserve l’ordre, l’elitisme est explicite
DefaultMetaHeuristic	Reproduit le comportement GA standard (appariement adjacent)
NoOpMetaHeuristic	Neutre : aucun crossover ni mutation
Probabilites	Le crossover et la mutation sont contrôles par \(p_c\) et \(p_m\)

Pour aller plus loin

• Notebook suivant : MGS-2 Composition – combiner des métaheuristiques en pipeline
• Reference : Sorensen, K. (2015). Metaheuristics – The Metaphor Exposed. International Transactions in Operational Research.
• Code source : https://github.com/jsboige/MetaGeneticSharp

---

Exercice 1 : Modifier le chromosome pour un problème différent

L’objectif est de resoudre le problème Even-Parity : trouver un chromosome binaire qui maximise le nombre de bits pairs (c’est-a-dire le nombre de positions ou la somme des bits est paire).

Enonce : Remplacez FloatingPointChromosome par BinaryChromosome (ou un chromosome entier) et definissez une fonction de fitness appropriee.

Indices : - Utilisez BinaryChromosome avec une longueur de 16 bits - La fonction de fitness peut simplement compter le nombre de configurations paires - BinaryChromosome est disponible dans GeneticSharp - Adaptez le crossover : UniformCrossover fonctionne bien avec les chromosomes binaires

// Exercice 1 : Modifier le chromosome pour le probleme Even-Parity
// TODO: Remplacez FloatingPointChromosome par un chromosome adapte au probleme Even-Parity
// Indice: Utilisez BinaryChromosome et definissez une fonction de fitness appropriee
// Indice: GenetiqueSharp propose BinaryChromosome(int length)

// Etape 1 : Definir la fonction de fitness Even-Parity
// public class EvenParityFitness : IFitness { ... }

// Etape 2 : Creer le chromosome Adam
// var adam = new BinaryChromosome(16);

// Etape 3 : Configurer et lancer le GA
// var ga = new MetaGeneticAlgorithm(
//     new MetaPopulation(50, 50, adam),
//     new EvenParityFitness(),
//     new TournamentSelection(3),
//     new UniformCrossover(),
//     new UniformMutation(),
//     new DefaultMetaHeuristic());
// ga.Termination = new GenerationNumberTermination(50);
// ga.Start();

object result = null; // TODO etudiant : lancer le GA et afficher le resultat
Console.WriteLine("Exercice a completer : Even-Parity avec BinaryChromosome");

Exercice a completer : Even-Parity avec BinaryChromosome

Exercice 2 : Comparer DefaultMetaHeuristic et NoOpMetaHeuristic avec plus de generations

Nous avons vu que NoOpMetaHeuristic ne converge pas. Mais que se passe-t-il si on augmente le nombre de generations a 100 ? Et si on augmente la taille de la population a 200 ?

Enonce : Executez DefaultMetaHeuristic et NoOpMetaHeuristic avec 100 generations et une population de 200. Observez si NoOpMetaHeuristic s’ameliore.

Indices : - Reutilisez le code de la section 6 ci-dessus - Changez new MetaPopulation(200, 200, adam) et new GenerationNumberTermination(100) - NoOpMetaHeuristic ne produit jamais de nouveau materiel génétique : plus de generations n’aide pas

// Exercice 2 : Comparer Default vs NoOp avec population=200, generations=100
// TODO: Reprenez le code de la section 6 avec les nouveaux parametres
// TODO: Observez et expliquez pourquoi NoOpMetaHeuristic ne s'amelioire pas

object result = null; // TODO etudiant : lancer les deux configurations et comparer
Console.WriteLine("Exercice a completer : Default vs NoOp (pop=200, gen=100)");

Exercice a completer : Default vs NoOp (pop=200, gen=100)

Exercice 3 : Implementer un IMetaHeuristic personnalise

L’objectif est de créer une métaheuristique qui desactive la mutation sur les generations paires et l’active sur les generations impaires. Cela simule une stratégie d’exploration alternee.

Enonce : Implementez une classe EvenGenerationMutationMetaHeuristic qui herite de ScopedMetaHeuristic et surcharge ScopedMutateChromosome.

Indices : - Heritez de ScopedMetaHeuristic avec new DefaultMetaHeuristic() comme sous-metaheuristic - Le numéro de generation est accessible via ctx.Population.GenerationsNumber - Si la generation est paire, ne faites rien (ou deleguez a un EmptyMetaHeuristic) - Si la generation est impaire, appelez mutation.Mutate(offspring[ctx.LocalIndex], mutationProbability) - L’interface EvolutionStage permet de limiter le scope a la mutation seulement

// Exercice 3 : Implementer un IMetaHeuristic personnalise
// TODO: Creez une classe EvenGenerationMutationMetaHeuristic
// Indice: Heritez de ScopedMetaHeuristic avec new DefaultMetaHeuristic() comme base
// Indice: ctx.Population.GenerationsNumber donne le numero de generation

// public class EvenGenerationMutationMetaHeuristic : ScopedMetaHeuristic
// {
//     public EvenGenerationMutationMetaHeuristic() : base(new DefaultMetaHeuristic()) { }
//
//     protected override IList<IChromosome> ScopedSelectParentPopulation(...) { ... }
//     protected override IList<IChromosome> ScopedMatchParentsAndCross(...) { ... }
//     protected override void ScopedMutateChromosome(IEvolutionContext ctx, IMutation mutation,
//         float mutationProbability, IList<IChromosome> offSprings)
//     {
//         // TODO: Appliquer la mutation uniquement sur les generations impaires
//         // if (ctx.Population.GenerationsNumber % 2 == 1)
//         //     mutation.Mutate(offSprings[ctx.LocalIndex], mutationProbability);
//     }
//     protected override IList<IChromosome> ScopedReinsert(...) { ... }
// }

object result = null; // TODO etudiant : tester avec la fonction de Rastrigin
Console.WriteLine("Exercice a completer : EvenGenerationMutationMetaHeuristic");

Exercice a completer : EvenGenerationMutationMetaHeuristic

---

Navigation : Index | MGS-2 Composition >>