Natürliche Algorithmen

Bienenstock-Algorithmen zur Lösung scheinbar unlösbarer Probleme

James McCaffrey

Beispielcode herunterladen.

Simulierte Bienenstockalgorithmen (Simulated Bee Colony, SBC) modellieren das Verhalten von Honigbienen und können verwendet werden, um Lösungen für schwierige oder unlösbar scheinende kombinatorische Probleme zu finden. In diesem Artikel erkläre ich, was genau SBC-Algorithmen sind, beschreibe die Art von Problemen, die mit SBC-Algorithmen gelöst werden können, und zeige ein vollständiges Beispiel für die Verwendung eines SBC-Algorithmus zur Lösung des „Handlungsreisendenproblems“.

Eine gute Möglichkeit, sich einen Eindruck von SBC-Algorithmen zu verschaffen und zu verstehen, worauf ich in diesem Artikel abziele, ist die Betrachtung des Demoprogramms in Abbildung 1. Das Demoprogramm verwendet einen SBC-Algorithmus, um einen Satz aus 20 Städten (A bis T) zu analysieren und den kürzesten Weg zu finden, auf dem jede Stadt genau einmal besucht werden kann. Die Daten für die Städte sind künstlich konstruiert, sodass der beste Pfad in Stadt A beginnt und in Stadt T endet und eine Länge von 19 Einheiten hat.

Abbildung 1 Demo eines simulierten Bienenstocks

Der SBC-Algorithmus instanziiert im Hintergrund einen Bienenstock mit 100 simulierten Bienen. Jede dieser Bienen hat eine zufällige mögliche Lösung. Zu Beginn hat die beste der zufälligen Lösungen eine Pfadlänge von 95 Einheiten. Der SBC-Algorithmus beginnt eine Verarbeitungsschleife, angezeigt durch den textbasierten Fortschrittbalken, die das Verhalten von Bienen bei der Nahrungssuche simuliert. Am Ende der SBC-Verarbeitungsschleife enthält die beste gefundene Lösung 16 korrekte Stadtpositionen von 20 und hat eine Pfadlänge von 26,5. Dies ist nahe der optimalen Lösung, aber nicht die optimale Lösung.

SBC-Algorithmen werden häufig metaheuristisch genannt, da sie einen allgemeinen Rahmen und Richtliniensatz für die Entwicklung einer Problemlösung bereitstellen und keine detaillierte Beschreibung der Lösung. In diesem Artikel wird ein Beispiel gezeigt, in dem SBC verwendet wird, um ein bestimmtes Problem zu lösen. Wenn Sie verstanden haben, wie ein SBC-Algorithmus zur Lösung eines Problems verwendet werden kann, können Sie den hier gezeigten SBC-Algorithmus zur Lösung eigener Probleme verwenden. Dieser Artikel zeigt, dass SBC-Algorithmen am besten für die Lösung komplexer kombinatorischer Probleme geeignet sind, für die es keine praktischen deterministischen Lösungen gibt.

Dieser Artikel setzt mittlere Programmierkenntnisse voraus. Das Beispiel in diesem Artikel wurde mittels C# programmiert. Der Code wurde jedoch so geschrieben, dass er leicht in andere Programmiersprachen übertragen werden kann. Ich denke, Sie werden diesen Artikel sehr interessant finden und SBC-Algorithmen als nützliche Ergänzung Ihrer Fähigkeiten erkennen.

Bienen

Die allgemeine Honigbiene, Apis mellifera, spielt in ihrem Stock über die Zeit verschiedene Rollen. Ein typischer Stock hat 5.000 bis 20.000 Bienen. Erwachsene Bienen (im Alter von 20 bis 40 Tagen) werden in der Regel zu Nahrungssammlern. Diese Sammlerbienen haben in der Regel eine von drei Rollen: aktive Sammler, Erkundungssammler und inaktive Sammler.

Aktive Sammlerbienen suchen Futterquellen auf, untersuchen benachbarte Futterquellen, sammeln Futter und kehren zum Stock zurück.

Erkundungsbienen untersuchen den Bereich um den Stock. Dieser Bereich kann bis zu 80 Quadratkilometer umfassen. Dort suchen sie nach attraktiven neuen Futterquellen. Ungefähr 10 Prozent der Sammlerbienen in einem Stock sind Erkundungsbienen.

Zu jedem Zeitpunkt sind einige der Sammlerbienen inaktiv. Diese inaktiven Sammlerbienen warten nahe dem Eingang des Stocks. Wenn aktive Sammlerbienen und Erkundungsbienen zum Stock zurückkehren, führen sie – abhängig von der Qualität der gerade besuchten Futterquelle – einen Tanz für die wartenden inaktiven Sammlerbienen auf. Es gibt konkrete Hinweise darauf, dass dieser Tanz den inaktiven Sammlerbienen Informationen zum Ort und zur Qualität der Futterquelle gibt. Die inaktiven Sammlerbienen erhalten diese Informationen zu Futterquellen aus dem Tanz und werden möglicherweise zu aktiven Sammlerbienen.

Im Allgemeinen sammelt eine aktive Sammlerbiene solange Futter aus einer bestimmten Futterquelle, bis diese erschöpft ist. Dann wird aus dieser Biene eine inaktive Sammlerbiene.

Das Problem des Handelsreisenden

Das Handelsreisendenproblem (Traveling Salesman Problem, TSP) gehört zu den am besten erforschten Problemen in der Informatik. Es gibt zahlreiche Varianten des TSP. Im Grunde geht es jedoch stets darum, den kürzesten Pfad zu finden, auf dem jeder Ort in einem bestimmten Satz von Orten genau einmal besucht wird.

Bei der Betrachtung von Abbildung 1 können Sie erkennen, dass das SBC-Demoprogramm einen Satz aus 20 Orten verwendet, die zufällig mit A bis T benannt sind. Ein gültiger Pfad ist ein strukturierter Satz aus den 20 Ortsbezeichnungen, in dem jeder Ort genau einmal vorkommt. Es gibt daher insgesamt 20! = 2.432.902.008.176.640.000 mögliche Pfade.

