Navigation : << Search-10 SymbolicAutomata | Index
Twin .NET du notebook Search-11-Metaheuristics (Python/MEALPy). Ce notebook est le port fidèle en C#/.NET, implémentant les métaheuristiques from-scratch.
| Twin | Outil | Valeur pédagogique |
|---|---|---|
| Python (MEALPy) | librairie MEALPy (20+ algorithmes préimplémentés) | utiliser une boîte à outils SOTA, comparer rapidement |
| .NET (this) | implémentation from-scratch en C# | comprendre l’algorithme de l’intérieur |
Il n’existe pas d’équivalent NuGet maintenu et didactique à MEALPy en .NET. Le twin .NET tire parti de cette absence pour démontrer les algorithmes à la main — c’est précisément l’occasion pédagogique, pas une régression.
À la fin de cette tranche, vous saurez : 1. Distinguer exploration et exploitation en optimisation 2. Implémenter le recuit simulé (Simulated Annealing) from-scratch en C# 3. Comprendre le rôle du schéma de température et du critère d’acceptation de Metropolis 4. Vérifier SA sur un benchmark multimodal non-convexe (Ackley) où une descente pure échoue
Note : Le recuit simulé (Kirkpatrick, Gelatt, Vecchi, 1983) s’inspire de la thermodynamique : en refroidissant lentement un métal, ses atomes trouvent un état d’énergie minimale. L’algorithme autorise ponctuellement des mouvements qui dégradent la solution, avec une probabilité décroissant avec la température — c’est l’anti-dote au piège des optima locaux.
// Setup : aucune dépendance externe — algos from-scratch, uniquement la BCL .NET.
using Microsoft.DotNet.Interactive;
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
// PRNG déterministe (seed fixe) pour reproductibilité pédagogique.
var rng = new Random(42);
"Environnement prêt — métaheuristiques from-scratch (BCL .NET seule).".Display();Environnement prêt — métaheuristiques from-scratch (BCL .NET seule).L’optimisation d’une fonction \(f: \mathbb{R}^n \to \mathbb{R}\) cherche \(x^* = \arg\min f(x)\). Deux forces antagoniques :
Les métaheuristiques sont des heuristiques génériques qui orchestrent ce compromis. Le recuit simulé est l’une des plus simples et des plus élégantes : il accepte probabilistiquement des dégradations, de moins en moins au fil du temps.
Une descente pure (greedy hill-climbing) n’accepte jamais un voisin moins bon. Sur une fonction multimodale (plusieurs vallées), elle reste bloquée dans la première vallée trouvée. Le recuit simulé, grâce au critère de Metropolis, peut escalader temporairement une colline pour atteindre une vallée plus profonde.
Pour valider SA, nous utilisons deux fonctions classiques de l’optimisation continue :
\[f(x) = \sum_{i=1}^{n} x_i^2, \quad x^* = \mathbf{0}, \quad f(x^*) = 0\] Facile : un seul minimum global, toute descente y arrive.
\[f(x) = -20 \exp\left(-0.2 \sqrt{\tfrac{1}{n}\sum x_i^2}\right) - \exp\left(\tfrac{1}{n}\sum \cos(2\pi x_i)\right) + 20 + e\] Difficile : paysage raboteux avec une infinité d’optima locaux, mais un seul minimum global en \(\mathbf{0}\). Une descente pure s’y piège ; c’est le test discriminant pour SA.
// Fonctions de benchmark (dim n quelconque).
static double Sphere(double[] x) =>
x.Select(xi => xi * xi).Sum();
static double Ackley(double[] x)
{
int n = x.Length;
double sumSq = x.Select(xi => xi * xi).Sum();
double sumCos = x.Select(xi => Math.Cos(2 * Math.PI * xi)).Sum();
return -20.0 * Math.Exp(-0.2 * Math.Sqrt(sumSq / n))
- Math.Exp(sumCos / n) + 20.0 + Math.E;
}
// Domaine de recherche pour les benchmarks ([-5, 5]^n recommandé pour Ackley).
const double LO = -5.0, HI = 5.0;
// Vérification : minimum global connu = 0 en l'origine.
var origin = new double[] { 0.0, 0.0 };
var sb = new StringBuilder();
sb.AppendLine($"Sphere(0,0) = {Sphere(origin):F6} (attendu ≈ 0)");
sb.AppendLine($"Ackley(0,0) = {Ackley(origin):F6} (attendu ≈ 0)");
// Un point hors de l'optimum pour montrer la rugosité
var rough = new double[] { 2.5, -1.3 };
sb.AppendLine($"Ackley(2.5,-1.3) = {Ackley(rough):F6} (point raboteux hors optimum)");
sb.ToString().Display();Sphere(0,0) = 0,000000 (attendu ≈ 0)
Ackley(0,0) = 0,000000 (attendu ≈ 0)
Ackley(2.5,-1.3) = 8,772021 (point raboteux hors optimum)L’algorithme maintient une solution courante \(x\) et une température \(T\) qui décroît. À chaque itération :
À haute température (\(T \to \infty\)), \(\exp(-\Delta/T) \to 1\) : tout mouvement est accepté (exploration pure). À basse température (\(T \to 0\)), \(\exp(-\Delta/T) \to 0\) : seules les améliorations sont acceptées (exploitation = descente). Le schéma de refroidissement orchestre la transition exploration → exploitation.
L’implémentation est volontairement explicite (pas de framework) : chaque étape (voisinage, Metropolis, refroidissement) est lisible. Le voisinage est une perturbation gaussienne bornée dans le domaine.
// Recuit simulé (Simulated Annealing) from-scratch.
// f : fonction objectif à minimiser
// dim : dimension du problème
// T0 : température initiale
// alpha : facteur de refroidissement géométrique (0 < alpha < 1)
// iters : nombre d'itérations par palier
// steps : nombre de paliers de température
// rng : PRNG partagé (seed fixe hors de la fonction)
static (double[] bestX, double bestF, List<double> history) SimulatedAnnealing(
Func<double[], double> f, int dim,
double T0, double alpha, int iters, int steps,
Random rng)
{
// Solution initiale aléatoire dans [LO, HI]
double[] x = new double[dim];
for (int i = 0; i < dim; i++) x[i] = LO + rng.NextDouble() * (HI - LO);
double fx = f(x);
double[] bestX = (double[])x.Clone();
double bestF = fx;
var history = new List<double> { bestF };
double T = T0;
for (int s = 0; s < steps; s++)
{
for (int k = 0; k < iters; k++)
{
// Voisin : perturbation gaussienne (Box-Muller) d'amplitude ~ T
double[] cand = (double[])x.Clone();
for (int i = 0; i < dim; i++)
{
double u1 = Math.Max(rng.NextDouble(), 1e-12);
double u2 = rng.NextDouble();
double gauss = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Cos(2.0 * Math.PI * u2);
cand[i] = x[i] + gauss * (HI - LO) * 0.05; // amplitude 5% du domaine
if (cand[i] < LO) cand[i] = LO; // bornage domaine
if (cand[i] > HI) cand[i] = HI;
}
double fcand = f(cand);
double delta = fcand - fx;
// Critère de Metropolis
bool accept = delta <= 0 || rng.NextDouble() < Math.Exp(-delta / T);
if (accept) { x = cand; fx = fcand; }
if (fx < bestF) { bestF = fx; bestX = (double[])x.Clone(); }
}
T *= alpha; // refroidissement géométrique
history.Add(bestF);
}
return (bestX, bestF, history);
}
"Implémentation SA prête (Box-Muller, Metropolis, refroidissement géométrique).".Display();Implémentation SA prête (Box-Muller, Metropolis, refroidissement géométrique).// SA sur Sphere (unimodal) — sanity check : doit approcher 0.
rng = new Random(42); // reset seed pour reproductibilité
var (bestX_sph, bestF_sph, hist_sph) = SimulatedAnnealing(
Sphere, dim: 2, T0: 10.0, alpha: 0.92, iters: 50, steps: 200, rng);
var sb = new StringBuilder();
sb.AppendLine("=== SA sur Sphere (unimodal) ===");
sb.AppendLine($"Meilleur x trouvé : ({bestX_sph[0]:F4}, {bestX_sph[1]:F4})");
sb.AppendLine($"Meilleur f(x) : {bestF_sph:F6} (optimum global = 0)");
sb.AppendLine($"Distance à 0 : {Math.Sqrt(bestX_sph[0]*bestX_sph[0]+bestX_sph[1]*bestX_sph[1]):F6}");
sb.AppendLine($"Paliers de température : {hist_sph.Count}");
sb.ToString().Display();=== SA sur Sphere (unimodal) ===
Meilleur x trouvé : (0,0050, 0,0042)
Meilleur f(x) : 0,000043 (optimum global = 0)
Distance à 0 : 0,006545
Paliers de température : 201SA converge facilement vers l’origine sur Sphere (fonction convexe) : l’optimum global est aussi le seul minimum, aucune possibilité de piège. C’est le sanity check — si SA échouait ici, l’implémentation serait buguée. Le recuit simulé est conçu pour les paysages difficiles ; sur un problème facile, il se comporte comme une descente.
// SA sur Ackley (multimodal) — le vrai test. Une descente pure s'y échouerait.
rng = new Random(42);
var (bestX_ack, bestF_ack, hist_ack) = SimulatedAnnealing(
Ackley, dim: 2, T0: 10.0, alpha: 0.92, iters: 50, steps: 200, rng);
var sb = new StringBuilder();
sb.AppendLine("=== SA sur Ackley (multimodal, non-convexe) ===");
sb.AppendLine($"Meilleur x trouvé : ({bestX_ack[0]:F4}, {bestX_ack[1]:F4})");
sb.AppendLine($"Meilleur f(x) : {bestF_ack:F6} (optimum global = 0)");
sb.AppendLine($"Distance à 0 : {Math.Sqrt(bestX_ack[0]*bestX_ack[0]+bestX_ack[1]*bestX_ack[1]):F6}");
sb.AppendLine();
sb.AppendLine("Convergence (best f(x) tous les 25 paliers) :");
for (int i = 0; i < hist_ack.Count; i += 25)
sb.AppendLine($" palier {i,3} : best f = {hist_ack[i]:F6}");
sb.ToString().Display();=== SA sur Ackley (multimodal, non-convexe) ===
Meilleur x trouvé : (-0,0001, -0,0121)
Meilleur f(x) : 0,038244 (optimum global = 0)
Distance à 0 : 0,012136
Convergence (best f(x) tous les 25 paliers) :
palier 0 : best f = 10,770053
palier 25 : best f = 0,292674
palier 50 : best f = 0,085684
palier 75 : best f = 0,064659
palier 100 : best f = 0,064659
palier 125 : best f = 0,064659
palier 150 : best f = 0,038244
palier 175 : best f = 0,038244
palier 200 : best f = 0,038244Lecture chiffree. Les paliers rendus (paliers 0 a 200, tous les 25) racontent la trajectoire : best f = 10,770053 au depart, 0,292674 des le palier 25 — le meilleur est divise par environ 37 en un quart de course. Puis deux geleurs : 0,064659 tient les paliers 75, 100 et 125 (trois lignes identiques), casse a 0,038244 au palier 150 et ne bouge plus jusqu’a 200 — l’exploitation finale apres l’exploration, exactement le scenario Metropolis. Le point final (-0,0001, -0,0121) porte sa distance a l’origine (0,012136) presque entierement sur la seconde coordonnee : sur les valeurs affichees, 0,0121 / 0,0001 = 121. Et la sanity Sphere se verifie par carres : le meilleur f rendu 0,000043 est bien la somme 0,0050^2 + 0,0042^2 — la fonction objective est ce qu’elle dit etre.
Ackley est le test discriminant : son paysage est parsemé d’optima locaux, et seul \(\mathbf{0}\) est le minimum global. Une descente pure (hill-climbing greedy) s’arrête au premier optimum local rencontré — typiquement \(f \approx 2\) à \(6\), jamais \(0\).
SA s’en sort parce qu’au début (haute \(T\)), il accepte des dégradations et peut escalader une colline pour atteindre un meilleur bassin. La convergence vers \(f \approx 0\) (ou très proche) démontre que le critère de Metropolis a rempli son rôle : exploration initiale, puis exploitation finale.
Sensibilité : si \(\alpha\) est trop grand (refroidissement rapide), SA se comporte comme une descente et reste piégé. Si \(\alpha\) est trop petit (refroidissement lent), cela converge mais coûte plus d’itérations. C’est le compromis exploration/exploitation incarné dans un seul paramètre.
SA est très sensible au facteur de refroidissement \(\alpha\). Complétez le stub pour comparer \(\alpha \in \{0.80, 0.92, 0.99\}\) sur Ackley (mêmes iters/steps/seed). Quel \(\alpha\) donne le meilleur \(f(x)\) final ? Lequel converge le plus vite ? Interprétez le compromis.
// Exercice 1 : comparaison de schémas de refroidissement (étudiant à compléter)
// Indice 1 : reset rng = new Random(42) avant chaque run pour isoler l'effet de alpha.
// Indice 2 : collecter bestF final pour chaque alpha dans un tableau, afficher en table texte.
// Étape 1 : boucler sur alpha in {0.80, 0.92, 0.99}
// Étape 2 : appeler SimulatedAnnealing(Ackley, ...) pour chaque
// Étape 3 : afficher alpha vs bestF final
double[] alphas = { 0.80, 0.92, 0.99 };
// TODO étudiant : comparer les schémas de refroidissement
"Exercice 1 à compléter — comparer alpha = 0.80 / 0.92 / 0.99 sur Ackley.".Display();Exercice 1 à compléter — comparer alpha = 0.80 / 0.92 / 0.99 sur Ackley.La température initiale \(T_0\) contrôle l’intensité de l’exploration. Complétez le stub pour comparer \(T_0 \in \{0.1, 5, 50\}\) sur Ackley avec \(\alpha = 0.92\). Une \(T_0\) trop basse empêche-t-elle l’évasion des optima locaux ? Une \(T_0\) trop haute gaspille-t-elle des itérations en exploration aléatoire ?
// Exercice 2 : impact de la température initiale (étudiant à compléter)
// Indice : T0 bas =exploitation tôt (piège local possible), T0 haut = exploration prolongée.
double[] T0s = { 0.1, 5.0, 50.0 };
// TODO étudiant : comparer T0 = 0.1 / 5 / 50 sur Ackley (alpha=0.92)
"Exercice 2 à compléter — comparer T0 = 0.1 / 5 / 50 sur Ackley.".Display();Exercice 2 à compléter — comparer T0 = 0.1 / 5 / 50 sur Ackley.L’amplitude de la perturbation gaussienne (ici 0.05 * (HI-LO)) contrôle la portée d’un pas. Complétez le stub pour tester des amplitudes \(\in \{0.01, 0.05, 0.20\}\) (modifiez le facteur dans SimulatedAnnealing ou ajoutez un paramètre). Une amplitude trop petite empêche-t-elle de franchir les collines d’Ackley ? Trop grande saute-t-elle l’optimum ?
// Exercice 3 : impact de l'amplitude du voisinage (étudiant à compléter)
// Indice : l'amplitude est le facteur 0.05 dans cand[i] += gauss * (HI-LO) * 0.05.
// Étape 1 : paramétrer l'amplitude (ajouter un arg à SimulatedAnnealing, ou recopier avec un facteur)
// Étape 2 : tester amplitude in {0.01, 0.05, 0.20} sur Ackley
double[] amps = { 0.01, 0.05, 0.20 };
// TODO étudiant : comparer l'amplitude du voisinage
"Exercice 3 à compléter — comparer amplitude = 0.01 / 0.05 / 0.20 sur Ackley.".Display();Exercice 3 à compléter — comparer amplitude = 0.01 / 0.05 / 0.20 sur Ackley.Cette tranche a posé les fondations des métaheuristiques en C#/.NET via le recuit simulé from-scratch.
| Concept | Implémentation C# |
|---|---|
| Fonction objectif | délégué Func<double[], double> (Sphere, Ackley) |
| Voisinage | perturbation gaussienne (Box-Muller), bornée au domaine |
| Critère de Metropolis | delta <= 0 \|\| rng.NextDouble() < Math.Exp(-delta / T) |
| Refroidissement | géométrique T *= alpha |
| Reproductibilité | Random(42) (seed fixe hors des fonctions) |
Tranche 1 du twin .NET⇄Python (#4956, marathon). SA = 1er des 4 algorithmes (SA, PSO, ABC, benchmark).