Dieser Artikel wurde maschinell übersetzt.

Test Run

Multi-Swarm Optimization

James McCaffrey

Multi-Schwarm Optimierung (MSO) ist eine Technik zur Abschätzung der Lösung schwierig oder unmöglich numerische Probleme.Es ist eine Variation des Particle Swarm Optimization (siehe meinen Artikel zu diesem Thema bei msdn.microsoft.com/magazine/hh335067).Regelmäßige Partikel Schwarm Optimierungsmodelle Beflockung Verhalten, z. B., die in Gruppen von Vögeln und Fischschwärme gesehen.MSO erweitert Particle Swarm Optimization mithilfe mehrere Schwärme von simulierten Teilchen und keinen einzigen Schwarm.

MSO kann auf mehrere Machine-Learning-Szenarien, z. B. schätzen der Gewichte und Bias-Werte für ein künstliches neurales Netz oder schätzen die Gewichte der schwachen Lernenden Ensemble Einstufung und Vorhersage angewendet werden.MSO ist eine Meta heuristische, d.h. die Technik ist wirklich eine Reihe von Design-Prinzipien und Richtlinien, die verwendet werden können, um einen bestimmten Algorithmus, um ein bestimmtes Optimierungsproblem gelöst zu konstruieren.

Eine gute Möglichkeit, Multi-Schwarm Optimierung zu verstehen ist zu prüfen, das Demoprogramm in Abbildung 1 und das Diagramm in der Abbildung 2.Das Demoprogramm ist die Lösung für ein standard-Benchmark-Numerische Optimierungsverfahren-Problem Rastrigins-Funktion schätzen.Ziel ist es, die Werte von X 0 und X 1, die die Funktion zu minimieren:

Abbildung 1 Multi Schwarm Optimierung Demo

Abbildung 2 Rastrigin-Funktion

Die Funktion hat eine bekannte Lösung von f = 0.0 Wenn x 0 = 0.0 und x 1 = 0.0, so ist die Verwendung von MSO wirklich notwendig, in dieser Situation nicht.Das Diagramm in der Abbildung 2 zeigt Rastrigins-Funktion.Wenn die Funktion viele Gipfel hat und Täler, falsche Lösungen darstellt, gibt es in der Mitte des Bildes nur ein globales Minimum.Mehrere schließen-aber-nicht-ganz-Lösungen der Rastrigins Funktion sind bewusst und Ärger für Optimierungsalgorithmen.

Das Demoprogramm in Abbildung 1 beginnt durch die Einrichtung einige Eingabeparameter für die MSO-Algorithmus.Es gibt drei Schwärme, und jeder Schwarm hat vier Teilchen.In die meisten numerischen Optimierungsprobleme ist die Palette der möglichen Werte in gewisser Weise begrenzt.Hier ist der Suchraum zunächst beschränkt auf x-Werte zwischen 100,0 und +100.0.

Das Demoprogramm Initialisiert jedes der 12 Teilchen zufällig (X 0, x 1) Werte.Jedes Paar von Werten stellt eine Partikel-Position, die auch als eine mögliche Lösung interpretiert werden kann.Der Wert der Rastrigin Funktion auf jede Position wird bezeichnet die Kosten für die Position zu behaupten, dass das Ziel, die Funktion zu minimieren.Nach der Initialisierung ist der beste Partikel (diejenige mit der geringste Aufwand) nullbasiert Partikel 0 in Schwarm 2.Diese Partikel hat Position [-40.57, 28,54] und damit verbundenen Kosten 2498.93.

Multi-Schwarm Optimierung ist ein iterativer Prozess.Das Demoprogramm legt einen willkürlichen maximale Schleife-Wert von 150.Der MSO-Algorithmus sucht nach besseren Lösungen, die Verfolgung der der besten Lösung, die von jedem der 12 Teilchen gefunden.Am Ende von 150 Iterationen, die beste Lösung gefunden wurde, f = 0,000043 at x 0 = 0.0001 x 1 = 0,0004, die sehr nah an aber nicht ganz die tatsächliche Lösung ist.Das Demoprogramm finden Sie in der Tat die tatsächliche Lösung indem die Variable MaxLoop auf 500, aber es ist zu beachten, dass in möglichst realistische Problemszenarien nicht Sie wissen wenn MSO die optimale Lösung gefunden hat.