Im Hintergrund ist mit jedem Ortspaar ein Distanzwert verknüpft. Einfach ausgedrückt: Wenn Ort c1 < Ort c2, ist die Distanz zwischen c1 und c2 genau das 1,0-Fache der ordinalen Distanz zwischen den Ortsbezeichnungen. Wenn c1 > c2, ist die Distanz das 1,5-Fache der ordinalen Distanz zwischen c1 und c2. Die Distanz zwischen A und B beträgt 1,0 arbiträre Einheiten, die Distanz zwischen B und A beträgt 1,5 Einheiten, die Distanz zwischen A und C beträgt 2,0 Einheiten usw. Daher ist der beste Pfad, auf dem jede Stadt genau einmal besucht wird, A -> B-> C -> ... -> T, und die beste (kürzeste) Padlänge ist (20-1) * 1,0 = 19,0.

In den meisten TSP-Szenarien würden die Entfernungen zwischen Orten nicht künstlich berechnet werden. Stattdessen würden die Entfernungen wahrscheinlich in einer Art von nachschlagbarer Datenstruktur gespeichert werden. Einige TSP-Varianten nehmen an, dass jeder Ort mit allen anderen Orten verbunden ist, und einige Varianten nehmen an, dass nicht alle Orte miteinander verbunden sind. Zusätzlich wird in einigen TSP-Varianten angenommen, dass die Distanz zwischen einem beliebigen Ort c1 und einem Ort c2 die gleiche ist wie die Distanz zwischen c2 und c1. In einigen Varianten des Problems wird diese bidirektionale Annahme nicht gemacht.

Außer in trivialen Situationen ist ein brachialer Ansatz für die Ermittlung des kürzesten Pfads nicht praktikabel. Bei 20 Orten würde die Überprüfung aller 20! möglichen Pfade mehr als 77.000 Jahre dauern, selbst wenn 1 Million Pfade pro Sekunde überprüft werden könnten. Diese Art von extrem schwierigen, kombinatorischen Optimierungsproblemen ist die Art von Problemen, für die SBC-Algorithmen sehr gut geeignet sind.

Das TSP-Dummyproblem ist in einer Klasse namens CitiesData implementiert, wie in Abbildung 2 gezeigt. Der vollständige Quellcode für das SBC-Demoprogramm ist auf code.msdn.microsoft.com/mag201104BeeColony verfügbar.

Abbildung 2 Die Definition der Klasse 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;
  }
}

Die Definition einer Klasse oder Datenstruktur, die Ihr bestimmtes Problem darstellt, wird sich von der hier gezeigten Definition unterscheiden. Als Faustregel gilt jedoch, dass Probleme, die sich gut für die Lösung mittels eines SBC-Algorithmus eignen, in der Regel als ein nicht numerisches Array, eine nicht numerische Matrix oder ein nicht numerisches, gezacktes Array von Arrays dargestellt werden können.

Der CitiesData-Konstruktor akzeptiert einen Wert für die Anzahl der Orte und weist dem ersten Ort die Bezeichnung A, dem zweiten Ort die Bezeichnung B usw. zu.

Die Distance-Methode wird unidirektional definiert, wie ich es zuvor beschrieben habe, und setzt voraus, dass jeder Ort von jedem anderen Ort aus erreicht werden kann.

Die ShortestPathLength-Methode gibt die optimale Länge des Pfads unter Berücksichtigung der Distance-Definition wieder. In den meisten SBC-Fällen verfügen Sie nicht über die erforderlichen Informationen, um eine Methode zu implementieren, die die optimale Lösung zurückgibt.

Die NumberOfPossiblePaths-Methode berechnet ausschließlich n!, wobei n die Anzahl der Orte ist. In einigen TSP-Szenarien ist die Anzahl der möglichen Pfade n-1! (wenn der Startort nicht wichtig ist), und in einigen Szenarien ist die Anzahl der möglichen Pfade n/2! (wenn die Richtung des Pfads nicht wichtig ist).

Die ToString-Methode verwendet Zeichenfolgenkonkatenierung und nicht die effizientere StringBuilder-Klasse, um einen String mit beschreibenden Daten zu assemblieren. Die Zeichenfolgenkonkatenierung wird verwendet, um die Übertragung auf andere Programmiersprachen zu vereinfachen.

In diesem Artikel verwende ich Abkürzungsverfahren, um den Code vergleichsweise kurz und sauber zu halten, die sie im Produktionscode nicht verwenden würden. Beispielsweise habe ich auf den größten Teil der Fehlerprüfung verzichtet. Beispielsweise adressiert die Methode NumberOfPossiblePaths keinen numerischen Overflow, wenn das Ergebnis größer als long.MaxValue ist.

SBC-Programmstruktur

Der in Abbildung 1 gezeigte SBC-Algorithmus wird al seine C#-Konsolenanwendung implementiert. Abbildung 3 zeigt die Gesamtstruktur des Programms. Beachten Sie, dass die SBC-Programmstruktur vergleichsweise einfach ist und nur den einfachen System-Namespace verwendet. Es gibt drei Klassen: die Klasse Program, die nur die Methode Main enthält; die Klasse Hive, die die gesamte SBC-Algorithmuslogik enthält; und die Klasse CitiesData, die im vorherigen Abschnitt dieses Artikels vorgestellt wurde. Die Klasse Hive wurde generisch mit „Hive“ benannt und nicht mit einem spezifischeren Namen wie z. B. TravelingSalesmanHive, obwohl Implementierungen von SBC-Algorithmen stark von dem jeweiligen Problem abhängig sind, das sie lösen sollen.

Abbildung 3 Allgemeine Programmstruktur

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

Die Methode Main ist sehr einfach. Nach der Anzeige der Startnachricht wird das CitiesData-Objekt instanziiert:

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"));

In vielen SBC-Szenarien befinden sich die Problemdaten in einem externen Speicher, z. B. in einer Textdatei oder SQL-Datenbank. Sie laden die Problemdaten in diesem Fall mittels eines Ladekonstruktors oder einer Lademethode entsprechend myProblemData.Load(dataFile).

Als Nächstes wird der Hive-Konstruktor vorbereitet und aufgerufen:

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);

Wie Sie in den nächsten Abschnitten dieses Artikels sehen werden, verwendet ein SBC-Algorithmus drei Arten von Bienen: aktive, inaktive und Erkundungsbienen. Obwohl die Anzahl der einzelnen Arten von Bienen hart kodiert werden kann, ist es in den meisten Szenarien die bessere Entscheidung, diese Zahlen als Parameter an den Hive-Konstruktor zu übergeben, damit die Leistung des Algorithmus einfacher angepasst werden kann.

