Dieser Artikel wurde maschinell übersetzt.
Künstliche Intelligenz
Particle Swarm Optimization
James McCaffrey
.jpg "James McCaffrey")
Partikel Schwarm Optimierung (PSO) ist eine künstliche Intelligenz (KI)-Technik, die verwendet werden kann, um ungefähre Lösungen für extrem schwierig oder unmöglich numerische Maximierung und Minimierung Probleme zu finden. Die Version des PSO, die in diesem Artikel beschrieben wurde zuerst in einer Forschungsarbeit 1995 von j. präsentiert. Kennedy und R. Eberhart. PSO wird lose auf Gruppenverhalten, wie z. B. Vögel Strömen und Fisch Schulbildung modelliert. Der beste Weg für Sie ein Gefühl dafür, was PSO ist zu bekommen und zu sehen, wo ich hier Überschrift bin zu prüfen ist Abbildung 1.
Der erste Teil der Abbildung beschreibt ein dummy Problem wird gelöst, indem eine Demonstration PSO-Programm. Das Ziel X 0 und 1 X-Werten suchen, so ist der Wert der Funktion f = 3 + 0 X ^ 2 + 1 X ^ 2 wird minimiert. Hier verwende die Notation ^ 2, um den squaring Vorgang anzugeben. Beachten Sie, dass ich ein unrealistisch einfaches Problem halten Sie die Ideen des PSO klar bewusst gewählt haben. Es ist offensichtlich, dass die Lösung dieses Problems ist x 0 = 0.0 und x 1 = 0.0, ergibt den Funktionswert minimale 3.0, PSO mit wirklich notwendig ist. Erörtert, realistischer Probleme, die später in diesem Artikel von PSO gelöst werden können. In diesem Beispiel ist die Dimension der Funktion minimiert 2, da wir für numerische Werte 2 lösen müssen. PSO ist im Allgemeinen gut geeignet für numerische Probleme mit den Abmessungen 2 oder größer. In den meisten Fällen müssen PSO einige Einschränkungen für den Bereich der möglichen X-Werte. Hier sind X 0 und 1 X willkürlich auf den Bereich 100.0 auf 100,0 beschränkt.
.jpg)
Abbildung 1 Partikel Schwarm Optimierung Demo ausführen
Der nächste Teil des Abbildung 1 gibt an, dass das Programm PSO 10 Teilchen, und das Programm 1.000 Mal durchlaufen wird. Wie Sie in Kürze sehen werden, stellt jedes Partikel eine mögliche Lösung für das PSO-Problem gelöst wird. PSO ist ein Iterationsverfahren und in den meisten Fällen ist es nicht möglich, zu wissen, wann eine optimale Lösung gefunden wurde. PSO Algorithmen müssen daher in der Regel einige Limit auf die Anzahl der Iterationen durchführen.
Der nächsten Zeilen Abbildung 1 anzugeben, dass jedes der 10 Teilchen in den Schwarm auf eine zufällige Position initialisiert wird. Ein Partikel repräsentiert eine mögliche Lösung auf Optimierungsproblem gelöst werden. Die besten nach dem Zufallsprinzip generiert Ausgangsposition ist x 0 = 26.53 und x 1 =-6.09, die eine Eignung (das Maß für die Qualität der Lösung) von 3 + 26.53 entspricht ^ 2 + (-6.09) ^ 2 = 744.12. PSO-Algorithmus gibt anschließend eine Hauptverarbeitungsschleife, wo jedes Partikel Position bei jedem Durchlauf der Schleife aktualisiert. Das Update-Verfahren ist das Kernstück des PSO und später in diesem Artikel wird erläutert. Nach 1.000 Iterationen PSO-Algorithmus in der Tat finden die optimale Lösung x 0 = 0.0 und x 1 = 0.0, aber lassen Sie mich betonen, dass in den meisten Situationen nicht wissen, ob ein PSO-Programm eine optimale Lösung gefunden hat.
In diesem Artikel ich PSO-Algorithmus im Detail erklären und gehen Sie die Zeile für Zeile durch das Programm in Abbildung 1. Ich codiert das Demo-Programm in C# sollten, aber Sie den Code, der hier vorgestellten zu einer anderen Sprache, wie z. B. Visual Basic leicht anpassen.NET oder Python. Der vollständige Quellcode für das Programm in diesem Artikel vorgestellten steht unter code.msdn.microsoft.com/mag201108PSO. Dieser Artikel setzt voraus, intermediate Programmierkenntnisse mit modernen prozedurale Sprache haben aber wird nicht davon ausgegangen, dass Sie etwas über PSO oder verwandte AI-Techniken kennen.
Partikel
Wenn PSO verwenden, wird eine mögliche Lösung des Problems numerische Optimierung unter Untersuchung durch die Position eines Partikels dargestellt. Darüber hinaus hat jedes Partikel eine aktuelle Geschwindigkeit, die ein Betrag und Richtung in eine neue Richtung darstellt, vermutlich bessere Lösung-Position. Ein Partikel hat auch ein Maß für die Qualität von seiner aktuellen Position, die Partikel bekannt Position (das heißt, eine vorherige Position mit der Qualität bekannt) und die Qualität der bekanntesten Position. Ich eine Partikel-Klasse codiert, wie in gezeigt Abbildung 2.
Abbildung 2 Partikel (Definition)
public class Particle
{
public double[] position;
public double fitness;
public double[] velocity;
public double[] bestPosition;
public double bestFitness;
public Particle(double[] position, double fitness,
double[] velocity, double[] bestPosition, double bestFitness)
{
this.position = new double[position.Length];
position.CopyTo(this.position, 0);
this.fitness = fitness;
this.velocity = new double[velocity.Length];
velocity.CopyTo(this.velocity, 0);
this.bestPosition = new double[bestPosition.Length];
bestPosition.CopyTo(this.bestPosition, 0);
this.bestFitness = bestFitness;
}
public override string ToString()
{
string s = "";
s += "==========================\n";
s += "Position: ";
for (int i = 0; i < this.position.Length; ++i)
s += this.position[i].ToString("F2") + " ";
s += "\n";
s += "Fitness = " + this.fitness.ToString("F4") + "\n";
s += "Velocity: ";
for (int i = 0; i < this.velocity.Length; ++i)
s += this.velocity[i].ToString("F2") + " ";
s += "\n";
s += "Best Position: ";
for (int i = 0; i < this.bestPosition.Length; ++i)
s += this.bestPosition[i].ToString("F2") + " ";
s += "\n";
s += "Best Fitness = " + this.bestFitness.ToString("F4") + "\n";
s += "==========================\n";
return s;
}
} // class Particle
Die Partikel-Klasse verfügt über fünf öffentliche Datenmitglieder: Position, Fitness, Geschwindigkeit, BestPosition und BestFitness. Wenn mithilfe des PSO, der Einfachheit halber bevorzuge öffentlichen Bereich Felder, aber Sie verwenden möchten private Felder zusammen mit Eigenschaften abrufen und festlegen statt. Das Feld mit der Position ist ein Array vom Typ double und eine mögliche Lösung des Problems Optimierung unter Untersuchung darstellt. Obwohl PSO verwendet werden kann, um numerische Probleme zu lösen, ist es im Allgemeinen am besten geeignet für numerische Probleme zu lösen. Feld Fitness ist ein Maß, wie gut die Lösung durch Position dargestellt ist. Minimierung Probleme, die der häufigsten Probleme von PSO gelöst sind, sind kleinere Werte des Feldes Fitness besser als größere Werte; Maximierung Probleme sind größere Werte Eignung besser.
Feld-Geschwindigkeit ist ein Array vom Typ double und notwendigen Informationen zum Aktualisieren eines Partikels aktuelle Position/Lösung darstellt. Ich werde kurz Partikel Velocity im Detail. Die vierte und fünfte Felder in der Partikel-Typ sind BestPosition und BestFitness. Diese Felder enthalten die beste Position/Lösung durch das Partikel-Objekt und der zugeordneten Eignung der besten Position gefunden.
Die Partikel-Klasse verfügt über einen einzigen Konstruktor, der fünf Parameter akzeptiert, die jeweils fünf Datenfelder des Partikels entsprechen. Der Konstruktor kopiert einfach jeden Parameterwert in das entsprechende Datenfeld der. Da alle fünf Felder der Partikel öffentlichen Bereich, ich konnte den Konstruktor angegeben haben und nur Feld Zuweisungsanweisungen verwendet, im Code PSO, aber ich denke, der Konstruktor cleaner Code führt.
Die Partikel-Klassendefinition enthält eine ToString-Methode, die die Werte der Datenfelder fünf Echos. Als mit dem Konstruktor, da ich deklariert, die Position, Fitness, Velocity, BestPosition und BestFitness-Felder mit dem öffentlichen Bereich, ich wirklich brauchen eine ToString-Methode für ein Partikel-Objekt anzeigen, aber einschließlich es vereinfacht die Anzeige der Felder und es ist nützlich für die WriteLine-Stil zu debuggen, während der Entwicklung. In der ToString-Methode verwende ich Zeichenfolgenverkettung anstelle der effizienter StringBuilder-Klasse Umgestalten von Code in eine Microsoft erleichtern.NET Framework-basierte Sprache, wenn Sie wünschen.
PSO-Algorithmus
Obwohl das Herz des ThePSO-Algorithmus ziemlich einfach ist, müssen Sie es gründlich zu verstehen, um den Code in diesem Artikel an Ihre eigenen Anforderungen ändern. PSO ist ein iterativer Prozess. Bei jeder Iteration in der Hauptverarbeitungsschleife PSO ist jedes Partikel aktuelle Velocity zuerst aktualisiert basierend auf aktuelle Geschwindigkeit der Partikel, die Partikel lokale Informationen und globale Schwarm Informationen. Dann wird jedes Partikel Position mithilfe der Partikel neue Velocity aktualisiert. In Mathematik sind Begriffe, die die beiden Gleichungen aktualisieren:
v(t+1) = (w * v(t)) + (c1 * r1 * (p(t) – x(t)) + (c2 * r2 * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)
Tragen Sie hier mit mir; der Aktualisierungsvorgang Position ist tatsächlich viel einfacher, als diese Gleichungen vorschlagen. Die erste Gleichung aktualisiert ein Partikel Velocity. Der Begriff v(t + 1) bedeutet, dass die Geschwindigkeit am Zeitpunkt t + 1. Beachten Sie, dass v fett formatiert ist, ist ein Vektor-Wert, der angibt, dass Velocity und verfügt über mehrere Komponenten wie z. B. {1,55,-0.33}, anstatt einen einzelnen Skalarwert. Die neue Geschwindigkeit hängt von drei Begriffe. Der erste Begriff ist w * v(t). W Faktor ist das Gewicht der Trägheit aufgerufen und ist einfach eine Konstante wie 0,73 (mehr dazu in Kürze); v(t) ist die aktuelle Geschwindigkeit zum Zeitpunkt t. Der zweite Ausdruck ist c1 * r1 * (p(t) – x(t)). Der c1-Faktor ist eine Konstante, die das Gewicht kognitive (oder persönliche oder lokale) aufgerufen. Der r1-Faktor ist eine Zufallsvariable im Bereich [0, 1), die größer oder gleich 0 und kleiner als 1 ist. Die p(t)-Vektor-Wert ist die Partikel optimale Position gefunden, so weit. Die x(t)-Vektor-Wert ist aktuelle Position des Partikels. Ist die dritte Amtszeit Velocity-Update-Gleichung (c2 * r2 * (g(t) – x(t)). Der c2-Faktor ist eine Konstante namens sozialen – oder globale – Gewicht. Der r2-Faktor ist ein Random Variable in den [0, 1). Die **g (**t) Vektor-Wert ist die beste bekannte Position durch ein beliebiges Partikel in den Schwarm gefunden werden, so weit. Sobald die neue Velocity, v(t+1), festgestellt wurde, es wird zum Berechnen der neuen Partikel Position x(t + 1).
Ein konkretes Beispiel machen die Aktualisierung zu deaktivieren. Angenommen, Sie versuchen, zu minimieren, 3 + 0 X ^ 2 + 1 X ^ 2, wie im einleitenden Abschnitt dieses Artikels beschrieben. Die Funktion wird in Abbildung 3 dargestellt. Die Basis des enthaltenden Cube in Abbildung 3 stellt X 0 und 1 X-Werte und die vertikale Achse stellt den Funktionswert. Beachten Sie, dass die Plot-Oberfläche mit f minimiert ist = 3, wenn x 0 = 0 und x 1 = 0.
.jpg)
Abbildung 3 Grundstück f = 3 + 0 X ^ 2 + 1 X ^ 2
Angenommen, dass ein Partikel aktuelle Position, x(t), ist {x 1 X 0} = {3.0, 4.0}, und dass das Partikel aktuelle Geschwindigkeit, v(t), ist {1.0,-1.5}. Nehmen wir ferner an, dass ständige w = 0.7, Konstante c1 = 1,4, Konstante c2 = 1,4, und Zufallszahlen r1 und r2 0,5 und 0,6 bzw. sind. Schließlich angenommen, das Partikel bekannt 's Position ist p(t) = {2.5, 3.6} und ist die globale bekannte Position durch ein beliebiges Partikel in den Schwarm g(t) = {2.3, 3.4}. Dann werden die neuen Werte für Geschwindigkeit und Position:
V(t + 1) = (0,7 * {1.0,-1.5}) +
(1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +
(1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})
= {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}
= {-1.64, -1.83}
X(t + 1) = {3.0, 4.0} + {-1.64,-1.83}
= {1.36, 2.17}
Denken Sie daran, dass die optimale Lösung {x 1 X 0} = (0.0, 0.0}. Beachten Sie, dass der Aktualisierungsvorgang die alte Position/Lösung von verbessert hat (3.0, 4.0} zu {1,36, 2,17}. Wenn Sie ein wenig über den Updateprozess mull, sehen Sie sich, dass die neue Velocity ist die alte Velocity (Zeiten ein Gewicht) plus ein Faktor, der ein Partikel bekannt Position hängt plus ein weiterer Faktor, der die bekanntesten Position aus alle Partikel in der Schwarm abhängt. Neue Position eines Partikels tendenziell daher nach einer besseren Position, basierend auf der Partikel bekannt und der bekanntesten Position aller Teilchen bewegen. Das Diagramm in der Abbildung 4 zeigt die Bewegung eines der Partikel während der ersten acht Iterationen der Demo PSO ausführen. Das Partikel beginnt bei 0 X = 100,0 x 1 = 80,4 und tendenziell hinbewegen x 0 = 0 x 1 = 0 die optimale Lösung. Die spiralförmige Bewegung ist typisch für PSO.
.jpg)
Abbildung 4 Partikel Bewegung in Richtung optimale Lösung
Implementieren des PSO-Algorithmus
Abbildung 5 stellt die allgemeine Struktur des Programms PSO das Programm ausgeführt, siehe erzeugt Abbildung 1. Ich habe Visual Studio ein C# Konsolenanwendungsprojekt mit dem Namen ParticleSwarmOptimization erstellen. PSO Code ist ziemlich einfach, so dass jede Version von der.NET Framework (1.1 bis 4) funktioniert gut. Alle Visual Studio generierte using-Anweisungen außer für den Verweis auf die Core-System-Namespace wurde entfernt. Ich erklärte ein Gültigkeitsbereich der Klasse-Objekt vom Typ Random zum Generieren der kognitiven und sozialen Zufallszahlen, die im vorherigen Abschnitt beschrieben. Ich habe auch das Random-Objekt zum Generieren von zufälligen Anfangsgeschwindigkeiten und Positionen für jedes Partikel-Objekt. Innerhalb die Main-Methode, die ich alle meine Code in einem einzigen allgemeinen wrap try-Anweisung, um Ausnahmen abzufangen.
Abbildung 5 PSO-Programmstruktur
using System;
namespace ParticleSwarmOptimization
{
class Program
{
static Random ran = null;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin PSO demo\n");
ran = new Random(0);
int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2; // dimensions
double minX = -100.0;
double maxX = 100.0;
Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue;
double minV = -1.0 * maxX;
double maxV = maxX;
// Initialize all Particle objects
double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizations
// Main processing loop
// Display results
Console.WriteLine("\nEnd PSO demo\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal error: " + ex.Message);
}
} // Main()
static double ObjectiveFunction(double[] x)
{
return 3.0 + (x[0] * x[0]) + (x[1] * x[1]);
}
} // class Program
public class Particle
{
// Definition here
}
} // ns
Nach der Instanziierung des Random-Objekts mit einer beliebigen Startwert 0, initialisiert einige wichtigen PSO Variablen:
int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;
Ich verwende 10 Partikel-Objekte. Als Faustregel gilt mehr Partikel-Objekte sind besser als weniger, aber mehr Programmleistung erheblich beeinträchtigen kann. Kann ich festgelegt die Anzahl der Schleifeniterationen wichtigsten Verarbeitung auf 1.000. Die Anzahl der Iterationen, die Sie verwenden möchten, müssen hängt von der Komplexität des Problems, die Sie optimieren möchten, und die Verarbeitungsleistung des Host-Maschine. PSO-Programme verwenden normalerweise einen Wert zwischen 1.000 und 100.000. Die Variable namens Iteration ist ein Zähler zu verfolgen die Anzahl der Iterationen Hauptschleife. Die Dim-Variable enthält die Anzahl der x-Werte in einer Lösung/Position. Da mein Beispiel Problem muss finden die Werte von 0 X und die Minimierung von 3 X 1 + 0 X ^ 2 + 1 X ^ 2, I Dim auf 2 festgelegt. Wie bereits erwähnt, sollten Sie in den meisten Situationen der PSO die X-Werte zu beschränken, die den Vektor Position-Lösung auf einige Problem-abhängige Bereich bilden. Ohne einige Beschränkungen sind effektiv von double gesucht werden.MinValue zu verdoppeln.MaxValue. Hier beschränken ich willkürlich X 0 und X 1, [100.0, +100.0].
Als Nächstes vorbereiten ich die Partikel Schwarm instanziieren:
Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue;
double minV = -1.0 * maxX;
double maxV = maxX;
Ich erstellen ein Array von Partikel-Objekte, die mit dem Namen Schwarm. Ich auch richten Sie ein Array, halten die globale bekannte Position durch ein beliebiges Partikel bestimmt – gekennzeichnet durch g(t) in den Algorithmus – und die entsprechenden Eignung des Arrays Position. Einschränkungen für die maximalen und minimalen Werte für eine neue Velocity festgelegt. Die Idee dahinter ist, dass da eine neue Velocity ein Partikel neue Position bestimmt, das Ausmaß der Velocity Komponenten enorm sein sollen nicht.
Der Code zum Initialisieren des Punktschwarms lautet wie folgt:
for (int i = 0; i < swarm.Length; ++i)
{
double[] randomPosition = new double[Dim];
for (int j = 0; j < randomPosition.Length; ++j) {
double lo = minX;
double hi = maxX;
randomPosition[j] = (hi - lo) * ran.NextDouble() + lo;
}
...
Iterieren durch jedes Partikel-Objekt im Array mit dem Namen Punktschwarms. Ich erkläre es sich um ein Array der Größe Dim eine zufällige Position für das aktuelle Partikel zu halten. Für jede X-Wert der Position ich einen zufälligen Wert zwischen MinX (100.0) und MaxX (+100.0) generiert. In vielen realistischen PSO Probleme wird der Bereich für jede X-Wert unterschiedlich sein, so Sie Code hinzufügen, um mit jedem X-Wert im Positionsarray gesondert eingehen müssen.
Jetzt fortgesetzt, die den Initialisierungsprozess:
double fitness = ObjectiveFunction(randomPosition);
double[] randomVelocity = new double[Dim];
for (int j = 0; j < randomVelocity.Length; ++j) {
double lo = -1.0 * Math.Abs(maxX - minX);
double hi = Math.Abs(maxX - minX);
randomVelocity[j] = (hi - lo) * ran.NextDouble() + lo;
}
swarm[i] = new Particle(randomPosition, fitness, randomVelocity,
randomPosition, fitness);
...
Zuerst berechnet die Qualität des aktuellen Zufallsposition Arrays von Arrays an die Methode ObjectiveFunction übergeben. Wenn Sie zurück in Abbildung 5, sehen Sie, dass die ObjectiveFunction-Methode einfach den Wert der Funktion, die ich Versuche zu minimieren, nämlich 3 + x 0 berechnet ^ 2 + 1 X ^ 2. Als Nächstes berechnen Sie eine zufällige Geschwindigkeit für das aktuelle Partikel-Objekt. Nachdem ich eine zufällige Position, die Eignung des zufällige Position und eine zufällige habe, übergeben diese Werte für die Partikel-Konstruktor. Denken Sie daran, dass der vierten und fünften Parameter bekannt das Partikel-Position und seine zugeordneten Fitness, so dass beim Initialisieren eines Partikels zufällige anfänglichen Position und Fitness die bekannt Werte sind.
Der Initialisierungscode Schwarm endet mit:
...
if (swarm[i].fitness < bestGlobalFitness) {
bestGlobalFitness = swarm[i].fitness;
swarm[i].position.CopyTo(bestGlobalPosition, 0);
}
} // End initialization loop
Ich überprüfen, ob die Eignung des aktuellen Partikel das beste ist (im Falle eines Problems Minimierung kleinste) Fitness bisher gefunden. Wenn dies der Fall ist, aktualisiert Array-BestGlobalPosition und die entsprechende Variable BestGlobalFitness.
Als Nächstes vorbereiten ich die Hauptschleife für die Verarbeitung des PSO eingeben:
double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizers
Ich legen den Wert für w, das Gewicht Trägheit zu 0.729. Dieser Wert wurde von einer Forschungsarbeit empfohlen, die die Auswirkungen der verschiedenen PSO Parameterwerte auf eine Reihe von Benchmark-Minimierung Probleme untersucht. Anstatt ist einen einzelnen, konstanten Wert für w ein alternativer Ansatz der Wert von w variieren. Beispielsweise wenn PSO-Algorithmus ist könnte festgelegt, 10.000 Mal durchlaufen Sie zunächst w als 0,90 und allmählich verringern, 0,40 durch Reduzierung w w 0.10 nach jeder 2.000 Iterationen. Die Idee einer dynamischen w ist, dass frühzeitig im Algorithmus Sie größere Änderungen in Position untersuchen möchten, aber später kleinere Partikel Bewegungen werden soll. Ich legen die Werte für c1 und c2, die Gewichte kognitiven und sozialen auf 1.49445. Wieder wurde dieser Wert durch eine Studie empfohlen. Wenn den Wert größer als der Wert von c2 c1 festgelegt wird, platzieren Sie mehr Gewicht auf ein Partikel bekannt Position als weltweit bekanntesten Position des Punktschwarms und umgekehrt. Zufallsvariablen r1 und r2 PSO-Algorithmus eine zufällige Komponente hinzu, und verhindern, dass den Algorithmus eine nicht optimale lokalen minimale oder maximale Lösung stecken.
Als Nächstes, beginnen Sie die Hauptschleife für die Verarbeitung des PSO:
for (int i = 0; i < swarm.Length; ++i)
{
Particle currP= swarm[i];
for (int j = 0; j < currP.velocity.Length; ++j)
{
r1 = ran.NextDouble();
r2 = ran.NextDouble();
newVelocity[j] = (w * currP.velocity[j]) +
(c1 * r1* (currP.bestPosition[j] - currP.position[j])) +
(c2 * r2 * (bestGlobalPosition[j] - currP.position[j]));
...
Jedes Partikel-Objekt unter Verwendung von i Schwarm werden durchlaufen als Indexvariable. Ich erstellen Sie einen Verweis auf das aktuelle Partikel-Objekt mit dem Namen CurrP, um mein Code zu vereinfachen, aber ich konnte Schwarm [i] bereits direkt verwendet haben. Wie im vorherigen Abschnitt erläutert, ist der erste Schritt jedes Partikel Geschwindigkeitsvektors aktualisieren. Für das aktuelle Partikel-Objekt ich jedes einer der Werte in der Object-Velocity-Array durchlaufen Zufallsvariablen r1 und r2 generieren und aktualisieren jede Velocity-Komponente, wie im vorherigen Abschnitt erläutert.
Nachdem ich eine neue Velocity-Komponente für das aktuelle Partikel-Objekt zu berechnen, prüfe ich, ob diese Komponente zwischen der minimalen und maximalen Werte für eine Velocity-Komponente ist:
if (newVelocity[j] < minV)
newVelocity[j] = minV;
else if (newVelocity[j] > maxV)
newVelocity[j] = maxV;
} // each j
newVelocity.CopyTo(currP.velocity, 0);
...
Wenn die Komponente außerhalb des Bereichs liegt, bringe ich es wieder in den Bereich. Die Idee dahinter ist, dass extreme Werte für die Velocity-Komponente nicht da Extremwerte meine neue Position außerhalb der Grenzen Spin könnte. Nachdem alle Velocity-Komponenten berechnet wurden, aktualisieren Sie das aktuelle Partikel Objekt Velocity Array mit dem handy.NET CopyTo-Methode.
Sobald die Geschwindigkeit der aktuellen Partikel festgestellt worden ist, kann verwendet die neue Velocity zu berechnen und aktualisieren das aktuelle Partikel-Position:
for (int j = 0; j < currP.position.Length; ++j)
{
newPosition[j] = currP.position[j] + newVelocity[j];
if (newPosition[j] < minX)
newPosition[j] = minX;
else if (newPosition[j] > maxX)
newPosition[j] = maxX;
}
newPosition.CopyTo(currP.position, 0);
...
Führen Sie erneut eine Bereichsüberprüfung, dieses Mal auf das aktuelle Partikel neue Position Komponenten. In gewisser Hinsicht ist dies eine redundante Kontrollkästchen weil ich habe bereits den Wert jeder Komponente Velocity eingeschränkt, aber meiner Meinung nach zusätzliche Kontrollkästchen hier gerechtfertigt ist.
Nun, ich das aktuelle Partikel Objekt neue Position, ich neue Fitness-Wert zu berechnen und Fitness-Feld des Objekts zu aktualisieren:
newFitness = ObjectiveFunction(newPosition);
currP.fitness = newFitness;
if (newFitness < currP.bestFitness) {
newPosition.CopyTo(currP.bestPosition, 0);
currP.bestFitness = newFitness;
}
if (newFitness < bestGlobalFitness) {
newPosition.CopyTo(bestGlobalPosition, 0);
bestGlobalFitness = newFitness;
}
} // each Particle
} // main PSO loop
...
Nach der Aktualisierung des aktuellen Partikels, prüfe ich, ob die neue Position der bekanntesten Position des Partikels ist; Ich auch überprüfen, ob die neue Position eine optimale Position für den globalen Schwarm ist. Beachten Sie, dass logisch, kann es eine neue globale beste Position nur, wenn es ist am besten lokale Position, damit ich die globale beste Überprüfung innerhalb der Kontrollkästchen für eine lokale optimale Position geschachtelt haben könnte.
An dieser Stelle meine Hauptschleife PSO Algorithmus abgeschlossen ist, und ich kann meine Ergebnisse angezeigt:
Console.WriteLine("\nProcessing complete");
Console.Write("Final best fitness = ");
Console.WriteLine(bestGlobalFitness.ToString("F4"));
Console.WriteLine("Best position/solution:");
for (int i = 0; i < bestGlobalPosition.Length; ++i){
Console.Write("x" + i + " = " );
Console.WriteLine(bestGlobalPosition[i].ToString("F4") + " ");
}
Console.WriteLine("");
Console.WriteLine("\nEnd PSO demonstration\n");
}
catch (Exception ex)
{
Console.WriteLine("Fatal error: " + ex.Message);
}
} // Main()
Erweitern und ändern
Nun, Sie schreiben eine grundlegende PSO gesehen haben, betrachten Sie zum Erweitern und ändern Sie den Code vorgestellten. Das Beispiel-Problem, das ich gelöst ist künstlich in dem Sinne, dass es keine Notwendigkeit, PSO verwenden, um eine ungefähre Lösung zu finden, da genau das Problem gelöst werden kann. Wobei PSO wirklich nützlich ist ist, wenn das numerische Problem untersucht extrem schwierig oder unmöglich ist, lösen mit standard-Techniken ist. Betrachten Sie das folgende Problem. Die Bewertung einer (amerikanische) Fußballspiel zwischen Teams A und b vorhergesagt werden soll Historische Daten bestehend aus der vorherigen Ergebnisse von a und b gegen andere Teams. Mathematisch Modellieren Sie die historische Bewertung für ein Team X so, dass gewinnt das Team ein Spiel, das Team Bewertung von einigen fester Wert (z. B. 16 Punkte geht) plus einen anderen Wert, den Unterschied zwischen Ratings der Teams hängt (0,04 Zeiten den Unterschied sagen, wenn das Team X-Rating kleiner als des gegnerischen Teams ist). Darüber hinaus Modellieren Sie den vorhergesagten Rand Sieg eines Teams als eine Funktion der Differenz im Team Bewertungen; beispielsweise prognostiziert Wenn Team X 1720 bewertet wird und Team Y wird als 1.620 eingestuft, Ihr Modell eine Gewinnspanne von Sieg für x 3,5 Punkte. Kurz gesagt, haben eine große Datenmenge und müssen mehrere numerische Werte (z. B. die 16 und die 0,04) zu bestimmen, die Ihre Vorhersage-Fehler zu minimieren. Diese Data-driven Parameterschätzung ist die Art des Problems, das nach rechts oben des PSO Alley ist.
PSO ist nur eine mehrere AI-Techniken, die das Verhalten von natürlichen Systemen. Vielleicht ist die Technik, PSO Algorithmen am nächsten genetischen Algorithmen (GAs). Beide Verfahren sind gut geeignet für schwierige numerische Probleme. GAs wurden ausführlich untersucht seit Jahrzehnten. Ein Vorteil des PSOs über GAs ist, dass PSO Algorithmen wesentlich einfacher zu implementieren als GAs. Es ist nicht klar zu diesem Zeitpunkt ob PSOs mehr oder weniger effektiv als GAs oder ungefähr gleich sind.
Die Version des PSO die hier vorgestellten kann in vielerlei Hinsicht geändert werden. Eine Änderung besonders interessant ist, mehrere Sub-swarms Partikel anstelle einer globalen Schwarm verwenden. With such a design, each particle belongs to a sub-swarm and the new velocity of a particle could depend on four terms rather than three: the old velocity, the particle’s best known position, the best known position of any particle in the sub-swarm, and the best known position of any particle. Die Idee dieses Sub-swarm-Design ist, verringern das Risiko des PSO-Algorithmus in eine nicht optimale Lösung stecken. Zu den besten meines Wissens ist ein solches Design nicht noch gründlich untersucht worden.
Dr. James McCaffrey arbeitet für Volt Information Sciences Inc. und wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington Campus. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. Dr. McCaffrey ist Autor von ".NET Test Automation Recipes"(Apress, 2006), und erreichen Sie unter jammc@microsoft.com.
Dank der folgenden technischen Experten von Microsoft für die Überprüfung dieses Artikels: Paul Koch, Dan Liebling, Anne Loomis Thompson und Shane Williams