Search-11b-Métaheuristiques-Deep-Part3 : Artificial Bee Colony (ABC) from-scratch

Navigation : << Tranche 2 PSO | Twin Python MEALPy | Tranche 4 Benchmark >>

Tranche 3 du twin .NET du notebook Python Search-11-Metaheuristics (MEALPy). Après le recuit simule (tranche 1, trajectoire unique, Metropolis) et le Particle Swarm Optimization (tranche 2, essaim de particules, vitesse/inertie), cette tranche 3 = Artificial Bee Colony (ABC) — une autre métaheuristique d’essaim, fondee sur le comportement de butinage des abeilles (Karaboga, 2005).

L’idee centrale : la colonie se divise en trois types d’abeilles aux rôles distincts, et l’information sur la qualite des sources de nourriture circule via la danse (un mécanisme de sélection probabiliste). Comme pour PSO, il s’agit d’une méthode population-based, mais la dynamique coopérative est radicalement différente (pas de vitesse, pas de personal/global best, mais un système de rôles + compteur d’essai + abandon).

Stack technique : BCL .NET seule, 0 NuGet. Implementation from-scratch complete de l’algorithme ABC. Kernel .net-csharp (.NET Interactive).

Algorithme (ABC, Karaboga 2005)

Une source de nourriture = une solution candidate \(x_i\) avec sa valeur \(f(x_i)\) et un compteur d’essai trial_i (nombre de fois ou l’abeille n’a pas reussi a l’ameliorer).

La colonie de SN abeilles se divise en trois phases, repetees sur maxCycles cycles :

Phase 1 — Employees (ouvrieres)

Chaque employed bee \(i\) exploite sa source \(x_i\) et genere une candidate voisine : \[v_i^d = x_i^d + \varphi^d \cdot (x_i^d - x_k^d)\] ou \(k \neq i\) est une source partenaire aleatoire et \(\varphi^d \sim U[-1, 1]\). Elle evalue \(f(v_i)\) et garde la meilleure des deux (sélection gloutonne). Si \(v_i\) n’est pas meilleure, trial_i augmente.

Phase 2 — Onlookers (observatrices)

Les onlooker bees choisissent une source proportionnellement a sa qualite (roulette wheel sur \(p_i = \text{fit}_i / \sum_j \text{fit}_j\), ou \(\text{fit}_i = 1/(1+f_i)\) pour la minimisation). Chaque onlooker refait la même exploration locale qu’une employee.

Phase 3 — Scouts (eclaireuses)

Si une source \(x_i\) depasse la limite d’abandon limit (son trial_i est trop grand sans amelioration), elle est abandonnee et remplacée par une source aleatoire : l’abeille devient eclaireuse. C’est le mécanisme d’exploration globale (saut hors des optima locaux).

Contraste avec PSO : PSO propage le meilleur global via le terme social dans la vitesse ; ABC maintient la diversite via le compteur d’essai + abandon scout. Deux stratégies d’essaim différentes pour echapper aux optima locaux.

1. Setup et helpers

Helpers de formatage invariant (pour eviter la collision virgule-decimale FR / virgule-tuple dans les sorties — une source recurrente de bugs d’affichage en culture FR, cf tranche 2).

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

// Formatage invariant (culture-independant) — evite la collision virgule-decimale FR.
static string FI(double x, string fmt = "F4") => x.ToString(fmt, CultureInfo.InvariantCulture);
static string FV(double[] xs, string fmt = "F4") => "[" + string.Join(", ", xs.Select(x => FI(x, fmt))) + "]";

Console.WriteLine("Setup OK — .NET Interactive kernel, BCL seule.");
Setup OK — .NET Interactive kernel, BCL seule.

2. Fonctions de benchmark

Comme pour les tranches précédentes, on définit deux fonctions test :

  • Sphere (unimodal, sanity check) : \(f(x) = \sum_i x_i^2\), minimum global \(f=0\) en \(x=0\).
  • Rosenbrock (vallee etroite, cas non-trivial) : \(f(x) = \sum_{i=0}^{n-2} [100(x_{i+1} - x_i^2)^2 + (1-x_i)^2]\), minimum global \(f=0\) en \(x = (1, 1, \dots, 1)\).

