Algorithmes naturels

  • Article

Utiliser des algorithmes de colonies d'abeilles pour résoudre des problèmes impossibles

James McCaffrey

Télécharger l'exemple de code

image: James McCaffreyLes algorithmes de colonie d'abeilles simulée (SBC, Simulated Bee Colony) modélisent le comportement des abeilles à miel et peuvent servir à rechercher des solutions à des problèmes combinatoires difficiles ou impossibles. Dans cet article, j'expliquerai ce que sont exactement les algorithmes SBC, je décrirai les types de problèmes pouvant être résolus à l'aide des algorithmes SBC et je présenterai un exemple complet de bout en bout qui utilise un algorithme SBC pour résoudre le problème du voyageur de commerce.

Pour avoir un aperçu des algorithmes SBC et savoir ce qui vous attend dans cet article, consultez le programme de démonstration en cours d'exécution à la Figure 1. Ce programme de démonstration utilise un algorithme SBC pour analyser une série de 20 villes (étiquetées de A à T) et trouver le chemin le plus court qui passe exactement une fois par chaque ville. Les données des villes sont construites de manière artificielle, de sorte que l'itinéraire idéal commence par la ville A et continue jusqu'à la ville T, dans l'ordre, et que celui-ci ait une longueur de 19,0 unités.

image: Simulated Bee Colony Demo

Figure 1 Démonstration de colonie d'abeilles simulée

En coulisse, l'algorithme SBC instancie une ruche de 100 abeilles simulées, dont chacune dispose d'une solution potentielle aléatoire. Initialement, la meilleure des solutions aléatoires présente une longueur du trajet de 95,0 unités. L'algorithme SBC entre une boucle de traitement, indiquée par la barre de progression textuelle, qui simule le comportement des abeilles à miel communes en train de butiner à la recherche de nourriture. À l'issue de la boucle de traitement SBC, la meilleure solution trouvée a 16 positions de villes correctes sur 20 et une longueur du trajet de 26,5, ce qui s'approche de la solution optimale, sans y correspondre tout à fait.

Les algorithmes SBC sont souvent qualifiés de métaheuristiques, car ils offrent un cadre général et un ensemble de règles permettant de créer une solution à un problème, plutôt que de prescrire une solution ultra-détaillée. Cet article présente un exemple d'utilisation d'une colonie d'abeilles simulée pour résoudre un problème spécifique. Une fois que vous aurez compris comment utiliser une colonie d'abeilles simulée pour résoudre un problème, vous pourrez adapter l'algorithme SBC présenté ici pour résoudre vos propres problèmes. Comme va le démontrer cet article, les algorithmes SBC conviennent à la résolution de problèmes combinatoires complexes sans solutions déterministes pratiques.

Cet article part du principe que vous disposez de compétences de niveau intermédiaire en programmation. L'exemple illustrant cet article est codé avec C#, mais tout le code a été écrit de façon à pouvoir être facilement refactorisé pour d'autres langages de programmation. Je pense que vous trouverez cet article passionnant et que la possibilité d'utiliser les algorithmes SBC vous apparaîtra comme un complément utile à l'éventail de vos compétences personnelles.

À propos des abeilles

Les abeilles à miel communes, telles que Apis mellifera, jouent différents rôles dans leur colonie, au fil du temps. Une ruche type peut contenir de 5 000 à 20 000 abeilles. Les abeilles adultes (âgées de 20 à 40 jours) deviennent habituellement des butineuses. Les abeilles butineuses jouent en général l'un des trois rôles suivants : butineuses actives, butineuses éclaireuses et butineuses inactives.

Les abeilles butineuses actives volent jusqu'à une source de nourriture, explorent les sources de nourriture voisines, recueillent la nourriture et reviennent à la ruche.

Les éclaireuses explorent la zone autour de la ruche à la recherche de nouvelles sources de nourriture attirantes. Il n'est pas rare que cette zone fasse jusqu'à 130 km². Dans une ruche, environ 10 % des butineuses sont des éclaireuses.

À n'importe quel moment, certaines butineuses sont inactives. Elles restent alors attendre près de l'entrée de la ruche. À leur retour à la ruche, selon la qualité de la source de nourriture à laquelle elles viennent d'accéder, les butineuses et les éclaireuses peuvent effectuer une danse frétillante pour les abeilles inactives en attente. Il existe des preuves convaincantes que cette danse frétillante fournit des informations sur le lieu et la qualité de la source de nourriture aux abeilles inactives. Les informations s'y rapportant sont transmises aux butineuses inactives par la danse frétillante. Celles-ci peuvent alors devenir actives.

En général, une butineuse active continue à recueillir de la nourriture auprès d'une source de nourriture particulière jusqu'à ce que celle-ci soit épuisée et se transforme ensuite aussitôt en butineuse inactive.

Problème du voyageur de commerce

Le PVC (Problème du voyageur de commerce) est l'un des problèmes les plus étudiés en recherche informatique. Il présente de nombreuses variantes, mais pour faire simple, ce problème consiste à trouver le chemin le plus court qui passe exactement une fois par chaque ville d'un ensemble donné.

Si vous regardez la Figure 1, vous constatez que le programme de démonstration d'une SBC utilise un ensemble de 20 villes arbitrairement étiquetées de A à T. Un chemin valide se compose d'un ensemble ordonné de 20 étiquettes de villes dans lequel chaque ville survient exactement une fois. Le nombre total de chemins possibles s'élève donc à 20! = 2 432 902 008 176 640 000.

En coulisse, une valeur de distance est associée à chaque paire de villes. Pour simplifier, si ville c1 < ville c2, la distance entre c1 et c2 est exactement égale à 1,0 fois la distance ordinale entre les étiquettes des villes. Si c1 > c2, la distance est égale à 1,5 fois la distance ordinale entre c1 et c2. La distance entre A et B est donc égale à 1,0 unité arbitraire, la distance entre B et A est égale à 1,5 unité, la distance entre A et C est égale à 2,0 unités, etc. Le chemin idéal qui passe exactement une fois par chaque ville est donc A -> B -> C -> ... -> T et la longueur du trajet idéal (le plus court) est (20-1) * 1,0 = 19,0.

Dans la plupart des scénarios de PVC, les distances entre les villes ne seraient pas calculées artificiellement. Au lieu de cela, elles seraient probablement enregistrées dans une sorte de structure de données de consultation. Certaines variantes du PVC partent du principe que chaque ville est reliée à chacune des autres et d'autres que les villes ne sont pas toutes reliées entre elles. De plus, certaines variantes du PVC partent du principe que la distance qui sépare n'importe quelle ville c1 d'une ville c2 est égale à la distance qui sépare la ville c2 de c1, tandis que d'autres ne sont pas basées sur cette hypothèse bidirectionnelle.

