Algorithmes d'optimisation de la population : Colonie d'Abeilles Artificielles (ABC)

Sommaire

1. Introduction
2. Description de l'algorithme
3. Version modifiée
4. Résultats des tests
   

1. Introduction

Les insectes sociaux sont des créatures hautement évoluées qui réalisent de nombreuses tâches complexes effectuées par de nombreux insectes seuls. La communication, la construction de nids complexes, le contrôle de l'environnement, la protection et la division du travail ne sont que quelques-uns des comportements que les abeilles ont adoptés pour prospérer dans les colonies sociales.
Les abeilles appartiennent à des essaims d’individus et démontrent des capacités extraordinaires pour trouver des solutions optimales. Dans la nature, elles trouvent des grappes de fleurs pour récolter le nectar et le pollen près de la ruche. Le rayon de recherche peut même parfois augmenter jusqu'à plusieurs kilomètres. Les abeilles qui reviennent rapportent leurs découvertes à l'aide d'une danse improvisée.

À première vue, cela semble impossible, mais elles sont capables de se transmettre des informations sur la position géographique par le biais de mouvements rythmiques. En fonction de l'intensité de la danse de leurs congénères, les abeilles tirent des conclusions sur le nombre de fleurs et la quantité estimée de nectar à un point précis. Plus il y a de nourriture potentielle, plus la danse est active. Ce phénomène inhabituel a été découvert au milieu du 20e siècle par le chercheur sur les insectes Karl von Frisch.

Pendant de nombreuses années, les méthodes de recherche des abeilles ont été étudiées exclusivement par des biologistes. Cependant, l'intérêt pour l'application du comportement en essaim dans le développement de nouveaux algorithmes d'optimisation augmentait. En 2005, le professeur Dervis Karaboga s'est intéressé aux résultats de la recherche. Il a publié un article scientifique et a été le premier à décrire le modèle d'intelligence en essaim principalement inspiré de la danse des abeilles. Le modèle a été appelé la colonie d'abeilles artificielles.

2. Description de l'algorithme

Il existe de nombreuses implémentations d'une colonie d'abeilles artificielles, différant dans les principes de gestion des abeilles dans une ruche et dans les règles d'exploration de la zone. Dans cet article, je parlerai de mon interprétation de la version classique de l'algorithme.

L'idée de l'algorithme est basée sur le comportement des abeilles lorsqu'elles recherchent des endroits où elles peuvent trouver le plus de nectar possible. Toutes les abeilles sortent tout d’abord de la ruche dans une direction aléatoire, agissant comme des éclaireuses et essayent de trouver des zones où il y a du nectar. Les abeilles retournent ensuite à la ruche et, d'une manière spéciale, disent aux autres où et combien de nectar elles ont trouvé.

Les abeilles ouvrières sont envoyées dans les zones trouvées. Plus il y a de nectar supposé dans cette zone, plus les abeilles volent dans cette direction. Les éclaireurs s'envolent à nouveau pour chercher d'autres zones, mais déjà à proximité des zones trouvées. Toutes les abeilles sont ainsi divisées en 2 types : les abeilles ouvrières collectant le nectar et les abeilles éclaireuses explorant de nouvelles zones. Les zones de collecte de nectar ont une valeur correspondant à la quantité de nectar qu'elles contiennent. Les régions de rang inférieur sont déplacées par rapport à une région de rang supérieur le long d'une ligne passant par les centres des régions.

Schématiquement, la répartition des abeilles ouvrières par région peut être visualisée sur la figure 1 :

Fig. 1 : Le nombre d'abeilles dans les zones en fonction du rang des zones

La zone 1 a un rang plus élevé, elle contient le plus de nectar, donc plus d'abeilles auront tendance à y voler. Par le nombre d'abeilles, nous pouvons déterminer visuellement que la zone 4 a le rang (la valeur) le plus bas. Des informations sur la valeur de chaque zone sont rapportées par les abeilles sous la forme d'une danse spéciale. Chaque ruche a sa propre danse, dans laquelle la direction et la quantité de nectar dans la zone sont programmées.