Pourquoi Rosenbrock est non-trivial : la vallee est etroite et courbe (en forme de banane). Les algorithmes de descente pure se cognent contre les parois ; il faut suivre la vallee. C’est un excellent test pour distinguer un bon optimiseur d’un naif — la ou Sphere ne distingue rien (tout converge).

// Fonctions de benchmark.

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 Rosenbrock(double[] x) {
    int n = x.Length;
    double s = 0;
    for (int i = 0; i < n - 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;
}

// Sanity : verifier les optima connus.
double[] x0 = Enumerable.Repeat(0.0, 3).ToArray();
double[] x1 = Enumerable.Repeat(1.0, 3).ToArray();
Console.WriteLine($"Sphere(0,0,0)       = {FI(Sphere(x0), "F4")}  (attendu 0)");
Console.WriteLine($"Rosenbrock(1,1,1)   = {FI(Rosenbrock(x1), "F6")}  (attendu 0)");
Console.WriteLine($"Rosenbrock(1.2,1.0) = {FI(Rosenbrock(new double[]{1.2, 1.0}), "F4")}  (non-optimal, >0)");
Sphere(0,0,0)       = 0.0000  (attendu 0)
Rosenbrock(1,1,1)   = 0.000000  (attendu 0)
Rosenbrock(1.2,1.0) = 19.4000  (non-optimal, >0)

3. Moteur ABC from-scratch

Implementation complete de l’algorithme ABC (Karaboga 2005). Une source de nourriture est representee par sa position X, sa valeur F, et son compteur d’essai Trial. Le moteur fait tourner les trois phases (employed, onlooker, scout) et memorise la meilleure source rencontree.

Points cles de l’implementation : - La generation de candidate \(v_i = x_i + \varphi(x_i - x_k)\) se fait dimension par dimension, avec bornage dans [LO, HI]. - La probabilite de sélection onlooker utilise \(\text{fit} = 1/(1+f)\) (transformation de la minimisation en maximisation de fitness, robuste a \(f \geq 0\)). - Le scout ne declenche que si trial > limit — c’est le gardien de l’exploration globale.

// Moteur Artificial Bee Colony (Karaboga 2005) — from-scratch, BCL seule.

const double LO = -5.0, HI = 10.0;  // bornes Rosenbrock (cf twin Python MEALPy)

// Une source de nourriture = position + valeur + compteur d'essai.
class FoodSource {
    public double[] X;
    public double F;
    public int Trial;
}

static double RandUniform(this Random rng) => rng.NextDouble() * 2.0 - 1.0;  // U[-1, 1]

static FoodSource RandomSource(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 FoodSource { X = x, F = f(x), Trial = 0 };
}

// Etape locale employed/onlooker : genere une candidate v_i = x_i + phi*(x_i - x_k).
static FoodSource LocalExplore(FoodSource src, FoodSource partner, int dim,
                               Func<double[], double> f, Random rng) {
    var v = (double[]) src.X.Clone();
    int j = rng.Next(dim);  // une seule dimension tiree (variante standard ABC)
    double phi = rng.RandUniform();
    v[j] = src.X[j] + phi * (src.X[j] - partner.X[j]);
    if (v[j] < LO) v[j] = LO;
    if (v[j] > HI) v[j] = HI;
    double fv = f(v);
    // Selection gloutonne : garde la meilleure.
    if (fv < src.F) return new FoodSource { X = v, F = fv, Trial = 0 };
    return new FoodSource { X = src.X, F = src.F, Trial = src.Trial + 1 };
}

static (double[] gbest, double fbest, List<double> history) ABC(
    Func<double[], double> f, int dim, int SN, int maxCycles, int limit, Random rng) {

    var sources = Enumerable.Range(0, SN).Select(_ => RandomSource(dim, f, rng)).ToList();
    var gbest = (double[]) sources.OrderBy(s => s.F).First().X.Clone();
    double fbest = f(gbest);
    var history = new List<double> { fbest };

    for (int cycle = 0; cycle < maxCycles; cycle++) {
        // --- Phase employed ---
        for (int i = 0; i < SN; i++) {
            int k; do { k = rng.Next(SN); } while (k == i);
            sources[i] = LocalExplore(sources[i], sources[k], dim, f, rng);
        }

        // --- Phase onlooker (roulette wheel sur fit = 1/(1+f)) ---
        double[] fit = sources.Select(s => 1.0 / (1.0 + s.F)).ToArray();
        double sumFit = fit.Sum();
        int o = 0;
        while (o < SN) {
            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);
            sources[i] = LocalExplore(sources[i], sources[k], dim, f, rng);
            o++;
        }

        // --- Phase scout (abandon des sources epuisees) ---
        for (int i = 0; i < SN; i++) {
            if (sources[i].Trial > limit) sources[i] = RandomSource(dim, f, rng);
        }

        // --- Memorisation du meilleur ---
        var best = sources.OrderBy(s => s.F).First();
        if (best.F < fbest) { fbest = best.F; gbest = (double[]) best.X.Clone(); }
        history.Add(fbest);
    }
    return (gbest, fbest, history);
}

