Navigation : << Tranche 3 ABC | Twin Python MEALPy
Tranche 4 (FINALE) du twin .NET du notebook Python Search-11-Metaheuristics (MEALPy). Après le recuit simule (tranche 1, trajectoire unique, Metropolis), le PSO (tranche 2, essaim, vitesse/inertie) et l’ABC (tranche 3, essaim a rôles, employed/onlooker/scout), cette tranche 4 = le benchmark comparatif capstone qui synthesize les trois métaheuristiques sur un panel de fonctions test.
L’ideee : maintenant que nous avons compris chaque algorithme individuellement (tranches 1-3), la question naturelle est — lequel choisir pour un problème donne ? Il n’y a pas de reponse universelle (no free lunch). Ce notebook apporte la reponse empirique : on lance les trois algorithmes sur quatre fonctions aux paysages opposes (unimodal vs multimodal, vallée etroite vs optima locaux nombreux), avec plusieurs seeds, et on identifie le meilleur algorithme par type de paysage.
Stack technique : BCL .NET seule, 0 NuGet. Implementation from-scratch des trois algorithmes (re-définis de maniere self-contained). Kernel .net-csharp.
Le theoreme No Free Lunch (Wolpert & Macready, 1997) dit que, moyennes sur TOUS les problemes possibles, toutes les métaheuristiques ont les mêmes performances. Consequence : aucun algorithme n’est universellement meilleur. Le choix depend du paysage du problème :
| Paysage | Caractéristique | Algorithme typiquement avantage |
|---|---|---|
| Unimodal | un seul minimum, pente reguliere | descente locale, PSO (terme social) |
| Multimodal peu d’optima | quelques pieges | SA (Metropolis), scout ABC |
| Multimodal beaucoup d’optima | Rastrigin (optima reguliers) | essaim (PSO/ABC) |
| Vallee etroite courbe | Rosenbrock | PSO (suit la vallee via gbest) |
Ce benchmark verifie empiriquement ces intuitions sur quatre fonctions representatives.
Au fond, le tableau qui suit est une instance locale de ce théorème : trois algorithmes, quatre paysages, et aucun sweep de la couronne. La question n’est pas « quel est le meilleur algorithme » mais « quel algorithme sur quel paysage à quelle dimension » — c’est la grille de lecture des sections 5 et 6.
Helper de formatage invariant (culture-indépendant) — evite la collision virgule-decimale FR / virgule-tuple dans les sorties.
Trois invariants rendent la comparaison honnête : la dimension fixée à 5, les bornes communes \([-5, 10]^5\), et le budget identique en évaluations pour les trois algorithmes. Les seeds {1, 7, 42} prémunissent contre le verdict mono-run : chaque cellule du tableau qui suit est une moyenne ± écart-type sur 3 exécutions, pas un coup de dés unique.
Le critère est le même pour tous : la valeur finale de \(f\), l’optimum étant 0 sur les quatre fonctions. Un lecteur pressé ne lira que la colonne « Gagnant » ; les deux sections suivantes montrent pourquoi la moyenne ET le taux de convergence racontent des histoires différentes.
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
static string FI(double x, string fmt = "F4") => x.ToString(fmt, CultureInfo.InvariantCulture);
static string FV(double[] xs, string fmt = "F3") => "[" + string.Join(", ", xs.Select(x => FI(x, fmt))) + "]";
Console.WriteLine("Setup OK — kernel .net-csharp, BCL seule.");Setup OK — kernel .net-csharp, BCL seule.Quatre fonctions aux paysages deliberement opposes :
| Fonction | Paysage | Optimum | Difficulte |
|---|---|---|---|
| Sphere | unimodal (bol) | \(f=0\) en \(x=0\) | facile (sanity) |
| Rastrigin | multimodal (optima reguliers) | \(f=0\) en \(x=0\) | moyenne (pieges nombreux) |
| Rosenbrock | vallee etroite courbe | \(f=0\) en \(x=(1,\dots,1)\) | dure (suivre la vallee) |
| Ackley | multimodal (entonnoir) | \(f=0\) en \(x=0\) | moyenne (profond piege central) |
Ces quatre couvrent les grandes classes de paysages — un bon benchmark ne teste pas qu’un seul type.
Les quatre paysages sont choisis pour leurs défauts distincts : Sphere (unimodal, sans piège) valide la mécanique ; Rastrigin (multimodal régulier) teste l’évasion des optima locaux ; Rosenbrock (vallée parabolique étroite) punit l’exploration large — la vallée se suit, elle ne se saute pas ; Ackley (puits central entouré d’un plateau presque plat) épuise les méthodes qui confondent « presque plat » et « optimum ». Aucun algorithme ne peut être bon sur les quatre par hasard.
// Quatre fonctions de benchmark, paysages opposes. Bornes [-5, 10] (cf twin Python).
const double LO = -5.0, HI = 10.0;
static double Sphere(double[] x) {
double s = 0;
for (int i = 0; i < x.Length; i++) s += x[i] * x[i];
return s;
}
static double Rastrigin(double[] x) {
double s = 0;
for (int i = 0; i < x.Length; i++) s += x[i] * x[i] - 10.0 * Math.Cos(2.0 * Math.PI * x[i]);
return 10.0 * x.Length + s;
}
static double Rosenbrock(double[] x) {
double s = 0;
for (int i = 0; i < x.Length - 1; i++) {
double a = x[i + 1] - x[i] * x[i];
double b = 1.0 - x[i];
s += 100.0 * a * a + b * b;
}
return s;
}
static double Ackley(double[] x) {
int n = x.Length;
double sq = 0, cs = 0;
for (int i = 0; i < n; i++) { sq += x[i] * x[i]; cs += Math.Cos(2.0 * Math.PI * x[i]); }
double term1 = -20.0 * Math.Exp(-0.2 * Math.Sqrt(sq / n));
double term2 = -Math.Exp(cs / n);
return term1 + term2 + 20.0 + Math.E;
}
// Sanity : verifier les optima connus.
double[] x0 = Enumerable.Repeat(0.0, 5).ToArray();
double[] x1 = Enumerable.Repeat(1.0, 5).ToArray();
Console.WriteLine("Sanity (dim=5) :");
Console.WriteLine($" Sphere(0) = {FI(Sphere(x0), "F6")} (attendu 0)");
Console.WriteLine($" Rastrigin(0) = {FI(Rastrigin(x0), "F6")} (attendu 0)");
Console.WriteLine($" Rosenbrock(1) = {FI(Rosenbrock(x1), "F6")} (attendu 0)");
Console.WriteLine($" Ackley(0) = {FI(Ackley(x0), "F6")} (attendu 0)");Sanity (dim=5) :
Sphere(0) = 0.000000 (attendu 0)
Rastrigin(0) = 0.000000 (attendu 0)
Rosenbrock(1) = 0.000000 (attendu 0)
Ackley(0) = 0.000000 (attendu 0)Les trois métaheuristiques des tranches 1-3, re-ecrites de maniere compacte et self-contained. Chacune expose la même signature : (fonction, dim, seed) -> (best_x, best_f) pour pouvoir les brancher dans le benchmark.
delta<=0 || rnd<exp(-delta/T), cooling geometrique.w*v + c1*r1*(p_i-x) + c2*r2*(g-x), inertie + cognitif + social.fit=1/(1+f).// === SA (tranche 1, compact) — trajectoire unique + Metropolis ===
static (double[] x, double f) SA(Func<double[], double> f, int dim, int seed,
int iters = 3000, double T0 = 100.0, double Tend = 0.01) {
var rng = new Random(seed);
double[] x = new double[dim], xc = new double[dim];
for (int d = 0; d < dim; d++) { x[d] = LO + rng.NextDouble() * (HI - LO); xc[d] = x[d]; }
double fx = f(x), fxc = fx;
double T = T0;
double cool = Math.Pow(Tend / T0, 1.0 / iters);
for (int it = 0; it < iters; it++) {
double[] xn = (double[]) xc.Clone();
int j = rng.Next(dim);
xn[j] = Math.Max(LO, Math.Min(HI, xn[j] + rng.NextDouble() * 2.0 - 1.0));
double fn = f(xn);
double delta = fn - fxc;
if (delta <= 0 || rng.NextDouble() < Math.Exp(-delta / T)) { xc = xn; fxc = fn; }
if (fxc < fx) { fx = fxc; x = (double[]) xc.Clone(); }
T *= cool;
}
return (x, fx);
}
// === PSO (tranche 2, compact) — essaim + vitesse ===
static (double[] x, double f) PSO(Func<double[], double> f, int dim, int seed,
int nParts = 30, int iters = 100, double w = 0.7, double c1 = 1.5, double c2 = 1.5) {
var rng = new Random(seed);
double[][] pos = new double[nParts][], vel = new double[nParts][], pbest = new double[nParts][];
double[] fpbest = new double[nParts];
double[] gbest = new double[dim]; double fgbest = double.PositiveInfinity;
for (int i = 0; i < nParts; i++) {
pos[i] = new double[dim]; vel[i] = new double[dim]; pbest[i] = new double[dim];
for (int d = 0; d < dim; d++) { pos[i][d] = LO + rng.NextDouble() * (HI - LO); vel[i][d] = 0; }
double fi = f(pos[i]); fpbest[i] = fi; Array.Copy(pos[i], pbest[i], dim);
if (fi < fgbest) { fgbest = fi; Array.Copy(pos[i], gbest, dim); }
}
for (int it = 0; it < iters; it++) {
for (int i = 0; i < nParts; i++) {
for (int d = 0; d < dim; d++) {
vel[i][d] = w * vel[i][d] + c1 * rng.NextDouble() * (pbest[i][d] - pos[i][d])
+ c2 * rng.NextDouble() * (gbest[d] - pos[i][d]);
pos[i][d] += vel[i][d];
if (pos[i][d] < LO) { pos[i][d] = LO; vel[i][d] *= -0.5; }
if (pos[i][d] > HI) { pos[i][d] = HI; vel[i][d] *= -0.5; }
}
double fi = f(pos[i]);
if (fi < fpbest[i]) { fpbest[i] = fi; Array.Copy(pos[i], pbest[i], dim); }
if (fi < fgbest) { fgbest = fi; Array.Copy(pos[i], gbest, dim); }
}
}
return (gbest, fgbest);
}
// === ABC (tranche 3, compact) — essaim a roles + scout ===
class Src { public double[] X; public double F; public int Trial; }
static Src RandSrc(int dim, Func<double[], double> f, Random rng) {
var x = new double[dim];
for (int d = 0; d < dim; d++) x[d] = LO + rng.NextDouble() * (HI - LO);
return new Src { X = x, F = f(x), Trial = 0 };
}
static (double[] x, double f) ABC(Func<double[], double> f, int dim, int seed,
int SN = 30, int maxCycles = 100, int limit = 50) {
var rng = new Random(seed);
var srcs = Enumerable.Range(0, SN).Select(_ => RandSrc(dim, f, rng)).ToList();
double[] gbest = (double[]) srcs.OrderBy(s => s.F).First().X.Clone();
double fgbest = f(gbest);
for (int cycle = 0; cycle < maxCycles; cycle++) {
for (int i = 0; i < SN; i++) {
int k; do { k = rng.Next(SN); } while (k == i);
int j = rng.Next(dim);
double phi = rng.NextDouble() * 2.0 - 1.0;
double vj = srcs[i].X[j] + phi * (srcs[i].X[j] - srcs[k].X[j]);
if (vj < LO) vj = LO; if (vj > HI) vj = HI;
var v = (double[]) srcs[i].X.Clone(); v[j] = vj;
double fv = f(v);
if (fv < srcs[i].F) { srcs[i].X = v; srcs[i].F = fv; srcs[i].Trial = 0; }
else srcs[i].Trial++;
}
double[] fit = srcs.Select(s => 1.0 / (1.0 + s.F)).ToArray();
double sumFit = fit.Sum();
for (int o = 0; o < SN; o++) {
double r = rng.NextDouble(); int i = 0; double cumul = 0;
while (i < SN - 1) { cumul += fit[i] / sumFit; if (r <= cumul) break; i++; }
int k; do { k = rng.Next(SN); } while (k == i);
int j = rng.Next(dim);
double phi = rng.NextDouble() * 2.0 - 1.0;
double vj = srcs[i].X[j] + phi * (srcs[i].X[j] - srcs[k].X[j]);
if (vj < LO) vj = LO; if (vj > HI) vj = HI;
var v = (double[]) srcs[i].X.Clone(); v[j] = vj;
double fv = f(v);
if (fv < srcs[i].F) { srcs[i].X = v; srcs[i].F = fv; srcs[i].Trial = 0; }
else srcs[i].Trial++;
}
for (int i = 0; i < SN; i++) if (srcs[i].Trial > limit) srcs[i] = RandSrc(dim, f, rng);
var best = srcs.OrderBy(s => s.F).First();
if (best.F < fgbest) { fgbest = best.F; gbest = (double[]) best.X.Clone(); }
}
return (gbest, fgbest);
}
Console.WriteLine("Trois algorithmes compiles : SA, PSO, ABC.");Trois algorithmes compiles : SA, PSO, ABC.Le harness lance chaque algorithme sur chaque fonction avec plusieurs seeds, et agrège les résultats (moyenne et ecart-type de la meilleure valeur trouvee). On utilise un budget d’evaluations comparable : SA ~3000 evals (3000 iters × 1 trajectoire), PSO/ABC ~3000 evals (30 particules × 100 cycles). C’est une comparaison equitable en budget — le facteur discriminant est la stratégie, pas le nombre d’evals.
Dimension = 5 (modeste pour garder un runtime raisonnable en notebook pedagogique). Seeds = {1, 7, 42} (3 seeds pour les statistiques).
// Harness de benchmark : 3 algos × 4 fonctions × 3 seeds.
int dim = 5;
int[] seeds = { 1, 7, 42 };
var funcs = new (string name, Func<double[], double> f)[] {
("Sphere", Sphere), ("Rastrigin", Rastrigin), ("Rosenbrock", Rosenbrock), ("Ackley", Ackley)
};
var algos = new (string name, Func<Func<double[], double>, int, int, (double[] x, double f)> run)[] {
("SA", (f, d, s) => SA(f, d, s)),
("PSO", (f, d, s) => PSO(f, d, s)),
("ABC", (f, d, s) => ABC(f, d, s)),
};
// resultats[func][algo] = liste des f-finaux sur les seeds
var results = new Dictionary<string, Dictionary<string, List<double>>>();
foreach (var (fname, f) in funcs) {
results[fname] = new Dictionary<string, List<double>>();
foreach (var (aname, run) in algos) {
var fs = new List<double>();
foreach (int s in seeds) { var (_, fb) = run(f, dim, s); fs.Add(fb); }
results[fname][aname] = fs;
}
}
Console.WriteLine("Benchmark termine : 3 algos × 4 fonctions × 3 seeds = 36 runs.");Benchmark termine : 3 algos × 4 fonctions × 3 seeds = 36 runs.Pour chaque fonction, on reporte la moyenne et l’ecart-type de la meilleure valeur sur 3 seeds, et on identifie le gagnant (algorithme avec la plus basse moyenne). Les ecarts-types petits = convergence stable cross-seed ; grands = sensibilite a l’initialisation.
Comment lire ce tableau. Chaque cellule = moyenne ± écart-type du meilleur \(f\) final sur les seeds {1, 7, 42} en dimension 5 ; le gagnant est la moyenne la plus basse. L’écart-type compte autant que la moyenne : 0.0260 ± 0.0162 (SA sur Rastrigin) dit « souvent proche, rarement sous le seuil », un profil très différent d’un 0.0000 ± 0.0000 reproductible au bit près.
Trois lectures sautent aux yeux avant toute analyse : PSO parfait sur Sphere et Ackley mais crevé à 3.6816 sur Rastrigin ; Rosenbrock sans gagnant net (meilleure moyenne ABC 0.4434, loin de 0) ; SA jamais gagnant mais jamais catastrophique sauf sur Rosenbrock. La section 6 quantifie ce que ces moyennes cachent.
// Tableau comparatif + identification du gagnant par fonction.
Console.WriteLine($"Benchmark (dim={dim}, seeds={{{string.Join(", ", seeds)}}}, f-optimal = 0 pour toutes)");
Console.WriteLine();
Console.WriteLine(" " + "Fonction".PadLeft(12) + " | " + "SA (moy et std)".PadLeft(22) + " | " + "PSO (moy et std)".PadLeft(22) + " | " + "ABC (moy et std)".PadLeft(22) + " | " + "Gagnant".PadLeft(8));
Console.WriteLine(" " + new string('-', 12) + " | " + new string('-', 22) + " | " + new string('-', 22) + " | " + new string('-', 22) + " | " + new string('-', 8));
string Winner(string fn) {
var m = results[fn];
double sa = m["SA"].Average(), pso = m["PSO"].Average(), abc = m["ABC"].Average();
double best = Math.Min(sa, Math.Min(pso, abc));
if (best == sa) return "SA";
if (best == pso) return "PSO";
return "ABC";
}
string Cell(List<double> fs) {
double mean = fs.Average();
double std = Math.Sqrt(fs.Select(v => (v - mean) * (v - mean)).Average());
return $"{FI(mean, "F4"),10} ± {FI(std, "F4"),7}";
}
foreach (var (fname, _) in funcs) {
var m = results[fname];
Console.WriteLine($" {fname,12} | {Cell(m["SA"]),22} | {Cell(m["PSO"]),22} | {Cell(m["ABC"]),22} | {Winner(fname),8}");
}Benchmark (dim=5, seeds={1, 7, 42}, f-optimal = 0 pour toutes)
Fonction | SA (moy et std) | PSO (moy et std) | ABC (moy et std) | Gagnant
------------ | ---------------------- | ---------------------- | ---------------------- | --------
Sphere | 0.0050 ± 0.0040 | 0.0000 ± 0.0000 | 0.0000 ± 0.0000 | ABC
Rastrigin | 0.0260 ± 0.0162 | 3.6816 ± 0.9163 | 0.0034 ± 0.0046 | ABC
Rosenbrock | 2.6304 ± 1.3973 | 0.9001 ± 0.2705 | 0.4434 ± 0.2704 | ABC
Ackley | 0.0690 ± 0.0467 | 0.0002 ± 0.0001 | 0.0001 ± 0.0001 | ABCLa lecture doit etre honnête vis-a-vis des chiffres observes (pas d’affirmations genereuses). Points cles :
Lecon empirique : même si un algorithme domine sur ce panel, la marge varie fortement selon le paysage, et la variance cross-seed revele la robustesse. C’est le VRAI enseignement du No Free Lunch — non pas qu’un autre algo gagnerait ailleurs, mais que la confiance dans un résultat depend du paysage et de la stabilite.
Le choc dimensionnel. En dimension 2 (tranche 2), le PSO verrouillait Rastrigin à 0.0000 dès l’itération 40 ; en dimension 5, le même algorithme finit à 3.6816 ± 0.9163 — l’essaim se fige dans des minima locaux de plus en plus nombreux à mesure que le volume de recherche explose. C’est la leçon centrale du marathon : la hiérarchie des métaheuristiques n’est pas une propriété des algorithmes, elle est une propriété du couple (algorithme, dimension).
Pourquoi Rosenbrock résiste à tous. Sa vallée est étroite et courbée : descendre vers le fond est facile, mais suivre la vallée jusqu’à l’optimum demande une suite de pas corrélés dans la bonne direction. Les perturbations aléatoires du recuit et l’attraction sociale de l’essaim s’y révèlent toutes deux myopes — d’où le triple 0 % de taux de convergence ci-dessous, même pour ABC et sa moyenne 0.4434 : être dans la vallée n’est pas être à l’optimum.
Une autre facette : a quelle frequence chaque algorithme atteint-il l’optimum (seuil \(f < 10^{-3}\)) sur les seeds ? Un bon algorithme ne fait pas que baisser f en moyenne — il converge fiablement.
Lecture chiffrée du taux (sortie commitée ci-dessus, seuil \(f < 10^{-3}\)) : Rosenbrock aligne 0 % partout — aucune méthode n’atteint le seuil, la meilleure moyenne (ABC, 0.4434) reste 440 fois au-dessus ; Rastrigin ne réussit qu’ABC, à 67 % (2 seeds sur 3) ; Sphere et Ackley voient PSO et ABC à 100 % pendant que SA décroche (33 % et 0 %).
Moyenne et taux ne disent pas la même chose. SA sur Rastrigin : moyenne 0.0260, taux 0 % — proche à chaque run, sous le seuil jamais. ABC sur Rastrigin : moyenne 0.0034, taux 67 % — sous le seuil deux fois sur trois, un seed l’a manqué. C’est exactement pourquoi le harness est multi-seed : un mono-run sur le seed manquant aurait déclaré ABC champion incontesté de Rastrigin.
// Taux de succes : frequence ou f < 1e-3 sur les seeds.
double threshold = 1e-3;
Console.WriteLine($"Taux de succes (f < 1e-3 = convergence) sur {seeds.Length} seeds :");
Console.WriteLine();
Console.WriteLine(" " + "Fonction".PadLeft(12) + " | " + "SA".PadLeft(8) + " | " + "PSO".PadLeft(8) + " | " + "ABC".PadLeft(8));
Console.WriteLine(" " + new string('-', 12) + " | " + new string('-', 8) + " | " + new string('-', 8) + " | " + new string('-', 8));
foreach (var (fname, _) in funcs) {
var m = results[fname];
int sa = m["SA"].Count(v => v < threshold);
int pso = m["PSO"].Count(v => v < threshold);
int abc = m["ABC"].Count(v => v < threshold);
Console.WriteLine($" {fname,12} | {FI(100.0 * sa / seeds.Length, "F0") + "%",8} | {FI(100.0 * pso / seeds.Length, "F0") + "%",8} | {FI(100.0 * abc / seeds.Length, "F0") + "%",8}");
}Taux de succes (f < 1e-3 = convergence) sur 3 seeds :
Fonction | SA | PSO | ABC
------------ | -------- | -------- | --------
Sphere | 33% | 100% | 100%
Rastrigin | 0% | 0% | 67%
Rosenbrock | 0% | 0% | 0%
Ackley | 0% | 100% | 100%Trois exercices pour aller plus loin. Chaque stub est conforme a la règle C.1 (pas d’erreur volontaire).
Les trois exercices balayent les trois questions que ce benchmark laisse ouvertes : la dimension (le levier qui a crevé PSO sur Rastrigin — jusqu’où la malédiction va-t-elle ?), la diversité d’algorithmes (BRO/Bat : le podium d’ABC est-il robuste à un 4e concurrent ?), et l’équité du budget (les trois algorithmes ont-ils consommé le même nombre d’évaluations, et qui gagne quand on l’égalise strictement ?).
Enonce : Etudiez l’effet de la dimension dim sur les trois algorithmes. Testez dim dans {2, 5, 10, 20} sur Rosenbrock (3 seeds). Reportez f moyen par algorithme et par dimension.
Questions : (a) Quel algorithme degrade le moins quand la dimension augmente ? (b) La malédiction de la dimension touche-t-elle les essaims (PSO/ABC) autant que la trajectoire (SA) ?
Indice : Reutilisez le harness de benchmark, remplacez la boucle sur les fonctions par une boucle sur dim. Observez comment f-moyen croit avec dim.
Exercice 1 a completer : effet de la dimension sur Rosenbrock.Enonce : Le twin Python MEALPy compare aussi BRO (Brownian-based Optimization) ou l’algorithme des chauves-souris (Bat Algorithm). Implementez un de ces deux algorithmes from-scratch et ajoutez-le au benchmark.
Étape 1 : Documentez-vous sur BRO ou Bat Algorithm (deplacement brownien / echolocation). Étape 2 : Implementez-le avec la même signature (f, dim, seed) -> (x, f). Étape 3 : Ajoutez-le au harness (4 algos × 4 fonctions × 3 seeds) et identifiez le nouveau gagnant.
Indice : Bat Algorithm = positions + vitesses + frequence/pulse (analogue au sonar), proche de PSO.
Enonce : La comparaison ci-dessus n’est pas totalement equitable : SA et PSO font ~3000 evals, mais ABC en fait ~6000 (phases employee + onlooker). Refaites le benchmark en fixant un budget d’evaluations de fonction identique (ex: 3000 evals pour chaque algorithme) et observez si le classement change.
Questions : (a) A budget egal, quel algorithme est le plus efficace ? (b) SA (peu d’evals mais trajectoire longue) vs essaim (beaucoup d’evals) — qui exploite le mieux un budget fixe ?
Indice : Comptez les evaluations via un compteur global incremente dans chaque fonction. Ajustez les paramètres (iters SA, pop×cycles essaim) pour egaliser le total.
Ce que nous avons appris :
| Concept | Definition |
|---|---|
| No Free Lunch | Aucun algorithme n’est universellement meilleur ; le choix depend du paysage |
| Benchmark | Comparaison empirique multi-fonction multi-seed pour guider le choix |
| Taux de succes | Frequence de convergence a l’optimum (fiabilite cross-seed) |
| Paysage | Forme de la fonction (unimodal/multimodal/vallée) — determine la difficulte |
Synthese des trois métaheuristiques du marathon :
| Algorithme | Stratégie | Force typique | Faiblesse typique |
|---|---|---|---|
| SA (t1) | Trajectoire + Metropolis | optima locaux isoles | essaim, vallée etroite |
| PSO (t2) | Essaim + vitesse sociale | unimodal, vallée douce | tuning (w, c1, c2) |
| ABC (t3) | Essaim a rôles + scout | multimodal, robustesse | vallée etroite (scout) |
Lecon finale : le choix d’une métaheuristique est un choix empirique, guide par la nature du problème et valide par un benchmark. Comprendre les trois dynamiques (trajectoire Metropolis, vitesse sociale, rôles + abandon) — l’objet des tranches 1-3 — est ce qui permet de choisir intelligemment.
Implementation from-scratch, BCL .NET seule, 0 NuGet. Capstone du marathon Search-11 (#4956). Twin du notebook Python MEALPy Search-11-Metaheuristics.