Dieser Artikel setzt voraus, Sie haben mindestens Mittelstufe Programmierkenntnisse, aber nicht annehmen, dass Sie wissen nichts über Multi-Schwarm Optimierung.Das Demoprogramm ist in c# codiert aber Sie sollte nicht zu viel Mühe für die Umgestaltung in eine andere Sprache.Um die Größe des kleinen Codes und die wichtigsten Ideen zu halten habe ich klar, die meisten normalen Fehlerüberprüfung aus dem Demo-Code entfernt.Die Demo ist zu lang, um in seiner Gesamtheit in diesem Artikel präsentieren, sondern der gesamten Quellcode ist verfügbar unter archive.msdn.microsoft.com/mag201309TestRun.

Allgemeine Programmstruktur

Die Struktur des Programms Demo mit einigen geringfügigen Änderungen und die meisten der WriteLine-Anweisungen entfernt, präsentiert sich in Abbildung 3.

Abbildung 3 Multi-Schwarm Demo Programmstruktur

using System;
namespace MultiSwarm
{
  class MultiSwarmProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine(
          "\nBegin Multiple Particle Swarm optimization demo\n");
        int dim = 2;
        double minX = -100.0;
        double maxX = 100.0;
        int numParticles = 4; // Particles in each swarm
        int numSwarms = 3; // Swarms in multi-swarm
        Multiswarm ms = new Multiswarm(numSwarms, numParticles, 
          dim, minX, maxX);
        Console.WriteLine("\nInitial multiswarm:");
        Console.WriteLine(ms.ToString());
        int maxLoop = 150;
        ms.Solve(maxLoop);
        Console.WriteLine("\nFinal multiswarm:");
        Console.WriteLine(ms.ToString());
        Console.WriteLine("\nBest solution found = " +
          ms.bestMultiCost.ToString("F6"));
        Console.Write("at x0 = " + ms.bestMultiPos[0].ToString("F4"));
        Console.WriteLine(", x1 = " 
          + ms.bestMultiPos[1].ToString("F4"));
        Console.WriteLine("\nEnd demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    }
    public static double Cost(double[] position) { . 
          .
          }
  } // Program
  public class Particle { . 
     .
      }
  public class Swarm { . 
      . 
      }
  public class Multiswarm { . 
        .
       }
} // ns

Um das Demoprogramm zu erstellen habe ich Visual Studio 2012. Die Demo hat keine erheblichen Abhängigkeiten, und jede Version von Visual Studio sollte funktionieren. Ich wählte die C#-Konsole-Anwendung-Vorlage und mit dem Namen des Projekts MultiSwarm. Nachdem Visual Studio die Codevorlage geladen, umbenannt Fenster ich umbenannt in MultiSwarmProgram.cs und Visual Studio automatisch die Program.cs-Datei im Projektmappen-Explorer die Program-Klasse für mich. An der Spitze des Quellcodes, die ich gelöscht nicht alle Namespaceverweise, so dass nur den Verweis auf den Namespace System benötigte.

Das Demoprogramm definiert eine Public-Bereich Kosten-Methode, die Rastrigins Funktion ist:

public static double Cost(double[] position)
{
  double result = 0.0;
  for (int i = 0; i < position.Length; ++i) {
    double xi = position[i];
    result += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
  }
  return result;
}

Die Kosten-Methode akzeptiert einen einzelnes Array-Parameter, der ein Teilchen repräsentiert die eine mögliche Lösung ist. In die meisten Machine-Learning Szenarien der Kostenfunktion, die Sie versuchen zu minimieren stellt irgendeine Form von Fehler und erfordert zusätzliche Parameter wie eine Ausbildung-Datenquelle. Der Kostenfunktion ist in der Regel den Leistungsengpass für MSO, so dass Sie es so effizient wie möglich zu programmieren sollte.

Die Multiswarm-Klasse kapselt den MSO-Algorithmus. Klassen-Partikel und Schwarm sind Hilfsklassen für Klasse Multiswarm. Neuartiger Bauweise in Sprachen, die geschachtelte Klassendefinitionen zu unterstützen ist Klassen Teilchen und Schwarm innerhalb Multiswarm-Klasse definiert.

Das Demoprogramm beginnt durch die Einrichtung von fünf Parameter:

int dim = 2;
double minX = -100.0;
double maxX = 100.0;
int numParticles = 4;
int numSwarms = 3;

