Dieser Artikel wurde maschinell übersetzt.

Testlauf

Fireworks-Algorithmusoptimierung

James McCaffrey

Laden Sie die Codebeispiele herunter

Viele Maschinelles Lernen Software Systeme verwenden Numerische Optimierungsverfahren. Zum Beispiel in die logistische Regression Einstufung ist Schulung die Klassifikator der Prozess finden Sie eine Reihe von Werten für die Gewichte, die input-Variablen zugeordnet, so dass die berechneten Ausgabewerte für eine Auflistung von Trainingsdaten, eng die Variablenwerte bekannte Ausgabe übereinstimmen. Mit anderen Worten, das Ziel ist, zur Optimierung (minimieren) der Fehler zwischen berechnet und Ausgabewerte gewünscht.

Es gibt viele unterschiedliche numerische Optimierungsalgorithmen. Back-Propagation basiert auf klassischen Kalkül Techniken und wird oft mit neuronalen Netzen. Particle Swarm Optimization imitiert Gruppenverhalten wie die Scharen von Vögeln. Evolutionärer Algorithmus Optimierung, eine Form des genetischen Algorithmus Optimierung, Modelle der biologischen Prozesse der Chromosom-Replikation.

Dieser Artikel beschreibt eine relativ neue (Erstveröffentlichung im Jahr 2010) Optimierungstechnik namens Feuerwerk Algorithmus Optimierung (FAO). Die Technik nicht explizit model oder das Verhalten von Feuerwerkskörpern zu imitieren, aber wenn der Algorithmus visuell angezeigt wird, ähnelt das resultierende Bild die Geometrie der explodierenden Feuerwerkskörper.

Der beste Weg, um zu sehen, wohin dieses Artikels und bekommen eine Vorstellung davon, was FAO ist, ist ein Blick auf das Demoprogramm in Abbildung 1. Das Demoprogramm soll FAO verwenden, um den Mindestwert des Ackley Funktion mit 10 Variablen zu finden. Ackley Funktion ist eine standard-Benchmark zur Bewertung der Wirksamkeit von numerischen Optimierungsalgorithmen. Die Demoversion hat einen minimalen Wert von 0.0 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0) liegt. Ackley Funktion ist schwierig, weil es viele lokale minimale Lösungen, die Suchalgorithmen auffangen kann hat, bevor die ein globales Minimum zu finden. Zeigt ein Diagramm der Ackleys Funktion von zwei Variablen Abbildung 2.

Abbildung 1 Feuerwerk Algorithmus Optimierung in Aktion

Abbildung 2 Ackley-Funktion von zwei Variablen

Das Demoprogramm legt die Anzahl von Feuerwerkskörpern bis 5. Mehr Feuerwerk erhöhen die Chance auf eine echte optimale Lösung, auf Kosten der Leistung. FAO, funktioniert in der Regel gut mit 3 bis 10 Feuerwerk. FAO ist ein iterativer Prozess und erfordert eine maximale Schleife Zählerwert. Eine Zählervariable der Schleife in der Maschine lernen Optimierung ist oft benannte "Epoche" und die Demo wird der maximalen Wert auf 1.000 Iterationen. Das ist ein bisschen klein, für Demo-Zwecke bestimmt und in realistischen Szenarien, Werte von 10.000 bis 100.000 sind typisch.

In der Demo führen in Abbildung 1, der beste (kleinste) Fehler zugeordnet die beste Position gefunden, so weit ist jeder 100 Epochen angezeigt. Beachten Sie, dass die FAO beginnt sehr schnell konvergieren. Nach 1.000 Epochen, die beste Position gefunden ist (0,034 0,098 0,003 0,132-0.054 0,181-0.018 0,051 0,004-0.023) und der damit verbundenen Fehler ist 0,41. Wenn die maximale Anzahl der Epochen auf 10.000 erhöht wird, wird FAO in der Tat die optimale Lösung finden. FAO, ist nicht wie die meisten numerischen Optimierungsalgorithmen, garantiert eine optimale Lösung in realistischen Szenarien wo nicht die optimale Lösung bekannt ist.

Dieser Artikel setzt voraus, Sie haben zumindest fortgeschrittene Programmierkenntnisse, aber nicht annehmen, dass Sie wissen nichts über Numerische Optimierungsverfahren oder die FAO. Das Demoprogramm ist codiert mit c# sollte nicht, aber Sie allzu große Schwierigkeiten, die Umgestaltung des Codes in eine andere Sprache wie JavaScript oder Python.