Sauf dans des situations insignifiantes, l'approche en force ne permet pas de trouver le chemin le plus court. Par exemple, avec 20 villes, même si vous pouviez évaluer 1 million de chemins par seconde, vous auriez besoin de plus de 77 000 ans pour examiner la totalité des chemins possibles qui s'élève à 20!. Les problèmes d'optimisation combinatoire extrêmement compliqués de ce type sont précisément ceux que les algorithmes SBC permettent de gérer.

Le problème du voyageur de commerce fictif est implémenté dans une classe appelée CitiesData, illustré à la Figure 2. Le code source intégral du programme de démonstration d'une colonie d'abeilles simulée est disponible à la page code.msdn.microsoft.com/mag0411BeeColony.

Figure 2 Définition de la classe CitiesData

class CitiesData {
  public char[] cities;

  public CitiesData(int numberCities) {
    this.cities = new char[numberCities];
    this.cities[0] = 'A';
    for (int i = 1; i < this.cities.Length; ++i)
      this.cities[i] = (char)(this.cities[i - 1] + 1);
  }

  public double Distance(char firstCity, char secondCity) {
    if (firstCity < secondCity)
      return 1.0 * ((int)secondCity - (int)firstCity);
    else
      return 1.5 * ((int)firstCity - (int)secondCity);
  }

  public double ShortestPathLength() {
    return 1.0 * (this.cities.Length - 1);
  }

  public long NumberOfPossiblePaths() {
    long n = this.cities.Length;
    long answer = 1;
    for (int i = 1; i <= n; ++i)
      checked { answer *= i; }
    return answer;
  }

  public override string ToString() {
    string s = "";
    s += "Cities: ";
    for (int i = 0; i < this.cities.Length; ++i)
      s += this.cities[i] + " ";
    return s;
  }
}

La définition d'une structure de données ou de classe représentant votre problème particulier sera différente de celle qui figure ici. Cependant, conformément à la règle générale, les problèmes adaptés à une solution utilisant un algorithme SBC peuvent généralement être représentés sous la forme d'un tableau non numérique, d'une matrice non numérique ou de tableaux en escalier non numériques.

Le constructeur CitiesData accepte une valeur pour le nombre de villes et attribue à la première ville l'étiquette A, à la seconde l'étiquette B, etc.

La méthode Distance est définie d'une manière unidirectionnelle, comme je l'ai indiqué précédemment. Elle part du principe que toute ville peut être atteinte depuis n'importe quelle autre ville.

La méthode ShortestPathLength renvoie la longueur du trajet optimale étant donnée la définition de la distance. Dans la plupart des cas de colonies d'abeilles simulées, vous ne disposerez pas des informations nécessaires pour implémenter une méthode renvoyant la solution optimale.

La méthode NumberOfPossiblePaths calcule n!, où n représente le nombre de villes. Dans certains scénarios de PVC, le nombre des chemins possibles est égal à n-1! (si la ville de départ n'a pas d'importance), alors que dans d'autres scénarios le nombre des chemins possibles est égal à n/2! (si la direction du chemin n'a pas d'importance).

La méthode ToString utilise la concaténation de chaînes de caractères au lieu de la classe StringBuilder plus efficace pour assembler une chaîne avec des données descriptives. La concaténation de chaînes de caractères est utilisée pour simplifier la refactorisation pour d'autres langages de programmation.

Dans cet article, afin que le code reste court et propre, j'utilise des raccourcis que vous n'utiliseriez pas dans un code de production, tels que la suppression de la plupart des vérifications des erreurs. Ainsi, la méthode NumberOfPossiblePaths ne gère pas les dépassements de capacité numérique si le résultat est supérieur à long.MaxValue.

Structure du programme SBC

L'algorithme SBC reproduit à la Figure 1 est implémenté en tant qu'application console C#. La structure générale du programme est listée à la Figure 3. Notez que la structure du programme SBC est relativement simple et qu'elle utilise uniquement l'espace de noms System basique. Il existe trois classes : la classe Program, qui contient une méthode Main unique ; la classe Hive, qui contient toute la logique de l'algorithme SBC ; et la classe CitiesData, présentée dans la section précédente de cet article. J'attribue à la classe Hive le nom générique Hive, au lieu d'un nom plus spécifique, tel que TravelingSalesmanHive, bien que les implémentations d'algorithmes SBC dépendent beaucoup du problème particulier pour lequel ils ont été conçus.

Figure 3 Structure générale du programme

using System;
namespace SimulatedBeeColony {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("\nBegin Simulated Bee Colony algorithm demo\n");
      . . . 
      Console.WriteLine("End Simulated Bee Colony demo");
    } 
  } 

  class Hive {
    public class Bee {
      . . . 
    }

    // Hive data fields here

    public override string ToString() { . . . }
    
    public Hive(int totalNumberBees, int numberInactive,
      int numberActive, int numberScout, int maxNumberVisits,
      int maxNumberCycles, CitiesData citiesData) {
      . . .      
    } 

    public char[] GenerateRandomMemoryMatrix() { . . . }
    
    public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) { . . . }
    
    public double MeasureOfQuality(char[] memoryMatrix) { . . . }
    
    public void Solve() { . . . }

    private void ProcessActiveBee(int i) { . . . }

    private void ProcessScoutBee(int i) { . . . }

    private void ProcessInactiveBee(int i) { . . . }

    private void DoWaggleDance(int i) { . . . }
  } 

  class CitiesData {
    . . .
  }

} // ns

La méthode Main est très simple. Après l'affichage d'un message de démarrage, l'objet CitiesData est instancié :

Console.WriteLine(
  "Loading cities data for SBC Traveling Salesman Problem analysis");
CitiesData citiesData = new CitiesData(20);
Console.WriteLine(citiesData.ToString());
Console.WriteLine("Number of cities = " + citiesData.cities.Length);
Console.WriteLine("Number of possible paths = " + 
  citiesData.NumberOfPossiblePaths().ToString("#,###"));
Console.WriteLine("Best possible solution (shortest path) length = " + 
  citiesData.ShortestPathLength().ToString("F4"));

Dans de nombreux scénarios de SBC, les données de votre problème seront stockées en externe, dans un fichier texte ou des bases de données SQL par exemple, et vous chargerez ces données via un constructeur de chargement ou une méthode de chargement du genre myProblemData.Load(dataFile).

Ensuite, le constructeur Hive est préparé et appelé :

int totalNumberBees = 100;
int numberInactive = 20;
int numberActive = 50;
int numberScout = 30;
int maxNumberVisits = 100; 
int maxNumberCycles = 3460;
       
Hive hive = new TravelingSalesmanHive(totalNumberBees,
  numberInactive, numberActive, numberScout, maxNumberVisits,
  maxNumberCycles, citiesData);