Variable dim repräsentiert die Anzahl der Dimensionen des Problems gelöst werden. Da Rastrigins Funktion X 0 und X 1 akzeptiert, wird der Wert von Dim auf 2 festgelegt. Multi-Schwarm Optimierung eignet sich gut für Probleme mit einer beliebigen Anzahl von Dimensionen. Schränken die Suche auf eine begrenzte Anzahl von Werten, Variablen MinX und MaxX. Die Werte für MinX und MaxX variiert von Problem zu Problem. Variable NumParticles definiert die Anzahl der Partikel, die in jedem Schwarm sind. Variable NumSwarms definiert die Gesamtzahl der Schwärme. Größere Werte von NumParticles und NumSwarms produzieren im allgemeinen genauere Lösungen auf Kosten der Leistung.

Als nächstes wird das primäre Multi-Schwarm-Objekt instanziiert und die MSO Algorithmus zu lösen heißt:

Multiswarm ms = new Multiswarm(numSwarms, numParticles, 
  dim, minX, maxX);
Console.WriteLine("\nInitial multiswarm:");
Console.WriteLine(ms.ToString());
int maxLoop = 150;
ms.Solve(maxLoop);

Die Demo Ruft eine Auflistung von Teilchen einen "Schwarm" und eine Sammlung von Schwärmen ein "Multi-Schwarm." Statt dieses Benennungsschema ruft einige Forschungsliteratur, eine Sammlung von Teilchen ein "Sub-Schwarm" und eine Sammlung von Sub Schwärme ein "Schwarm." Das Multiswarm-Objekt wird mit den zuvor definierten Eingabeparametern instanziiert. Variable MaxLoop enthält die maximale Anzahl der Zeiten, die die Problemlösung Algorithmus Hauptschleife durchlaufen wird. Im Allgemeinen werden höhere Werte der MaxLoop genauere Lösungen auf Kosten der Leistung produzieren.

Die Solve-Methode sucht iterativ die beste Lösung für Rastrigins-Funktion. Beachten Sie, dass der Kostenfunktion nach außen auf das Multiswarm-Objekt definiert ist. In den meisten Fällen ist MSO-Code ein Softwaresystem integriert anstatt als eine Klassenbibliothek DLL, die erfordert, Sie übergeben der Kostenfunktion in das Multiswarm-Objekt (über ein Delegate, zum Beispiel) oder verwenden Sie einen Interface-Design-Ansatz dass definieren Sie einen Programmierung Vertrag implementiert.

Nachdem die Solve-Methode die Ausführung abgeschlossen ist, wird der endgültige Status des Multiswarm-Objekts angezeigt, und die beste Lösung gefunden durch jedes Partikel in jedem Schwarm in der Multi-Schwarm explizit angezeigt:

Console.WriteLine("\nFinal multiswarm:");
Console.WriteLine(ms.ToString());
Console.WriteLine("\nBest solution found = " +
 ms.bestMultiCost.ToString("F6"));
Console.Write("at x0 = " + ms.bestMultiPos[0].ToString("F4"));
Console.WriteLine(", x1 = " + ms.bestMultiPos[1].ToString("F4"));

Partikel

Die Partikel-Klasse verfügt über sechs Mitgliedern:

static Random ran = new Random(0);
public double[] position;
public double[] velocity;
public double cost;
public double[] bestPartPos;
public double bestPartCost;

Ich bevorzuge zum öffentlichen Bereich der Einfachheit halber verwenden, aber Sie möchten verwenden privaten Bereich zusammen mit Get und set-Methoden. Das Random-Objekt wird vom Konstruktor verwendet, um ein Partikel-Objekt an eine zufällige Position zu initialisieren. Das Array mit dem Namen Position repräsentiert die Position eines Partikels. Array Geschwindigkeit stellt die Geschwindigkeit und die Richtung für ein Teilchen. Nehmen wir beispielsweise an, dass ein Teilchen an Position [12.0, 24,0] und die Geschwindigkeit ist [5.0, 0.0]. Dies kann dahingehend interpretiert werden, dass das Partikel während der nächsten Zeitintervall 5,0 Einheiten entlang der X-0 bewegt Dimension und 0,0 Einheiten entlang der X 1 Dimension. Nachdem das Teilchen bewegt hat, wird seine neue Position [17,0, 24.0].

