Dieser Artikel wurde maschinell übersetzt.
Testlauf
Simulierte Härtung und Tests
.jpg "James McCaffrey")
Im Artikel dieses Monats präsentiere ich C#-Code, der einen Algorithmus Simulated Annealing (SA) ein scheduling Problem zu lösen, implementiert.Ein SA-Algorithmus ist eine künstliche Intelligenz Technik basierend auf dem Verhalten der Kühlung Metall.Es kann verwendet werden, um Lösungen für schwierig oder unmöglich kombinatorische Optimierungsprobleme finden.
Der beste Weg zu sehen, wohin ich bin ist es, einen Blick auf Abbildung 1 und Abbildung 2.Die Tabelle in Abbildung 1 beschreibt ein scheduling Problem: fünf Arbeitern und sechs Aufgaben.Jeder Eintrag in der Tabelle stellt dar, wie lange es dauert für einen Arbeiter, eine Aufgabe auszuführen.Zum Beispiel benötigt Arbeitnehmer w2 5,5 Stunden Aufgabe t3.Ein leerer Eintrag in einer Zeile gibt an, dass die entsprechenden Mitarbeiter eine Aufgabe durchführen kann.Das Problem ist jede der sechs Aufgaben zuweisen einer der Arbeiter in einer Weise, dass die Gesamtzeit für alle Aufgaben minimiert wird.Darüber hinaus gehen wir davon aus, dass jedes Mal, wenn ein Arbeitnehmer in einer neuen Aufgabe wechselt, es eine 3,5 Stunden Umrüsten Strafe gibt.
Abbildung 1 Zeit für Arbeitnehmer Vorgangs
| T0 | T1 | T2 | T3 | T4 | T5 | |
| W0 | 7.5 | 3.5 | 2.5 | |||
| W1 | 1.5 | 4.5 | 3.5 | |||
| W2 | 3.5 | 5.5 | 3.5 | |||
| w3 | 6.5 | 1.5 | 4.5 | |||
| W4 | 2.5 | 2.5 | 2.5 |
.png)
Abbildung 2 SimulatedAnnealing in Aktion
Abbildung 2 zeigt ein Programm, das einen SA-Algorithmus verwendet, um eine Lösung für das scheduling Problem zu finden.Das Programm beginnt durch eine zufällige Lösung generieren.In der Terminologie von SA ist eine mögliche Lösung den Zustand des Systems aufgerufen.Der anfängliche Zustand ist [4 0 0 2 2 3], d. h. Aufgabe 0 Arbeitnehmer 4, Aufgabe 1 zugewiesen wurde, die Arbeitnehmer 0 zugewiesen wurde, Aufgabe 2 Arbeitnehmer 0 zugewiesen wurde, Aufgabe 3 Arbeiter 2 zugewiesen wurde, Aufgabe 4 Arbeitnehmer 2 zugewiesen wurde und Aufgabe 5 Arbeiter 3 zugewiesen wurde.Die Gesamtzeit für die zufällige Ausgangszustand ist 2.5 + 3.5 + 2.5 + 5.5 + 3.5 + 4.5 = 22 Stunden plus eine 3,5 Stunden Umrüsten Strafe für Arbeitnehmer 0 und ein 3,5 Stunden Strafe für Arbeitnehmer 2, für insgesamt 29 Stunden.In SA-Terminologie wird die Menge, die Sie versuchen zu minimieren (oder seltener maximieren) die Energie des Staates genannt.
Das Programm gibt eine Schleife.In jeder Iteration der Schleife der SA-Algorithmus generiert einen angrenzenden Staat und wertet die angrenzenden Staat zu sehen, ob es besser als der aktuelle Zustand ist.Hinter den Kulissen verwendet den SA-Algorithmus eine Temperatur-Variable, die langsam abnimmt, wie ich in Kürze erläutern werde.Die SA-Schleife endet, wenn die Temperatur, hinreichend nahe bei Null liegen abkühlt.Das Programm schließt durch anzeigen die beste Lösung gefunden.
In diesem Beispiel ist künstlich einfach weil mit sechs Aufgaben wo jede Aufgabe durchgeführt werden können, von einem der drei Arbeiter, es gibt nur 36 mögliche Kombinationen, die 729, entspricht damit Sie jeder nur beurteilen könnten.Aber davon aus, dass Sie hatte ein Problem mit 20 Aufgaben, wo jede Aufgabe kann von einem der 12 Mitarbeiter durchgeführt werden.Würde es 1220 Kombinationen, die eine satte 3,833,759,992,447,475,122,176 entspricht.Selbst wenn Sie eine Million mögliche Lösungen pro Sekunde ergeben könnte, müssten etwa 121 Millionen Jahren Sie jede Möglichkeit zu bewerten.
SA ist ein metaheuristic — das heißt, einen allgemeinen konzeptionellen Rahmen, die zum Erstellen eines bestimmten Algorithmus zur Lösung eines bestimmten Problems verwendet werden kann.Es ist am besten für kombinatorische Optimierungsprobleme verwendet wo es keine praktische Lösung deterministischen Algorithmus.Zuerst beschrieben in einem 1983 Papier von S.Kirkpatrick, c.Gelatt und M.Vecchi, SA basiert lose auf dem Glühen Verhalten der Kühlung Metall.Wenn einige Metalle auf eine hohe Temperatur erhitzt werden, brechen die Atome und Molekühle ihre Anleihen.Wenn das Metall langsam abgekühlt ist, reform die Atome und Molekühle ihrer Anleihen in einer Weise, dass die Energie des Systems minimiert wird.
Diese Spalte wird davon ausgegangen, dass Sie mittelaktive Programmierkenntnisse haben.Ich das SA-Programm mit c# implementieren, aber Sie sollten nicht zu viel Mühe umgestalten von mein Code in eine andere Sprache wie Visual Basic oder Python.In den folgenden Abschnitten, ich werde durchlaufen Sie das Programm, das generiert Abbildung 2.Ich denke, dass Sie finden der Fähigkeit zu verstehen und zu verwenden SA eine interessante und möglicherweise nützliche Ergänzung zu Ihrem persönlichen Fertigkeiten.
Programmstruktur
Ich habe implementiert das Demoprogramm SA als einzigen C#-Konsolenanwendung.Die allgemeine Struktur des Programms erscheint Abbildung 3.
Figure 3 Struktur der SimulatedAnnealing Programm
using System;
namespace SimulatedAnnealing
{
class SimulatedAnnealingProgram
{
static Random random;
static void Main(string[] args)
{
try
{
// Set up problem data.
// Create random state.
// Set up SA variables for temperature and cooling rate.
while (iteration < maxIteration && currTemp > 0.0001)
{
// Create adjacent state.
// Compute energy of adjacent state.
// Check if adjacent state is new best.
// If adjacent state better, accept state with varying probability.
// Decrease temperature and increase iteration counter.
}
// Display best state found.
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
Console.ReadLine();
}
} // Main
static double[][] MakeProblemData(int numWorkers, int numTasks) { ...
}
static int[] RandomState(double[][] problemData) { ...
}
static int[] AdjacentState(int[] currState,
double[][] problemData) { ...
}
static double Energy(int[] state, double[][] problemData) { ...
}
static double AcceptanceProb(double energy, double adjEnergy,
double currTemp) { ...
}
static void Display(double[][] matrix) { ...
}
static void Display(int[] vector) { ...
}
static void Interpret(int[] state, double[][] problemData) { ...
}
} // Program
} // ns
Ich habe Visual Studio um eine Konsolenanwendungsprogramm namens SimulatedAnnealing zu erstellen. Im Fenster Projektmappen-Explorer umbenannt ich die standardmäßige Datei Program.cs, SimulatedAnnealingProgram.cs, die automatisch die einzige Klasse in das Projekt umbenannt. Ich löschte alle die Vorlage generierte using-Anweisungen außer für den System-Namespace — SA ist ganz einfach und in der Regel nicht brauchen viel Bibliothek unterstützen. Ich erklärte ein Gültigkeitsbereich der Klasse Random-Objekt mit dem Namen zufällige. SA Algorithmen sind probabilistische, wie Sie bald sehen werden.
Das Herz der Verarbeitung Algorithmus SA ist eine Weile Schleife. Die Schleife wird gesteuert, indem eine Schleife Counter-Variable mit dem Namen "Iteration" und eine Variable, die Temperatur des Systems darstellt. In der Praxis die Variable Temperatur fast immer nahe Null erreicht und wird die Schleife beendet, bevor der Schleifenzähler seine maximalen Wert erreicht und wird die Schleife beendet.
SA Algorithmen müssen drei Problem-spezifische Methoden wie in Abbildung3. Der SA-Algorithmus muss eine Methode verfügen, die eine anfängliche (in der Regel zufällige) Zustand/Lösung generiert. Der SA-Algorithmus muss eine Methode verfügen, die einen angrenzenden Staat gegenüber einem bestimmten Zustand generiert. Und der SA-Algorithmus müssen eine Methode, die die Energiekosten eines Staates berechnet – der Wert Sie versuchen zu minimieren oder maximieren. In Abbildung 3 Dies sind die Methoden RandomState, nebenZustand und Energie, beziehungsweise. AcceptanceProb-Methode generiert einen Wert verwendet, um festzustellen, ob der aktuelle Zustand des Systems in den benachbarten Zustand übergeht, selbst wenn der benachbarte Zustand schlechter als der aktuelle Zustand ist. MakeProblemData-Methode ist eine Hilfsmethode und erstellt eine Daten-Struktur Matrix, das entspricht Abbildung 1. Die überladenen Methoden auf Display und die Methode interpretieren sind nur Helfer, um Informationen anzuzeigen.
Programm-Initialisierung
Die Main-Methode beginnt wie so dass:
try
{
Console.WriteLine("\nBegin Simulated Annealing demo\n");
Console.WriteLine("Worker 0 can do Task 0 (7.5) Task 1 (3.5) Task 2 (2.5)");
Console.WriteLine("Worker 1 can do Task 1 (1.5) Task 2 (4.5) Task 3 (3.5)");
Console.WriteLine("Worker 2 can do Task 2 (3.5) Task 3 (5.5) Task 4 (3.5)");
Console.WriteLine("Worker 3 can do Task 3 (6.5) Task 4 (1.5) Task 5 (4.5)");
Console.WriteLine("Worker 4 can do Task 0 (2.5) Task 4 (2.5) Task 5 (2.5)");
...
Ich wickeln alle SA Code in eine einzelne, High-Level Try-Catch-Block und zeigen das Pseudo-Problem, das ich einrichten wollen. Hier, ich bin benutze ein künstlich einfaches Beispiel — aber Vertreter der Art von kombinatorischen Problemen ist, die für eine Lösung von SA Algorithmen geeignet sind. Als nächstes kommt:
random = new Random(0);
int numWorkers = 5;
int numTasks = 6;
double[][] problemData = MakeProblemData(numWorkers, numTasks);
Ich initialisieren das Random-Objekt mit einer beliebigen Startwert 0. Und ich Hilfsmethode MakeProblemData angezeigt, die Datenstruktur erstellen rufen Sie dann Abbildung 1. Ich präsentiere MakeProblemData und die anderen Hilfsmethoden, nachdem ich beende alle den Code in die Main-Methode zu präsentieren. Als nächstes kommt:
int[] state = RandomState(problemData);
double energy = Energy(state, problemData);
int[] bestState = state;
double bestEnergy = energy;
int[] adjState;
double adjEnergy;
Ich fordere Hilfsmethode RandomState generiert einen zufälligen Zustand /Lösung für das Problem. Zustand wird als ein Int-Array dargestellt, wobei der Arrayindex eine Aufgabe und den Wert im Array, an der Index darstellt, des Arbeitnehmers, die dem Vorgang zugeordnet. Hilfsmethode Energie berechnet die Gesamtzeit von der State-Parameter, unter Berücksichtigung die 3,5 Stunden Strafe für Umrüstung jedes Mal, wenn ein Arbeitnehmer eine weitere Aufgabe ist erforderlich. Ich werde die besten Zustand gefunden und seine entsprechende Energie, nachverfolgt, damit ich erkläre die Variablen BestState und BestEngery. Variablen AdjState und AdjEnergy werden verwendet, um einen Zustand zu halten, der neben den aktuellen Status und die entsprechende Energie ist. Als nächstes kommt:
int iteration = 0;
int maxIteration = 1000000;
double currTemp = 10000.0;
double alpha = 0.995;
Die primäre SA Verarbeitungsschleife beendet auf eine der beiden Bedingungen: Wenn ein Leistungsindikator einen maximalen Wert überschreitet oder wenn die Temperatur-Variable auf einen Wert nahe sinkt 0 (null). Ich nenne die Schleife Leistungsindikator "Iteration", aber ich konnte haben nannte es "Zähler" oder "Zeit" oder "Tick" oder etwas ähnliches. Ich nenne die Variable Temperatur-CurrTemp, anstatt temp, so es weniger Chancen gibt jemand Überprüfen des Codes möglicherweise interpretieren sie als eine temporäre Variable. Variable Alpha darstellt die Kühlgeschwindigkeit oder ein Faktor, der bestimmt, wie die Variable Temperatur verringert oder abkühlt, jedes Mal durch die Verarbeitungsschleife. Als nächstes kommt:
Console.WriteLine("\nInitial state:");
Display(state);
Console.WriteLine("Initial energy: " + energy.ToString("F2"));
Console.WriteLine("\nEntering main Simulated Annealing loop");
Console.WriteLine("Initial temperature = " + currTemp.ToString("F1") + "\n");
Vor dem Eintritt in der wichtigsten Verarbeitungsschleife, ich einige Informationsmeldungen über den Ausgangszustand, Energie und Temperatur angezeigt. Vielleicht möchten zusätzliche Informationen wie z. B. die Kühlgeschwindigkeit anzuzeigen. Hier ist die Schleife:
while (iteration < maxIteration && currTemp > 0.0001)
{
adjState = AdjacentState(state, problemData);
adjEnergy = Energy(adjState, problemData);
if (adjEnergy < bestEnergy)
{
bestState = adjState;
bestEnergy = adjEnergy;
Console.WriteLine("New best state found:");
Display(bestState);
Console.WriteLine("Energy = " + bestEnergy.ToString("F2") + "\n");
}
...
Beachten Sie, dass das Steuerelement Schleife wird beendet, wenn die Variable Temperatur sinkt unter 0,0001 anstatt trifft es 0.0. Sie können den minimale Temperaturwert parametrisieren. Nach Erstellen eines angrenzenden Staates und seiner Energie computing, überprüfe ich, ob dieses angrenzenden Staates eine neue globale beste Lösung ist, und wenn so dass ich diese Informationen speichern. Ich kann den besten Zustand als Verweis kopiert werden, da Methode AdjacentState ein neues Array ordnet, aber ich eine explizite Kopie gemacht haben könnte. Wenn ein neuer globaler besten Status gefunden wird, zeigen Sie es und seine Energie. Die wichtigsten Verarbeitungsschleife endet wie folgt:
double p = random.NextDouble();
if (AcceptanceProb(energy, adjEnergy, currTemp) > p)
{
state = adjState;
energy = adjEnergy;
}
currTemp = currTemp * alpha;
++iteration;
} // While
Die Schleife beendet oben indem zuerst generiert einen zufälligen Wert p größer oder gleich 0,0 und kleiner als 1,0 und vergleicht diesen Wert gegen die Rückkehr von Hilfsmethode AcceptanceProb. Wenn die Akzeptanzwahrscheinlichkeit zufälligen Wert überschreitet, wechselt der aktuelle Zustand der angrenzenden Staat. Als nächstes wird die aktuelle Temperatur leicht mit der kühlen Faktor multipliziert verringert, und die Zählervariable wird erhöht. Als nächstes kommt:
Console.Write("Temperature has cooled to (almost) zero ");
Console.WriteLine("at iteration " + iteration);
Console.WriteLine("Simulated Annealing loop complete");
Console.WriteLine("\nBest state found:");
Display(bestState);
Console.WriteLine("Best energy = " + bestEnergy.ToString("F2") + "\n");
Interpret(bestState, problemData);
Console.WriteLine("\nEnd Simulated Annealing demo\n");
Console.ReadLine();
Nach Abschluss die wichtigsten SA Verarbeitungsschleife anzeigen die besten Zustand (Lösung) gefunden und seine entsprechende Energie (Stunden). Die Main-Methode wird wie folgt:
...
} // Try
catch (Exception ex)
{
Console.WriteLine(ex.Message);
Console.ReadLine();
}
} // Main
Die Methode umschließt bis durch die Behandlung von Ausnahmen einfach indem die Ausnahmemeldung angezeigt.
Die Hilfsprogramm-Methoden
Der Code für die MakeProblemData-Hilfsmethode ist:
static double[][] MakeProblemData(int numWorkers, int numTasks)
{
double[][] result = new double[numWorkers][];
for (int w = 0; w < result.Length; ++w)
result[w] = new double[numTasks];
result[0][0] = 7.5; result[0][1] = 3.5; result[0][2] = 2.5;
result[1][1] = 1.5; result[1][2] = 4.5; result[1][3] = 3.5;
result[2][2] = 3.5; result[2][3] = 5.5; result[2][4] = 3.5;
result[3][3] = 6.5; result[3][4] = 1.5; result[3][5] = 4.5;
result[4][0] = 2.5; result[4][4] = 2.5; result[4][5] = 2.5;
return result;
}
Ich entschied zu Verwendung Type double [] [] — das heißt, ein Array von Arrays — Mein Terminplan Problemstellung zu halten. Die C#-Sprache, im Gegensatz zu vielen Sprachen der C-Familie, unterstützt ein integriertes zweidimensionales Array, so dass ich Typ double [,] verwendet haben konnte aber ein Arrays von Arrays einfacher, umgestalten, ist wenn Sie wollen recode mein Beispiel in eine Sprache, die zweidimensionale Arrays nicht unterstützt. In diesem Beispiel habe ich willkürlich den Arbeitnehmer Index erste und den Task Index zweite (also Ergebnis [1] [3] die Arbeitnehmer 1 Aufgabe 3 erforderliche Zeit ist), aber ich konnte die Reihenfolge umgekehrt haben. Beachten Sie, dass c# automatisch Typ double-Arrayzellen auf 0,0, initialisiert so habe ich nicht explizit dazu. Ich konnte verwendet haben einen anderen Wert, wie z. B. 1.0 um anzugeben, dass ein Arbeitnehmer eine bestimmte Aufgabe ausführen kann.
Hilfsmethode ist RandomState:
static int[] RandomState(double[][] problemData)
{
int numWorkers = problemData.Length;
int numTasks = problemData[0].Length;
int[] state = new int[numTasks];
for (int t = 0; t < numTasks; ++t) {
int w = random.Next(0, numWorkers);
while (problemData[w][t] == 0.0) {
++w; if (w > numWorkers - 1) w = 0;
}
state[t] = w;
}
return state;
}
Denken Sie daran, dass ein Staat eine Lösung darstellt und dass ein Staat ein Int-Array, ist wobei der Index ist die Aufgabe und des Werts der Arbeitnehmer. Für jede Zelle im Zustand generieren ich eine zufällige Arbeitnehmer w. Aber dem Arbeitnehmer möglicherweise nicht in der Lage, die Aufgabe, so dass ich überprüfen, ob der entsprechende Wert in der Datenmatrix Problem ist 0,0 (was bedeutet, dass der Arbeitnehmer die Aufgabe nicht), und wenn ich also versuchen die nächste Arbeiter, achten Sie darauf zurück zu Arbeitnehmer 0 umbrochen, wenn den Index des letzten Arbeitnehmers überschritten.
Hilfsmethode ist AdjacentState:
static int[] AdjacentState(int[] currState, double[][] problemData)
{
int numWorkers = problemData.Length;
int numTasks = problemData[0].Length;
int[] state = new int[numTasks];
int task = random.Next(0, numTasks);
int worker = random.Next(0, numWorkers);
while (problemData[worker][task] == 0.0) {
++worker; if (worker > numWorkers - 1) worker = 0;
}
currState.CopyTo(state, 0);
state[task] = worker;
return state;
}
Methode AdjacentState beginnt mit einem angegebenen Zustand dann wählt eine zufällige Aufgabe und wählt dann eine zufällige Arbeitnehmer, die das tun kann Aufgabe. Beachten Sie, dass dies ein ziemlich grob Ansatz ist; es überprüfen nicht, ob der nach dem Zufallsprinzip generierte neue Arbeiter identisch mit der aktuellen Arbeitnehmer, ist so dass der Rückkehr Zustand möglicherweise identisch mit den aktuellen Zustand. Je nach Art des Problems wird durch einen Algorithmus SA Ziel können Sie Code-Logik einfügen, die sicherstellt, dass ein angrenzender Staat von den aktuellen Zustand unterscheidet.
Die Energie-Methode wird angezeigt, Abbildung 4.
Abbildung 4 die Energie-Methode
static double Energy(int[] state, double[][] problemData)
{
double result = 0.0;
for (int t = 0; t < state.Length; ++t) {
int worker = state[t];
double time = problemData[worker][t];
result += time;
}
int numWorkers = problemData.Length;
int[] numJobs = new int[numWorkers];
for (int t = 0; t < state.Length; ++t) {
int worker = state[t];
++numJobs[worker];
if (numJobs[worker] > 1) result += 3.50;
}
return result;
}
Die Energie-Methode durchläuft jede Aufgabe in das Zustandsfeld, schnappt sich den zugewiesenen Arbeitnehmer Wert, sucht der Zeitaufwand in der Datenmatrix Problem zuerst und sammelt das Ergebnis. Als nächstes zählt die Methode die Anzahl der Zeiten, die ein Arbeitnehmer mehr als eine Aufgabe und fügt eine 3,5 Stunden Umrüsten Strafe für jede zusätzliche Aufgabe. In diesem Beispiel ist die Energie eines Staates Datenverarbeitung schnell; jedoch dominiert in realistischste SA Algorithmen, die Energie-Methode die Ausführungszeit, sollten Sie sicherstellen, dass die Methode so effizient wie möglich ist.
Hilfsmethode ist AcceptanceProb:
static double AcceptanceProb(double energy, double adjEnergy,
double currTemp)
{
if (adjEnergy < energy)
return 1.0;
else
return Math.Exp((energy - adjEnergy) / currTemp);
}
Wenn die Energie des angrenzenden Staates ist weniger als (oder mehr als bei der Maximierung Problem) die Energie des aktuellen Zustands der Methodenrückgabe 1.0, so dass der aktuelle Zustand immer an den neue, bessere angrenzenden Staat Übergang. Aber wenn die Energie des angrenzenden Staates als oder schlechter als der aktuelle Zustand entspricht, gibt die Methode einen Wert kleiner als 1,0, der die aktuelle Temperatur abhängt. Für hohe Werte von Temperatur früh in der Algorithmus ist der Rückgabewert nah an 1,0, also der aktuelle Zustand oft zu der neuen, noch schlimmer angrenzenden Staat Übergang wird. Aber als die Temperatur abkühlt, wird des Rückgabewertes von AcceptanceProb kleiner und kleiner, so gibt es weniger Chancen für den Übergang zu einem schlechteren Zustand.
Die Idee hier ist, dass Sie manchmal — besonders früh in der Algorithmus — zu einem schlechteren Zustand gehen, damit Sie auf eine nicht optimale lokale Lösung konvergiert nicht möchten. Indem Sie manchmal auf ein schlechter Zustand, können Sie nicht optimale Sackgasse Staaten entkommen. Beachten Sie, dass da die Funktion den Wert des die aktuelle Temperatur arithmetische Division durchführt, die Temperatur nicht darf, 0 zu erreichen. Die Annahme-Funktion verwendet, hier ist die am häufigsten verwendeten Funktion und basiert auf einige mathematische Annahmen, aber es gibt keinen Grund, dass Sie andere Annahme-Funktionen verwenden können.
Die Methoden anzeigen und interpretieren Helfer sind sehr einfach, wie in gezeigt Abbildung 5.
Abbildung 5 die anzeigen und interpretieren Hilfsmethoden
static void Display(double[][] matrix)
{
for (int i = 0; i < matrix.Length; ++i) {
for (int j = 0; j < matrix[i].Length; ++j)
Console.Write(matrix[i][j].ToString("F2") + " ");
Console.WriteLine("");
}
}
static void Display(int[] vector)
{
for (int i = 0; i < vector.Length; ++i)
Console.Write(vector[i] + " ");
Console.WriteLine("");
}
static void Interpret(int[] state, double[][] problemData)
{
for (int t = 0; t < state.Length; ++t) { // task
int w = state[t]; // worker
Console.Write("Task [" + t + "] assigned to worker ");
Console.WriteLine(w + ", " + problemData[w][t].ToString("F2"));
}
}
Einige Schwächen
SA Algorithmen sind einfach zu implementieren und kann leistungsfähige Werkzeuge, aber sie haben Schwächen. Da diese Algorithmen in den meisten Fällen in Situationen verwendet werden, wo es keine guten deterministischer lösen Algorithmus im Allgemeinen Sie werden nicht wissen, wann, oder selbst wenn, treffen Sie eine optimale Lösung. Zum Beispiel, in Abbildung 1, die beste Lösung gefunden hatte eine Energie von 20,5 Stunden, aber durch Ausführen des Algorithmus ein bisschen länger finden Sie einen Staat, der Energie von 19,5 Stunden hat. Wenn Sie SAs verwenden, müssen Sie also, eine gute, aber nicht unbedingt optimale Lösung akzeptieren sein. Eine ähnliche Schwäche mit SA Algorithmen und andere Algorithmen basierend auf dem Verhalten von natürlichen Systemen ist, dass die Spezifikation der freie Parameter wie z. B. die Anfangstemperatur und die Kühlung erforderlich. Die Effektivität und Leistung dieser Algorithmen, einschließlich SAs, sind oft sehr empfindlich auf die Werte, die Sie für die freie Parameter auswählen.
SA Algorithmen sind eng verwandt mit simulierten Biene-Kolonie (SBC) Algorithmen, die ich in der Ausgabe April 2011 beschrieben (msdn.microsoft.com/magazine/gg983491). Beide Methoden sind gut geeignet für kombinatorische Optimierung nicht-numerische Probleme zu lösen. Im allgemeinen SAs sind schneller als SBCs, aber SBCs tendenziell bessere Lösungen auf Kosten der Leistung produzieren.
Die Verwendung von Techniken der künstlichen Intelligenz in Software-Tests ist ein Bereich, der fast völlig unerforscht. Ein Beispiel, wo SAs in Software-Tests verwendet werden können, ist als Algorithmus Validierung. Angenommen, Sie haben einige kombinatorischen Problem, das in der Tat mit einem deterministischen Algorithmus gelöst werden können. Ein Beispiel ist das Diagramm shortest-Path Problem, die von mehreren effiziente aber relativ komplizierte Algorithmen wie z. B. Dijkstra-Algorithmus gelöst werden können. Wenn Sie eine shortest-Path Algorithm codiert haben, können Sie es testen, indem schnell Codierung ein einfacher SA-Algorithmus und den Vergleich Ergebnisse. Wenn das SA-Ergebnis der deterministischen Algorithmus besser ist, wissen Sie, dass Sie einen Fehler in Ihrem deterministischen Algorithmus haben.
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 ist in mehreren Microsoft-Produkten, einschließlich Internet Explorer und MSN Search gearbeitet. Dr. McCaffrey ist der Autor von ".NET Test Automation Recipes"(Apress, 2006), und kann erreicht werden unter jammc@microsoft.com.
Dank der folgenden technischen Experten für die Überprüfung dieses Artikels: Paul Koch, Dan Liebling, Ann Loomis Thompson und Shane Williams