Comme vous le verrez plus en détail dans les sections suivantes de cet article, un algorithme SBC utilise trois types d'abeilles : actives, inactives et éclaireuses. Bien que le nombre d'abeilles de chaque type puisse être codé en dur, dans la plupart des scénarios il est préférable d'entrer ces nombres en tant que paramètres du constructeur Hive, afin de pouvoir plus facilement régler les performances de l'algorithme.

La valeur de la variable totalNumberBees pourrait être déduite à partir des trois autres variables, mais cette variable supplémentaire améliore ici la lisibilité du code. Le nombre total d'abeilles dépendra de votre problème particulier. Un nombre élevé d'abeilles est préférable, mais cela ralentit l'exécution du programme. Pour ce qui est des proportions, certaines recherches suggèrent que les pourcentages d'abeilles actives, inactives et éclaireuses les plus efficaces sont souvent respectivement de 75 %, 10 % et 15 % environ. 

La valeur 100 utilisée pour la variable maxNumberVisits sera bientôt expliquée, mais est liée au nombre de solutions voisines qui existent par rapport à une solution donnée.

La variable maxNumberCycles est utilisée pour contrôler le nombre de fois que la routine Solve effectuera une itération. Cela est nécessaire parce que, dans les scénarios d'algorithmes SBC, vous ne savez généralement pas quand vous avez trouvé une solution optimale (si vous connaissez la solution optimale, vous n'avez en fait pas de problème à résoudre). Dans ce cas, la valeur de la variable maxNumberCycles a été limitée à 3 460 uniquement, afin que l'algorithme SBC ne produise pas de résultat parfait. L'idée ici est que, bien que les algorithmes SBC puissent produire un résultat optimal, vous n'avez généralement aucun moyen de le savoir et vous devez donc être disposé à accepter un « bon » résultat.

Quand un constructeur s'exécute, il crée un ensemble d'abeilles, dont chacune dispose d'une solution aléatoire. L'objet Hive effectue le suivi du chemin idéal (le plus court) global trouvé par l'une des abeilles de la ruche et de la longueur du trajet associée à la meilleure solution.

Après l'appel du constructeur Hive, la méthode Main se termine en utilisant la méthode ToString pour afficher les valeurs Hive initiales générées de manière aléatoire, en appelant la méthode Solve avec un paramètre indiquant qu'une barre de progression textuelle devrait s'imprimer, puis en affichant le meilleur chemin et la longueur de trajet associée qui a été trouvée :

...
  Console.WriteLine("\nInitial random hive");
  Console.WriteLine(hive);

  bool doProgressBar = true;
  hive.Solve(doProgressBar);

  Console.WriteLine("\nFinal hive");
  Console.WriteLine(hive);
  Console.WriteLine("End Simulated Bee Colony demo");
}

Classe Bee

Comme illustré à la Figure 3, la classe Hive contient une définition de classe Bee imbriquée. Les détails de la définition de classe Bee sont indiqués à la Figure 4.

Figure 4 Définition de classe Bee

public class Bee {
  public int status;
  public char[] memoryMatrix;
  public double measureOfQuality; 
  public int numberOfVisits;

  public Bee(int status, char[] memoryMatrix, 
    double measureOfQuality, int numberOfVisits) {
    this.status = status;
    this.memoryMatrix = new char[memoryMatrix.Length];
    Array.Copy(memoryMatrix, this.memoryMatrix, memoryMatrix.Length);
    this.measureOfQuality = measureOfQuality;
    this.numberOfVisits = numberOfVisits;
  }

  public override string ToString() {
    string s = "";
    s += "Status = " + this.status + "\n";
    s += " Memory = " + "\n";
    for (int i = 0; i < this.memoryMatrix.Length-1; ++i)
      s += this.memoryMatrix[i] + "->";
    s += this.memoryMatrix[this.memoryMatrix.Length-1] + "\n";
    s += " Quality = " + this.measureOfQuality.ToString("F4");
    s += " Number visits = " + this.numberOfVisits;
    return s;
  }
}

La classe Bee contient trois champs de données communs à toutes les implémentations de colonies d'abeilles simulées et un champ de données propre au problème. Le champ propre au problème est nommé memoryMatrix. Chaque implémentation SBC doit disposer d'un moyen de représenter une solution. Dans le cas du PVC de cet article, une solution peut être représentée par un tableau de type char. Je souligne que l'objet représentant une solution varie grandement selon le problème et que chaque problème doit être analysé séparément pour produire une représentation de solution valable.

Le champ nommé status contient une valeur int indiquant le type de l'objet Bee : 0 pour inactive, 1 pour active et 2 pour éclaireuse. Si vous écrivez votre code dans un langage qui prend en charge les types d'énumérations, vous avez la possibilité de refactoriser le champ status en tant qu'énumération.

Le champ measureOfQuality contient une valeur double représentant la validité de l'objet memoryMatrix de l'objet Bee. Dans le cas du PVC, la longueur du trajet représenté par l'objet memoryMatrix est une mesure naturelle de la qualité d'une solution. Notez que, dans cette situation, les trajets courts sont préférables aux trajets longs. C'est pourquoi des valeurs basses dans le champ measureOfQuality indiquent des solutions meilleures que des valeurs élevées. Chaque implémentation SBC doit avoir un moyen de calculer une mesure de la qualité d'une solution. Dans bon nombre de situations, une valeur de type double constitue la meilleure représentation de cette mesure.

Le troisième champ de données commun de la classe Bee est nommé numberOfVisits. Ce champ contient une valeur int qui représente le nombre de fois que l'objet Bee a accédé à une source de nourriture/solution au problème particulière, sans trouver de solution voisine meilleure. Ce champ est utilisé pour simuler une abeille accédant à une source de nourriture jusqu'à épuisement de celle-ci. Pour une abeille active, lorsque la valeur du champ numberOfVisits dépasse une valeur de seuil, l'abeille fictive aura virtuellement entièrement consommé la source d'approvisionnement et passera à l'état inactif (et une abeille inactive passera à l'état actif).

Le constructeur Bee accepte des valeurs pour les quatre champs de données : status, memoryMatrix, measureOfQuality et numberOfVisits. Notez que le constructeur Bee doit accepter une valeur pour le champ measureOfQuality, parce qu'une abeille ne peut pas la calculer directement à partir de son champ memoryMatrix. Déterminer la mesure de la qualité dépend des informations stockées dans l'objet CitiesData propre au problème.

La définition de classe Bee contient une méthode ToString qui expose les valeurs des quatre champs de données. La méthode Bee.ToString n'est pas absolument nécessaire, mais peut s'avérer très utile durant le développement de la colonie d'abeilles simulée pour découvrir des bogues à l'aide d'instructions WriteLine.