Der Wert der totalNumberBees-Variablen kann von den anderen drei Variablen abgeleitet werden. Die zusätzliche Variable verbessert hier jedoch die Lesbarkeit des Codes. Die Gesamtzahl der Bienen ist von Ihrem bestimmten Problem abhängig. Mehr Bienen sind zwar besser, verlangsamen jedoch die Ausführung des Programms. Was das Verhältnis der drei Arten von Bienen angeht, zeigen Studien, dass das Verhältnis von aktiven, inaktiven und Erkundungsbienen häufig am besten in etwa 75 Prozent, 10 Prozent und 15 Prozent entspricht. 

Der für die maxNumberVisits-Variable verwendete Wert 100 wird in Kürze erklärt werden. Er steht jedoch im Zusammenhang mit der Anzahl der Nachbarlösungen, die mit einer bestimmten Lösung verwandt sind.

Die maxNumberCycles-Variable wird zur Steuerung der Anzahl der Wiederholungen der Solve-Routine verwendet. Dies ist notwendig, da in Szenarien mit SBC-Algorithmen Sie häufig nicht wissen, ob Sie eine optimale Lösung erreicht haben. Wenn Sie die optimale Lösung kennen, dann gibt es kein Problem, das Sie lösen müssten. In diesem Beispiel ist der Wert für maxNumberCycles auf 3.460 begrenzt, sodass der SBC-Algorithmus kein perfektes Ergebnis erzielte. Der Punkt hier ist, dass SBC-Algorithmen zwar ein optimales Ergebnis erzielen können, Sie jedoch gewöhnlich nicht wissen können, wann dies der Fall ist. Daher müssen Sie sich mit einem guten Ergebnis zufrieden geben.

Wenn der Konstruktor ausgeführt wird, erzeugt er eine Sammlung von Bienen, von denen jede über eine zufällige Lösung verfügt. Das Hive-Objekt ermittelt den insgesamt besten (kürzesten) Pfad, den eine Biene aus dem Stock findet, sowie die mit der besten Lösung verknüpfte Pfadlänge.

Nach dem Aufruf des Hive-Konstruktors verwendet die Main-Methode die ToString-Methode, um die anfänglichen, zufällig generierten Hive-Werte anzuzeigen, ruft die Solve-Methode mit einem Parameter auf, der anzeigt, dass ein textbasierter Fortschrittsbalken gedruckt werden sollte, und zeigt anschließend den besten gefundenen Pfad und die mit diesem verknüpfte Pfadlänge an:

...
  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");
}

Die Bee-Klasse

Wie in Abbildung 3 gezeigt, enthält die Hive-Klasse eine verschachtelte Definition der Bee-Klasse. Die Details der Bee-Definition werden in Abbildung 4 aufgelistet.

Abbildung 4 Definition der Bee-Klasse

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;
  }
}

Die Bee-Klasse hat drei Datenfelder, die allen SBC-Implementierungen gemeinsam sind, und ein problemspezifisches Datenfeld. Das problemspezifische Feld hat die Bezeichnung memoryMatrix. Jede SBC-Implementierung muss über eine Möglichkeit verfügen, eine Lösung darzustellen. Im Fall des TSP in diesem Artikel kann eine Lösung mittels eines Arrays des Typs char dargestellt werden. Ich möchte betonen, dass das lösungsdarstellende Objekt in hohem Maß vom betreffenden Problem abhängig ist und jedes Problem getrennt analysiert werden muss, um eine sinnvolle Lösungsdarstellung zu generieren.

Das Feld namens „status“ enthält einen int-Wert, der den Typ des Bee-Objekts anzeigt: 0 für inaktiv, 1 für aktiv und 2 für Erkundung. Wenn Sie in einer Sprache kodieren, die Enumerierungstypen unterstützt, werden Sie das Statusfeld wahrscheinlich als Enumerierung übernehmen.

Das Feld „measureOfQuality“ enthält double-Wert, der die Qualität von memoryMatrix des Bee-Objekts darstellt. Im Fall des TSP ist die Pfadlänge, die vom memoryMatrix-Objekt dargestellt wird, ein natürliches Maß für die Qualität. Beachten Sie, dass in dieser Situation kürzere Pfade besser als längere Pfade sind. Kleinere Werte im measureOfQuality-Feld stellen daher bessere Lösungen als größere Werte dar. Jede SBC-Implementierung muss in der Lage sein, das Maß der Lösungsqualität zu berechnen. In vielen Situationen wird dieses Maß am besten durch einen Wert des Typs double dargestellt.

Das dritte gemeinsame Datenfeld in der Bee-Klasse heißt numberOfVisits. Dieses Feld enthält einen int-Wert, der die Anzahl der Besuche des Bee-Objekts bei einer bestimmten Futterquelle/Problemlösung darstellt, ohne dass eine bessere benachbarte Lösung gefunden wurde. Dieses Feld wird für die Simulierung einer Biene verwendet, die eine Futterquelle besucht, bis diese Futterquelle aufgebraucht ist. Wenn im Fall einer aktiven Biene der Wert des numberOfVisits-Felds einen bestimmten Grenzwert überschreitet, hat die simulierte Biene die Futterquelle erschöpft und wird in den inaktiven Status versetzt (und eine inaktive Biene wird in den aktiven Status versetzt).

Der Bee-Konstruktor akzeptiert Werte für die vier Datenfelder: status, memoryMatrix, measureOfQuality und numberOfVisits. Beachten Sie, dass der Bee-Konstruktor einen Wert für measureOfQuality akzeptieren muss, da das Bee-Objekt diesen nicht direkt anhand des memoryMatrix-Felds berechnen kann. Das Maß für die Qualität ist von den Informationen abhängig, die im problemspezifischen CitiesData-Objekt gespeichert sind.

Die Definition der Bee-Klasse enthält die ToString-Methode, die die Werte der vier Datenfelder veröffentlicht. Die Bee.ToString-Methode ist nicht unbedingt notwendig, kann jedoch während der SBC-Entwicklung ziemlich nützlich sein, um Fehler mittels WriteLine-Anweisungen zu entdecken.

Die Hive-Datenfelder

Die Hive-Klasse wird in Abbildung 5 vorgestellt. Es gibt 14 Hive-Datenfelder. Das Verstehen des Zwecks jedes dieser Datenfelder ist wichtig, um zu verstehen, wie ein spezifischer SBC-Algorithmus implementiert wird.

