Februar 2016
Band 31, Nummer 2
Dieser Artikel wurde maschinell übersetzt.
Testlauf: Effekt der sozialen Erleichterung – Von Kakerlaken lernen
Durch James McCaffrey
.jpg "James McCaffrey")
Günstig internen Netzwerk herstellten Optimierung ist eine numerische Optimierungsalgorithmus, der das Verhalten der allgemeinen Küchenschaben wie z. B. Periplaneta Americana lose basiert. Ja, Sie lesen, die ordnungsgemäß. Im Folgenden soll dies näher erläutert werden.
Machine learning wird ein numerischer Optimierungsalgorithmus häufig verwendet, um einen Satz von Werten für (zumeist als Gewichtungen bezeichnete) Variablen zu finden, die Fehlermaß minimieren. Für die logistische Regressionsklassifizierung wird z. B. die folgende mathematische Gleichung verwendet: wenn es n Vorhersagevariablen gibt, gibt es n+1 Gewichtungswerte, die ermittelt werden müssen. Der Prozess des Bestimmens der Werte für die Gewichtungen wird als Trainieren des Modells bezeichnet. Die Idee ist es, eine Auflistung von Trainingsdaten zu verwenden, die über bekannt korrekte Ausgabewerte verfügen. Ein numerischer Optimierungsalgorithmus wird verwendet, um die Werte der Gewichtungen zu finden, die den Fehler zwischen berechneten Ausgabewerten und bekannt korrekte Ausgabewerte zu minimieren.
Es gibt viele verschiedene numerische Optimierungsalgorithmen. Die am häufigsten verwendeten basieren auf Kalkül Derivate, aber es gibt auch Algorithmen, die auf das Verhalten der natürlichen Systemen basieren. Diese werden manchmal Bio Inspirierte Algorithmen bezeichnet. Dieser Artikel erläutert eine relativ neue (zuerst in 2008 veröffentlichte) Technik günstig internen Netzwerk herstellten Optimierung (RIO). RIO-Optimierung modelliert lose die Nahrungssuche und aggregieren das Verhalten einer Auflistung von Roaches.
Eine gute Möglichkeit, um einen ersten Eindruck vom Inhalt RIO abzurufen und worauf dieser Artikel ist ist auf einen Blick auf das Demoprogramm in Abbildung 1. Das Ziel der Demo ist RIO verwenden, um den minimalen Wert der Rastrigin-Funktion mit acht Eingabevariablen zu suchen. Die Rastrigin-Funktion ist eine standardmäßige benchmarkfunktion zum Bewerten der Effektivität numerischer Optimierungsalgorithmen. Die Funktion verfügt über einen bekannten Mindestwert von 0,0 am x = (0, 0,... 0), wenn die Anzahl der Werte von 0 gleich der Anzahl der Eingabewerte ist.
.png "Die günstig internen Netzwerk herstellten Optimierungsalgorithmus in Aktion")
Abbildung 1: die günstig internen Netzwerk herstellten Optimierungsalgorithmus in Aktion
Die Rastrigin-Funktion ist für die meisten Optimierungsalgorithmen schwierig, da viele Spitzen und Täler, die lokalen Mindestwerte, die erstellen die Algorithmen abfangen können. Es ist nicht möglich, die Funktion Rastrigin mit acht Eingabewerten einfach zu visualisieren, aber erhalten Sie eine Vorstellung der Merkmale der Funktion durch ein Diagramm der Funktion für zwei Eingabewerte, siehe untersuchen Abbildung 2.
.png "Die Rastrigin-Funktion mit zwei Variablen")
Abbildung 2: die Rastrigin-Funktion mit zwei Variablen
Das Demoprogramm legt die Anzahl der Roaches auf 20 fest. Jedes simulierte günstig hat es sich um eine Position, die eine mögliche Lösung für das Minimierungsproblem darstellt. Weitere Roaches erhöhen die Wahrscheinlichkeit die tatsächlich optimale Lösung auf Kosten der Leistung zu finden. RIO verwendet normalerweise 10 bis 100 Roaches.
RIO ist ein iterativer Prozess und erfordert einen maximalen schleifenzählerwert. Die Demo wird der maximale Wert auf 10.000 Iterationen. Die maximale Anzahl von Iterationen variiert Problem zum Problem, aber Werte zwischen 1.000 und 100.000 gelten. RIO ist ein Element der Zufälligkeit und die Demo wird der Startwert für den Zufallszahlen-Generator, 6, da 6 repräsentative Demo Ausgabe gegeben haben.
In der Demo gezeigt Abbildung 1, die beste (kleinste) Fehler mit der besten günstig Position wurden bisher gefunden angezeigt wurde jedem 500 Einheiten. Nach Abschluss des Algorithmus, die optimale Position gefunden wurde günstig x = (0, 0, 0, 0, 0, 0, 0, 0), die in der Tat die richtige Antwort ist. Aber beachten Sie, wenn die maximale Anzahl von Iterationen 5.000 anstelle von 10.000 festgelegt hatten, RIO nicht mindestens eine globale gefunden haben würde. RIO, wie fast alle numerischen Optimierungsalgorithmen nicht notwendigerweise in praktische Szenarien eine optimale Lösung zu suchen.
Dieser Artikel setzt mindestens fortgeschrittene Programmierkenntnisse verfügen jedoch nicht vorausgesetzt, dass Sie irgendetwas über numerische Optimierung oder den günstig internen Netzwerk herstellten Optimierungsalgorithmus kennen. Das Demoprogramm ist mit c# codiert, aber Sie sollten keine Umgestalten von Code in einer anderen Sprache wie Visual Basic oder JavaScript.
In diesem Artikel wird der gesamte Democode mit ein paar kleinen Änderungen gezeigt, um Platz zu sparen. Die Demo ist im Codedownload enthalten, der diesen Artikel begleitet. Aus dem Democode wurden alle üblichen Fehlerprüfungen entfernt, um die wichtigsten Konzepte so klar wie möglich und die Größe des Codes gering zu halten.
Allgemeine Programmstruktur
Die allgemeine Programmstruktur wird in Abbildung 3 gezeigt. Um die Demo zu erstellen, wenn ich Visual Studio gestartet und erstellt eine neue C#-Konsolenanwendung namens RoachOptimization. Die Demo hat keine nennenswerten Microsoft .NET Framework-Abhängigkeiten, daher kann eine beliebige Version von Visual Studio verwendet werden.
Abbildung 3 günstig Optimierung Struktur des Demoprogramms
using System;
namespace RoachOptimization
{
class RoachOptimizationProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin roach optimization demo");
// Code here
Console.WriteLine("End roach demo");
Console.ReadLine();
}
static double[] SolveRastrigin(int dim, int numRoaches,
int tMax, int rndSeed) { . . }
public static double Error(double[] x) { . . }
static double Distance(double[] pos1,
double[] pos2) { . . }
static void Shuffle(int[] indices,
int seed) { . . }
} // Program
public class Roach
{
// Defined here
}
}
Nachdem der Vorlagencode im Visual Studio-Editor geladen, im Projektmappen-Explorer-Fenster habe ich die Datei "Program.cs" den aussagekräftigeren RoachOptimizationProgram.cs umbenannt und Visual Studio Class Program automatisch für mich umbenannt. Klicken Sie oben auf der Quellcode habe ich gelöscht unnötige using-Anweisungen, verlassen einfach die einzelnen Verweis auf System.
Ich programmiert die Demo einen Ansatz größtenteils statische Methode statt einer vollständigen objektorientierten Programmierung (OOP) Ansatz. Die Demo hat die gesamte Steuerlogik in der Main-Methode. Zunächst wird der Algorithmus Eingabeparameterwerte einrichten:
Console.WriteLine("Begin roach optimization demo");
int dim = 8;
int numRoaches = 20;
int tMax = 10000;
int rndSeed = 6;
Die dim-Variable gibt die Anzahl der Eingabewerte für Rastrigins-Funktion. In einem Szenario mit nicht-Demo maschinelles stellt die Dimension die Anzahl der Gewichtungen in das Vorhersagemodell dar. Die Anzahl der Roaches wird auf 20 festgelegt. Variable tMax ist die maximale Anzahl von Iterationen. RIO, ist ähnlich wie die meisten Algorithmen Bio Inspirierte probabilistisch. Hier ist ein Startwert Random-Variablen auf 6 festgelegt.
Als Nächstes werden die RIO-Parameter in der Konsole ausgegeben:
Console.WriteLine("Goal is to minimize Rastrigin's " +
"function in " + dim + " dimensions");
Console.WriteLine("Problem has known min value = 0.0 " +
"at (0, 0, .. 0) ");
Console.WriteLine("Setting number of roaches = " +
numRoaches);
Console.WriteLine("Setting maximum iterations = " +
tMax);
Console.WriteLine("Setting random seed = " + rndSeed);;
Die günstig Optimierungsalgorithmus wird aufgerufen, wie folgt:
Console.WriteLine("Starting roach optimization ");
double[] answer = SolveRastrigin(dim, numRoaches,
tMax, rndSeed);
Console.WriteLine("Roach algorithm completed");
Die Main-Methode endet mit dem Anzeigen der Ergebnisse:
double err = Error(answer);
Console.WriteLine("Best error found = " +
err.ToString("F6") + " at: ");
for (int i = 0; i < dim; ++i)
Console.Write(answer[i].ToString("F4") + " ");
Console.WriteLine("");
Console.WriteLine("End roach optimization demo");
Console.ReadLine();
Die in diesem Artikel vorgestellten günstig Optimierungsalgorithmus 2008 Forschungsbericht "Günstig internen Netzwerk herstellten Optimization" von t Häfen, C. Spanien, N. Lachsfarbe und J. Keller basiert. Sie finden das Papier an verschiedenen Speicherorten im Web.
Grundlegendes zu den günstig Optimierungsalgorithmus
In RIO ist es eine Sammlung von simulierten Roaches. Jede günstig hat eine Position in n-Dimensionen, die eine mögliche Lösung für ein Minimierungsproblem darstellt. Simulierte günstig Verhalten basiert auf drei Verhaltensweisen von echten Roaches. Roaches tendenziell zuerst nach dunkle Bereiche bewegen. Zweitens: wie Roaches zu gruppieren. Drittens Wenn Roaches hungrig erhalten, lassen ihren aktuellen Speicherort für Nahrungsmittel suchen. Genau wie simulierte Roaches Modell werden diese Verhaltensweisen klar, wenn der Code angezeigt wird.
In High Pseudocode ausgedrückt, die günstig Optimierungsalgorithmus werden im Abbildung 4. Auf den ersten Blick scheint der Algorithmus relativ einfach; Es gibt jedoch viele Details, die nicht in der Pseudocode sichtbar sind.
Abbildung 4: des Algorithmus günstig auf hoher Ebene
initialize n roaches to random positions
loop tMax times
compute distances between all roaches
compute median distance
for-each roach
compute number neighbors
exchange data with neighbors
if not hungry
compute new velocity
compute new position
check if new best position
else if hungry
relocate to new position
end-if
end-for
end loop
return best position found
Die günstig-Klasse
Die Definition der Anwendung definierte Klasse günstig beginnt mit:
public class Roach
{
public int dim;
public double[] position;
public double[] velocity;
public double error;
...
Dim Feld ist das Problem, 8 für die Demo ist. Das Feld Position ist ein Array, das vom Konzept her den Speicherort der repräsentiert eine günstig und stellt auch eine mögliche Lösung für ein Minimierungsproblem. Das Feld Geschwindigkeit ist ein Array von Werten, die bestimmen, wo die günstig in die nächste Einheit verschoben werden kann. Z. B. wenn dim = 2 und Position = (5.0, 3.0) und Geschwindigkeit = (1.0,-2.0), die günstig auf verschoben wird (6.0, 1.0). Feld für den Fehler ist der Fehler, die die aktuelle Position zugeordnet.
Die Definition wird fortgesetzt:
public double[] personalBestPos;
public double personalBestErr;
public double[] groupBestPos;
public int hunger;
private Random rnd;
Das PersonalBestPos-Feld enthält die optimale Position gefunden durch die simulierte günstig zu einem beliebigen Zeitpunkt während der Bewegung. Die PersonalBestError enthält Fehler, der die PersonalBestPos entspricht. Das GroupBestPos-Feld enthält die optimale Position gefunden, die von keiner der eine Gruppe von Nachbarn Roaches. Der Hunger-Feld ist ein Integer-Wert, der darstellt, wie viel die günstig ist. Rnd der Random-Objekt wird verwendet, um eine günstig an eine zufällige Position zu initialisieren.
Die Klassendefinition günstig weiterhin durch Definieren eines Konstruktors:
public Roach(int dim, double minX, double maxX,
int tHunger, int rndSeed)
{
this.dim = dim;
this.position = new double[dim];
this.velocity = new double[dim];
this.personalBestPos = new double[dim];
this.groupBestPos = new double[dim];
...
Die Parameter "minx" und "Maxx" werden verwendet, um Grenzwerte für die Komponenten des Vektors Position festzulegen. Parameter tHunger ist eine maximale Hunger-Wert. Wenn eine günstig Hunger tHunger erreicht, wird die günstig an einen neuen Speicherort verschoben. Der Konstruktor reserviert Speicherplatz für die vier Arrayfelder.
Als Nächstes wird der Konstruktor initialisiert das Random-Objekt, und klicken Sie dann zum Festlegen des anfänglichen Hunger Werts auf einen zufälligen Wert verwendet:
this.rnd = new Random(rndSeed);
this.hunger = this.rnd.Next(0, tHunger);
Als Nächstes der Konstruktor Anfangsposition, Geschwindigkeit, persönliche besten Ort und festgelegt Gruppe beste Speicherort Arrays zu Zufallswerten zwischen "minx" und "Maxx":
for (int i = 0; i < dim; ++i) {
this.position[i] = (maxX - minX) * rnd.NextDouble() + minX;
this.velocity[i] = (maxX - minX) * rnd.NextDouble() + minX;
this.personalBestPos[i] = this.position[i];
this.groupBestPos[i] = this.position[i];
}
Die Definition Abschluss die günstig Konstruktor wie folgt:
...
error = RoachOptimizationProgram.Error(this.position);
personalBestErr = this.error;
} // ctor
} // Roach
Feld für den Fehler wird durch Aufrufen der externen Methode Fehler in der aufrufenden Programmklasse definiert festgelegt. Ein alternativer Ansatz ist zum Berechnen des Fehlerwert vor dem Aufrufen der Konstruktor und anschließend den Fehlerwert als Parameter an den Konstruktor übergeben.
Implementieren des günstig-Algorithmus
RIO-Algorithmus ist in statischen Methode SolveRastrigin, enthalten, deren Definition als beginnt:
static double[] SolveRastrigin(int dim, int numRoaches,
int tMax, int rndSeed)
{
double C0 = 0.7;
double C1 = 1.43;
double[] A = new double[] { 0.2, 0.3, 0.4 };
...
Konstanten C0 und C1 werden verwendet, wenn computing neue Geschwindigkeit eine günstig, wie Sie gleich sehen werden. Die verwendeten Werte 0,7 und 1,43, stammen aus Particle Swarm Theorie. Möglicherweise möchten andere Werte zu untersuchen.
Roaches, die nahe beieinander liegen, werden als Nachbarn bezeichnet. Nachbarn werden in einigen Fällen aber nicht immer, die Exchange-Informationen. Das Array, mit dem Namen einer Wahrscheinlichkeiten enthält. Der erste Wert, 0,2, ist die Wahrscheinlichkeit, dass ein günstig mit einem Nachbarn mit der Nachbar austauschen wird. Der zweite Wert, 0,3, ist die Wahrscheinlichkeit, dass ein günstig Informationen austauschen, zwei Nachbarn verfügt. Der dritte Wert, 0,4, ist die Wahrscheinlichkeit für den Austausch von Informationen, wenn eine günstig mindestens drei Nachbarn verfügt.
Diese Wahrscheinlichkeitswerte (0,2, 0,3, 0,4) stimmen nicht mit den in der Forschungsarbeit Quelle verwendet wurden. Die ursprüngliche Studie verwendet Wahrscheinlichkeitswerte (0,49 0,63, 0.65), die tatsächlichen günstig Verhalten wie beschrieben in einer Forschungsarbeit Rahmen entsprechen. Habe ich entdeckt, dass die Wahrscheinlichkeit, die echte günstig Verhalten entsprechen nicht so effektiv wie die künstliche Wahrscheinlichkeitswerte verwendet, in der Demo waren. Die Definition der Methode SolveRastrigin fort:
int tHunger = tMax / 10;
double minX = -10.0;
double maxX = 10.0;
int extinction = tMax / 4;
Random rnd = new Random(rndSeed);
Lokale Variablen tHunger bestimmt, wann eine günstig hungrig geworden und lassen Sie den aktuellen Speicherort und Nachbarn wird. Z. B. wenn tMax 10.000 wie in der Demo ist, wenn ein günstig Hunger Wert erreicht tMax / 10 = 1.000, die günstig wird an eine neue Position verschoben.
Variablen "minx" und "Maxx" legen Grenzwerte für eine günstig Position Vektor. Die Werte (-10.0, + 10,0) sind normal für maschinelles lernen Gewichten und auch üblichen Grenzen für die Rastrigin-Funktion entsprechen. Zum Beispiel für ein Problem mit der Dimension = 3, Position Vektor ist ein Array von drei Zellen, alle Werte zwischen 10,0 und + 10,0 müssen.
Lokale Variable erlöschen bestimmt, wann alle Roaches sterben und an neue Positionen reborn sein werden. Dieser Mechanismus ist ein Neustart und hilft zu verhindern, dass den Algorithmus einen nicht optimalen Lösung verbleiben.
Lokale Rnd der Random-Objekt wird vom Algorithmus für drei Zwecke verwendet. Die Reihenfolge, in der die Roaches verarbeitet werden, wird zufällig; der Austausch von Informationen zwischen benachbarten Roaches auftritt, mit einer bestimmten Wahrscheinlichkeit. und es gibt eine zufällige Komponente jeder günstig neue Geschwindigkeit. Methode SolveRastrigin wird fortgesetzt:
Roach[] herd = new Roach[numRoaches];
for (int i = 0; i < numRoaches; ++i)
herd[i] = new Roach(dim, minX, maxX, tHunger, i);
Die Auflistung der simulierten Roaches ist ein Array mit dem Namen Bestand. Es gibt viele interessante Namen für Auflistungen von Elementen, z. B. einen z. b-Pod und eine Reihe von Geese. Der Tat ist eine Sammlung von Küchenschaben Angriff Roaches bezeichnet. (Diese Informationen kann ein nützliches Balken Suchergebnis für Sie gestalten.)
Beachten Sie, dass die Schleife Variable index i, an die günstig-Konstruktor übergeben wird. Die Indexvariable fungiert als zufälliger Ausgangswert für das Random-Objekt, das Teil der Klassendefinition günstig ist. Übergeben Sie eine Schleife Index-Variable als einen zufälligen Ausgangswert verwendet werden soll, ist ein gängiges Verfahren Machine Learning. Die Methodendefinition fort:
int t = 0; // Loop counter (time)
int[] indices = new int[numRoaches];
for (int i = 0; i < numRoaches; ++i)
indices[i] = i;
double bestError = double.MaxValue;
double[] bestPosition = new double[numRoaches];
int displayInterval = tMax / 20;
Das Array mit dem Namen Indizes enthält Werte (0, 1-2,.. NumRoaches-1). Das Array wird in der Hauptverarbeitungsschleife gemischt werden, damit die Reihenfolge, in der die Roaches verarbeitet werden, jedes Mal unterscheidet. Lokale Variablen BestPosition und BestError enthalten die bestmöglichen Position und den zugeordneten Fehler günstig zu einem beliebigen Zeitpunkt. Lokale Variable "displayinterval" bestimmt, wann eine Statusnachricht an der Konsole angezeigt wird. Als Nächstes wird eine Array von Arrays Style-Matrix instanziiert, um den Abstand zwischen alle Paare von Roaches enthalten:
double[][] distances = new double[numRoaches][];
for (int i = 0; i < numRoaches; ++i)
distances[i] = new double[numRoaches];
Zum Beispiel wenn Abstände [0] [3] = 7.89 und Abstände [3] [0] ist 7.89 und des Abstands zwischen günstig 0 und günstig 3 7.89. Beachten Sie, dass die redundanten Daten schwerwiegende nicht, da in den meisten Fällen eine riesige Anzahl von Roaches lassen. Im nächsten Schritt startet die Hauptverarbeitungsschleife vor:
while (t < tMax)
{
if (t > 0 && t % displayInterval == 0) {
Console.Write("time = " + t.ToString().PadLeft(6));
Console.WriteLine(" best error = " +
bestError.ToString("F5"));
}
...
Klicken Sie dann die Abstände zwischen Roaches berechnet wird:
for (int i = 0; i < numRoaches - 1; ++i) {
for (int j = i + 1; j < numRoaches; ++j) {
double d = Distance(herd[i].position,
herd[j].position);
distances[i][j] = distances[j][i] = d;
}
}
Die Entfernung-Werte werden mit der Hilfsmethode Entfernung in Kürze vorgestellt wird berechnet. Das Array, das hier Indizierung ist etwas schwieriger, aber ich überlasse es, um zu überprüfen, wenn Sie neugierig sind. Als Nächstes werden die Abstandswerte kopiert, aus der Entfernung in ein Array damit sortiert werden können, und klicken Sie dann der Median Abstand ermittelt werden kann:
double[] sortedDists =
new double[numRoaches * (numRoaches - 1) / 2];
int k = 0;
for (int i = 0; i < numRoaches - 1; ++i) {
for (int j = i + 1; j < numRoaches; ++j) {
sortedDists[k++] = distances[i][j];
}
}
Die Größe des Arrays wird am besten anhand eines Beispiels erläutert. Angenommen, es gibt n = 4 Roaches. Die Matrix Abstände Größe 4 x 4 haben. Die Werte auf die diagonale, [0] [0], [1] [1], [2] [2] und [3] [3] wird 0,0 sein und sollte nicht eingeschlossen werden. Die bewirkt, dass der Wert 6 [0] [1], [0] [2], [0] [3], [1] [2], [1] [3] und [2] [3]. Ist nicht die Werte identisch Entfernung bei symmetrischen Indizes [1] [0], [2] [0] usw. erforderlich. Also werden n * (n-1) / 2 unterschiedliche Werte Abstand. Als Nächstes wird der Median Abstand zwischen Roaches berechnet und günstig Indizes werden zufällig festgelegt:
Array.Sort(sortedDists);
double medianDist = sortedDists[sortedDists.Length / 4];
Shuffle(indices, t); // t is used as a random seed
Hier, da ich durch 4 aufteilen, die Entfernung ist ein Viertel vom Anfang des Arrays sortierten Abstände, damit das Ergebnis nicht unbedingt ein Wendepunkt, sondern eine Quartil. Der ursprünglichen Forschungsarbeit anhand des tatsächlichen Medians (geteilt durch 2), aber ich festgestellt, dass eine bessere Leistung als der Median der Quartil gearbeitet. Die Idee ist, dass der Median oder Quartil bestimmt, wie viele Nachbarn ein günstig ist, beeinflusst die wiederum wie genau die Roaches gruppiert werden. Mit der Quartil behält die Roaches weiter auseinander, und ihnen die bessere Möglichkeit schwierig globale für einen minimalen Wert der Zielfunktion minimieren gefunden.
Die günstig Indizes werden zufällig festgelegt, mit der Hilfsmethode mischen, die in Kürze angezeigt wird. Beachten Sie, dass die Zeit Variable index t, an der Shuffle-Methode übergeben wird, und fungiert als Ausgangswert für die zufällige Wiedergabe Zufallszahlen-Generator. Danach beginnt die Schleife verarbeitet jede günstig:
for (int i = 0; i < numRoaches; ++i) // Each roach
{
int idx = indices[i]; // Roach index
Roach curr = herd[idx]; // Ref to current roach
int numNeighbors = 0;
...
Ein Verweis auf die aktuelle günstig, Bestand [Idx], erstellt und mit dem Namen (BW). Dies wird nur ergänzend bereitgestellt. Als Nächstes wird die Anzahl der Nachbarn von der aktuellen günstig berechnet:
for (int j = 0; j < numRoaches; ++j) {
if (j == idx) continue;
double d = distances[idx][j];
if (d < medianDist) // Is a neighbor
++numNeighbors;
}
Die Bedingung j == Idx wird verwendet, um zu verhindern, dass die aktuelle günstig als Nachbar selbst gezählt. Als Nächstes wird die effektive Anzahl der Nachbarn bestimmt:
int effectiveNeighbors = numNeighbors;
if (effectiveNeighbors >= 3)
effectiveNeighbors = 3;
Denken Sie daran, dass dient zur Berechnung der Anzahl der Nachbarn Nachbarn Informationen austauschen, die Wahrscheinlichkeit ermitteln. Die Wahrscheinlichkeit, dass Informationsaustausch ist jedoch gleich 3 oder mehr Nachbarn. Der Algorithmus fest, wenn Informationen ausgetauscht werden soll:
for (int j = 0; j < numRoaches; ++j) {
if (j == idx) continue;
if (effectiveNeighbors == 0) continue;
double prob = rnd.NextDouble();
if (prob > A[effectiveNeighbors - 1]) continue;
...
Die aktuelle günstig wird mit allen anderen Roaches verglichen. Verfügt das aktuelle günstig Nachbarn ist keine Informationsaustausch. Weist der aktuellen günstig auf eine oder mehrere Nachbarn, dient das ein Array von Wahrscheinlichkeiten zu entscheiden, ob Informationen ausgetauscht werden soll. Weiter:
double d = distances[idx][j];
if (d < medianDist) { // a neighbor
if (curr.error < herd[j].error) { // curr better than [j]
for (int p = 0; p < dim; ++p) {
herd[j].groupBestPos[p] = curr.personalBestPos[p];
curr.groupBestPos[p] = curr.personalBestPos[p];
}
}
...
Tritt zwischen benachbarten Roaches wird Gruppe optimale Position und zugeordneten Fehler besser von den beiden Roaches in der schlechter günstig kopiert. Die zweite Verzweigung des Codes Exchange Informationen ist:
...
else { // [j] is better than curr
for (int p = 0; p < dim; ++p) {
curr.groupBestPos[p] = herd[j].personalBestPos[p];
herd[j].groupBestPos[p] = herd[j].personalBestPos[p];
}
}
} // If a neighbor
} // j, each neighbor
Nach dem Austausch von Informationen zwischen benachbarten Roaches durchgeführt wird, verschiebt die aktuelle günstig ist es nicht viel. Der erste Teil des Verschiebens ist die neue Geschwindigkeit der aktuellen günstig zu berechnen:
if (curr.hunger < tHunger) {
for (int p = 0; p < dim; ++p)
curr.velocity[p] = (C0 * curr.velocity[p]) +
(C1 * rnd.NextDouble() * (curr.personalBestPos[p] -
curr.position[p])) +
(C1 * rnd.NextDouble() * (curr.groupBestPos[p] -
curr.position[p]));
Die neue Geschwindigkeit besteht aus drei Komponenten. Die erste Komponente ist die alten Geschwindigkeit, die auch als Trägheit Particle Swarm Terminologie bezeichnet wird. Trägheit fungiert, um ein Verschieben in die gleiche Richtung günstig zu halten. Die zweite Komponente ist die günstig bekannteste Position den Begriff kognitiven bezeichnet. Die "kognitive" Komponente verhindert, dass ein günstig auf fehlerhafte Positionen verschieben. Die dritte Komponente ist die bekannteste Position der günstig Nachbarn. Diese Komponente mehr oder weniger für RIO eindeutig und nicht über einen standardmäßigen Namen. Dieser dritte Begriff fungiert, um Gruppen mit Roaches zusammenzuhalten.
Nach die Geschwindigkeit der aktuellen günstig berechnet wurde, wird die günstig verschoben:
for (int p = 0; p < dim; ++p)
curr.position[p] = curr.position[p] + curr.velocity[p];
double e = Error(curr.position);
curr.error = e;
Nachdem der aktuelle günstig verschoben wurde, wird die neue Position überprüft, um festzustellen, ob es sich um eine neue am besten für die günstig ist:
if (curr.error < curr.personalBestErr) {
curr.personalBestErr = curr.error;
for (int p = 0; p < dim; ++p)
curr.personalBestPos[p] = curr.position[p];
}
Als Nächstes wird die neue Position überprüft, um festzustellen, ob eine neue globale am besten ist, und der Hunger Indikator wird erhöht:
if (curr.error < bestError) {
bestError = curr.error;
for (int p = 0; p < dim; ++p)
bestPosition[p] = curr.position[p];
}
++curr.hunger;
} // If not hungry
Jede günstig Schleife endet mit dem Umgang mit leistungsstarken Roaches:
else { // Roach is hungry
{
herd[idx] = new Roach(dim, minX, maxX, tHunger, t);
}
} // j each roach
Wenn eine günstig Hunger Zähler den tHunger Schwellenwert ist, wird die günstig an ein neues, zufälliges verschoben. Nachdem alle Roaches verarbeitet wurden, beendet der Algorithmus wird überprüft, ob es eine globale erlöschen dauert die Hauptschleife Leistungsindikator erhöht und die optimale Position gefunden, indem alle günstig zurückgeben:
if (t > 0 && t % extinction == 0) { // Extinction?
Console.WriteLine("Mass extinction at t = " +
t.ToString().PadLeft(6));
for (int i = 0; i < numRoaches; ++i)
herd[i] = new Roach(dim, minX, maxX, tHunger, i);
}
++t;
} // Main while loop
return bestPosition;
} // Solve
Beachten Sie, dass der Algorithmus in einer Methode namens SolveRastrigin statt eines allgemeineren z. B. lösen enthalten ist. Die Idee dabei ist, dass RIO ist wirklich eine metaheuristik, anstatt ein vorschreibender Algorithmus und muss angepasst werden, um beliebige Minimierungsproblem Sie lösen möchten, ausschlaggebend.
Die Hilfsmethoden
SolveRastrigin-Methode ruft die Hilfsmethoden Entfernung, Fehler und mischen. Hilfsmethode Abstand gibt den euklidischen Abstand (Quadratwurzel der Summe der quadrierten Term Unterschiede):
static double Distance(double[] pos1, double[] pos2)
{
double sum = 0.0;
for (int i = 0; i < pos1.Length; ++i)
sum += (pos1[i] - pos2[i]) * (pos1[i] - pos2[i]);
return Math.Sqrt(sum);
}
Hilfsmethode Fehler gibt das Quadrat der Differenz zwischen den berechneten Wert Rastrigins-Funktion auf einem bestimmten günstig Position X und dem tatsächlichen Mindestwert 0 (null) zurück:
public static double Error(double[] x)
{
double trueMin = 0.0; double rastrigin = 0.0;
for (int i = 0; i < x.Length; ++i) {
double xi = x[i];
rastrigin += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
}
return (rastrigin - trueMin) * (rastrigin - trueMin);
}
Shuffle-Methode legt die Reihenfolge der Werte in einem Array mit dem Mini Fisher-Yates-Algorithmus, zufällig fest:
static void Shuffle(int[] indices, int seed)
{
Random rnd = new Random(seed);
for (int i = 0; i < indices.Length; ++i) {
int r = rnd.Next(i, indices.Length);
int tmp = indices[r]; indices[r] = indices[i];
indices[i] = tmp;
}
}
Die ursprüngliche Version Research RIO nicht zufällig die Verarbeitungsreihenfolge günstig, aber ich habe festgestellt, dass dieser Ansatz fast immer die Richtigkeit der Biografie Inspirierte Optimierungsalgorithmen verbessert.
Ein paar Kommentare
Also, wie effektive günstig Inspirierte Optimierung im Vergleich zu anderen Methoden numerische Optimierung? Basierend auf einige begrenzte Experimente, die ich ausgeführt habe, RIO scheint besser als andere Algorithmen Benchmark-Probleme zu lösen, aber auf andere Probleme schwächer wird. Abschließend RIO ist, zwar keine fantastische neue allgemeine Optimierungsalgorithmus Zusage verfügt über und kann für bestimmte spezifische Minimierungsprobleme hilfreich sein. Vergewissern Sie sich, günstig internen Netzwerk herstellten Optimierung hat und eine der meisten ungewöhnlichen Namen aller Computer Science.
Dr. James McCaffrey ist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.
Dank den folgenden technischen Experten von Microsoft für die Überprüfung dieses Artikels: Todd Bello, Marciano Moreno Diaz Covarrubias und Alisson Sol