Champs de données de la ruche

Le code de la classe Hive est présenté à la Figure 5. Il existe 14 champs de données de ruche et le fait de comprendre le but de chacun d'entre eux est primordial pour comprendre comment implémenter un algorithme SBC spécifique.

Figure 5 Les 14 champs de données de la ruche

static Random random = null;

public CitiesData citiesData;

public int totalNumberBees; 
public int numberInactive; 
public int numberActive;
public int numberScout;

public int maxNumberCycles;
public int maxNumberVisits; 

public double probPersuasion = 0.90;
public double probMistake = 0.01; 

public Bee[] bees;
public char[] bestMemoryMatrix;
public double bestMeasureOfQuality;
public int[] indexesOfInactiveBees;

Pour plus de simplicité et afin de faciliter le débogage avec des instructions WriteLine, les 14 champs de données sont définis avec une étendue publique. Vous avez la possibilité de limiter les champs à une étendue privée et de créer des propriétés pour ceux auxquels vous avez besoin d'accéder en dehors de la définition de classe.

Le premier champ est nommé random et est de type Random. Les algorithmes SBC sont probabilistes et l'objet Random est utilisé pour générer des nombres pseudo-aléatoires avec plusieurs objectifs. L'objet Random sera instancié dans le constructeur Hive.

Le second champ de données est un objet de type CitiesData. L'implémentation SBC doit connaître les détails du problème à résoudre. Dans la plupart des cas, comme dans celui-ci, les données du problème sont représentées en tant qu'objet. Rappelez-vous que CitiesData dispose d'une liste d'étiquettes de villes et d'une méthode qui renvoie la distance entre deux villes, quelles qu'elles soient.

Du troisième champ au sixième, les champs de données sont des variables int qui contiennent le nombre total d'abeilles, le nombre d'abeilles inactives, le nombre d'abeilles actives et le nombre d'éclaireuses. Comme je le mentionnais plus tôt, chaque abeille représente une solution potentielle, c'est pourquoi, plus elles sont nombreuses, mieux c'est. Cependant, des nombres très élevés d'abeilles nuisent aux performances du programme.

Le septième champ de données, maxNumberCycles, est une valeur de seuil utilisée pour limiter la durée d'exécution de la méthode Solve. Un cycle représente le traitement de chaque abeille dans la ruche.

Le huitième champ de données, maxNumberVisits, est une valeur de seuil utilisée pour empêcher une abeille de rester trop longtemps sur une solution particulière. Dans chaque itération de la boucle de traitement principale de la méthode Solve, si une abeille ne trouve pas de source de nourriture voisine de meilleure qualité, le compteur numberOfVisits de l'abeille est incrémenté. Si le compteur numberOfVisits d'un objet Bee dépasse la valeur de seuil maxNumberVisits, l'abeille passe à l'état inactif.

Le neuvième champ de données, probPersuasion, est une valeur de seuil probabiliste utilisée pour déterminer si une abeille inactive qui observe la danse frétillante d'une abeille revenue à la ruche avec une meilleure solution se laissera convaincre de mettre à jour sa mémoire avec cette dernière.

La valeur de probPersuasion est codée en dur à 0,90, ce qui signifie qu'une abeille inactive sera convaincue d'accepter une meilleure solution environ 90 % du temps. La valeur 0,90 pour le champ probPersuasion est basée sur des résultats de recherches, mais vous avez la possibilité de faire des essais avec d'autres valeurs. Des valeurs supérieures produiront un algorithme de SBC qui convergera plus rapidement vers une solution, ce qui augmente le risque de convergence vers une solution qui ne serait pas optimale.

Le dixième champ de données, probMistake, est une valeur de seuil probabiliste utilisée pour déterminer si une abeille active fera une erreur, à savoir, si elle rejettera une solution voisine meilleure que sa solution actuelle, ou si elle acceptera de manière incorrecte une solution voisine moins bonne que sa solution actuelle. La valeur du champ probMistake est codée en dur à 0,01, ce qui signifie qu'une abeille active commettra une erreur lors de l'évaluation d'une solution voisine dans environ 1 % des cas.

Le onzième champ de données, bees, est un tableau d'objets Bee. Rappelez-vous que chaque abeille dispose d'un état (active, inactive, butineuse), d'une solution (memoryMatrix), d'une mesure de la qualité de la solution (measureOfQuality) et d'un compteur qui comptabilise le nombre de fois qu'une source de nourriture virtuelle particulière a été visitée sans qu'aucune meilleure source de nourriture voisine soit trouvée (numberOfVisits). Comme Bee est défini en tant que classe, chaque entrée dans le tableau bees est une référence à un objet Bee.

Le douzième champ de données, bestMemoryMatrix, est un tableau de caractères et représente la meilleure solution dans le tableau bees. N'oubliez pas que, comme les algorithmes de colonie d'abeilles simulée sont des implémentations spécifiques d'une métaheuristique, la représentation d'une solution au problème variera en fonction du problème en question. Une approche conceptuelle alternative au codage en dur d'une définition de type de solution consiste à paramétrer ce champ de données comme type générique. Quand j'utilise un algorithme SBC, c'est généralement pour tenter de résoudre un problème spécifique. Je préfère donc recoder chaque nouvelle implémentation SBC à partir de zéro.

Le treizième champ de données, bestMeasureOfQuality, est la mesure de la qualité correspondant à la solution bestMemoryMatrix.

Le dernier champ de données de la ruche, indexesOfInactiveBees, est un tableau d'entiers. Ce tableau contient les index des abeilles de la ruche actuellement inactives. N'oubliez pas que les abeilles actives peuvent passer à l'état inactif et les abeilles inactives à l'état actif. Une implémentation d'algorithmes SBC doit fréquemment déterminer quelles abeilles sont actuellement inactives quand une abeille active effectue une danse frétillante virtuelle : le stockage des index des abeilles inactives améliore les performances, par rapport à la solution alternative d'itération dans l'intégralité du tableau bees et de vérification du champ de données status de chaque abeille.

Une représentation virtuelle d'un objet Hive potentiel est illustrée à la Figure 6. La ruche présentée contient 10 abeilles : 5 actives, 2 éclaireuses et 3 inactives. Les abeilles actuellement inactives sont aux index 2, 7 et 4 du tableau bees. L'objet CitiesData contient cinq villes. La meilleure solution actuelle est :

A->B->E->C-D

La longueur du trajet de cette solution, en unités de distance, est de :

1.0 + (3 * 1.0) + (2 * 1.5) + 1.0 = 8.0

Notez que le champ citiesData est une référence à un objet CitiesData défini à l'extérieur de l'objet Hive.

image: The Hive Representation

Figure 6 Représentation de la ruche

Constructeur Hive