Abbildung 5 Die 14 Hive-Datenfelder

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;

Aus Gründen der Einfachheit und des leichteren Debuggens mittels WriteLine-Anweisungen werden alle 14 Datenfelder mit öffentlichem Bereich definiert. Sie sollten die Felder auf den privaten Bereich beschränken und Eigenschaften für diejenigen Felder erstellen, auf die Sie außerhalb der Klassendefinition zugreifen müssen.

Das erste Feld heißt random ist vom Typ Random. SBC-Algorithmen sind probabilistisch, und das random-Objekt wird für die Generierung von pseudo-zufälligen Zahlen für verschiedene Zwecke verwendet. Das random-Objekt wird im Hive-Konstruktor instantiiert.

Das zweite Datenfeld ist ein Objekt vom Typ CitiesData. Die SBC-Implementierung muss Details des Problems kennen, das gelöst wird. In den meisten Fällen werden die Problemdaten als Objekt dargestellt. Dies trifft auch auf unser Beispiel zu. Denken Sie daran, dass CitiesData eine Liste von Ortsbezeichnungen und eine Methode besitzt, die die Entfernung zwischen zwei beliebigen Orten wiedergibt.

Das dritte bis sechste Datenfeld sind int-Variablen, die die Gesamtzahl der Bienen, die Anzahl der inaktiven Bienen, die Anzahl der aktiven Bienen und die Anzahl der Erkundungsbienen enthalten. Da jede Biene eine mögliche Lösung darstellt, ist eine große Zahl von Bienen im Stock besser, wie bereits gesagt. Eine höhere Zahl an Bienen reduziert jedoch die Leistung des Programms.

Das siebte Datenfeld heißt maxNumberCycles und ist ein Grenzwert, der verwendet wird, um die zeitliche Dauer der Ausführung der Solve-Methode zu beschränken. Ein Zyklus stellt die Verarbeitung jeder Biene im Stock dar.

Das achte Datenfeld heißt maxNumberVisits und ist ein Grenzwert, der verwendet wird, um zu verhindern, dass eine Biene zu lange bei einer bestimmten Lösung verweilt. Bei jeder Iteration der Hauptverarbeitungsschleife in der Solve-Methode wird der numberOfVisits-Zähler einer Biene um 1 erhöht, wenn diese keine benachbarte Futterquelle mit besserer Qualität findet. Wenn der Wert für den numberOfVisits-Zähler in einem Bee-Objekt den maxNumberVisits-Grenzwert überschreitet, wechselt die Biene in den inaktiven Status.

Das neunte Datenfeld namens probPersuasion ist ein probabilistischer Grenzwert, der für die Entscheidung verwendet wird, ob eine inaktive Biene, die den Tanz einer Biene beobachtet, die mit einer besseren Lösung zum Stock zurückgekehrt ist, ihr Gedächtnis mit der besseren Lösung aktualisiert.

Der Wert von probPersuasion ist als 0,90 hart kodiert. Das bedeutet, dass eine inaktive Biene in 90 Prozent aller Fälle eine bessere Lösung akzeptieren wird. Der Wert von 0,90 für probPersuasion basiert auf Ergebnissen von Studien. Sie können jedoch auch andere Werte versuchen. Höhere Werte bringen einen SBC-Algorithmus hervor, der schneller zu einer Lösung kommt. Gleichzeitig ist jedoch das Risiko höher, dass es sich dabei um eine nicht optimale Lösung handelt.

Das zehnte Datenfeld namens probMistake ist ein probabilistischer Grenzwert, der für die Entscheidung verwendet wird, ob eine aktive Biene einen Fehler machen wird, d. h., fälschlicherweise eine benachbarte Lösung ablehnt, die besser als die aktuelle Lösung der Biene ist, oder fälschlicherweise eine benachbarte Lösung akzeptiert, die schlechter als die aktuelle Lösung der Biene ist. Der Wert von probMistake ist als 0,01 hart kodiert. Das bedeutet, dass eine aktive Biene in 1 Prozent aller Fälle einen Fehler bei der Evaluierung einer benachbarten Lösung machen wird.

Das elfte Datenfeld namens bees ist ein Array von Bee-Objekten. Denken Sie daran, dass jede Biene einen Status hat (aktiv, inaktiv und Erkundung), eine Lösung (memoryMatrix), eine Messung der Lösungsqualität (measureOfQuality) und eine Zählung der Häufigkeit, mit der eine bestimmte Futterquelle aufgesucht wurde, ohne dass eine bessere benachbarte Futterquelle gefunden wurde (numberOfVisits). Da eine Biene als Klasse definiert ist, ist jeder Eintrag im Bienenarray ein Verweis auf ein Bee-Objekt.

Das zwölfte Datenfeld heißt bestMemoryMatrix und ist ein Array von char. Es stellt die beste Lösung im Bienenarray dar. Denken Sie daran, dass die Darstellung der Problemlösung vom Problem abhängig ist, da simulierte Bienenstockalgorithmen spezifische Implementierungen eines Metaheurismus sind. Ein alternativer Entwurfsansatz zur Hartkodierung einer Lösungstypdefinition besteht in der Parametrisierung dieses Datenfelds als generischer Typ. Wenn ich einen SBC-Algorithmus verwende, versuche ich in der Regel, ein bestimmtes Problem zu lösen. Daher ziehe ich es vor, jede SBC-Implementierung von Grund auf neu zu kodieren.

Das dreizehnte Datenfeld heißt bestMeasureOfQuality und ist das Maß der Qualität, das der bestMemoryMatrix-Lösung entspricht.

Das letzte Hive-Datenfeld heißt indexesOfInactiveBees und ist ein Array von int. Dieses Array enthält die Indexe der Bienen im Stock, die zurzeit inaktiv sind. Denken Sie daran, dass aktive Bienen in den inaktiven Status und inaktive Bienen in den aktiven Status wechseln können. Die Implementierung eines SBC-Algorithmus muss häufig ermitteln, welche Bienen gerade inaktiv sind, wenn eine aktive Biene den virtuellen Tanz aufführt. Das Speichern der Indexe der inaktiven Bienen verbessert die Leistung im Vergleich zur Iterierung durch das gesamte Bienenarray und Prüfung des Statusfelds jeder einzelnen Biene.