Variable Kosten enthält den Wert der der Kostenfunktion an der aktuellen Position. Variable BestPartCost enthält den besten (kleinsten) Kostenwert, den ein Teilchen jemals erlebt, und Variable BestPartPos ist die Position, wo die bekannteste Kosten gefunden wurde.

Der Partikel-Konstruktor wird definiert, Abbildung 4.

Abbildung 4 der Partikel-Konstruktor

public Particle(int dim, double minX, double maxX)
{
  position = new double[dim];
  velocity = new double[dim];
  bestPartPos = new double[dim];
  for (int i = 0; i < dim; ++i) {
    position[i] = (maxX - minX) * ran.NextDouble() + minX;
    velocity[i] = (maxX - minX) * ran.NextDouble() + minX;
  }
  cost = MultiSwarmProgram.Cost(position);
  bestPartCost = cost;
  Array.Copy(position, bestPartPos, dim);
}

Der Konstruktor reserviert Speicherplatz für die Positions-, Geschwindigkeits- und BestPartPos Arrays, basierend auf der Anzahl der Dimensionen des Problems. Jede Position und Geschwindigkeit Zelle erhält einen zufälligen Wert zwischen MinX und MaxX. Die Kosten für die Ausgangsposition wird berechnet. Bekannteste Position des Partikels und Kosten werden auf die Ausgangsposition und die Kosten festgelegt.

Ein bedeutender alternativer Ansatz besteht darin, jedes Teilchen nicht zufällige Startpositionen zuordnen. Einige MSO-Forschungsliteratur zufolge Zuweisen von Partikeln in verschiedenen schwärmen in verschiedene Bereiche des den Suchraum zu einem zufälligen-Zuordnung-Ansatz überlegen ist. Zum Beispiel hätten Sie zwei Schwärme mit 10 Teilchen, konnte die 10 Teilchen in der ersten Schwarm Positionen mit X-Werte zwischen 100,0 0,0 und die 10 Partikel in der zweiten Schwarm an Positionen mit X-Werte zwischen 0,0 und +100.0 zugewiesen werden. Ich bin nicht ganz überzeugt von dieser Forschungsergebnisse und einfache zufällige Partikel Position Zuordnung hat gut für mich in der Praxis gearbeitet.

Schwärme

Ein Schwarm ist eine Sammlung von Teilchen. Die Schwarm-Klasse besteht aus drei Mitgliedern:

public Particle[] particles;
public double[] bestSwarmPos;
public double bestSwarmCost;

Benennung kann ein bisschen schwierig mit MSO. Ich nenne das Array von Objekten der Partikel in der Schwarm-Klasse als "Teilchen", aber vielleicht möchten stattdessen den Namen "Schwarm" zu verwenden. Member Variable BestSwarmCost hält die beste (kleinste) Kosten, die während der Ausführung des Algorithmus von keinem der Partikel in der Schwarm gefunden. Array BestSwarmPos hält die Position, wo diese beste Schwarm-Mitglied Kosten gefunden wurde.

Der Schwarm-Konstruktor wird angezeigt, Abbildung 5.

Abbildung 5 der Schwarm-Konstruktor

public Swarm(int numParticles, int dim, double minX, double maxX)
{
  bestSwarmCost = double.MaxValue;
  bestSwarmPos = new double[dim];
  particles = new Particle[numParticles];
  for (int i = 0; i < particles.Length; ++i) {
    particles[i] = new Particle(dim, minX, maxX);
    if (particles[i].cost < bestSwarmCost) {
      bestSwarmCost = particles[i].cost;
      Array.Copy(particles[i].position, bestSwarmPos, dim);
    }
  }
}

Der Schwarm-Konstruktor reserviert Speicherplatz, und ruft dann die Partikel-Konstruktor NumParticles Zeiten, um zufällige Position Teilchen zu erzeugen. Jedes Teilchen erstellt wird, wird geprüft, um festzustellen, ob es die besten Kosten eines der Teilchen in der Schwarm hat.

Die Multiswarm-Klasse

Ein Multi-Schwarm ist eine Sammlung von Schwärmen. Die Klasse die obersten Ebene Multiswarm hat sieben Mitglieder:

public Swarm[] swarms;
public double[] bestMultiPos;
public double bestMultiCost;
public int dim;
public double minX;
public double maxX;
static Random ran = new Random(0);