Le code du constructeur Hive est présenté à la Figure 7. Le constructeur Hive accepte sept arguments d'entrée. Six de ces paramètres sont scalaires et l'un est un objet (citiesData). Le paramètre totalNumberBees est redondant dans le sens où il peut être déterminé à partir des paramètres numberInactive, numberActive et numberScout, mais je pense que ce code supplémentaire améliore la lisibilité.

Figure 7 Constructeur Hive

public Hive(int totalNumberBees, int numberInactive,
  int numberActive, int numberScout, int maxNumberVisits,
  int maxNumberCycles, CitiesData citiesData) {

  random = new Random(0);
      
  this.totalNumberBees = totalNumberBees;
  this.numberInactive = numberInactive;
  this.numberActive = numberActive;
  this.numberScout = numberScout;
  this.maxNumberVisits = maxNumberVisits;
  this.maxNumberCycles = maxNumberCycles;

  this.citiesData = citiesData;

  this.bees = new Bee[totalNumberBees];
  this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
  this.bestMeasureOfQuality = 
    MeasureOfQuality(this.bestMemoryMatrix);

  this.indexesOfInactiveBees = new int[numberInactive]; 

  for (int i = 0; i < totalNumberBees; ++i) {
    int currStatus; 
    if (i < numberInactive) {
      currStatus = 0; // inactive
      indexesOfInactiveBees[i] = i; 
    }
    else if (i < numberInactive + numberScout)
      currStatus = 2; // scout
    else
      currStatus = 1; // active
    
    char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
    double mq = MeasureOfQuality(randomMemoryMatrix);
    int numberOfVisits = 0;

    bees[i] = new Bee(currStatus, 
      randomMemoryMatrix, mq, numberOfVisits); 
        
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix, 
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    }
  } 
}

L'objet random d'étendue de classe est instancié avec une valeur de départ de 0. Le fait de fournir une valeur de départ vous permet de reproduire les résultats. Ensuite, six valeurs de paramètres d'entrée pour les champs de données scalaires sont copiées vers les champs de données de la ruche. L'objet hive présente 14 champs de données au total ; les valeurs de seuil probPersuasion et probMistake sont codées en dur.

Le constructeur Hive prend le paramètre citiesData d'entrée et attribue le champ citiesData au paramètre comme référence. Une alternative à cette approche par référence consiste à faire une nouvelle copie des données du problème, comme suit :

int n = citiesData.cities.Length;
this.citiesData = new CitiesData(n);

Cette approche utilise davantage de mémoire, mais évite les erreurs secondaires potentielles. L'approche alternative peut être utilisée si vous refactorisez le code présenté ici pour un langage de programmation ne prenant en charge ni les pointeurs, ni les références.

À ce stade, toutes les entrées du tableau bees seront nulles dans le constructeur Hive. Ensuite, le constructeur initialise la solution globalement la meilleure (c'est-à-dire, la meilleure solution parmi toutes les abeilles de la ruche) et la qualité de la solution correspondante :

this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
this.bestMeasureOfQuality = 
  MeasureOfQuality(this.bestMemoryMatrix);

La méthode d'assistance GenerateRandomMemoryMatrix génère une solution aléatoire. La méthode d'assistance MeasureOfQuality accepte la solution générée de manière aléatoire et calcule sa qualité. Je reviendrai sur le code de ces deux méthodes d'assistance plus loin dans l'article.

Après avoir initialisé la meilleure solution globale et la qualité correspondante, le constructeur Hive alloue le tableau d'abeilles indexesOfInactiveBees à l'aide de la valeur figurant dans le champ numberInactive. À ce stade, toutes les valeurs de ce tableau d'index seront 0.

La partie suivante du code du constructeur itère dans chaque objet Bee du tableau bees et l'instancie à l'aide du constructeur Bee. La logique de cette boucle part du principe que les premières cellules numberInactive du tableau bees sont des abeilles inactives, que les cellules numberScout suivantes sont des éclaireuses et que les cellules restantes sont des abeilles actives.

Par exemple, s'il y a cinq abeilles actives, deux abeilles inactives et trois abeilles éclaireuses, le constructeur initialise un tableau bees d'une taille de 10, et instancie les cellules 0 et 1 en tant qu'abeilles inactives, les cellules 2 à 4 en tant qu'éclaireuses et les cellules 5 à 9 en tant qu'abeilles actives. En outre, le tableau indexesOfInactiveBees aura une taille de 2 et contiendra les valeurs 0 et 1.

Une fois que l'état de l'abeille actuelle a été déterminé en fonction de la variable d'index de la boucle, une solution générée de manière aléatoire est créée et sa qualité correspondante est calculée, le compteur du nombre de visites est défini de manière explicite sur 0 et le constructeur Bee est appelé :

char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
double mq = MeasureOfQuality(randomMemoryMatrix);
int numberOfVisits = 0;
bees[i] = new Bee(currStatus, randomMemoryMatrix, 
  mq, numberOfVisits);

Une fois que chaque abeille est instanciée, la qualité de la solution générée de manière aléatoire de l'abeille est vérifiée pour déterminer si elle est meilleure que la meilleure solution globale. Si c'est le cas, la solution de l'abeille actuelle et la qualité correspondante sont copiées vers les champs bestMemoryMatrix et bestMeasureOfQuality. Notez que, lors de la vérification de la qualité de la meilleure solution globale, une valeur basse est meilleure qu'une valeur plus élevée, car la valeur de la qualité correspond à des longueurs de trajets et le PVC a pour objectif de réduire cette longueur.

Au lieu de copier de manière explicite la mémoire d'une abeille dans le tableau bestMemoryMatrix, il existe une autre approche consistant à attribuer par référence. Cette approche améliore les performances au détriment d'une complexité plus importante.

Trois méthodes de SBC essentielles

Chaque implémentation d'un algorithme SBC doit comporter trois méthodes propres au problème : une méthode permettant de générer une solution aléatoire, une méthode permettant de générer une solution voisine par rapport à une solution donnée et une méthode permettant de calculer la qualité d'une solution donnée. Dans cet exemple de PVC, chaque méthode est implémentée d'une manière personnalisée et complètement dépendante du problème.

Une conception alternative consiste à définir des interfaces et à les implémenter. La programmation via interfaces offre plusieurs avantages et désavantages par rapport à l'approche sans interface utilisée, mais cela est, d'après moi, essentiellement d'une question de préférences personnelles. La méthode permettant de générer une solution aléatoire, GenerateRandomMemoryMatrix, est présentée ci-dessous :

public char[] GenerateRandomMemoryMatrix() {
  char[] result = new char[this.citiesData.cities.Length];
  Array.Copy(this.citiesData.cities, result,
    this.citiesData.cities.Length);      
  for (int i = 0; i < result.Length; i++) {
    int r = random.Next(i, result.Length);
    char temp = result[r];
    result[r] = result[i];
    result[i] = temp;
  }
  return result;
}

La solution au problème du voyageur de commerce étant un tableau de caractères dans lequel chaque caractère représente l'étiquette d'une ville, la méthode GenerateRandomMemoryMatrix renvoie un tableau de caractères. La taille du tableau des résultats local est allouée en fonction de l'objet CitiesData de la ruche et les ID des villes stockés dans la référence de la ruche à l'objet CitiesData sont copiés dans le tableau des résultats. L'ordre des valeurs figurant dans le tableau des résultats est ensuite randomisé à l'aide de l'objet random d'étendue de classe et de l'algorithme de permutation aléatoire de Fisher-Yates (parfois appelé Mélange de Knuth).

Au début, il peut sembler que la méthode GenerateRandomMemoryMatrix appartient, par sa conception, à un objet Bee. Cependant, dans la mesure où la génération d'une solution aléatoire dépend en partie de données propres au problème, CitiesData dans le cas présent, la conception consistant à placer une méthode de génération de solution aléatoire dans la définition de ruche globale est préférable.

La méthode permettant de générer une solution voisine, GenerateNeighborMemoryMatrix, est présentée à la Figure 8.

Figure 8 Génération d'une solution voisine

public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) {
  char[] result = new char[memoryMatrix.Length];
  Array.Copy(memoryMatrix, result, memoryMatrix.Length);

  int ranIndex = random.Next(0, result.Length);
  int adjIndex;
  if (ranIndex == result.Length - 1)
    adjIndex = 0;
  else
    adjIndex = ranIndex + 1;

  char tmp = result[ranIndex];
  result[ranIndex] = result[adjIndex];
  result[adjIndex] = tmp;  return result;
}