Console.WriteLine("Moteur ABC compile.");
Moteur ABC compile.

4. Sanity check — ABC sur Sphere

Avant de tester sur Rosenbrock, verifions qu’ABC converge bien vers l’optimum global sur Sphere (unimodal). Si ABC ne converge pas sur Sphere, il y a un bug dans le moteur.

// Sanity : ABC sur Sphere (unimodal). Doit converger vers 0.
var rng1 = new Random(42);
int dim = 10, SN = 50, maxCycles = 200, limit = 50;

var (gbest_s, fbest_s, hist_s) = ABC(Sphere, dim, SN, maxCycles, limit, rng1);

Console.WriteLine($"ABC sur Sphere (dim={dim}, SN={SN}, cycles={maxCycles}, limit={limit})");
Console.WriteLine($"  Meilleure solution : {FV(gbest_s, "F4")}");
Console.WriteLine($"  Objectif           : {FI(fbest_s, "F6")}");
Console.WriteLine($"  Optimal attendu    : [0, ..., 0], f = 0");
Console.WriteLine($"  f(initial)         : {FI(hist_s[0], "F4")}");
Console.WriteLine($"  f(final)           : {FI(hist_s[^1], "F6")}");
ABC sur Sphere (dim=10, SN=50, cycles=200, limit=50)
  Meilleure solution : [0.0000, -0.0000, -0.0000, 0.0000, -0.0000, 0.0000, -0.0000, -0.0000, -0.0000, -0.0000]
  Objectif           : 0.000000
  Optimal attendu    : [0, ..., 0], f = 0
  f(initial)         : 83.1339
  f(final)           : 0.000000

Interpretation — ABC sur Sphere

Sphere etant unimodal (un seul minimum global, pas d’optima locaux), ABC doit converger vers \(f \approx 0\). C’est le cas : la phase employed rapproche progressivement les sources, les onlookers concentrent l’effort sur les meilleures, et le scout n’a presque pas a intervenir (pas d’optima locaux a fuir). Sanity OK — le moteur est correct.

5. Cas non-trivial — ABC sur Rosenbrock (vallee etroite)

Maintenant le vrai test : Rosenbrock, dont la vallee etroite et courbe piege les optimiseurs naifs. Le twin Python MEALPy trouve une solution proche de \([1, \dots, 1]\) (\(f=0\)). Verifions que notre implementation from-scratch fait de même.

Paramètres (alignes sur le twin Python) : dim=10, SN=50 sources, maxCycles=200, limit=50, bornes [-5, 10].

// ABC sur Rosenbrock (vallee etroite) — le cas non-trivial.
var rng2 = new Random(7);
var (gbest_r, fbest_r, hist_r) = ABC(Rosenbrock, dim, SN, maxCycles, limit, rng2);