Der Demo-Code ist ein bisschen zu lang, in seiner Gesamtheit zu präsentieren, aber der vollständige Quellcode ist verfügbar in den Codedownload zu diesem Artikel. Der Demo-Code hat die meisten normalen Fehlerüberprüfung entfernt, die wichtigsten Ideen, die so klar wie möglich und die Größe des Codes klein zu halten.

Allgemeine Programmstruktur

Die gesamte Programmstruktur mit einigen geringfügigen Änderungen platzsparend, präsentiert sich in Abbildung 3. Um die Demo zu erstellen, ich Visual Studio gestartet und erstellt eine neue C#-Konsolenanwendung mit dem Namen Fireworks­Algorithmus. Die Demo hat keine bedeutenden .NET-Abhängigkeiten, damit aktuelle Version des Visual Studio funktioniert.

Abbildung 3 Allgemeine Programmstruktur

using System;
using System.Collections.Generic;
namespace FireworksAlgorithm
{
  class FireworksProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin fireworks algorithm demo\n");
      Console.WriteLine("Goal is to solve Ackley's function");
      Console.WriteLine("Function has min value = 0.0 at (0, .. ))");
      int dim = 10;
      int n = 5;    // Number of fireworks
      int maxEpochs = 10000;
      Console.WriteLine("\nSetting Ackley's dimension to " + dim);
      Console.WriteLine("Setting number fireworks to " + n);
      Console.WriteLine("Setting maxEpochs to " + maxEpochs);
      Console.WriteLine("\nBegin algorithm\n");
      double[] bestPosition = Solve(dim, n, maxEpochs);
      Console.WriteLine("\nAlgorithm complete");
      Console.WriteLine("\nBest solution found: ");
      for (int i = 0; i < dim; ++i)
        Console.Write(bestPosition[i].ToString("F3") + " ");
      Console.WriteLine();
      double error = Error(bestPosition);
      Console.WriteLine("\nError of best solution found = " +
        error.ToString("F5"));
      Console.WriteLine("\nEnd fireworks algorithm demo\n");
      Console.ReadLine();
    } // Main
    public static double Error(double[] position) { . . }
    public static double[] Solve(int dim, int n, int maxEpochs) { . . }
    private static int[] PickDimensions(int dim, int z, int seed) { . . }
    private static double YMax(Info[] fireworks) { . . }
    private static double YMin(Info[] fireworks) { . . }
    private static int[] NumberSparks(Info[] fireworks, int m,
      double a, double b) { . . }
    private static double[] Amplitudes(Info[] fireworks, int A,
      int epoch, int maxEpochs, double minX, double maxX) { . . }
    private static double MinAmplitude(int epoch, int maxEpochs,
      double minX, double maxX) { . . }
    private static void AddGaussianSparks(Info[] fireworks,
      List<Info>[] sparksList, int dim, int mHat, int epoch, double minX,
      double maxX, double[] bestPosition, ref double bestError, Random rnd)
  }
  public class Info
  {
    public double[] position;
    public double error;
  }
} // ns

Nach der Vorlagencode in den Visual Studio -Editor geladen, umbenannt, im Projektmappen-Explorer Fenster ich Datei Program.cs automatisch in die aussagekräftigeren FireworksProgram.cs und Visual Studio umbenannt Klasse Programm für mich. An der Spitze des Quellcodes löschte ich alle using-Anweisungen, die auf nicht benötigte Namespaces verwiesen, so dass nur die Verweise auf System und Collections.Generic.

Ich codiert die Demo mit einer Static-Methode-Ansatz als eine Objekt-orientierte Programmierung (OOP)-Ansatz. Die Demo hat die Steuerlogik in der Main-Methode, die zwei öffentliche Methoden, Probleme und Fehler nennt. Die wesentlichen aufrufenden Anweisungen sind:

int dim = 10;
int n = 5;
int maxEpochs = 1000;
double[] bestPosition = Solve(dim, n, maxEpochs)
double error = Error(bestPosition);