L'idée que chaque source de nourriture virtuelle représentant une solution possède une solution voisine est un concept clé des algorithmes SBC. Sans ce concept de voisinage, l'idée même d'un algorithme basé sur le comportement d'abeilles s'écroule. Dans le cas du PVC, où une solution peut être représentée sous forme d'un tableau d'ID de villes représentant un chemin allant de ville en ville, une solution voisine naturelle relative à une solution actuelle est une permutation de la solution actuelle dans laquelle deux villes adjacentes ont été inversées.

Par exemple, si A, B, C, D, E est une solution actuelle au problème du voyageur de commerce, alors A, C, B, D, E constitue une solution voisine raisonnable. Le fait qu'une permutation de deux villes arbitrairement choisies (par opposition à deux villes adjacentes) représente une solution voisine raisonnable est moins évident. Pour l'exemple précédent, la solution A, D, C, B, E est-elle une solution voisine raisonnable ? La définition d'une solution voisine pour un algorithme SBC est une décision propre au problème et qui implique généralement des critères subjectifs.

Le concept de solution voisine sert également à illustrer en partie pourquoi les problèmes combinatoires non numériques sont particulièrement adaptés aux résolutions par des algorithmes SBC. Si un problème est numérique par nature, l'idée de voisinage est souvent difficile à définir de manière satisfaisante. Si un problème est combinatoire par nature, l'idée de voisinage peut souvent être correctement définie par forme de combinaison ou de permutation mathématique.

La méthode GenerateNeighborMemoryMatrix accepte la représentation d'une solution memoryMatrix actuelle d'une abeille comme paramètre d'entrée et la copie dans un tableau de résultats. La méthode sélectionne un index random unique dans le tableau des résultats actuels à l'aide de l'objet random à étendue de classe. Si l'index random pointe vers la dernière cellule, alors la première et la dernière ID des villes sont échangées. Par contre, si l'index random pointe vers une autre cellule que la dernière, les ID vers lesquelles pointe l'index random et l'index suivant sont échangés.

Le concept de solution voisine est lié à la valeur maxNumberVisits. Certaines recherches suggèrent qu'une bonne valeur pour la variable maxNumberVisits est environ 5 fois le nombre de solutions voisines possibles pour une solution donnée. Par exemple, pour trois villes (A, B, C), si une solution voisine est définie par l'échange d'une paire de villes adjacentes, alors il existe trois voisins possibles (échange de A et B, échange de B et C, échange de A et C). Donc, pour 20 villes, une valeur maxNumberVisits raisonnable est environ 20 * 5 = 100.

La méthode d'évaluation de la qualité de la solution d'une abeille, MeasureOfQuality, est la suivante :

public double MeasureOfQuality(char[] memoryMatrix) {
  double answer = 0.0;
  for (int i = 0; i < memoryMatrix.Length - 1; ++i) {
    char c1 = memoryMatrix[i];
    char c2 = memoryMatrix[i + 1];
    double d = this.citiesData.Distance(c1, c2);
    answer += d;
  }
  return answer;
}

Pour résoudre un problème à l'aide d'un algorithme SBC, une caractéristique essentielle du problème est que toute solution doit pouvoir être évaluée pour produire une mesure de sa qualité. En termes conceptuels, un problème d'optimisation combinatoire réel présente presque toujours une mesure de la qualité inhérente qui relève du bon sens. Cependant, dans la pratique, le calcul de la mesure de la qualité d'une solution peut être difficile et long.

Dans cet exemple, la méthode MeasureOfQuality itère dans chaque paire d'ID de villes consécutives de la solution représentée par le paramètre memoryMatrix, détermine la distance entre chaque paire à l'aide de la méthode Distance de l'objet CitiesData et cumule la distance totale. N'oubliez pas que les données des villes ont été construites artificiellement de telle sorte que la distance entre deux villes quelconques puisse être rapidement et facilement calculée en utilisant la distance ordinale entre les ID de deux villes. Mais, dans un problème réel, la distance entre deux villes devrait être consultée dans une sorte de structure de données. Dans les implémentations SBC, la méthode MeasureOfQuality est souvent la routine qui domine le temps d'exécution du programme. C'est pourquoi il est généralement utile de vous assurer que cette méthode soit non seulement optimisée pour les performances, mais également réaliste, étant donné les ressources mémoire du système hôte.

Méthode Solve

La méthode Solve contient toute la logique qui simule le comportement des abeilles butineuses pour résoudre un problème. La méthode Solve est modérément complexe et utilise trois méthodes d'assistance : ProcessActiveBee, ProcessScoutBee et ProcessInactiveBee. Les méthodes ProcessActiveBee et ProcessScoutBee utilisent à leur tour la méthode d'assistance DoWaggleDance. La méthode Solve est présentée à la Figure 9.

Figure 9 Méthode Solve