Array-Schwärme hält jedes Schwarm-Objekt, von denen jede eine Auflistung von Objekten der Partikel ist. Also stellt Schwärme [2] .particles [3] .position [0] den X 0-Wert für Partikel 3 in Schwarm 2.

Member Variable BestMultiCost enthält die besten Kosten jedes Partikel in jedem Schwarm während der Ausführung des Algorithmus gefunden. Array BestMultiPos hält die zugehörige Position, wo die besten weltweite Kosten gefunden wurde. Member-Variablen dim, MinX und MaxX für Bequemlichkeit gespeichert werden, damit ihre Werte von Klassenmethoden verwendet werden können, ohne als Parameter übergeben wird.

Rückruf, dass Klasse Teilchen ein Random-Objekt mit dem Namen lief, die verwendet wird, um zufällige Startpositionen zu generieren. Klasse Multiswarm hat ein anderes Random-Objekt, das durch die MSO-Algorithmus, zum Einfügen von Pseudo-Zufallszahlen Verhalten während des Prozesses zu lösen verwendet wird.

Der Multiswarm-Konstruktor wird aufgeführt, Abbildung 6.

Abbildung 6 Multiswarm Konstruktor

public Multiswarm(int numSwarms, int numParticles, int dim,
  double minX, double maxX)
{
  swarms = new Swarm[numSwarms];
  bestMultiPos = new double[dim];
  bestMultiCost = double.MaxValue;
  this.dim = dim;
  this.minX = minX;
  this.maxX = maxX;
  for (int i = 0; i < numSwarms; ++i)
  {
    swarms[i] = new Swarm(numParticles, dim, minX, maxX);
    if (swarms[i].bestSwarmCost < bestMultiCost)
    {
      bestMultiCost = swarms[i].bestSwarmCost;
      Array.Copy(swarms[i].bestSwarmPos, bestMultiPos, dim);
    }
  }
}

Nach dem Zuweisen von Arrays und speichern Eingabeparameterwerte, ruft den Multiswarm Konstruktor die Schwarm-Konstruktor NumSwarms Zeiten. Jeder Schwarm erstellt wird, wird die besten Kosten für jedes Partikel innerhalb dieser Schwarm überprüft, um festzustellen, ob es ein globales am besten Kosten ist. Wenn ja, werden diese Kosten und seine zugehörigen Position in BestMultiCost und BestMultiPos, gespeichert.

Die MSO-Algorithmus

In sehr hochrangigen Pseudocode ist der grundlegende MSO-Algorithmus:

loop maxLoop times
  for each swarm
    for each particle
      compute new velocity
      use velocity to update position
      check if a new best cost has been found
    end for
  end for
end loop

Vorgang für der Schlüssel in MSO ist eine neue Geschwindigkeit für ein Teilchen computing. Eine neue Geschwindigkeit für ein bestimmtes Teilchen wird durch die aktuelle Geschwindigkeit, die aktuelle Position, die bekannteste Position des Partikels, die bekannteste Position jedes Partikel in der gleichen Schwarm als das Teilchen und die bekannteste Position jedes Partikel in jedem Schwarm beeinflusst. Math ausgedrückt ist die neue Geschwindigkeit:

v(t+1) = w * v(t) +
         (c1 * r1) * (p(t) - x(t)) +
         (c2 * r2) * (s(t) - x(t)) +
         (c3 * r3) * (m(t) - x(t))

Nachdem eine neue Geschwindigkeit berechnet worden ist, ist ein Teilchen Neupositionierung:

x(t+1) = x(t) + v(t+1)

Geduld mit mir für einen Moment. Die Berechnung ist viel einfacher, als es zunächst scheint. Der Begriff v(t+1) bedeutet die Geschwindigkeit zum Zeitpunkt t + 1, mit anderen Worten, die neue Geschwindigkeit. Begriff v(t) ist die aktuelle Geschwindigkeit. Begriff x(t) wird die aktuelle Position. Beachten Sie, dass x und v sind in Fett, was darauf hinweist wie Vektoren sind [12,0, 25,0] anstatt Einzelwerte.

Begriff p(t) ist ein Teilchen bekannteste Position. Begriff s(t) ist die beste Position der jedes Partikel in der Partikel Schwarm. Begriff m(t) ist die beste Position der jedes Partikel in jedem Schwarm.