Die Variable Dim hält die Anzahl der Dimensionen des Problems. Im Falle der Maschine lernen Ausbildung wäre dies normalerweise die Anzahl der Modell-Gewichte zu bestimmen. Variable n ist die Anzahl von Feuerwerkskörpern. Ich verwende so weit wie möglich die eher knappen Variablennamen, z. B. n, die in die Forschungsarbeiten auf FAO verwendet werden, so dass Sie die Papiere leichter als Ressource verwenden können. Die FAO-Technik enthält Methode lösen. Fehler-Methode akzeptiert eine Position (ein Array von 10 Werten), berechnet den Wert der Ackley Funktion für diese Werte und gibt den Durchschnitt der Summe der quadrierten Differenzen zwischen den bekannten Minimum 0,0 und die berechneten Ausgaben zurück.

Das Demoprogramm hat eine Utility-Klasse mit dem Namen Info, dass Encap­Sulates eine Position und seiner zugehörigen Fehlermeldungen. Die Klasse hat keinen zugeordneten Methoden, z. B. einen expliziten Konstruktor, um es einfacher für Sie, gestalten Sie den Demo-Code, um Sprachen mit eingeschränkter OOP-Unterstützung machen.

Verständnis des Algorithmus

Der Feuerwerk-Algorithmus Prozess wird dargestellt in der Grafik in Abbildung 4. Das Bild stellt ein vereinfachtes Pseudo-Minimierung Problem, nicht die Ackley Funktion der Demo-Programm. Das Ziel des Pseudo-Problems ist eine willkürliche Funktion zu minimieren, die hat zwei input-Variablen, X und Y, wo die Funktion einen minimalen Wert hat von 0.0 liegt bei X = 0 und Y = 0.

Abbildung 4 der Fireworks-Algorithmus

Das Bild im Abbildung 4 drei Feuerwerk verwendet. Jedes Feuerwerk hat so genannte Funken. Es gibt zwei Arten von Funken, regelmäßige und Gauß. Abbildung 5 zeigt den Feuerwerk-Algorithmus in Pseudocode sehr hochrangigen.

Abbildung 5 der Fireworks-Algorithmus in hochrangigen Pseudocode

initialize 3 fireworks to random positions
loop until done
  for each firework
    calculate the amplitude of the firework
    calculate the number of regular sparks
    generate the regular sparks
  end for
  generate special Gaussian sparks
  evaluate each spark
  from the list of sparks,
    select 3 to act as positions of new fireworks
  create 3 new fireworks
end loop
return the position of the best spark found

Für das Bild in Abbildung 4, die Positionen der drei Feuerwerk werden durch die farbigen Punkt-Marker bei angegeben (-6, 2), (3, 4) und (3,-3). Beachten Sie, dass das erste Feuerwerk das Schlimmste ist, weil es am weitesten weg von die Zielposition des ist (0, 0) und die dritte Feuerwerk das beste ist, weil es am nächsten ist. Die Amplituden sind durch die gestrichelte Kreise um jedes Feuerwerk gekennzeichnet. Gute Feuerwerk haben kleinere Amplituden und schlechte Feuerwerk haben größere Amplituden.

Jedes Feuerwerk wird eine unterschiedliche Anzahl von regulären (nicht-Gaussian) Funken erzeugen. Schlechte Feuerwerk erzeugt weniger Funken als gute Feuerwerk. In Abbildung 4, Feuerwerk [0] generiert drei Funken, Feuerwerk [1] generiert vier Funken und Feuerwerk [2] erzeugt fünf Funken. Jede reguläre Funke wird sich in seiner übergeordneten Feuerwerk Amplitude befinden. Da gute Feuerwerk kleine Amplitude und relativ viele Funken haben, konzentriert sich die Algorithmus-Suche in der Nähe von guten Feuerwerk. Schlechte Feuerwerk sollte nicht gänzlich vernachlässigt werden, weil sie zu einer optimalen Lösung führen könnte, die sich außerhalb des Bereichs der aktuellen Feuerwerk befindet. Die Gaußschen Funken entstehen so, dass sie neigen dazu, sich zwischen ein Feuerwerk und die bekannteste Position Funken bei der Suche gefunden werden.

Nachdem alle reguläre und Gaußsche Funken erzeugt wurden, wird jede ausgewertet. Neue Feuerwerk für die nächste Runde von Explosionen werden aus den aktuellen Sparks ausgewählt. Die Position des besten Zündfunkens wird beibehalten, als einer der neuen Feuerwerk, Suche in guten Lagen zu intensivieren. Die Position des der schlimmsten Funke wird beibehalten, um Erhaltung der Suche Vielfalt und verhindern, dass des Algorithmus schnell stürzt auf eine Lösung, die möglicherweise nicht optimal. Die Positionen der verbleibenden Feuerwerkskörper, nur ein Feuerwerk im einfachen Beispiel in Abbildung 4, sind aus der aktuellen Funken nach dem Zufallsprinzip ausgewählt.