public void Solve(bool doProgressBar) {
  bool pb = doProgressBar;
  int numberOfSymbolsToPrint = 10; 
  int increment = this.maxNumberCycles / numberOfSymbolsToPrint;
  if (pb) Console.WriteLine("\nEntering SBC Traveling Salesman Problem algorithm main processing loop\n");
  if (pb) Console.WriteLine("Progress: |==========|");
  if (pb) Console.Write("           ");
  int cycle = 0;
      
  while (cycle < this.maxNumberCycles) {
    for (int i = 0; i < totalNumberBees; ++i) {
      if (this.bees[i].status == 1)
        ProcessActiveBee(i);
      else if (this.bees[i].status == 2)
        ProcessScoutBee(i);
      else if (this.bees[i].status == 0)
        ProcessInactiveBee(i);
    } 
    ++cycle;

    if (pb && cycle % increment == 0)
      Console.Write("^");
  } 

  if (pb) Console.WriteLine("");
}

La plus grande partie du travail réel est confiée aux méthodes d'assistance ProcessActiveBee, ProcessScoutBee et ProcessInactiveBee. Un paramètre d'entrée booléen est transmis à Solve pour indiquer s'il faut imprimer une barre de progression textuelle rudimentaire. Cela est utile lors du développement d'un algorithme SBC pour surveiller la vitesse de l'implémentation et permettre de découvrir les goulots d'étranglement de performances. Cette approche part de l'hypothèse que la méthode Solve fait partie d'une application console.

La valeur du paramètre booléen est transférée dans une variable booléenne locale nommée pb, simplement pour avoir un nom de variable court avec lequel travailler. La valeur numberOfSymbolsToPrint est définie sur 10 pour que chaque incrément dans la barre d'état représente 10 % de la progression totale. Celle-ci est déterminée par la valeur maxNumberCycles (la variable increment est utilisée pour déterminer combien de cycles représentent une progression de 10 %).

Une fois que la variable de contrôle de la boucle, nommée cycle, est initialisée sur 0, une boucle While est utilisée pour traiter chaque abeille de la ruche. Une boucle For pourrait tout aussi facilement être utilisée. Dans chaque cycle, le tableau bees est itéré à l'aide d'une boucle For et chaque objet Bee est traité par la méthode d'assistance appropriée. Après le traitement de chacune des abeilles, si le paramètre booléen doProgressBar est défini sur true, le code utilise l'opérateur modulo, %, pour vérifier s'il est temps d'imprimer une mise à jour de la barre de progression à l'aide d'un caractère ^.

Méthode ProcessActiveBee

La méthode ProcessActiveBee est le cœur d'un algorithme SBC et constitue la méthode la plus complexe en termes de branchement et de taille du code. La méthode ProcessActiveBee est présentée à la Figure 10.

Figure 10 La méthode ProcessActiveBee

private void ProcessActiveBee(int i) {
  char[] neighbor = GenerateNeighborMemoryMatrix(bees[i].memoryMatrix);
  double neighborQuality = MeasureOfQuality(neighbor); 
  double prob = random.NextDouble();
  bool memoryWasUpdated = false;
  bool numberOfVisitsOverLimit = false; 

  if (neighborQuality < bees[i].measureOfQuality) { // better
    if (prob < probMistake) { // mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
    else { // No mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0; 
      memoryWasUpdated = true; 
    }
  }
  else { // Did not find better neighbor
    if (prob < probMistake) { // Mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0;
      memoryWasUpdated = true; 
    }
    else { // No mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
  }

  if (numberOfVisitsOverLimit == true) {
    bees[i].status = 0; 
    bees[i].numberOfVisits = 0;
    int x = random.Next(numberInactive); 
    bees[indexesOfInactiveBees[x]].status = 1; 
    indexesOfInactiveBees[x] = i; 
  }
  else if (memoryWasUpdated == true) {
    if (bees[i].measureOfQuality < this.bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length); 
      this.bestMeasureOfQuality = bees[i].measureOfQuality
    }
    DoWaggleDance(i);
  }
  else {
    return;
  }
}

La méthode ProcessActiveBee accepte un paramètre d'entrée unique, i, qui est l'index de l'abeille dans le tableau bees. L'abeille active obtient tout d'abord une solution voisine relative à sa solution actuelle stockée dans memoryMatrix, puis détermine la qualité de cette solution voisine :

char[] neighbor =
  GenerateNeighborMemoryMatrix(bees[i].memoryMatrix); 
double neighborQuality = MeasureOfQuality(neighbor);

Ensuite, l'algorithme définit trois variables locales qui seront utilisées ultérieurement :

double prob = random.NextDouble();)
bool memoryWasUpdated = false; 
bool numberOfVisitsOverLimit = false;