Supposons que l'emplacement de l'extremum global est la zone où il y a le plus de nectar et qu'il n'y a qu'une seule zone de ce type. Il y a du nectar dans d'autres endroits, mais en moindre quantité. Les abeilles vivent dans un espace multidimensionnel, où chaque coordonnée représente un paramètre de la fonction à optimiser. La quantité de nectar trouvée est la valeur de la fonction objectif à ce stade si nous recherchons un maximum global. Si on cherche un minimum global, alors il suffit de multiplier la fonction objectif par -1.

Étant donné que les zones de collecte de nectar ont une certaine valeur, seule la zone avec le rang le plus élevé a le droit de se déplacer (décalage central) vers le point avec la plus forte concentration de nectar. Les zones de rang inférieur seront déplacées vers le centre de la concentration la plus élevée et vérifiées pour l'intersection avec une zone de rang supérieur. De cette manière, la concentration d'abeilles dans une petite zone étroite n'est pas autorisée et l'espace de recherche est desservi par les abeilles ouvrières aussi efficacement que possible, empêchant ainsi l'épuisement de la source de nourriture. En termes d'optimisation, cela élimine ou minimise le blocage dans les extrema locaux. Une fois que les zones sont dispersées et déplacées les unes par rapport aux autres le long de la chaîne de classement vers leurs optimums, leurs voisinages seront également étudiés par des abeilles éclaireuses.

De nombreux apiculteurs recommandent d'envoyer des abeilles éclaireuses dans des zones aléatoires de l'espace de recherche. Mais mon expérience montre que la valeur pratique d'un tel "scoutisme" est proche de zéro et n'est utile que pour 1 et 2 dimensions. En d'autres termes, si nous parlons d'espaces multidimensionnels, les degrés de liberté augmentent géométriquement. Et il est incroyablement difficile de tomber accidentellement sur une source de nectar plus précieuse. Les ressources de la ruche ne seront alors que gaspillées. Il est beaucoup plus utile d'envoyer des éclaireurs aux alentours des zones de recherche déjà connues pour que les coordonnées ne soient pas dispersées, mais concentrées spécifiquement dans les zones d'éventuelles sources de nectar.

Si les zones se croisent, il faut décaler le centre pour que les zones ne touchent que les bordures. C’est ce qui est illustré à la figure 2 :

Fig. 2 : La zone ayant un rang inférieur doit être décalée

Le rang des zones n'est pas défini de manière rigide, mais est formé de manière dynamique. Les découvertes d'abeilles éclaireuses seront affectées à la zone à proximité de laquelle elles ont volé. Dans le cas où une source de nourriture plus précieuse est découverte, le centre de la zone y sera déplacé. Il pourrait même devenir le nouveau meilleur centre de collecte de nectar. Les zones restantes seront maintenant décalées par rapport à celle-ci. En d'autres termes, elles seront décalées par rapport à elle le long de la chaîne de rang.

Le mode de transmission de l'information, que l'on appelle la danse des abeilles, est un élément essentiel de la stratégie de la ruche dans son ensemble. Il est nécessaire de répartir le plus rationnellement possible les ressources disponibles de la ruche pour les zones de transformation, de sorte que le nombre d'abeilles envoyées doit être proportionnel à la valeur de la zone. Cela signifie qu'un nombre égal d'abeilles sera envoyé dans des zones de valeur égale.

Passons maintenant à l'algorithme lui-même. Voici les étapes d'exécution :

1. Toutes les abeilles volent au hasard le long de l'espace de recherche en éclaireurs.
2. Mesure de la quantité de nectar reçue de chaque abeille.
3. Tri des abeilles.
4. Attribution des zones en fonction des informations sur la quantité de nectar obtenues des abeilles.
5. Envoi des abeilles ouvrières dans la région. Plus il y a de nectar dans la zone, plus d’abeilles seront envoyées.
6. Envoi d'abeilles éclaireuses à proximité d'une zone choisie au hasard.
   
