Dieser Artikel wurde maschinell übersetzt.
Testlauf
Ameisenalgorithmus
.jpg "James McCaffrey")
Im Artikel dieses Monats präsentiere ich C#-Code, der einen Ant Colony Optimization (ACO) Algorithmus zum lösen das Traveling Salesman Problem (TSP) implementiert.Ein ACO-Algorithmus ist eine künstliche Intelligenz-Technik basierend auf die Pheromon-Verlegung Verhalten der Ameisen; Es kann verwendet werden, um Lösungen für überaus komplexe Probleme zu finden, die den optimalen Weg durch einen Graphen suchen.Der beste Weg um zu sehen, wohin ich bin ist ein Blick auf den Screenshot in Abbildung 1.In diesem Fall ist die Demo Lösung eine Instanz des TSP mit dem Ziel den kürzesten Weg, der jeder der 60 Städte genau einmal besucht.Das Demoprogramm verwendet vier Ameisen; jede Ameise ist eine mögliche Lösung.ACO erfordert die Angabe verschiedener Parameter wie die Pheromon-Einflussgrößen (Alpha) und der Pheromon-Verdunstung-Koeffizient (Rho), die ich später eingehen werde.Die vier Ameisen sind auf zufällige Spuren durch die 60 Städte initialisiert; nach der Initialisierung hat die besten Ameise eine kürzeste Strecke Länge von 245,0 Einheiten.Die zentrale Idee der ACO ist die Verwendung von simulierte Pheromone, die Ameisen besser Wanderwege durch das Diagramm ziehen.Die wichtigsten Verarbeitungsschleife wechselt zwischen die Ameise Wege anhand der aktuellen Pheromon-Werte aktualisieren und aktualisieren die Pheromone auf der Grundlage der neuen Ant Trails.Nachdem die maximale Anzahl der durch die wichtigsten Verarbeitungsschleife (1.000) Mal, zeigt das Programm die besten Weg gefunden und der entsprechenden Länge (61.0 Einheiten).
Das 60-Stadt-Diagramm ist künstlich so konstruiert, dass jede Stadt jede andere Stadt verbunden ist, und der Abstand zwischen jeder zwei Städte ein Zufallswert zwischen 1,0 und 8,0 willkürliche Einheiten (Meilen, km usw. ist).Es gibt keine einfache Möglichkeit, die TSP zu lösen.Mit 60 Städten, vorausgesetzt, können Sie zu jeder Stadt und gehen vorwärts oder rückwärts, und dass alle Städte verbunden sind, gibt es insgesamt (60 - 1)!/ 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 mögliche Lösungen.Selbst wenn Sie mögliche Lösungen 1 Milliarde pro Sekunde ergeben könnte, würde es etwa 2.2 * 1063 Jahre dauern, um sie alle zu überprüfen ist oft länger als das geschätzte Alter des Universums.
ACO ist eine meta-heuristic, d.h. es ist ein allgemeines Rahmenwerk, das zum Erstellen eines bestimmten Algorithmus eine bestimmte Graph-Pfad-Problem zu lösen.Obwohl ACO von m in einer Dissertation 1991 vorgeschlagen wurde.Dorigo, die erste detaillierte Beschreibung des Algorithmus ist in der Regel ein Folgedokument 1996 von m zugeschrieben.Dorigo, V.Maniezzo und a.Colorni.Seitdem ACO weit studierte und geändert wurde, aber etwas neugierig, sehr wenige vollständige und richtige Implementierungen stehen online.
Diese Spalte wird vorausgesetzt, dass Sie Mittelstufe Fortgeschritten Programmierkenntnisse haben.Das ACO-Programm mit c# implementiert, aber Sie sollten nicht zu viel Mühe, meinen Code in eine andere Sprache, wie z. B. JavaScript umgestalten.Ich beschloss, zu vermeiden alle Nutzung der objektorientierten Programmierung (OOP), die Ideen des Algorithmus so klar wie möglich zu halten.Wegen der Raumbeschränkungen, präsentiere ich kann nicht alle den Code ausführen in Abbildung 1.Ich gehe über die schwierigste Teile und können Sie den vollständigen Code von archive.msdn.microsoft.com/mag201202TestRun.Zwar Sie ACO Code nie direkt verwenden, viele seiner Techniken, wie z. B. Roulette Rad Auswahl, können interessant sein und nützliche Ergänzungen zu Ihrem technischen Fähigkeiten festgelegt.
.png)
Abbildung 1 Ant Colony Optimization in Aktion
Programmstruktur
Ich habe implementiert das ACO-Demo-Programm als einzigen C#-Konsolenanwendung.Die allgemeine Struktur des Programms, mit die meisten WriteLine-Anweisungen entfernt, erscheint Abbildung 2.Obwohl einige Teile schwierig sind, ist das Programm nicht so kompliziert wie Bild2 schlägt vor, da viele der Methoden kurze Hilfsmethoden sind.
Abbildung 2 Ant Colony Optimization Programmstruktur
using System;
namespace AntColony
{
class AntColonyProgram
{
static Random random = new Random(0);
static int alpha = 3;
static int beta = 2;
static double rho = 0.01;
static double Q = 2.0;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
int[][] dists = MakeGraphDistances(numCities);
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
double[][] pheromones = InitPheromones(numCities);
int time = 0;
while (time < maxTime)
{
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
{
bestLength = currBestLength;
bestTrail = currBestTrail;
}
++time;
}
Console.WriteLine("\nBest trail found:");
Display(bestTrail);
Console.WriteLine("\nLength of best trail found: " +
bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
static int[][] InitAnts(int numAnts, int numCities) { .
.
}
static int[] RandomTrail(int start, int numCities) { .
.
}
static int IndexOfTarget(int[] trail, int target) { .
.
}
static double Length(int[] trail, int[][] dists) { .
.
}
static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
static double[][] InitPheromones(int numCities) { .
.
}
static void UpdateAnts(int[][] ants, double[][] pheromones,
int[][] dists) { .
.
}
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists) { .
.
}
static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
int[][] dists) { .
.
}
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists) { .
.
}
static void UpdatePheromones(double[][] pheromones, int[][] ants,
int[][] dists) { .
.
}
static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
static int[][] MakeGraphDistances(int numCities) { .
.
}
static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
static void Display(int[] trail) { .
.
}
static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
static void Display(double[][] pheromones) { .
.
}
}
}
Ich habe Visual Studio um eine Konsolenanwendungsprogramm namens AntColony zu erstellen. Im Fenster Projektmappen-Explorer ich benannte die standardmäßige Datei Program.cs zu AntColonyProgram.cs, die automatischematisch umbenannt die einzelne Klasse in das Projekt. Ich löschte alle die Vorlage generiert mit Anweisungen für den System-Namespace außer — ACO muss in der Regel nicht viel Unterstützung für Klassenbibliotheken. Die beiden wichtigsten Methoden sind UpdateAnts und UpdatePheromones. Methode UpdateAnts Ruft Helfer BuildTrail, die NextCity, die MoveProbs aufruft aufruft. Methode UpdatePheromones Ruft Helfer EdgeInTrail, die IndexOfTarget aufruft.
Ich erklärte ein Gültigkeitsbereich der Klasse Random-Objekt mit dem Namen zufällig. ACO Algorithmen sind probabilistische, wie Sie bald sehen werden. Der Gültigkeitsbereich der Klasse Variablen Alpha, Beta, Rho und q steuern das Verhalten des Algorithmus ACO. Ich benutze diese Variablen Namen, da sie in der ursprünglichen Beschreibung des ACO verwendet wurden.
Einrichten des Problems
Ich wendete Methode MakeGraphDistances zum Einrichten einer künstlichen Graph:
static int[][] MakeGraphDistances(int numCities)
{
int[][] dists = new int[numCities][];
for (int i = 0; i < dists.Length; ++i)
dists[i] = new int[numCities];
for (int i = 0; i < numCities; ++i)
for (int j = i + 1; j < numCities; ++j) {
int d = random.Next(1, 9); // [1,8]
dists[i][j] = d; dists[j][i] = d;
}
return dists;
}
Für eine reale Grafik Problem, würde Sie wahrscheinlich lesen Graph -Nachbarschaft und Distanz-zwischen-Knoten Daten aus einer Textdatei in eine Art von Datenstruktur. Hier simuliert ich ein Diagramm, indem Erstellen eines Arrays von Arrays, wobei der Zeilenindex, die ich aus der Stadt und der Spalte Index j stellt zu der Stadt darstellt. Beachten Sie, dass alle Städte verbunden sind, Entfernungen sind symmetrisch und die Entfernung von der Stadt zum selbst ist 0.
Einmal habe ich eine Datenstruktur Entfernungen kann es für eine Distance-Methode verwendet werden:
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
Um die Höhe der dargestellten Code zu minimieren, habe ich normale Fehler überprüfen, wie z. B. sicherstellen, dass die CityX und cityY Parameter gültig sind weggelassen.
Die Ameisen und die Pheromone
In dieser Implementierung nicht-OOP ist eine Ameise einfach ein Array von Int-Werten, die den Weg oder Pfad, eine erste Stadt durch alle anderen Städte darstellen. Eine Auflistung von Ameisen ist ein Array von Arrays, in denen der erste Index die Ameise angibt:
static int[][] InitAnts(int numAnts, int numCities)
{
int[][] ants = new int[numAnts][];
for (int k = 0; k < numAnts; ++k) {
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
Die Initialisierungsmethode weist eine Zeile für den Trail für jede Ameise, wählt eine zufällige Start Stadt und ruft dann eine Hilfsmethode RandomTrail:
static int[] RandomTrail(int start, int numCities)
{
int[] trail = new int[numCities];
for (int i = 0; i < numCities; ++i) { trail[i] = i; }
for (int i = 0; i < numCities; ++i) {
int r = random.Next(i, numCities);
int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;
return trail;
}
Die RandomTrail Helfer weist eine Spur und initialisiert es mit 0, 1, 2... NumCities-1. Als Nächstes verwendet die Methode den Fisher-Yates Shuffle Algorithmus die Reihenfolge der Städte der Weg zufällig. Die angegebenen Start-Stadt dann liegt und in Stellung Strecke [0] getauscht.
Pheromone sind Chemikalien Ameisen Platz auf ihren Spuren; Sie ziehen andere Ameisen. Weitere Ameisen reist auf eine kürzere Strecke nach einer Nahrungsquelle — und Einzahlung mehr Pheromone — als auf längeren Strecken. Die Pheromone verdunsten langsam im Laufe der Zeit. Hier ist Methode InitPheromones:
static double[][] InitPheromones(int numCities)
{
double[][] pheromones = new double[numCities][];
for (int i = 0; i < numCities; ++i)
pheromones[i] = new double[numCities];
for (int i = 0; i < pheromones.Length; ++i)
for (int j = 0; j < pheromones[i].Length; ++j)
pheromones[i][j] = 0.01;
return pheromones;
}
Pheromon-Informationen werden in ein Array von Arrays Stil symmetrische Matrix in die Zeile index i aus der Stadt und die Spalte Index j ist zu der Stadt. Alle Werte sind so eingestellt, eine willkürlich kleinen Wert (0,01) springen starten Sie den UpdateAnts-UpdatePheromones-Zyklus.
Aktualisierung der Ameisen
Der Schlüssel zu der ACO-Algorithmus ist der Prozess, der jede Ameise und Trail aktualisiert durch den Bau einer neuen — wir hoffen besser — Spur basierend auf den Informationen Pheromon und Distanz. Werfen Sie einen Blick auf Abbildung 3. Genommen Sie an, wir haben ein kleines Diagramm mit nur fünf Städte. In Abbildung 3 die neue Strecke für eine Ameise befindet sich im Aufbau. Der Trail beginnt am Stadt 1, dann geht zum Stadt 3, und der Update-Algorithmus ist die nächste Stadt bestimmen. Nehmen wir nun an die Distanz und Pheromon Informationen ist wie im Bild gezeigt. Der erste Schritt zur Ermittlung der nächsten Stadt baut ein Array ich habe "Taueta" genannt, (weil die ursprüngliche Forschungsarbeit die griechischen Buchstaben Tau und Eta verwendet). Der Taueta-Wert ist der Wert der das Pheromon am Rande potenziert mit dem alpha, mal einen über den Entfernungswert potenziert mit der Beta. Daran erinnern Sie, dass Alpha und Beta sind globale Konstanten, die angegeben werden müssen. Hier werde ich davon ausgehen, dass Alpha 3 und Beta 2. Die Taueta Werte für Stadt 1 und 3 werden nicht berechnet, weil sie bereits in der aktuellen Weg sind. Beachten Sie, dass größere Werte für das Pheromon Taueta erhöhen, aber größere Entfernungen Taueta verringern.
.png)
Abbildung 3 Aktualisierung Ant Informationen
Nachdem alle Taueta Werte berechnet wurden, der nächste Schritt ist, um diese Werte zu konvertieren, um Wahrscheinlichkeiten und legen Sie sie in einem Array habe ich Probs beschriftet. Der Algorithmus addiert die Werte Taueta, immer 82.26 in diesem Beispiel und teilt dann jeden Wert Taueta durch die Summe. An diesem Punkt hat die Stadt 0 eine Wahrscheinlichkeit von 0,09, ausgewählt und so weiter. Danach muss der Algorithmus die nächste Stadt auf der Grundlage der berechneten Wahrscheinlichkeiten auswählen. Wie bereits erwähnt, verwendet die ACO-Algorithmus, die mir in diesem Artikel vorgestellte eine saubere Technik namens Roulette Rad Auswahl. Konstruierte ich eine erweiterte Array mit dem Namen Cumul, die kumulierte Wahrscheinlichkeiten enthält. Die Größe des erweiterten Array ist größer ist als die Probs-Array ist, und Zelle [0] mit 0,0. Jede Zelle im Cumul ist die kumulierte Summe der Wahrscheinlichkeiten. Nachdem das Cumul-Array erstellt wurde, wird eine zufällige Zahl p zwischen 0.0 und 1.0 generiert. Angenommen, p = 0.538 wie gezeigt. Der p-Wert fällt im Cumul Array, was, dass bedeutet zwischen den Werten am [2] und [3] [2], oder die Stadt 2, als die nächste Stadt ausgewählt wird.
Die Top-Level-Methode für die Aktualisierung ist UpdateAnts benannt:
static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
for (int k = 0; k < ants.Length; ++k) {
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
Beachten Sie, dass jede Ameise ist eine neue, zufällige ab Stadt zugewiesen anstatt Beibehaltung der altes Stadt starten. Die meisten der die eigentliche Arbeit erfolgt durch Hilfsmethode BuildTrail, wie in Abbildung 4.
Abbildung 4 die BuildTrail-Methode
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists)
{
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i < numCities - 1; ++i) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
BuildTrail unterhält, ein Array von Boolean besucht, so dass nicht die Spur erstellt doppelte Städte enthalten. Spur [0] der Wert ist mit einer Start-Stadt ausgesät, und dann jede Stadt ist wiederum von Hilfsmethode NextCity, gezeigt Abbildung 5.
Abbildung 5 die NextCity-Methode
static int NextCity(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i < probs.Length; ++i)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i < cumul.Length - 1; ++i)
if (p >= cumul[i] && p < cumul[i + 1])
return i;
throw new Exception("Failure to return valid city in NextCity");
}
Die NextCity-Methode implementiert den Roulette Rad Auswahl Algorithmus.Beachten Sie, dass der Algorithmus scheitern wird, wenn der letzte Wert im Cumul-Array ist größer als 1,00 (möglicherweise aufgrund von Rundungsfehlern), und so fügen Sie Logik immer Cumul [Cumul. festlegen möchtenLänge-1] 1.00. NextCity erfordert ein Array von Wahrscheinlichkeiten produziert von Hilfsmethode MoveProbs, gezeigt Abbildung 6.
Abbildung 6 die MoveProbs-Methode
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
double sum = 0.0;
for (int i = 0; i < taueta.Length; ++i) {
if (i == cityX)
taueta[i] = 0.0; // Prob of moving to self is zero
else if (visited[i] == true)
taueta[i] = 0.0; // Prob of moving to a visited node is zero
else {
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
if (taueta[i] < 0.0001)
taueta[i] = 0.0001;
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
}
sum += taueta[i];
}
double[] probs = new double[numCities];
for (int i = 0; i < probs.Length; ++i)
probs[i] = taueta[i] / sum;
return probs;
}
Die Taueta Werte können sehr klein sein (wenn der Entfernungswert sehr groß ist) oder sehr groß (wenn der Pheromon-Wert groß ist), kann die Schwierigkeiten für den Algorithmus erzeugen. Um damit umzugehen, ich überprüfen Sie die Werte Taueta und willkürlichen min und max Werte zu verhängen.
Aktualisierung der Pheromone
Pheromon-Informationen aktualisieren ist viel einfacher als die Ameise Spur Informationen aktualisieren. Die wichtigsten Codezeilen in Methode UpdatePhermones sind:
double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
increase = (Q / length);
pheromones[i][j] = decrease + increase;
Wert jede Pheromon wird verringert Verdampfung, simulieren und erhöht, simulieren die Hinterlegung von Pheromone von Ameisen auf der Spur.Der Abnahme-Effekt entsteht durch Multiplikation des aktuelle Pheromon-Wertes mit dem Faktor kleiner als 1,0, der globalen Parameter Rho abhängt.Die größeren Rho ist, desto größer der Rückgang der Pheromon-Wert.Der Zunahme-Effekt entsteht durch Hinzufügen von einen Anteil an der aktuellen Ant total Weg Länge, wobei der Anteil durch globale Parameter Q bestimmt wird.Größere Werte von q erhöhen die Menge der Pheromon hinzugefügt.Methode UpdatePheromones Ruft Helfer EdgeInTrail, die bestimmt, wenn ein Segment zwischen zwei Städten ist auf der aktuellen Ameisenpfad.Können Sie sich den Codedownload für diesen Artikel für Details (archive.msdn.microsoft.com/mag201202TestRun).
Nachbereitung
Lassen Sie mich betonen, dass es viele Variationen von ACO gibt; die hier vorgestellte Version ist nur eine von vielen möglichen Ansätzen.ACO Befürworter haben zu einer Vielzahl von kombinatorischen Optimierungsproblemen der Algorithmus angewendet.Andere kombinatorische OptiMization Algorithmen basierend auf dem Verhalten von natürlichen Systemen gehören Simulated Annealing (SA), die ich letzten Monat abgedeckt (msdn.microsoft.com/magazine/hh708758), und simuliert Bee Colony (SBC), mit denen ich in meinem Artikel vom April 2011 (msdn.microsoft.com/magazine/gg983491).Jeder Ansatz hat stärken und Schwächen.ACO ist meiner Meinung nach am besten geeignet für Probleme, die das Traveling Salesman Problem, eng zu ähneln, während SA und SBC besser für allgemeine kombinatorische Optimierungsprobleme, z. B. die Einplanung.
ACO, gemeinsam mit anderen Meta-Heuristiken basierend auf natürliche Systeme, ist ziemlich empfindlich auf Ihrer Wahl freie globale Parameter — Alpha, Beta und So weiter.Zwar gab es durchaus eine Spitze der Forschung über ACO-Parameter, ist der allgemeine Konsens, dass Sie ein bisschen freie Parameter experimentieren müssen, die beste Kombination aus Leistung und Lösung Qualität erhalten.
Dr. James McCaffrey* arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington, Campus. Er war an verschiedenen Microsoft-Produkten, einschließlich Internet Explorer und MSN Search. McCaffrey ist Autor von ".NET Test Automation Recipes"(Apress, 2006) und kann unter jmccaffrey@volt.com oder jammc@microsoft.com erreicht werden.*
Dank der folgenden technischen Experten von Microsoft für die Überprüfung dieses Artikels: Dan Liebling und Anne Loomis Thompson