Begriff w ist eine Konstante, die den Trägheit-Faktor genannt. Begriffe-c1, c2 und c3 sind Konstanten, die eine maximale Änderung für jede Komponente der neuen Geschwindigkeit zu schaffen. Begriffe-r1, r2 und r3 sind zufällige Werte zwischen 0 und 1, die eine Randomisierung Wirkung jedes Velocity Update bereitstellen.

Die neue Velocity-Berechnung wird wahrscheinlich am besten durch Beispiel erklärt. Angenommen, ein Teilchen zurzeit ist [12,0, 24.0] und seine aktuelle Geschwindigkeit ist [1,0, 3,0]. Außerdem ist die bekannteste Position des Partikels [8.0, 10.0], ist die bekannteste Position jedes Partikel in den Schwarm [7.0, 9.0], und ist die bekannteste Position jedes Partikel in jedem Schwarm [5.0, 6.0]. Und annehmen, ständige w Wert 0.7 hat, Konstanten c1 und c2 beide 1.4 sind und Konstante c3 0.4 ist. Schließlich angenommen, zufällige Werte r1, r2 und r3 sind alle 0,2.

Die neue Geschwindigkeit des Teilchens wird angezeigt, Abbildung 7.

Abbildung 7 die neue Geschwindigkeit eines Teilchens Computing

v(t+1) = 0.7         * [-1.0, -3.0] +
         (1.4 * 0.2) * [8.0, 10.0] - [12.0, 24.0] +
         (1.4 * 0.2) * [7.0, 9.0] - [12.0, 24.0] +
         (0.4 * 0.2) * [5.0, 6.0] - [12.0, 24.0]
       = 0.7 * [-1.0, -3.0] +
         0.3 * [-4.0, -14.0] +
         0.3 * [-5.0, -15.0] +
         0.1 * [-7.0, -18.0]
       = [-0.7, -2.1] +
         [-1.2, -4.2] +
         [-1.5, -4.5] +
         [-0.7, -1.8]
       = [-4.1, -12.6]

Und ja, nach Abbildung 7, neue Position des Partikels ist:

x(t+1) = [12.0, 24.0] + [-4.1, -12.6]
       = [7.9, 11.4]

Vorausgesetzt, die optimale Lösung ist [0.0, 0.0], wie der Fall mit Rastrigins Funktion ist, feststellen, dass das Teilchen von seiner ursprünglichen Position an eine neue Position verschoben wurde, die näher an die optimale Lösung.

Der Begriff Trägheit im v(t+1) fördert ein Teilchen weiterhin in die aktuelle Richtung. Der Begriff p(t) fördert eine Partikel bis zu seiner historisch bekannteste Position bewegen. Der Begriff s(t) fördert ein Teilchen in Richtung der bekanntesten Position wurde von keinem der Partikel Schwarm Kameraden zu verschieben. Der Begriff m(t) fördert ein Teilchen auf die bekannteste Position jedes Partikel in jedem Schwarm gefunden.

Konstanten c1, c2 und c3 werden die kognitiven, sozialen und globalen Gewichte bezeichnet. Diese Konstanten zusammen mit Zufallswerten r1, r2 und r3 und die Trägheit Gewicht w, bestimmen, wie viel jeder Begriff die Bewegung eines Teilchens beeinflusst. Nachforschungen in regelmäßigen Partikel Schwarm Optimierung schlägt angemessene Werte für w, c1, und c2 sind 0.729, 1.49445 und 1.49445, beziehungsweise. Es gibt wenig Forschung auf die c3-Konstante in MSO, aber ich verwende in der Regel 0.3645 (die Hälfte des Gewichts Trägheit) und dies hat funktioniert gut für mich in der Praxis.

Tod und Einwanderung

Es gibt mehrere faszinierende Möglichkeiten den grundlegenden MSO-Algorithmus ändern. Eine Möglichkeit ist im Wesentlichen ein zufällig ausgewählter Teilchen hin und wieder zu töten, und dann gebären eines neuen Teilchens. Die Demo-Anwendung verwendet diese Tod-Geburt-Änderung. Die ersten Zeilen der Solve Methode werden angezeigt, Abbildung 8.

Abbildung 8 die ersten Zeilen von die Methode lösen