7. Mesure de la quantité de nectar reçue de chaque abeille.
8. Classement des zones selon la quantité de nectar.
   
9. Répétition depuis le point 4 jusqu'à ce que le critère d'arrêt soit rempli.

Pour faciliter la perception visuelle, faisons un schéma fonctionnel de l'algorithme de la figure 3 :

Fig. 3 : Schéma de l'algorithme

Décrivons plus en détail le code de l'algorithme Bee Colony.

Une abeille est une unité logique élémentaire de base de l'algorithme. Elle peut être décrite par une structure. Comme vous vous en souvenez peut-être, l'emplacement d'une abeille est défini par des coordonnées, une affiliation avec la zone où le nectar a été collecté et la quantité de nectar. Les abeilles de la ruche peuvent donc être représentées par un tableau. Chacune est accessible par son index.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bee
{
  double c []; //coordinates
  int    aInd; //area index
  double n;    //nectar
};
//——————————————————————————————————————————————————————————————————————————————

La deuxième unité logique, plus grande, est la zone de collecte du nectar. Elle est définie par le centre, le point de la plus grande concentration de nectar et la quantité de nectar qui détermine la valeur de la zone. Dans la zone du rang le plus élevé (la première de la liste), les coordonnées du centre et la plus forte concentration de nectar coïncident. Pour les zones du deuxième rang et des rangs inférieurs de la liste, elles peuvent ne pas correspondre, car elles ont été décalées. L'initialisation de la zone se termine par la réinitialisation de l'indicateur de quantité de nectar et par la distribution des coordonnées au nombre correspondant de paramètres de la fonction optimisée.

//——————————————————————————————————————————————————————————————————————————————
struct S_Area
{
  void Init (int coordinatesNumber)
  {
    n = -DBL_MAX;

    ArrayResize (cC, coordinatesNumber);
    ArrayResize (cB, coordinatesNumber);
  }

  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Décrivons la danse des abeilles comme une structure dont le tableau correspondra au nombre de zones.

//——————————————————————————————————————————————————————————————————————————————
struct S_BeeDance
{
  double start;
  double end;
};
//——————————————————————————————————————————————————————————————————————————————

Je décrirai la ruche comme une classe définissant les zones de recherche, les abeilles, les meilleures coordonnées et la plus grande quantité de nectar trouvée dans toutes les itérations. Toutes les méthodes nécessaires pour trier les abeilles et les zones, ainsi que pour déplacer les abeilles et les zones les unes par rapport aux autres seront aussi définies ici. Ici, nous pouvons voir les déclarations de fonctions déjà familières des algorithmes précédents : génération des nombres aléatoires uniformément répartis, mise à l'échelle d’une plage et choix d’un nombre dans une plage avec un pas.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ABC //Bees Hive
{
  //============================================================================
  public: S_Area areas     []; //nectar collection areas
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Bee  bees      []; //all the bees of the hive
  public: double cB        []; //best coordinates
  public: double nB;           //nectar of the best coordinates

  public: void InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP); //scout area radius

  public: void TasksForBees ();
  public: void CollectingNectar ();