Die visuelle Darstellung eines möglichen Hive-Objekts wird in Abbildung 6 gezeigt. Der gezeigte Stock hat 10 Bienen: 5 aktive Bienen, zwei Erkundungsbienen und drei inaktive Bienen. Die zurzeit inaktiven Bienen nehmen die Indexpositionen 2, 7 und 4 im Bienenarray ein. Das CitiesData-Objekt hat fünf Orte. Die zurzeit beste Lösung ist:

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

Diese Lösung hat, in Entfernungseinheiten gemessen, eine Pfadlänge von:

1,0 + (3 * 1,0) + (2 * 1,5) + 1,0 = 8,0

Beachten Sie, dass das citiesData-Feld ein Verweis auf ein CitiesData-Objekt außerhalb des Hive-Objekts ist.

Abbildung 6 Die Hive-Darstellung

Der Hive-Konstruktor

Der Code für den Hive-Konstruktor wird in Abbildung 7 gezeigt. Der Hive-Konstruktor akzeptiert sieben Eingabeparameter. Sechs der Parameter sind skalar, und einer ist ein Objekt (CitiesData). Der Parameter totalNumberBees ist redundant in dem Sinne, dass er anhand von numberInactive, numberActive und numberScout ermittelt werden kann. Die verbesserte Lesbarkeit lohnt meiner Meinung nach jedoch den zusätzlichen Code.

Abbildung 7 Hive-Konstruktor

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;
    }
  } 
}

Das random-Objekt wird mit einem Anfangswert von 0 instanziiert. Die Bereitstellung des Anfangswerts ermöglicht Ihnen die Reproduzierung der Ergebnisse. Als Nächstes werden sechs Eingabeparameter für die skalaren Datenfelder in die Hive-Datenfelder kopiert. Das Hive-Objekt verfügt über insgesamt 14 Datenfelder; die probPersuasion- und probMistake-Grenzwerte sind hart kodiert.

Der Hive-Konstruktor empfängt den citiesData-Parameter und weist dem Parameter das citiesData-Feld als Verweis zu. Eine Alternative zu diesem Verweisansatz besteht darin, eine neue Kopie der Problemdaten zu erstellen:

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

Dieser Ansatz benötigt mehr Arbeitsspeicher, vermeidet aber mögliche Fehler. Der alternative Ansatz kann verwendet werden, wenn Sie den hier gezeigten Code in eine Programmiersprache übertragen, die keine Pointer oder Verweise unterstützt.

An diesem Punkt im Hive-Konstruktor haben alle Einträge im Bienenarray den Wert Null. Als Nächstes initialisiert der Konstruktor die global beste Lösung (d. h. die beste Lösung aller Bienen im Stock) und die entsprechende Lösungsqualität:

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

Die GenerateRandomMemoryMatrix-Helfermethode generiert eine zufällige Lösung. Die MeasureOfQuality-Helfermethode akzeptiert die zufällig generierte Lösung und berechnet die Qualität. Ich bespreche den Code für diese beiden Helfermethoden später in diesem Artikel.

Nach der Initialisierung der global besten Lösung und der entsprechenden Qualität teilt der Hive-Konstruktor das indexesOfInactiveBees-Bienenarray unter Verwendung des Werts im Feld numberInactive zu. An diesem Punkt haben alle Werte in diesen Indexen den Wert 0.

Der nächste Abschnitt des Konstruktorcodes iteriert durch jedes Bee-Objekt im Bienenarray und instanziiert dieses unter Verwendung des Bee-Konstruktors. Die Logik in dieser Schleife nimmt an, dass die ersten numberInactive-Zellen im Bienenarray inaktive Bienen, die nächsten numberScout-Zellen Erkundungsbienen und die verbleibenden Zellen aktive Bienen sind.

Wenn es beispielsweise fünf aktive, zwei inaktive und drei Erkundungsbienen gibt, initialisiert der Konstruktor ein Bienenarray der Größe 10 und instanziiert die Zellen 0 und 1 als inaktive Bienen, die Zellen 2 bis 4 als Erkundungsbienen und die Zellen 5 bis 9 als aktive Bienen. Zusätzlich haben hat der indexesOfInactiveBees-Array die Größe 2 und enthält anfangs die Werte 0 und 1.

Nachdem der Status der aktuellen Biene anhand der Schleifenindexvariablen festgelegt wurde, wird eine zufällig generierte Lösung erstellt, deren Qualität berechnet, der Zähler für die Anzahl der Besuche explizit auf 0 gesetzt und der Bee-Konstruktor aufgerufen.

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

Nach der Instanziierung der einzelnen Bienen wird die Qualität der zufällig ausgewählten Lösung der Biene geprüft, um festzustellen, ob diese besser als die global beste Lösung ist. Wenn dies der Fall ist, werden die Lösung der aktuellen Biene und die entsprechende Qualität in die Felder bestMemoryMatrix und bestMeasureOfQuality kopiert. Beachten Sie, dass bei der Prüfung der Qualität hinsichtlich einer global besten Lösung kleinere Werte besser als größere Werte sind, da der Wert für die Qualität die Länge des Pfads ist und das TSP die Länge des Pfads zu minimieren versucht.

Statt das Gedächtnis einer Biene explizit in das bestMemoryMatrix-Array zu kopieren, können Sie dieses auch durch Verweis zuweisen. Dieser Ansatz verbessert die Leistung auf Kosten einer höheren Komplexität.

Drei essenzielle SBC-Methoden

Jede Implementierung eines SBC-Algorithmus muss drei problemspezifische Methoden verwenden: eine Methode zur Generierung einer zufälligen Lösung, eine Methode zur Generierung einer benachbarten Lösung, die einer gegebenen Lösung verwandt ist, und eine Methode zur Berechnung der Qualität einer gegebenen Lösung. In diesem TSP-Beispiel wird jede Methode auf eine angepasste und vollständig problemabhängige Weise implementiert.

Ein alternativer Designansatz besteht in der Definierung von Schnittstellen und deren Implementierung. Die Programmierung mittels Schnittstellen hat Vorteile und Nachteile im Vergleich zum hier verwendeten Ansatz ohne Verwendung von Schnittstellen. Meiner Meinung nach ist dies jedoch zum großen Teil eine Frage der persönlichen Präferenz. Im Folgenden wird die Methode zur Generierung einer zufälligen Lösung, GenerateRandomMemoryMatrix, gezeigt:

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;
}