public void Solve(int maxLoop)
{
  // Assign values to ct, w, c1, c2, c3
  double death = 0.005; ; // Prob of death
  while (ct < maxLoop)
  {
    ++ct;
    for (int i = 0; i < swarms.Length; ++i) {
      for (int j = 0; j < swarms[i].particles.Length; ++j) {
        double p = ran.NextDouble();
        if (p < death)
          swarms[i].particles[j] = new Particle(dim, minX, maxX);
        for (int k = 0; k < dim; ++k) {
...

Die Methode generiert einen zufälligen Wert zwischen 0 und 1 und speichert es in p. Wenn der zufällige Wert kleiner als 0,005 ist, wird das aktuelle Partikel neu instanziiert, durch Aufrufen des Konstruktors Partikel, effektiv töten das aktuelle Teilchen und die Geburt einer neuen Teilchen an einem zufälligen Ort.

Eine weitere Möglichkeit der MSO ist Modell Einwanderung in regelmäßigen Abständen zwei Teilchen in verschiedenen schwärmen und Austausch. Ein Teilchen in der aktuellen Schwarm effektiv wer einwandern darf und einem anderen Teilchen wandert aus der Schwarm. Das Demoprogramm enthält diese Option. Die wichtigste Methode ist:

private void Immigration(int i, int j)
{
  // Swap particle j in swarm i
  // with a random particle in a random swarm
  int otheri = ran.Next(0, swarms.Length);
  int otherj = ran.Next(0, swarms[0].particles.Length);
  Particle tmp = swarms[i].particles[j];
  swarms[i].particles[j] = swarms[otheri].particles[otherj];
  swarms[otheri].particles[otherj] = tmp;
}

Die Methode ist einfach und erlaubt die unerwünschte Möglichkeit, dass ein Teilchen mit sich selbst ausgetauscht werden kann. Das Einwanderung-Feature heißt innerhalb Methode lösen wie folgt:

double immigrate = 0.005;
... 
          double q = ran.NextDouble();
if (q < immigrate)
  Immigration(i, j);

Zusammenfassung

Die Erklärung präsentiert in diesem Artikel und den zugehörigen Codedownload sollte Ihnen eine solide Grundlage für Erfahrungen­Menting mit Multi-Schwarm-Optimierung. Im Vergleich zu regulären Partikel Schwarm Optimierung, Multi-Schwarm Optimierung ist nur etwas komplexer und tendenziell bessere Ergebnisse bringen, wenn es langsamer ist. Meine Erfahrung mit MSO lässt vermuten, dass es tendenziell schwieriger Optimierungsprobleme zu behandeln — mit vielen lokalen Minima — besser als reguläre Partikel Schwarm Optimierung.

MSO ist eine universell einsetzbare numerische Optimierung Meta heuristische und wird normalerweise als Teil eines größeren Computerlernen Szenarios verwendet, um einen Satz von Gewichten zu finden, die irgendeine Art von Fehler-Funktion zu minimieren. MSO kann beispielsweise verwendet werden, um den besten Satz von Gewichten und Bias-Werte für ein neuronales Netz zu finden, Minimierung von Fehlern der Klassifizierung auf eine Reihe von Trainingsdaten durch. Es gibt viele Alternativen, MSO, einschließlich evolutionären Optimierungsalgorithmen (auch genannt reellwertige genetische Algorithmen), bakterielle Futtersuche Optimierung und Amoeba Methodenoptimierung.

Im Vergleich zu den meisten Alternativen allgemeine Numerische Optimierungsverfahren Ansätze, meiner Meinung nach ist der MSO ist einfacher zu implementieren und leichter anpassen. Ein Nachteil der MSO im Vergleich zu einigen Alternativen ist in der Regel gibt es einige Richtlinien für die Auswahl des Wert der MSO-freie Parameter, einschließlich die Trägheit Gewicht Konstanten und die kognitive, soziale und globale Gewicht-Konstanten. Sagte aber, ich bin ein großer Fan von MSO und es hat sehr gut für mich mehrmals als ich brauchte, um eine numerische Optimierungsproblem gelöst in meiner Softwaresysteme durchgeführt.

Dr.James McCaffrey  arbeitet bei Microsoft auf dem Campus in Redmond, Washington. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und MSN Search. Dr. McCaffrey ist der Autor von ".NET Test Automation Recipes" (Rezepte für die .NET-Testautomatisierung, Apress 2006) und kann unter jammc@microsoft.com erreicht werden.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Kirk Olynyk (Microsoft)