  //============================================================================
  private: void   BeeFlight      (double &cC [] , S_Bee &bee);
  private: void   ScoutBeeFlight (double &cC [] , S_Bee &bee);
  private: void   MarkUpAreas    ();
  private: void   SortingBees    ();
  private: void   SortingAreas   ();
  private: double SeInDiSp       (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI      (double Min, double Max);
  private: double Scale          (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool Revers);

  private: int    coordinates;      //coordinates number
  private: int    beesNumber;       //the number of all bees
  private: int    workerBeesNumber; //worker bees number
  private: int    areasNumber;      //areas number
  private: S_Bee  beesT       [];   //temporary, for sorting
  private: S_Area areasT      [];   //temporary, for sorting
  private: int    indA        [];   //array for indexes when sorting
  private: double valA        [];   //array for nectar values when sorting
  private: int    indB        [];   //array for indexes when sorting
  private: double valB        [];   //array for nectar values when sorting
  private: double areasRadius [];   //radius for each coordinate
  private: double scoutRadius [];   //scout radius for each coordinate

  private: double collectionRadius;   //collection radius
  private: double scoutAreaRadius;    //scout area radius
  private: double hypersphereRadius;  //hypersphere radius
  private: double distHyperspCenters; //distance hyperspheres centers
  private: double scoutHyperspRadius; //scout hypersphere radius
  private: bool   scouting;           //scouting flag

  private: S_BeeDance beeDance [];    //bee dance
};
//——————————————————————————————————————————————————————————————————————————————

Chaque nouvelle optimisation doit nécessairement commencer par une initialisation de classe. La valeur de la quantité de nectar est réinitialisée pour l'ensemble de la ruche, pour les abeilles individuelles et pour les zones.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP)  //scout area radius
{
  MathSrand (GetTickCount ());
  scouting = false;
  nB       = -DBL_MAX;

  coordinates      = coordinatesP;
  beesNumber       = beesNumberP;
  workerBeesNumber = workerBeesNumberP;
  areasNumber      = areasNumberP < 3 ? 3 : areasNumberP;

  collectionRadius = collectionRadiusP; //collection radius
  scoutAreaRadius  = scoutAreaRadiusP;  //scout area radius

  ArrayResize (areas,  areasNumber);
  ArrayResize (areasT, areasNumber);
  for (int i = 0; i < areasNumber; i++)
  {
    areas  [i].Init (coordinates);
    areasT [i].Init (coordinates);
  }

  ArrayResize (beeDance, areasNumber);

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (indA, areasNumber);
  ArrayResize (valA, areasNumber);

  ArrayResize (areasRadius, coordinates);
  ArrayResize (scoutRadius, coordinates);
  for (int i = 0; i < coordinates; i++)
  {
    areasRadius [i] = (rangeMax [i] - rangeMin [i]) * collectionRadius;
    scoutRadius [i] = (rangeMax [i] - rangeMin [i]) * scoutAreaRadius;
  }

  double sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += areasRadius [i] * areasRadius [i];
  hypersphereRadius  = MathSqrt (sqr) * collectionRadius;

  distHyperspCenters = hypersphereRadius * 2.0;

  sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += scoutRadius [i] * scoutRadius [i];
  scoutHyperspRadius = MathSqrt (sqr) * scoutAreaRadius;

  ArrayResize (indB, beesNumber);
  ArrayResize (valB, beesNumber);

  ArrayResize (bees,  beesNumber);
  ArrayResize (beesT, beesNumber);
  for (int i = 0; i < beesNumber; i++)
  {
    ArrayResize (bees  [i].c, coordinates);
    ArrayResize (beesT [i].c, coordinates);
    bees  [i].n = -DBL_MAX;
    beesT [i].n = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

La méthode de classe la plus simple est la distribution des tâches aux abeilles. Tout est simple ici. Si les zones n'ont pas encore été explorées, alors on réinitialise la valeur du nectar pour toute la ruche et on lance le marquage de zone. Nous appelons la méthode à chaque itération jusqu'à ce que la valeur de la fonction de fitness soit obtenue.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::TasksForBees ()
{
  if (!scouting)
  {
    nB = -DBL_MAX;
  }
  MarkUpAreas ();
}
//——————————————————————————————————————————————————————————————————————————————

La deuxième méthode publique est appelée à chaque itération. Le lancement doit être effectué après avoir obtenu la valeur de la fonction fitness. Dans ce cas, si l'exploration n'a pas encore été effectuée, on trie les abeilles par la valeur du nectar et on copie les coordonnées et la quantité de nectar des premières abeilles de la liste dans les zones correspondantes. Si l'exploration a déjà eu lieu, nous copions les coordonnées et la quantité de nectar dans la zone où le nectar a été collecté si les résultats se sont améliorés. Il faut également mettre à jour les meilleurs résultats pour toute la ruche.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::CollectingNectar ()
{
  if (!scouting)
  {
    SortingBees ();

    for (int a = 0; a <areasNumber; a++)
    {
      ArrayCopy (areas [a].cB, bees [a].c, 0, 0, WHOLE_ARRAY);
      areas [a].n = bees [a].n;
    }

    scouting = true;
  }
  else
  {
    //transfer the nectar to the hive---------------------------------------------
    for (int b = 0; b < beesNumber; b++)
    {
      if (bees [b].n > areas [bees [b].aInd].n)
      {
        ArrayCopy (areas [bees [b].aInd].cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        areas [bees [b].aInd].n = bees [b].n;
      }

      if (bees [b].n > nB)
      {
        ArrayCopy (cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        nB = bees [b].n;
      }
    }

    SortingAreas ();
  }
}
//——————————————————————————————————————————————————————————————————————————————

La méthode MarkUpAreas() mérite d'être étudiée en détail. Décomposons le code en plusieurs parties.

Avant que toutes les zones ne soient explorées et qu'il n'y ait aucune information sur la recherche de fleurs pour récolter le nectar, nous enverrons toutes les abeilles pour effectuer une exploration préliminaire. A ce stade, toutes les abeilles jouent le rôle d'éclaireuses. Puisqu'il n'y a aucune information sur le nectar, nous envoyons des éclaireurs dans des directions aléatoires, générant des nombres aléatoires uniformément répartis sur la plage de coordonnées.

//if the areas is not scouting - send all the bees to scouting----------------
if (!scouting)
{
  for (int b = 0; b < beesNumber; b++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      bees [b].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      bees [b].c [c] = SeInDiSp  (bees [b].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Une fois les zones explorées, il est nécessaire de copier les coordonnées de la concentration maximale de nectar au centre de la zone. En d'autres termes, il est nécessaire de déplacer la zone vers un meilleur endroit. Après avoir effectué cette action, nous devons nous assurer que la zone ne croise pas la zone d'un rang supérieur. Nous pouvons vérifier l'intersection des zones en mesurant la distance entre leurs centres. Les zones se croisent si la distance entre les centres est inférieure à 2 rayons (c’est l'un des paramètres de l'algorithme). Si une intersection est détectée, la zone est transférée vers un point à une distance de 2 rayons, et les coordonnées du meilleur résultat obtenu (les coordonnées de la concentration maximale de nectar) restent au même endroit. Les zones sont donc constamment en mouvement. Les meilleures zones obligent à déplacer les autres. Les aires de repos, tout en se déplaçant, peuvent accéder à une source de nourriture plus riche, devenant la meilleure après le tri effectué dans la méthode suivante :

for (int s = 0; s < areasNumber; s++)
{
  //move the center of the area to the best point in with more nectar-------
  ArrayCopy (areas [s].cC, areas [s].cB, 0, 0, WHOLE_ARRAY);

  //ordinary area-----------------------------------------------------------
  if (s != 0)
  {
    //check if there is no intersection of a region with a region of higher rank
    //measure the distance from the centers of the regions
    double centersDistance = 0.0;

    for (int c = 0; c < coordinates; c++) centersDistance += pow (areas [s].cC [c] - areas [s - 1].cC [c], 2.0);
    centersDistance = MathSqrt (centersDistance);

    //the areas intersect, then need to move the current area
    if (centersDistance < distHyperspCenters)
    {
      double incrementFactor = (distHyperspCenters - centersDistance) / centersDistance;
      double coordDistance   = 0.0;

      for (int c = 0; c < coordinates; c++)
      {
        coordDistance = areas [s].cC [c] - areas [s - 1].cC [c];
        areas [s].cC [c] = areas [s].cC [c] + (coordDistance * incrementFactor);

        areas [s].cC [c] = SeInDiSp (areas [s].cC [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}

C'est là que se déroule la danse des abeilles. En utilisant des informations sur la direction et la quantité de nectar dans les régions et en appliquant une composante aléatoire, nous marquons la zone de distribution d'un nombre aléatoire afin que la probabilité qu'une abeille choisisse une zone à la prochaine itération soit proportionnelle à la quantité de nectar dans cette région. En termes simples, sur la droite numérique, nous traçons des segments dont les longueurs correspondent à la différence entre la valeur de nectar de chaque zone et celle de la zone la moins bonne.

//send bees to the marked areas-----------------------------------------------
double r = 0.0;

beeDance [0].start = bees [0].n;
beeDance [0].end   = beeDance [0].start + (bees [0].n - bees [areasNumber - 1].n);

for (int a = 1; a < areasNumber; a++)
{
  if (a != areasNumber - 1)
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a].n - bees [areasNumber - 1].n);
  }
  else
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a - 1].n - bees [a].n) * 0.1;
  }
}

Dans cette partie du code de la méthode, une sélection aléatoire de la zone se produit avec la probabilité transmise par la danse des abeilles ouvrières. Pour cela, nous générons un nombre aléatoire dans la plage faite en marquant sur la droite numérique avec une danse. Pour les éclaireurs, la danse n'a pas d'importance, car les abeilles volent avec un degré de probabilité égal à proximité de l'une des zones, élargissant ainsi les capacités de recherche de la stratégie des abeilles. Comme dans la nature, chaque participante de la ruche a une certaine valeur tout en jouant un rôle.

for (int b = 0; b < beesNumber; b++)
{
  if (b < workerBeesNumber)
  {
    r = RNDfromCI(beeDance [0].start, beeDance [areasNumber - 1].end);
        
    for (int a = 0; a < areasNumber; a++)
    {
      if (beeDance [a].start <= r && r < beeDance [a].end)
      {
        bees [b].aInd = a;
        break;
      }
    }

    BeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
  else
  {
    //choose the area to send the bees there
    r = RNDfromCI (0.0, areasNumber - 1);

    bees [b].aInd = (int)r; //area index

    ScoutBeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
}

Cette méthode privée met en œuvre le vol d'une abeille. Même si à première vue cela semble incompréhensible et compliqué, tout est simple ici. L'abeille vole vers une zone avec un décalage de probabilité cubique plus proche du centre. La probabilité diminue donc du centre de la zone vers ses frontières. Gardez à l'esprit qu'il s'agit bien du centre de la zone et non de la meilleure position trouvée précédemment. Même dans cette simple action, la stratégie de l'abeille peut être tracée, assurant une recherche continue de nouvelles sources de nourriture.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::BeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (0.0, 1.0);
    r  = r * r * r;
    r = Scale (r, 0.0, 1.0, 0.0, areasRadius [c], false);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Contrairement à la méthode précédente, le vol de l'abeille éclaireuse est décrit ici. L'abeille vole en dehors de la zone dans le rayon spécifié dans les paramètres de l'algorithme. Bien que le réglage soit le même, les rayons sont calculés au préalable lors de l'initialisation de la classe, car les plages de coordonnées peuvent différer. Les rayons doivent donc être appropriés. Pour lancer une abeille éclaireuse en vol, nous devons générer un nombre aléatoire dans la plage allant du rayon de la zone à la somme du rayon de la zone et du rayon de l'exploration, puis simplement ajouter la valeur résultante au centre de la zone. De manière aussi simple, l'abeille éclaireuse se trouvera par hasard à proximité de la zone, et les coordonnées ne seront pas dispersées dans l'espace de recherche.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::ScoutBeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (areasRadius [c], areasRadius [c] + scoutRadius [c]);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il existe 2 méthodes spécifiques dans l'algorithme : le tri des abeilles et le tri par zone. Cela n'a aucun sens de les décrire, c'est un simple tri à bulles. Je l'utilise dans presque tous les algorithmes d'optimisation où un tri est requis. Cette méthode est simple et facilement modifiable pour des tâches spécifiques, tout en offrant l'une des meilleures vitesses parmi toutes les méthodes de tri.

//——————————————————————————————————————————————————————————————————————————————
//Sorting of bees
void C_AO_ABC::SortingBees ()
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Sorting of areas
void C_AO_ABC::SortingAreas ()
//——————————————————————————————————————————————————————————————————————————————

Il est temps de récupérer tout le code et de le compiler. Après avoir exécuté l’ensemble des tests, nous pouvons voir les animations suivantes montrant le comportement de l'algorithme des abeilles. Les abeilles sont clairement observées dans des zones séparées. Nous pouvons voir comment les zones se déplacent en se remplaçant les unes avec les autres. La précision et le nombre d'"essaims" particuliers dépendent des paramètres de l'algorithme.

ABC sur la fonction de test Skin.

ABC sur la fonction de test Forest.

ABC sur la fonction de test Megacity.

Voici les résultats de l'algorithme sur les fonctions de test :

L'algorithme a entièrement convergé pour les deux fonctions de test à 2 variables, ce qui est un excellent indicateur de convergence. L'évaluation des résultats restants serait prématurée. Il est préférable de mettre les résultats dans un tableau et de tirer des conclusions en comparaison avec d'autres algorithmes d'optimisation.

3. Version modifiée

Lors du développement et de la conception de tout algorithme d'optimisation, la question suivante se pose toujours : "L'algorithme fonctionne-t-il comme prévu ou y a-t-il une erreur quelque part dans le code ?" Le processus de recherche stochastique est aléatoire de par sa nature même. Il n'est donc pas clair si les résultats de l'optimisation ont été obtenus par l'algorithme ou s'il y a eu une erreur quelque part et que le résultat ne serait pas vraiment aléatoire. Lors du développement de l'algorithme de colonie d'abeilles, j'ai rencontré le même phénomène. Lors du premier test (sur cinq), l'algorithme s'est évidemment bloqué aux points où il a commencé la recherche en n'essayant pas du tout de converger. Ce bug a été résolu d'une manière complètement incroyable du point de vue de la logique. Tout ce que j'avais à faire était d'initialiser la classe hive une deuxième fois à la première itération malgré le fait que la classe avait déjà été pré-initialisée au début (chaîne 142 dans Test_AO_ABC.mq5). Si quelqu'un parvient à percer ce mystère, je serai heureux d'entendre la solution dans les commentaires.

En partie à cause de ce qui précède, et en partie à cause des résultats pas entièrement satisfaisants des premiers tests (bien que plus tard, il soit devenu clair que je devais expérimenter les paramètres de l'algorithme), j'ai eu l'idée de changer la stratégie de recherche d'abeilles. Dans la version originale, les abeilles volent proportionnellement à la valeur de la surface. Dans le nouvel algorithme, il devrait y avoir un nombre fixe d'abeilles dans chaque zone. En d'autres termes : quel que soit le rang de la zone, chacune d'elles a toujours le même nombre d'abeilles. Le domaine s'est alors logiquement transformé en concept d'"Essaim d'abeilles".

Maintenant, au lieu d’une structure de zone, il y aura la structure suivante :

//——————————————————————————————————————————————————————————————————————————————
struct S_BeesSwarm
{
  void Init (int coordinatesNumber, int beesNumber)
  {
    ArrayResize (bees, beesNumber);

    for (int i = 0; i < beesNumber; i++)
    {
      ArrayResize (bees [i].c, coordinatesNumber);
      bees [i].n = -DBL_MAX;
    }

    n = -DBL_MAX;

    ArrayResize     (cC, coordinatesNumber);
    ArrayInitialize (cC, -DBL_MAX);
  }

  S_Bee  bees []; //bees
  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Cette structure a également une fonction d'initialisation, mais contient en plus un tableau bees[].

Le reste du code est très similaire à la version classique et il ne faut pas trop s'y attarder. Le code est joint dans cet article. Il convient de prêter une attention particulière aux différences dans la logique des algorithmes. Etape par étape, cela ressemble à ceci :

1. Création du centre pour le premier essaim et placement des abeilles autour de ce centre.
2. Création d’un centre pour les essaims suivants et vérification que la distance du centre aux essaims précédents est supérieure ou égale à R*2 (2 rayons), placement des abeilles à proximité du centre.
3. Envoi des abeilles éclaireuses de manière à ce que chacune des abeilles soit plus éloignée que les autres essaims d'une distance supérieure ou égale à R (rayon).
4. Obtention de la valeur de la fonction de fitness pour toutes les abeilles.
5. Tri des essaims.
6. Placement des abeilles autour du centre de chaque essaim.
7. Répétition à partir du point 4 jusqu'à ce que le critère d'arrêt soit atteint.

Comme vous l'avez peut-être remarqué, il existe une différence fondamentale dans la stratégie de recherche : alors que dans la version classique, chaque zone peut avoir un nombre d'abeilles différent, ici les essaims sont toujours de la même taille. Ceci est fait pour s'assurer que les zones continuent d'être explorées même si la source de nourriture se tarit, offrant ainsi une exploration plus approfondie de la surface dans l'hyperespace. Les tests confirment la légitimité de cette approche, les résultats s'améliorent. Les abeilles éclaireuses ne volent pas à proximité des zones, mais tombent dans des zones libres de l'espace, en suivant de plus les règles des zones, comme dans la version classique. Dans la version classique des abeilles, les éclaireurs ne se comportent pas comme nous l’avons décrit, car ils se dispersent dans une direction complètement aléatoire sans se soucier de pouvoir pénétrer dans des zones précédemment explorées, perdant ainsi leur exploration la plus élémentaire. Le dernier essaim du tableau est l'essaim d’éclaireurs. Pour cet essaim, la règle "ne pas entrer dans l'espace de quelqu'un d'autre" s'applique également. Mais pas pour l'essaim dans son ensemble, mais pour les abeilles éclaireuses de façon individuelle.

Voici les résultats de la version modifiée :

Nous pouvons voir que l'algorithme modifié a répété le succès sur 2 fonctions avec 2 variables montrant une convergence de 100 %. En général, les résultats se sont améliorés. Le score final est devenu plus élevé : 0,50836. Malheureusement, ce n'est pas non plus une amélioration significative des résultats. Les problèmes de convergence sur les fonctions avec un grand nombre de variables sont comparables à la version classique de l'implémentation de l'algorithme.

Il n'y a d’ailleurs pas de bug nécessitant une réinitialisation de la ruche dans la version modifiée.

4. Résultats des tests

Résumons. Étonnamment, l'algorithme de la colonie d'abeilles a montré une convergence de 100 % dans les cinq tests sur les deux fonctions de test Skin et Megacity (discrète), démontrant ainsi une vitesse et une qualité de convergence phénoménales. Cela ne s'applique cependant qu'aux fonctions à 2 variables. En termes d'évolutivité, l'algorithme est inférieur aux autres membres de la table des scores. Les fonctions à variables multiples ne sont certainement pas un point fort d'une colonie d'abeilles. Cela se voit à la fois dans l'animation du banc d'essai et dans les résultats fournis dans le tableau.

L'algorithme ABC oblige l'utilisateur à jouer avec plusieurs paramètres tels que la taille de l'essaim, le nombre d'éclaireurs et les rayons de zone. Si ces paramètres ne sont pas choisis de manière appropriée pour une application particulière, l'algorithme peut converger prématurément ou, au contraire, ne pas converger du tout. De plus, ABC présente des inconvénients tels qu'une convergence lente sur des fonctions complexes, la capture de solutions locales et des propriétés de recherche médiocres.