Da die Lösung für das TSP-Problem ein Array von char ist, bei dem jedes char-Element eine Ortsbezeichnung darstellt, gibt die GenerateRandomMemoryMatrix-Methode ein char-Array zurück. Die Größe des lokalen Ergebnisarrays wird auf der Basis des CitiesData-Objekts des Stocks zugewiesen, und die Ortsbezeichnungen im Verweis des Stocks auf das CitiesData-Objekt werden in den Ergebnisarray kopiert. Die Reihenfolge der Werte im result-Array wird anschließend mittels des random-Objekts für die Klasse und des Fisher-Yates-Mischalgorithmus (oder Knuth-Mischalgorithmus) randomisiert.

Zunächst kann es scheinen, dass die Methode GenerateRandomMemoryMatrix konzeptionell zu einem Bee-Objekt gehört. Da die Generierung einer zufälligen Lösung jedoch teilweise von problemspezifischen Daten abhängig ist, in diesem Fall CitiesData, ist es ein besserer Ansatz, die Methode für die zufällige Generierung in der Hive-Definition zu platzieren.

Die Methode zur Generierung einer benachbarten Lösung, GenerateNeighborMemoryMatrix, wird in Abbildung 8 gezeigt:

Abbildung 8 Generierung einer benachbarten Lösung

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;
}

Ein wesentliches Konzept von SBC-Algorithmen besteht darin, dass jede virtuelle Futterquelle, die eine Lösung darstellt, über eine benachbarte Lösung verfügt. Ohne das Konzept der benachbarten Lösung würde die gesamte Vorstellung eines Algorithmus, der auf dem Verhalten von Bienen basiert, kollabieren. Im Fall des TSP, in dem eine Lösung als ein Array von Ortsbezeichnungen dargestellt werden kann, die einen Pfad von Ort zu Ort wiedergeben, ist eine natürliche benachbarte Lösung, die mit einer aktuellen Lösung verwandt ist, eine Mutation der aktuellen Lösung, bei der zwei benachbarte Orte ausgetauscht wurden.

Wenn beispielsweise die aktuelle TSP-Lösung A, B, C, D, E ist, dann ist eine zu erwartende benachbarte Lösung A, C, B, D, E. Dies ist nicht so offensichtlich, wenn eine Mutation, bei der zwei beliebige Orte ausgetauscht werden (und nicht zwei benachbarte Orte) eine zu erwartende benachbarte Lösung darstellt. Ist im vorherigen Beispiel A, D, C, B, E eine zu erwartende benachbarte Lösung? Die Entscheidung hinsichtlich der Definition einer benachbarten Lösung für einen SBC-Algorithmus ist problemabhängig, und in der Regel sind subjektive Kriterien beteiligt.

Das Konzept der benachbarten Lösung dient auch dazu, teilweise zu belegen, warum nicht numerische kombinatorische Probleme besonders für die Lösung durch SBC-Algorithmen geeignet sind. Wenn ein Problem inhärent numerisch ist, kann das Konzept der benachbarten Lösung nur schwer zufrieden stellend gelöst werden. Wenn ein Problem inhärent kombinatorisch ist, kann das Konzept der benachbarten Lösung häufig durch eine mathematische Mutation oder Kombination gut definiert werden.

Die Methode GenerateNeighborMemoryMatrix akzeptiert die aktuelle memoryMatrix-Darstellung der Lösung einer Biene als einen Eingabeparameter und kopiert diesen in ein Ergebnisarray. Die Methode wählt zufällig einen einzelnen Index für das aktuelle Ergebnisarray aus, indem das random-Objekt für die Klasse verwendet wird. Wenn der zufällige Index auf die letzte Zelle zeigt, werden die erste und die letzte Ortsbezeichnung ausgetauscht. Andernfalls werden die Bezeichnungen ausgetauscht, auf die der zufällig ausgewählte Index und der nächste Index zeigen, wenn der zufällig ausgewählte Index nicht auf die letzte Zelle zeigt.

Das Konzept der benachbarten Lösung ist mit dem Wert maxNumberVisits verwandt. Einige Studien scheinen zu zeigen, dass ein guter Wert für maxNumberVisits ungefähr das 5-Fache der Anzahl der möglichen benachbarten Lösungen für eine gegebene Situation ist. Wenn beispielsweise für drei Städte (A, B, C) eine benachbarte Lösung als der Austausch eines beliebigen Paars benachbarter Orte definiert ist, dann gibt es drei mögliche benachbarte Lösungen (Tausch von A und B, Tausch von B und C, Tausch von A und C). Für 20 Orte ist daher ein angemessener maxNumberVisits-Wert 20 * 5 = 100.

Die Methode für die Evaluierung der Qualität der Lösung einer Biene (MeasureOfQuality) ist:

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;
}

Um ein Problem mittels eines SBC-Algorithmus zu lösen, ist es von wesentlicher Bedeutung, dass die Lösung evaluiert werden kann, um ein Maß der Qualität der Lösung zu erhalten. Konzeptionell gesehen, verfügt ein praktisches kombinatorisches Optimierungsproblem beinahe immer über ein inhärentes und verständliches Maß an Qualität. Praktisch gesehen, kann die Berechnung des Maßes der Qualität einer Lösung jedoch schwierig und zeitaufwendig sein.

In diesem Beispiel iteriert die MeasureOfQuality-Methode einfach durch jedes Paar aufeinander folgender Ortsbezeichnungen in der Lösung, die durch den Parameter memoryMatrix dargestellt wird, ermittelt mittels der Distance-Methode des CitiesData-Objekts die Entfernung zwischen den einzelnen Paaren und anschließend die Gesamtdistanz. Denken Sie daran, dass die Ortsdaten künstlich konstruiert sind, sodass die Entfernung zwischen zwei beliebigen Orten schnell und einfach berechnet werden kann, indem die Ordinalentfernung zwischen zwei Ortsbezeichnungen verwendet wird. In einem echten Problem müsste die Entfernung zwischen zwei Orten jedoch wahrscheinlich in einer Datenstruktur nachgeschlagen werden. In SBC-Implementierungen ist die MeasureOfQuality-Methode häufig die Routine, die die Laufzeit des Programms dominiert. Daher ist es in der Regel den Aufwand wert, sicherzustellen, dass diese Methode eine optimale Leistung aufweist und im Hinblick auf die Arbeitsspeicherressourcen des Hostsystems angemessen ist.

Die Solve-Methode