La valeur de la variable prob se situe entre 0,0 et 1,0 et sera comparée à la valeur du champ probMistake pour déterminer si l'abeille fait une erreur lors de l'évaluation de la solution voisine (c'est-à-dire, si elle rejette une solution voisine meilleure ou si elle accepte une solution voisine moins bonne).

La valeur booléenne memoryWasUpdated sera utilisée pour déterminer si l'abeille active devrait exécuter une danse frétillante devant les abeilles inactives (si elle est définie sur true) ou non (si elle est définie sur false). La valeur booléenne numberOfVisitsOverLimit sera comparée au champ maxNumberVisits pour déterminer si l'abeille a épuisé une source de nourriture particulière sans trouver de solution voisine meilleure et devrait, dans cas, passer d'un état actif à inactif.

Si l'abeille actuelle trouve une meilleure solution voisine, l'algorithme détermine si l'abeille fait une erreur et rejette cette solution voisine meilleure ou si elle l'accepte. De même, si l'abeille actuelle n'a pas trouvé de solution voisine meilleure, l'algorithme détermine si l'abeille fait une erreur et accepte la solution voisine moins bonne ou si elle ne fait pas d'erreur et rejette celle-ci.

Notez que deux types d'erreurs différents sont possibles, mais que tous deux offrent la même probabilité, probMistake = 0,01. Certaines recherches suggèrent que l'utilisation de deux probabilités différentes pour les deux types d'erreurs différents n'améliore pas l'efficacité des algorithmes SBC, mais vous avez la possibilité de faire des essais avec deux valeurs de seuil différentes.

Une fois que l'abeille active actuelle accepte ou refuse la solution voisine, l'algorithme vérifie si le compteur du nombre de visites a dépassé le seuil maxNumberVisits. Si c'est le cas, l'abeille actuelle passe à l'état inactif, une abeille inactive sélectionnée de manière aléatoire passe à l'état actif et le tableau indexesOfInactiveBees est mis à jour. Ensuite, l'algorithme vérifie si la mémoire de l'abeille a été mise à jour. Si c'est le cas, la nouvelle solution est vérifiée pour voir s'il s'agit d'une nouvelle solution globale optimale, puis une méthode d'assistance privée, DoWaggleDance, est appelée pour simuler l'abeille qui revient à la ruche et transmet des informations sur la nouvelle source de nourriture aux abeilles inactives.

Méthode DoWaggleDance

La méthode d'assistance DoWaggleDance simule une abeille active ou éclaireuse qui revient à la ruche et qui effectue une danse frétillante devant les abeilles inactives pour transmettre des informations sur l'emplacement et la qualité d'une source de nourriture. Voici la méthode DoWaggleDance :

private void DoWaggleDance(int i) {
  for (int ii = 0; ii < numberInactive; ++ii) {
    int b = indexesOfInactiveBees[ii]; 
    if (bees[i].measureOfQuality < bees[b].measureOfQuality) {
      double p = random.NextDouble(); 
      if (this.probPersuasion > p) {
        Array.Copy(bees[i].memoryMatrix, bees[b].memoryMatrix,
          bees[i].memoryMatrix.Length);
        bees[b].measureOfQuality = bees[i].measureOfQuality;
      } 
    } 
  } 
}

Le paramètre d'entrée, i, représente l'index de l'abeille actuelle qui effectue la danse frétillante virtuelle. La mesure de la qualité de la solution de l'abeille actuelle est comparée à la mesure de la qualité de chaque abeille inactive. Si la solution de l'abeille actuelle est meilleure et que l'abeille inactive actuelle est convaincue (avec une probabilité probPersuasion = 0,90), la mémoire de l'abeille actuelle est copiée vers la mémoire de l'abeille inactive.

Notez qu'il existe de nombreuses opportunités d'insérer une vérification des erreurs dans le code présenté dans cet article. Par exemple, à l'intérieur de la boucle For de la méthode DoWaggleDance, vous avez la possibilité de vérifier l'état actuel de l'abeille inactive avec :

if (bees[b].status != 0) throw new Exception(. . .);

Ou alors, vous pouvez vérifier le compteur du nombre de visites de l'abeille inactive avec :

if (bees[b].numberOfVisits != 0) throw new Exception(. . .);

ProcessScoutBee et ProcessInactiveBee

La méthode d'assistance ProcessScoutBee utilisée par la méthode Solve simule l'action d'une abeille éclaireuse qui cherche de manière aléatoire des sources de nourriture attrayantes. La méthode ProcessScoutBee est présentée à la Figure 11.

Figure 11 Méthode ProcessScoutBee

private void ProcessScoutBee(int i) {
  char[] randomFoodSource = GenerateRandomMemoryMatrix();
  double randomFoodSourceQuality = 
    MeasureOfQuality(randomFoodSource);
  if (randomFoodSourceQuality < bees[i].measureOfQuality {
    Array.Copy(randomFoodSource, bees[i].memoryMatrix,
      randomFoodSource.Length);
    bees[i].measureOfQuality = randomFoodSourceQuality;
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    } 
    DoWaggleDance(i);
  }
}

Le paramètre d'entrée i représente l'index d'une abeille éclaireuse dans le tableau bees. Une éclaireuse génère une solution aléatoire, vérifie si la solution aléatoire est meilleure que la solution actuelle en mémoire et, si tel est le cas, copie la solution aléatoire dans la mémoire. Rappelez-vous que les valeurs exprimant de faibles quantités sont préférables. Si l'éclaireuse a trouvé une meilleure solution, l'algorithme vérifie si la nouvelle solution est une solution globale optimale.

Notez que, contrairement aux abeilles actives, dans cette implémentation SBC les éclaireuses ne font jamais d'erreurs en évaluant la qualité d'une source de nourriture. Il n'existe actuellement aucune recherche sur l'effet d'erreurs qui seraient commises par des abeilles éclaireuses.

La méthode ProcessInactiveBee se présente comme suit :

`private void ProcessInactiveBee(int i) {
  return;
}
private void ProcessInactiveBee(int i) {
  return;
}

Dans cette implémentation SBC les abeilles inactives sont précisément ainsi, inactives. La méthode ProcessInactiveBee est donc simplement un paramètre fictif pour le cas où vous souhaiteriez implémenter une logique propre au problème pour une abeille inactive. Une modification possible pourrait être de modifier de manière aléatoire la mémoire d'une abeille inactive avec une probabilité très faible.

Synthèse

Le processus global d'implémentation d'un algorithme SBC débute par l'identification du problème. Les problèmes d'optimisation combinatoire complexes et non numériques, sans solutions déterministes pratiques sont souvent de bons candidats à une solution par colonie d'abeilles simulée. Le problème cible doit pouvoir représenter une solution (souvent sous forme de tableau ou matrice), et chaque solution doit avoir une solution voisine quelconque et une mesure de la qualité de la solution.

Prenons par exemple le problème de division d'un graphique en deux parties afin que le nombre de connexions dans chaque partie soit maximal et que celui des connexions entre les deux parties soit minimal. Ce problème de division d'un graphique est combinatoire et il n'existe aucun algorithme rapide permettant de trouver la solution optimale (bien qu'il y ait des algorithmes déterministes efficaces pour trouver des solutions quasi optimales). Beaucoup d'autres problèmes NP-complet ou NP-dur pourraient être abordés à l'aide d'une colonie d'abeilles simulée.

Les algorithmes SBC sont basés sur le comportement de systèmes naturels. Il existe d'autres algorithmes du même type, notamment les algorithmes génétiques (AG), basés sur l'évolution et la sélection naturelle, l'optimisation par colonie de fourmis (ACO, Ant Colony Optimization), basée sur le comportement de fourmis, et le recuit simulé (RS), basé sur les propriétés physiques des métaux qui refroidissent.

Les algorithmes basés sur les systèmes des systèmes naturels sont souvent faciles à implémenter par rapport aux approches déterministes. Cependant, les algorithmes basés sur des systèmes naturels requièrent généralement de spécifier des valeurs pour plusieurs paramètres qui ont tendance à être sensibles quant à leurs effets sur la vitesse de convergence de la solution et l'exactitude de la solution. Dans le cas d'une colonie d'abeilles simulées, les paramètres sensibles qui doivent être ajustés pour chaque problème comprennent le nombre de chaque type d'abeille, le nombre maximal de visites avant que la source de nourriture soit épuisée, le seuil de probabilité de persuasion des abeilles inactives et la probabilité d'erreur des abeilles actives.

Bien que les algorithmes SBC ne soient pas applicables à chaque problème, ils peuvent être des outils extrêmement puissants dans certains scénarios. 

Le Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Campus Microsoft à Redmond (État de Washington). Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Le Dr. James McCaffrey est l'auteur de « NET Test Automation Recipes » (Apress, 2006). Vous pouvez le contacter à l'adresse jammc@microsoft.com.

Merci aux experts techniques suivants d'avoir relu cet article : Dan Liebling et Anne Loomis Thompson, membres de l'équipe Microsoft Research