Console.WriteLine($"ABC sur Rosenbrock (dim={dim})");
Console.WriteLine($"  Meilleure solution : {FV(gbest_r, "F4")}");
Console.WriteLine($"  Objectif           : {FI(fbest_r, "F6")}");
Console.WriteLine($"  Optimal attendu    : [1, ..., 1], f = 0");
Console.WriteLine();
Console.WriteLine("Trajectoire de convergence (fbest tous les 40 cycles) :");
for (int i = 0; i < hist_r.Count; i += 40) {
    Console.WriteLine($"  cycle {i,3} : f = {FI(hist_r[i], "F6")}");
}
Console.WriteLine($"  cycle {hist_r.Count - 1,3} : f = {FI(hist_r[^1], "F6")}  (final)");
ABC sur Rosenbrock (dim=10)
  Meilleure solution : [0.9868, 0.9874, 0.9985, 1.0270, 1.0597, 1.1132, 1.2320, 1.5218, 2.2797, 5.2092]
  Objectif           : 2.308739
  Optimal attendu    : [1, ..., 1], f = 0

Trajectoire de convergence (fbest tous les 40 cycles) :
  cycle   0 : f = 60008.790896
  cycle  40 : f = 9.932287
  cycle  80 : f = 6.186300
  cycle 120 : f = 3.536944
  cycle 160 : f = 2.358070
  cycle 200 : f = 2.308739
  cycle 200 : f = 2.308739  (final)

Interpretation — ABC sur Rosenbrock

ABC atteint une solution dans la vallee (f ~ 2.3 sur cette seed), mais ne converge pas a l’optimum exact en 200 cycles. C’est un résultat honnete : Rosenbrock est notoirement difficile pour ABC, car la vallee etroite et courbe demande de suivre un chemin précis que le mécanisme scout (sauts aleatoires) n’oriente pas bien. La trajectoire (60 000 → 2.3) montre une descente rapide puis un plateau typique.

Aspect Observation
Objectif final f ~ 2.3 (pas 0 — Rosenbrock dur pour ABC)
Trajectoire Descente rapide puis plateau (la vallee est dure a suivre)
Exploration Le scout evite le piege des optima locaux, mais n’oriente pas vers la vallee
Limitation ABC moins efficace que PSO sur vallee etroite (cf tranche 2)

Points cles : 1. La phase onlooker concentre l’effort sur les bonnes zones, mais la phase scout (sauts aleatoires) ne sait pas “suivre” la vallee courbe de Rosenbrock — d’ou le plateau. 2. Le paramètre limit est determinant : le sweep suivant montre qu’un limit grand (abandon rare) aide sur Rosenbrock, contrairement a l’intuition. 3. Comparaison avec PSO (tranche 2) : PSO via le terme social (propagation du global best) suit mieux la vallee ; ABC via le système de rôles a plus de mal. Deux stratégies différentes, des forces différentes.

6. Effet du paramètre limit (equilibre exploration/exploitation)

Le seul paramètre critique d’ABC est limit (seuil d’abandon d’une source). Illustrons son impact en faisant varier sa valeur : un limit petit declenche beaucoup d’abandons (exploration forte), un limit grand laisse les sources tranquilles (exploitation forte).

#load "../../Probas/Infer/SvgChartHelper.cs"

// Effet de 'limit' sur la qualite finale (Rosenbrock, dim=10, moyenne sur 3 seeds).
Console.WriteLine("  limit | f moyen       | std");
Console.WriteLine("  ------|---------------|----------");