Das Verfahren zur Generierung von Feuerwerk und dann Funken wird durchlaufen, wenn einige stoppen-Bedingung erfüllt ist. Die anhalten-Bedingung ist nur eine maximale Schleife Zählerwert bei der Demo-Programm. Wenn FAO für Machine Learning Training verwenden, kann die Bedingung stoppen auch ein Fehlerschwellenwert enthalten, so dass Fehler einige kleine angegebenen Wert unterschreitet, von denen abhängt, das besondere Problem gelöst, die Verarbeitungsschleife beendet.

Implementieren des Fireworks-Algorithmus

Die Definition der Methode Solve beginnt mit:

public static double[] Solve(int dim, int n, int maxEpochs)
{
  int m = n * 10;
  int mHat = 5;
  double a = 0.04;
  double b = 0.8;
  int A = 40;
  double minX = -10.0;
  double maxX = 10.0;
...

Variable m ist die Gesamtzahl der regulären Funken, der das n Feuerwerk zugeteilt werden. Variable mHat (so genannt, da Studien drüber ein kleingeschriebenes m mit einem Karat verwenden) ist die Anzahl der speziellen Gauß Funken um zu erzeugen. Variablen a und b die minimale und maximale Anzahl der Funken für jede besondere Feuerwerk steuern. Variable A ist die maximale Amplitude für jedes Feuerwerk. Variablen MinX und MaxX halten die kleinsten und größten Werte für jeden einzelnen Wert in ein Informationsobjekt-Stellung-Array.

-Methode lösen erstellt n ersten Feuerwerk, etwa so:

Random rnd = new Random(3);
Info[] fireworks = new Info[n];
for (int i = 0; i < n; ++i)
{
  fireworks[i] = new Info();
  fireworks[i].position = new double[dim];
  for (int j = 0; j < dim; ++j)
    fireworks[i].position[j] = (maxX - minX) 
      * rnd.NextDouble() + minX;
  fireworks[i].error = Error(fireworks[i].position);
}

Random-Objekt Rnd ist zunächst einen Seed-Wert von 3 verwenden, nur, weil dieser Wert eine repräsentative Demo laufen gab. Jeder der n Feuerwerk werden als Info-Objekte in einem Array gespeichert. Der Initialisierungscode wählt zufällige Werte zwischen MinX und MaxX für jede Zelle im Array Position. Für einige spezifische Maschine Lernszenarien Training ist es vorteilhafter, das erste Feuerwerk zu initialisieren, so sind sie weit voneinander.

Dieser Position verbundenen Fehler-Methode lösen weiterhin durch die Festlegung von Variablen, um die beste Position, die von jedem Funken gefunden zu halten Im Gegensatz zu Feuerwerkskörper, die eine feste Anzahl haben, variiert die Anzahl von Funken pro Feuerwerk in jeder Iteration der Schleife wichtigsten Verarbeitung also Funken in ein Array, anstatt eine List-Auflistung gespeichert sind:

double[] bestPosition = new double[dim];
for (int k = 0; k < dim; ++k)
  bestPosition[k] = fireworks[0].position[k];
double bestError = fireworks[0].error; // arbitrary
List<Info>[] sparksList = new List<Info>[n];
for (int i = 0; i < n; ++i)
  sparksList[i] = new List<Info>();

Die wichtigsten Verarbeitungsschleife beginnt:

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % 100 == 0) // Show progress every 100 iterations
  {
    Console.Write("epoch = " + epoch);
    Console.WriteLine(" error at best known position = " +
      bestError.ToString("F4"));
  }
...

Hier wird die Fortschritte jeder 100 Epochen angezeigt. Vielleicht möchten erwägen, Sie übergeben eine boolesches Flag-Variable mit dem Namen "Fortschritt" zu steuern, ob Statusmeldungen angezeigt werden:

int[] numberSparks = NumberSparks(fireworks, m, a, b);
double[] amplitudes = 
  Amplitudes(fireworks, A, epoch, maxEpochs, minX, maxX);
for (int i = 0; i < n; ++i)
  sparksList[i].Clear(); // Number of sparks changed