Die Solve-Methode enthält die gesamte Logik, die das Verhalten der Sammlerbienen zur Lösung eines Problems simuliert. Die Solve-Methode ist moderat komplex und verwendet drei Helfermethoden, ProcessActiveBee, ProcessScoutBee und ProcessInactiveBee. Die Methoden ProcessActiveBee und ProcessScoutBee verwenden ihrerseits die DoWaggleDance-Helfermethode. Die Solve-Methode wird in Abbildung 9 gezeigt.

Abbildung 9 Die Solve-Methode

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("");
}

Der Großteil der tatsächlichen Arbeit wird an die Helfermethoden ProcessActiveBee, ProcessScoutBee und ProcessInactiveBee vergeben. Es wird ein Boole’scher Eingabeparameter an Solve übergeben, um anzuzeigen, ob ein einfacher Fortschrittsbalken gedruckt werden soll. Dies ist bei der Entwicklung eines SBC-Algorithmus nützlich, um die Geschwindigkeit der Implementierung zu überwachen und Leistungsengpässe zu entdecken. Bei diesem Ansatz wird davon ausgegangen, dass die Solve-Methode Teil einer Konsolenanwendung ist.

Der Wert des Boole’schen Parameterwerts wird in eine Boole'sche Variable namens pb übertragen, um mit einem kurzen Variablennamen arbeiten zu können. numberOfSymbolsToPrint ist als 10 festgelegt, sodass jedes Inkrement in der Statusleiste 10 Prozent des Gesamtfortschritts repräsentieren, der durch den maxNumberCycles-Wert festgelegt wird (die Inkrementvariable wird zur Festlegung verwendet, wie viele Zyklen einen Fortschritt von 10 Prozent ergeben).

Nach der Initialisierung der Schleifenvariablen cycle als 0, wird eine while-Schleife für die Verarbeitung der einzelnen Bienen im Stock verwendet. Genauso gut könnte eine for-Schleife verwendet werden. In jedem Zyklus wird das Bienenarray mittels einer for-Schleife iteriert, und jedes Bee-Objekt wird mittels der entsprechenden Helfermethode verarbeitet. Nach der Verarbeitung der einzelnen Bienen verwendet der Code den Modulusoperator %, um zu prüfen, ob ein Update für den Fortschritt unter Verwendung des ^-Zeichens gedruckt werden muss, wenn der Boole’sche Parameter doProgressBar „true“ ist.

Die ProcessActiveBee-Methode

Die ProcessActiveBee-Methode ist das Herz des SBC-Algorithmus und die komplexeste Methode im Hinblick auf Codeumfang und Codeverzweigung. Die ProcessActiveBee-Methode wird in Abbildung 10 gezeigt.

Abbildung 10 Die ProcessActiveBee-Methode

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;
  }
}

Die ProcessActiveBee-Methode akzeptiert einen einzelnen Eingabeparameter i. Dies ist der Index der Biene im Bienenarray. Die aktive Biene erhält zunächst eine benachbarte Lösung, die mit ihrer aktuellen, in memoryMatrix gespeicherten Lösung verwandt ist, und ermittelt anschließend die Qualität dieser benachbarten Lösung:

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

Als Nächstes richtet der Algorithmus drei lokale Variablen ein, die zu einem späteren Zeitpunkt verwendet werden:

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

Die prob-Variable hat einen Wert zwischen 0,0 und 1,0 und wird mit dem Wert für das probMistake-Feld verglichen, um festzustellen, ob die Biene einen Fehler bei der Evaluierung der benachbarten Lösung gemacht hat, d. h. eine bessere benachbarte Lösung abgelehnt oder eine schlechtere benachbarte Lösung akzeptiert hat.

Der Boole’sche Wert für memoryWasUpdated wird verwendet, um festzustellen, on die aktive Biene einen Tanz für die inaktiven Bienen aufführen sollte (wenn true) oder nicht (wenn false). Der Boole’sche Wert für numberOfVisitsOverLimit wird mit dem Wert für das maxNumberVisits-Feld verglichen, um festzustellen, ob die Biene eine bestimmte Futterquelle erschöpft hat, ohne eine bessere benachbarte Lösung zu finden. Wenn dies der Fall ist, wird sie vom aktiven Status in den inaktiven Status konvertiert.

Wenn die aktuelle Biene eine bessere benachbarte Lösung findet, ermittelt der Algorithmus, ob die Biene einen Fehler macht und eine bessere benachbarte Lösung ablehnt, oder ob die Biene die bessere benachbarte Lösung akzeptiert hat. Wenn die aktuelle Biene keine bessere benachbarte Lösung findet, ermittelt der Algorithmus, ob die Biene einen Fehler macht und eine schlechtere benachbarte Lösung akzeptiert, oder ob die Biene keinen Fehler macht und die benachbarte Lösung ablehnt.

Beachten Sie, dass es zwei verschiedene Arten von möglichen Fehlern gibt, beide Arten von Fehlern jedoch die gleiche Wahrscheinlichkeit haben, nämlich probMistake = 0,01. Einige Studien scheinen zu zeigen, dass die Verwendung unterschiedlicher Wahrscheinlichkeiten für die beiden Arten von Fehlern die Effektivität von SBC-Algorithmen nicht verbessert. Sie sollten jedoch dennoch mit zwei verschiedenen Grenzwerten experimentieren.

Nachdem die aktuelle aktive Biene die benachbarte Lösung akzeptiert oder abgelehnt hat, überprüft der Algorithmus, ob die Anzahl der Besuche den maxNumberVisits-Grenzwert überschreitet. Wenn dies der Fall ist, wird der Status der aktuellen Biene zu inaktiv konvertiert, eine zufällig ausgewählte inaktive Biene wird zum aktiven Status konvertiert und das indexesOfInactiveBees-Array wird aktualisiert. Als Nächstes überprüft der Algorithmus, ob das Gedächtnis der Biene aktualisiert wurde. Wenn dies der Fall ist, wird die neue Lösung überprüft, um festzustellen, ob es sich um eine neue global beste Lösung handelt. Anschließend wird die private Helfermethode DoWaggleDance aufgerufen, um die Rückkehr der Biene zum Stock zu simulieren und die Informationen über die neue Futterquelle an die inaktiven Bienen weiterzugeben.

Die DoWaggleDance-Methode