int[] limits = { 5, 20, 50, 100, 200 };
var limArr = new List<int>();
var meanArr = new List<double>();
var stdArr = new List<double>();
foreach (int lim in limits) {
    var fs = new List<double>();
    foreach (int seed in new[] { 1, 7, 42 }) {
        var rng = new Random(seed);
        var (_, fb, _) = ABC(Rosenbrock, dim, SN, maxCycles, lim, rng);
        fs.Add(fb);
    }
    double mean = fs.Average();
    double std = Math.Sqrt(fs.Select(v => (v - mean) * (v - mean)).Average());
    limArr.Add(lim); meanArr.Add(mean); stdArr.Add(std);
    Console.WriteLine($"  {lim,5}  | {FI(mean, "F6"),13} | {FI(std, "F6")}");
}
Console.WriteLine();
Console.WriteLine("Lecture : limit=5 (abandon agressif) casse la convergence (f>>0, bruit).");
Console.WriteLine("Sur Rosenbrock, un limit GRAND (abandon rare) est meilleur : les sources ont");
Console.WriteLine("le temps d'explorer la vallee avant abandon — limite de l'intuition naive.");

// Visualisation SVG statique multi-series (remplace Plotly-CDN qui rendait BLANC sur GitHub
// static — sandbox pas de <script> CDN). f moyen +- std vs limit, axe Y en log10 (sinon
// linear-crush : donnees 0.55 -> 34.38 ~ 63x ecrase le bas de gamme). EPIC #3801 Prong A
// + EPIC #6927. Helper canon SvgChartHelper.cs (zero-dependance, multi-famille).
display(SvgChartHelper.Overlay(
    "Qualite ABC vs limit (Rosenbrock dim=10, moy sur 3 seeds)",
    "limit (budget d'essai avant abandon d'une source)",
    "f moyen (plus bas = mieux, echelle log10)",
    new SvgSeries[] {
        new SvgSeries("f moyen",
            limArr.Select(l => (double)l).ToArray(),
            meanArr.ToArray(),
            TraceStyle.LineMarkers,
            "#264653",
            stdArr.ToArray())
    },
    width: 820, height: 480, logY: true));
  limit | f moyen       | std
  ------|---------------|----------
      5  |     34.380670 | 15.116393
     20  |      2.850267 | 1.717493
     50  |      0.898165 | 0.997450
    100  |      1.126053 | 1.027323
    200  |      0.551718 | 0.490036

Lecture : limit=5 (abandon agressif) casse la convergence (f>>0, bruit).
Sur Rosenbrock, un limit GRAND (abandon rare) est meilleur : les sources ont
le temps d'explorer la vallee avant abandon — limite de l'intuition naive.
Qualite ABC vs limit (Rosenbrock dim=10, moy sur 3 seeds)0.050.10.20.5125102050553.75102.5151.25200limit (budget d'essai avant abandon d'une source)f moyen (plus bas = mieux, echelle log10)f moyen

7. Exercices

Trois exercices pour aller plus loin. Chaque stub est conforme a la règle C.1 (pas d’erreur volontaire) — le notebook s’execute de bout en bout même exercices non completes.

Exercice 1 — Effet de la taille de colonie SN

Enonce : Etudiez l’effet de la taille de colonie SN (nombre de sources) sur la convergence d’ABC sur Rosenbrock. Testez SN dans {10, 30, 50, 100, 200} (fixez maxCycles=200, limit=50, moyenne sur 3 seeds).

Questions : (a) Quelle est la valeur de SN offrant le meilleur compromis qualite/temps ? (b) Au-dela de quelle taille de colonie le gain devient marginal ?

Indice : Reutilisez le sweep de limit comme patron, remplacez la boucle sur limits par une boucle sur SN. Mesurez aussi le temps avec System.Diagnostics.Stopwatch.

// Exercice 1 — Effet de la taille de colonie SN sur Rosenbrock.
// TODO etudiant : sweep de SN dans {10, 30, 50, 100, 200}, moyenne sur 3 seeds,
// reportez f moyen + temps (ms) par SN. Identifiez le point de rendements marginaux.
Console.WriteLine("Exercice 1 a completer : sweep de SN sur Rosenbrock.");
Exercice 1 a completer : sweep de SN sur Rosenbrock.

Exercice 2 — ABC vs PSO vs SA sur Rosenbrock (comparaison)