Als nächstes wird die Anzahl der Funken für jedes Feuerwerk und die maximale Amplitude für jedes Feuerwerk, mit Hilfsmethoden NumberSparks und Amplituden berechnet werden. Die Anzahl der Funken für ein Feuerwerk ist proportional zu den Fehler, das Feuerwerk, sodass gute Feuerwerk einen größeren Anteil der insgesamt regelmäßig Funken m empfangen. Ebenso ist jeder Amplitude proportional zu den Fehler, so dass gute Feuerwerk kleinere Amplituden.

Als nächstes wird jeder Funke instanziiert:

for (int i = 0; i < n; ++i)
{
  double amp = amplitudes[i]; // Amplitude for curr firework
  int ns = numberSparks[i];   // Number of sparks for curr firework
  for (int j = 0; j < ns; ++j) // Each spark for curr firework
  {
    Info spark = new Info(); // A spark has a position and error
    spark.position = new double[dim]; // Allocate space (ctor doesn't)
    for (int k = 0; k < dim; ++k) // Spark position based on its parent firework
      spark.position[k] = fireworks[i].position[k];

Ein Funke Position basiert auf seiner übergeordneten Feuerwerk Position. Als nächstes, ein paar (Z) der Dimensionen des Arrays Position nach dem Zufallsprinzip ausgewählt sind, und eine zufällige Verschiebung wird in das Array Position hinzugefügt:

int z = (int)Math.Round(dim * rnd.NextDouble());
int[] dimensions = PickDimensions(dim, z, epoch);
for (int ii = 0; ii < dimensions.Length; ++ii)
{
  double h = amp * 2 * rnd.NextDouble() - 1;
  int k = dimensions[ii]; // convenience
    spark.position[k] += h; // displace from parent
  if (spark.position[k] < minX || spark.position[k] > maxX)
    spark.position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
spark.error = Error(spar.position);
sparksList[i].Add(spark);

Nach dem Generieren eines Funken, prüft die Methode lösen um festzustellen, ob der neue Funke die beste Position hat bisher gefunden:

if (spark.error < bestError)
    {
      bestError = spark.error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = spark.position[k];
    }
  } // Each new regular spark
} // Each firework

Nächste, spezielle Gaußsche Funken werden generiert:

AddGaussianSparks(fireworks, sparksList, dim, mHat,
  epoch, minX, maxX, bestPosition, ref bestError, rnd);

Hilfsmethode AddGaussianSparks generiert spezielle Funken, so dass ihre Positionen sind in der Regel zwischen einem zufällig ausgewählten Feuerwerk und die bekannteste Position liegen. -Methode lösen schließt mit der Suche nach der beste und schlechteste Funken erzeugt und mit ihren Positionen für zwei der neuen Feuerwerk für die nächste Iteration. Die verbleibenden n-2-Feuerwerk werden mit zufällig ausgewählten Funken erstellt:

...
    // Find best, worst spark
    // Create 2 new fireworks
    // Create remaining n-2 fireworks
    ++epoch;
  } // main loop
  return bestPosition;
} // Solve

Finden Sie in den Codedownload Implementierungsdetails.

Ein paar Anmerkungen

Das ursprüngliche Papier, das den Feuerwerk-Algorithmus dargestellt ist "Feuerwerk Algorithmus für die Optimierung," von Y. Tan und Y. Zhu (2010). Das Papier enthielt mehrere Störungen und Faktoren, die den Algorithmus unpraktisch für realen Optimierung vorgenommen. Diese Mängel wurden schnell von anderen Forschern festgestellt. Mein Artikel basiert hauptsächlich auf die 2013 Forschungsarbeit "Fireworks-Algorithmus verbessert," von S. Zheng, A. Janecek und Y. Tan. Beide Papiere finden Sie an mehreren Stellen im Internet. Ich habe einige Vereinfachungen und kleinere Änderungen an den Algorithmen dargestellt in beiden Studien gemacht. Meiner Meinung nach gibt es nicht genug Forschungsergebnisse noch die Frage zu beantworten ob Feuerwerk Optimierung ist besser oder schlechter als andere Optimierungsalgorithmen. Aber es ist sicher interessant.

---

Dr. James McCaffrey arbeitet für Microsoft Research in Redmond, Wash. Er arbeitet an verschiedenen Microsoft-Produkten wie Internet Explorer und Bing. Sie erreichen Dr. McCaffrey unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Todd Bello, Kenneth Griffin, Yong Liu, Brian Mellinger und Esin Saka