Die DoWaggleDance-Helfermethode simuliert die Rückkehr einer aktiven oder Erkundungsbiene zum Stock und die anschließende Aufführung des Tanzes für inactive Bienen, um diesen Informationen zum Ort und zur Qualität der Futterquelle mitzuteilen. Dies ist die DoWaggleDance-Methode:

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;
      } 
    } 
  } 
}

Der Eingabeparameter i ist der Index der aktuellen Biene, die den Tanz aufführt. Das Maß der Qualität der Lösung der aktuellen Biene wird mit dem Maß der Qualität der Lösung der einzelnen inaktiven Bienen verglichen. Wenn die Lösung der aktuellen Biene besser ist, und die aktuell inaktive Biene davon überzeugt werden kann (die Wahrscheinlichkeit hierfür ist probPersuasion = 0,90), wird das Gedächtnis der aktuellen Biene in das Gedächtnis der inaktiven Biene kopiert.

Beachten Sie, dass es viele Möglichkeiten für das Einfügen von Fehlerprüfungen in den in diesem Artikel vorgestellten Code gibt. Im for-Loop in DoWaggleDance sollten Sie den Status der aktuell inaktiven Biene wahrscheinlich wie folgt überprüfen:

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

Oder Sie verifizieren die Anzahl der Besuche der inaktiven Biene wie folgt:

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

ProcessScoutBee und ProcessInactiveBee

Die ProcessScoutBee-Helfermethode, die von der Solve-Methode verwendet wird, simuliert die Aktion einer Erkundungsbiene, die nach dem Zufallsprinzip nach Futterquellen sucht. Die ProcessScoutBee-Methode wird in Abbildung 11 gezeigt.

Abbildung 11 Die ProcessScoutBee-Methode

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);
  }
}

Der Eingabeparameter i ist der Index einer Erkundungsbiene im Bienenarray. Eine Erkundungsbiene generiert eine zufällige Lösung und überprüft, ob die zufällige Lösung besser als die aktuelle Lösung im Speicher ist. Wenn dies der Fall ist, wird die zufällige Lösung in den Speicher kopiert. Denken Sie daran, dass kleinere Werte besser sind. Wenn eine Erkundungsbiene eine bessere Lösung gefunden hat, überprüft der Algorithmus, ob die neue Lösung eine global beste Lösung ist.

Beachten Sie, dass – anders als im Fall aktiver Bienen – Erkundungsbienen in dieser SBC-Implementierung niemals Fehler bei der Evaluierung der Qualität einer Futterquelle machen. Zurzeit gibt es keine Studien zu den Auswirkungen von Fehlern durch Erkundungsbienen.

Die ProcessInactiveBee-Methode ist:

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

In dieser SBC-Implementierung sind inaktive Bienen genau dies – inaktiv. Die ProcessInactiveBee-Methode ist lediglich ein Platzhalter für den Fall, dass Sie eine problemabhängige Logik für inaktive Bienen implementieren möchten. Eine mögliche Modifizierung könnte darin bestehen, das Gedächtnis einer inaktiven Biene zufällig zu verändern und hierfür eine sehr niedrige Wahrscheinlichkeit festzulegen.

Zusammenfassung

Die Implementierung eines SBC-Algorithmus beginnt mit der Identifizierung des Problems. Komplexe, nicht numerische und kombinatorische Optimierungsprobleme ohne praktische deterministische Lösungen sind häufig gute Kandidaten für eine SBC-Lösung. Das Zielproblem muss die Lösung darstellen können (häufig in Form eines Arrays oder einer Matrix), und jede Lösung muss eine benachbarte Lösung und ein Maß für die Lösungsqualität haben.

Betrachten Sie beispielsweise das Problem der Teilung eines Graphen in zwei Abschnitte, sodass die Anzahl der Verbindungen innerhalb der beiden Abschnitte maximiert und die Anzahl der Verbindungen zwischen den beiden Abschnitten minimiert wird. Dieses Problem der Graphenteilung ist kombinatorisch, und es gibt keinen passenden Algorithmus für die optimale Lösung. (Es gibt jedoch deterministische Algorithmen, die in der Lage sind, beinahe optimale Lösungen zu finden.) Es gibt zahlreiche weitere vollständige oder harte NP-Probleme, die mittels eines SBC-Algorithmus gelöst werden können.

SBC-Algorithmen basieren auf dem Verhalten natürlicher Systeme. Es gibt weitere Algorithmen dieser Art, darunter genetische Algorithmen (GA), die auf natürlicher Auswahl und Evolution basieren, die Ameisenkolonie-Optimierung (Ant Colony Optimization, ACO), die auf dem Verhalten von Ameisen basiert, und das simulierte Ausglühen (Simulated Annealing, SA), das auf den physikalischen Eigenschaften abkühlender Metalle basiert.

Algorithmen, die auf natürlichen Systemen basieren, sind im Vergleich zu deterministischen Ansätzen häufig einfacher zu implementieren. Algorithmen auf der Basis natürlicher Systeme erfordern in der Regel jedoch die Spezifizierung der Werte für verschiedene Parameter, die häufig eine kritische Bedeutung für die Geschwindigkeit der Lösungskonvergenz und für die Lösungsgenauigkeit haben. Im Fall eines SBC-Algorithmus gehören zu den kritischen Parametern, die für das jeweilige Problem optimiert werden müssen, die Anzahl der Bienen in den verschiedenen Bienentypen, die maximale Anzahl der Besuche an einer Futterquelle, bevor diese erschöpft ist, der Grenzwert für die Überzeugung inaktiver Bienen und die Wahrscheinlichkeit für Fehler der aktiven Bienen.

Obwohl SBC-Algorithmen nicht auf jedes Problem angewendet werden können, können sie für einige Szenarien äußerst leistungsfähige Tools darstellen. 

Dr. James McCaffrey ist Mitarbeiter von Volt Information Sciences Inc. Dort leitet er die technischen Schulungen für Software-Ingenieure, die auf dem Campus von Microsoft in Redmond arbeiten. Er hat an mehreren Microsoft-Produkten mitgearbeitet, darunter Internet Explorer und MSN Search. Dr. McCaffrey ist der Autor von „.NET Test Automation Recipes“ (Rezepte für die .NET-Testautomatisierung, Apress 2006) und kann unter jammc@microsoft.com erreicht werden.

Unser Dank gilt den folgenden technischen Experten für die Durchsicht dieses Artikels: Dan Liebling und Anne Loomis Thompson, beide Mitarbeiter von Microsoft Research