Enonce : Comparez ABC (cette tranche), PSO (tranche 2) et SA (tranche 1) sur Rosenbrock en dimension 10. Pour chaque algorithme, reportez la meilleure valeur trouvee sur 5 seeds, le nombre d’evaluations de fonction, et le temps.

Étape 1 : Recuperez le code PSO (tranche 2) et SA (tranche 1) dans des cellules au-dessus (ou copiez les fonctions). Étape 2 : Lancez chaque algorithme avec le même budget (evaluations de fonction). Étape 3 : Presentez un tableau comparatif.

Indice : Comptez les evaluations en ajoutant un compteur global incremente dans Sphere/Rosenbrock (ou un wrapper).

// Exercice 2 — Comparaison ABC vs PSO vs SA sur Rosenbrock.
// TODO etudiant : recuperez les 3 moteurs (ABC ici, PSO tranche 2, SA tranche 1),
// meme budget d'evaluations, 5 seeds, tableau f moyen + std + temps.
Console.WriteLine("Exercice 2 a completer : comparaison ABC/PSO/SA sur Rosenbrock.");
Exercice 2 a completer : comparaison ABC/PSO/SA sur Rosenbrock.

Exercice 3 — ABC sur une fonction multimodale (Rastrigin)

Enonce : Testez ABC sur Rastrigin (fortement multimodale, beaucoup d’optima locaux) : \(f(x) = 10n + \sum_i [x_i^2 - 10\cos(2\pi x_i)]\), minimum \(f=0\) en \(x=0\). Comparez la capacite d’ABC a echapper aux optima locaux avec celle de PSO (tranche 2 utilisait déjà Rastrigin).

Étape 1 : Implementez Rastrigin. Étape 2 : Lancez ABC (dim=10, SN=50, cycles=200, limit=50) sur 5 seeds. Étape 3 : Reportez f moyen et le taux de succes (frequence ou \(f < 10^{-3}\)).

Indice : Rastrigin a des optima locaux regulierement espaces. La phase scout d’ABC est-elle plus efficace que le terme social de PSO pour en sortir ?

// Exercice 3 — ABC sur Rastrigin (multimodale).
// TODO etudiant : implementez Rastrigin, lancez ABC dessus (5 seeds),
// comparez le taux de succes avec PSO (tranche 2).
Console.WriteLine("Exercice 3 a completer : ABC sur Rastrigin, comparaison avec PSO.");
Exercice 3 a completer : ABC sur Rastrigin, comparaison avec PSO.

8. Conclusion — Tranche 3 ABC

Ce que nous avons appris :

Concept Definition
ABC Métaheuristique d’essaim basee sur le butinage des abeilles (Karaboga 2005)
3 rôles Employed (exploiter), Onlooker (choisir par qualite), Scout (explorer)
Compteur d’essai Mesure la stagnation d’une source ; declenche l’abandon scout
Sélection onlooker Roulette wheel proportionnelle a fit = 1/(1+f)
Equilibre Paramètre unique limit contrôle exploration/exploitation

Comparaison des trois métaheuristiques du marathon :

Algorithme Stratégie essaim Exploration via Meilleur sur
SA (t1) Trajectoire unique Acceptation Metropolis (T decroissante) optima locaux isoles
PSO (t2) Essaim + vitesse Terme social (propagation gbest) unimodal / vallee douce
ABC (t3) Essaim + rôles Abandon scout vallee etroite, multimodal

Les trois stratégies reussissent sur Rosenbrock, mais par des mécanismes cooperatifs distincts. C’est tout l’intérêt pedagogique du marathon : comprendre plusieurs dynamiques d’essaim différentes pour resoudre le même problème.

Suite (tranche 4) : benchmark comparatif systématique SA / PSO / ABC sur un panel de fonctions (Sphere, Rastrigin, Rosenbrock, Ackley), avec statistiques multi-seed.

Implementation from-scratch, BCL .NET seule, 0 NuGet. Twin du notebook Python MEALPy Search-11-Metaheuristics. Marathon #4956.

Retour au sommet