Dieser Artikel wurde maschinell übersetzt.

Testlauf

Optimierung der Nahrungssuche von Bakterien

James McCaffrey

Bakterielle Futter Optimierung (BFO) ist eine faszinierende künstliche Intelligenz (KI)-Technik, die verwendet werden kann, um ungefähre Lösungen für äußerst schwierig oder unmöglich numerische Maximierung oder Minimierung Probleme finden. Die Version des BFO, die ich in diesem Artikel beschrieben basiert auf der 2002 Papier, "Biomimicry der bakterielle Futter für verteilt Optimierung und Kontrolle" von Dr. Kevin Passino. (Dieses Papier kann über Internet-Suche gefunden werden, aber Abonnement erforderlich ist.) BFO ist eine probabilistische Technik, die das Essen-sucht und reproduktive Verhalten von gemeinsamen Bakterien wie E. Modelle coli zur numerischen Optimierung Probleme wo es keine effektiver deterministischer Ansatz. Der beste Weg für Sie, um ein Gefühl für das, was BFO ist und zu sehen, wohin ich bin in diesem Artikel ist zu prüfen, Abbildung 1 und Abbildung 2.

Abbildung 1 das Problem der Rastrigin-Funktion

Abbildung 2 mit bakteriellen Futtersuche Optimierung

Abbildung 1 ist ein Graph der Funktion Rastrigin, die oft als ein standard-Benchmark-Problem verwendet wird, um die Wirksamkeit der Optimierungsalgorithmen zu testen. Das Ziel ist, finden die Werte von x und y, die die Funktion zu minimieren. Sie können sehen, dass es viele Täler, die lokalen Minima Lösungen sind. Allerdings gibt es nur eine globale Lösung bei X = 0,0 und y = 0.0, wobei der Wert der Funktion 0.0 ist.

Abbildung 2 ist ein Screenshot des BFO, die Rastrigin-Funktion zu lösen versucht. Das Programm richtet mehrere Parameter, einschließlich der Anzahl der simulierten Bakterien (100 in diesem Beispiel). Jedes Bakterium hat eine Position, die eine mögliche Lösung darstellt. Zunächst werden alle Bakterien auf zufällige Positionen festgelegt. Jede Position hat einen damit verbundenen Kosten, die den Wert der Rastrigin-Funktion darstellt. Während die wichtigsten Verarbeitungsschleife ausgeführt wird, finden verschiedene Bakterien sukzessive bessere Lösungen. Am Ende der Verarbeitung, ist die beste Lösung gefunden 0.0002 wenn X =-0.0010 und y = 0.0005 — sehr nah, aber nicht ganz die optimale Lösung.

Im Rest dieses Artikels ich im Detail erklären, den BFO-Algorithmus und gehen Sie durch das Programm läuft Abbildung 2. Ich codiert das Demoprogramm in c#, aber Sie sollten können leicht präsentierten sich hier in eine andere Sprache wie Visual Basic Code anzupassen.NET oder Windows PowerShell. Dieser Artikel setzt voraus, Sie haben intermediate oder advanced Programmierkenntnisse mit modernen prozedurale Sprache aber nicht davon ausgehen, dass Sie wissen nichts über BFO oder verwandten AI-Techniken.

Echte Bakterien Verhalten

Bakterien wie E. coli gehören zu den erfolgreichsten Organismen auf dem Planeten. Bakterien haben Semi-Rigid Anhängseln Flagellen genannt. Wenn alle Flagellen entgegen dem Uhrzeigersinn drehen, ein Propeller-Effekt entsteht und ein Bakterium wird in eine mehr oder weniger gerade Richtung schwimmen.

Bakterien sind in der Regel zu schwimmen, wenn sie in einem gewissen Sinne, wie Verbesserung sind bei eine zunehmende Nährstoffe Steigung, zum Beispiel zu finden. Wenn alle Flagellen im Uhrzeigersinn drehen, wird ein Bakterium schnell stürzen und in eine neue Richtung weisen. Bakterien neigen zu fallen, wenn eine schädliche Substanz auftreten oder wenn sie in einem Farbverlauf sind, die nicht verbessert. Bakterien vermehren ca. alle 20 Minuten oder so von asexuell Aufteilung in zwei identische Töchter. Gesündere Bakterien eher mehr als weniger gesunden Bakterien zu reproduzieren.

Allgemeine Programmstruktur

Die gesamte Programmstruktur für die BFO-Demo ist in aufgeführten Abbildung 3.

Figure 3 Struktur der insgesamt BFO-Programm

using System;
namespace BacterialForagingOptimization
{
  class BacterialForagingOptimizationProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        int dim = 2;
        double minValue = -5.12;
        double maxValue = 5.12;
        int S = 100;
        int Nc = 20;
        int Ns = 5;
        int Nre = 8;
        int Ned = 4;
        double Ped = 0.25;
        double Ci = 0.05;
        random = new Random(0);
        // Initialize bacteria colony
        // Find best initial cost and position
        int t = 0;
        for (int l = 0; l < Ned; ++l) // Eliminate-disperse loop
        {
          for (int k = 0; k < Nre; ++k) // Reproduce-eliminate loop
          {
            for (int j = 0; j < Nc; ++j) // Chemotactic loop
            {
              // Reset the health of each bacterium to 0.0
              for (int i = 0; i < S; ++i)
              {
                // Process each bacterium
              }
              ++t;
             }
            // Reproduce healthiest bacteria, eliminate other half
          }
          // Eliminate-disperse
        }
        Console.WriteLine("\nBest cost found = " + bestCost.ToString("F4"));
        Console.Write("Best position/solution = ");
        ShowVector(bestPosition);
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main
    static double Cost(double[] position) { ...
}
  }
  public class Colony // Collection of Bacterium
  {
    // ...
public class Bacterium : IComparable<Bacterium>
    {
      // ...
}
  }
} // ns

Ich habe Visual Studio erstellen Sie eine c#-Konsolenanwendung mit dem Namen BacterialForagingOptimization. Ich BacterialForagingOptimizationProgram.cs die Program.cs-Datei umbenannt und gelöscht, alle Vorlage-generated using-Anweisungen außer für den Verweis auf den Namespace System.

Ich erklärte ein Gültigkeitsbereich der Klasse Random-Objekt mit dem Namen zufällig; BFO ist ein probabilistischer Algorithmus, wie Sie bald sehen werden. Innerhalb der Main-Methode deklariert ich mehrere wichtige Variablen. Dim-Variable ist die Anzahl der Dimensionen des Problems. Da das Ziel in diesem Beispiel ist x und y für die Rastrigin-Funktion, eingestellte dim 2. Die Variablen MinValue und MaxValue werden willkürliche Grenze für sowohl x als auch y. Variable s ist die Anzahl der Bakterien. Ich habe etwas nicht beschreibende Variablennamen, wie s und Nc denn diese Namensgebung in der Forschung Artikel, so Sie leichter können sind, dass Artikel als Referenz verwenden.

Variable Nc ist die Anzahl der sogenannten Chemotaktische Schritte. Sie können dies als Zähler vorstellen, die die Lebensdauer der einzelnen Bakterium darstellt. Variable Ns ist die maximale Anzahl von Zeiten, die ein Bakterium, das in die gleiche Richtung schwimmen wird. Variable Nre ist die Anzahl der Vervielfältigung Schritte. Sie können dies als die Anzahl der Generationen von Bakterien vorstellen. Variable Ned ist die Anzahl der Zerstreuung Schritte. Hie und da zerstreut der BFO-Algorithmus zufällig einige Bakterien auf neue Positionen, Modellierung der Auswirkungen der externen Umgebung auf echte Bakterien. Variable Ped ist die Wahrscheinlichkeit, dass ein bestimmtes Bakterium verteilt wird. Variable Ci ist die grundlegende Schwimmen Länge für jedes Bakterium. Beim Schwimmen, werden Bakterien nicht mehr als Ci in jedem einzelnen Schritt bewegen. Variable t ist eine Zeitmarke BFO Fortschritt überwacht. Da BFO relativ neu ist, ist sehr wenig bekannt über die Auswirkungen der Verwendung unterschiedlicher Werte für BFO-Parameter.

Die wichtigste BFO Algorithmus Verarbeitung besteht aus mehreren verschachtelten Schleifen. Im Gegensatz zu den meisten AI-Algorithmen wie z. B. genetische Algorithmen, die ein einziges Mal-Zähler gesteuert werden, wird durch mehrere Schleifenzähler BFO gesteuert.

Das Programm verwendet eine statische Kostenfunktion. Dies ist die Funktion, die Sie versuchen zu minimieren oder maximieren. In diesem Beispiel die Kosten ist die Funktion nur die Rastrigin-Funktion. Die Eingabe ist, dass ein Array von double, ein Bakterium repräsentiert die wiederum eine mögliche Lösung darstellt. In diesem Beispiel wird die Kosten-Funktion folgendermaßen definiert:

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;

Finden Sie weitere Informationen über die Rastrigin-Funktion auf diese Weise eine Internet-Suche, aber der Punkt ist, dass die Kosten-Funktion ein Bakterium Standpunkt akzeptiert und den Wert, den Sie versuchen gibt zu minimieren oder maximieren.

Das Bakterium und die Kolonie Klassen

Das BFO-Programm definiert eine Kolonie-Klasse eine Auflistung von Bakterien stellt, mit einer geschachtelten Bakterium-Klasse, die eine einzelne Bakterium definiert. Die geschachtelte Klasse Bakterium notiert Abbildung 4.

Abbildung 4 die Bakterium-Klasse

public class Bacterium : IComparable<Bacterium>
{
  public double[] position;
  public double cost;
  public double prevCost;
  public double health;
  static Random random = new Random(0);
  public Bacterium(int dim, double minValue, double maxValue)
  {
    this.position = new double[dim];
    for (int p = 0; p < dim; ++p) {
      double x = (maxValue - minValue) * random.NextDouble() + minValue;
      this.position[p] = x;
    }
    this.health = 0.0;
  }
  public override string ToString()
  {
    // See code download
  }
  public int CompareTo(Bacterium other)
  {
    if (this.health < other.health)
      return -1;
    else if (this.health > other.health)
      return 1;
    else
      return 0;
  }
}

Klasse Bakterium wird abgeleitet aus der IComparable-Schnittstelle, sodass zwei Bakterium Objekte durch ihre Gesundheit sortiert werden können, bei der Bestimmung die Bakterien an die nächste Generation überleben werden.

Feld Position stellt eine Lösung dar. Das Kostenfeld sind die Kosten der Position zugeordnet. Feld PrevCost liegen die Kosten eines Bakteriums vorherige Position zugeordnet. Dadurch ist ein Bakterium, das zu wissen, ob es oder nicht besser ist, und deshalb, ob es sollten Schwimmen oder Wäschetrockner. Bereich der Gesundheit ist die Summe der kumulierten Kosten eines Bakteriums während das Bakterium Lebensdauer. Denn das Ziel ist es, Kosten zu minimieren, sind kleine Werte der Gesundheit besser als große Werte.

Der Bakterium-Konstruktor initialisiert ein Bakterium-Objekt an eine zufällige Position. Das Kostenfeld ist nicht explizit durch den Konstruktor festgelegt. Die CompareTo-Methode ordnet Bakterium Objekte aus der kleinsten Gesundheit größten Gesundheit.

Abbildung 5 zeigt die einfache Colony-Klasse.

Abbildung 5 die Colony-Klasse

public class Colony
{
  public Bacterium[] bacteria;
  public Colony(int S, int dim, double minValue, double maxValue)
  {
    this.bacteria = new Bacterium[S];
    for (int i = 0; i < S; ++i)
      bacteria[i] = new Bacterium(dim, minValue, maxValue);
  }
  public override string ToString() { // See code download }
  public class Bacterium : IComparable<Bacterium>
  {
    // ...
}
}

Die Kolonie-Klasse ist im Wesentlichen eine Sammlung von Bakterium-Objekten. Der Kolonie-Konstruktor erstellt eine Auflistung von wo jedes Bakterium eine zufällige Position zugeordnet ist, durch Aufrufen des Konstruktors Bakterium Bakterium.

Der Algorithmus

Nach dem Einrichten der BFO-Variablen wie s und Nc, die BFO-Algorithmus initialisiert die Bakterien-Kolonie etwa so:

Console.WriteLine("\nInitializing bacteria colony");
Colony colony = new Colony(S, dim, minValue, maxValue);
for (int i = 0; i < S; ++i) {
  double cost = Cost(colony.bacteria[i].position);
  colony.bacteria[i].cost = cost;
  colony.bacteria[i].prevCost = cost;
}
...

Da die Kosten-Funktion außerhalb der Kolonie ist, wird die Kosten für jedes Bakterium-Objekt außerhalb der Kolonie-Konstruktor mithilfe der Kostenfunktion festgelegt.

Nach der Initialisierung wird das beste Bakterium in der Kolonie bestimmt, unter Berücksichtigung der Tatsache, dass niedrigere Kosten besser als höhere Kosten bei der Minimierung der Rastrigin-Funktion:

double bestCost = colony.bacteria[0].cost;
int indexOfBest = 0;
for (int i = 0; i < S; ++i) {
  if (colony.bacteria[i].cost < bestCost) {
    bestCost = colony.bacteria[i].cost;
    indexOfBest = i;
  }
}
double[] bestPosition = new double[dim];
colony.bacteria[indexOfBest].position.CopyTo(bestPosition, 0);
Console.WriteLine("\nBest initial cost = " + bestCost.ToString("F4"));
...

Als nächstes werden die mehrere Schleifen der wichtigsten BFO Verarbeitung eingerichtet:

Console.WriteLine("\nEntering main BFO algorithm loop\n");
int t = 0;
for (int l = 0; l < Ned; ++l)
{
  for (int k = 0; k < Nre; ++k)
  {
    for (int j = 0; j < Nc; ++j)
    {
      for (int i = 0; i < S; ++i) { colony.bacteria[i].health = 0.0; }
      for (int i = 0; i < S; ++i) // Each bacterium
      {
        ...

Die äußerste Schleife mit Index l behandelt die Zerstreuung Schritte. Next-Schleife mit Index k behandelt die Vervielfältigung Schritte. Die dritte Schleife mit Index j behandelt die Chemotaktische Schritte, die die Lebensdauer der einzelnen Bakterium darstellen. Innerhalb der Schleife chemotaktische ist eine neue Generation von Bakterien nur erzeugt worden, so dass die Gesundheit jedes Bakterium auf 0 zurückgesetzt wird. Nach dem Zurücksetzen Bakterien Gesundheit Werte innerhalb der chemotaktische Schleife jedes Bakterium stürzt eine neue Richtung zu bestimmen und bewegt sich dann in die neue Richtung, etwa so:

double[] tumble = new double[dim];
for (int p = 0; p < dim; ++p) {
  tumble[p] = 2.0 * random.NextDouble() - 1.0;
}
double rootProduct = 0.0;
for (int p = 0; p < dim; ++p) {
  rootProduct += (tumble[p] * tumble[p]);
}
for (int p = 0; p < dim; ++p) {
  colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
}
...

Zunächst wird für jede Komponente des aktuellen Bakterium Position, ein zufälliger Wert zwischen -1,0 und 1,0 generiert. Dann wird der Stamm-Produkte von den sich ergebenden Vektor berechnet. Und dann die neue Position des Bakteriums wird berechnet, indem die alte Position und Bewegung ein Teil des Wertes der Variablen Ci.

Nach taumelnde, das aktuelle Bakterium wird aktualisiert, und das Bakterium wird dann überprüft, um festzustellen, ob es eine neue globale beste Lösung gefunden:

colony.bacteria[i].prevCost = colony.bacteria[i].cost;
colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].health += colony.bacteria[i].cost;
if (colony.bacteria[i].cost < bestCost) {
  Console.WriteLine("New best solution found by bacteria " + i.ToString()
    + " at time = " + t);
  bestCost = colony.bacteria[i].cost;
  colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
...

Als nächstes kommt das Bakterium Schlinge schwimmen wo wird es in die gleiche Richtung schwimmen, so lange, wie es besser ist, durch eine bessere Position zu finden:

int m = 0;
    while (m < Ns && colony.bacteria[i].cost < colony.bacteria[i].prevCost) {
      ++m;
      for (int p = 0; p < dim; ++p) {
        colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
      }
      colony.bacteria[i].prevCost = colony.bacteria[i].cost;
      colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // while improving
  } // i, each bacterium
  ++t;   // increment the time counter
} // j, chemotactic loop
...

Variable m ist ein Schwimmen, die maximale Anzahl von aufeinander folgenden schwimmt in die gleiche Richtung auf den Wert in Variable Ns zu begrenzen. Nach dem Schwimmen, der Zeit-Zähler wird erhöht und die chemotaktische Schleife beendet.

Zu diesem Zeitpunkt alle Bakterien gelebt haben ihre Lebensdauer von Nc gegeben und die gesündeste Hälfte der Kolonie wird Leben und die wenigsten-gesunde Hälfte wird sterben:

Array.Sort(colony.bacteria);
  for (int left = 0; left < S / 2; ++left) {
    int right = left + S / 2;
    colony.bacteria[left].position.CopyTo(colony.bacteria[right].position, 0);
    colony.bacteria[right].cost = colony.bacteria[left].cost;
    colony.bacteria[right].prevCost = colony.bacteria[left].prevCost;
    colony.bacteria[right].health = colony.bacteria[left].health;
  }
} // k, reproduction loop
...

Da IComparable ein Bakterium-Objekt abgeleitet, die Array.Sort-Methode wird automatisch sortiert vom kleinsten Gesundheit (kleiner ist besser) größte Gesundheit sind die besten Bakterien in den linken S/2 Zellen des Kolonie-Arrays. Die schwächere Hälfte der Bakterien in den richtigen Zellen der Kolonie effektiv durch Kopieren der Daten von der besseren Hälfte des Arrays Bakterien in der schwächeren rechten Hälfte getötet. Beachten Sie, dass dies bedeutet, dass die Gesamtzahl der Bakterien, S, eine Zahl durch 2 teilbar sein sollte.

An diesem Punkt haben die chemotaktischen und Reproduktion Schleifen fertig, so dass der BFO-Algorithmus die Zerstreuung Phase Eintritt:

for (int i = 0; i < S; ++i) {
    double prob = random.NextDouble();
    if (prob < Ped) {
      for (int p = 0; p < dim; ++p) {
        double x = (maxValue - minValue) *
          random.NextDouble() + minValue;
        colony.bacteria[i].position[p] = x;
      }
      double cost = Cost(colony.bacteria[i].position);
      colony.bacteria[i].cost = cost;
      colony.bacteria[i].prevCost = cost;
      colony.bacteria[i].health = 0.0;
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // if (prob < Ped)
  } // for
} // l, elimination-dispersal loop
...

Jedes Bakterium wird untersucht. Ein zufälliger Wert generiert und verglichen, Variable Ped um festzustellen, ob das aktuelle Bakterium in einem zufälligen Ort verschoben werden. Wenn ein Bakterium, das in der Tat verteilt ist, wird es überprüft, um festzustellen, ob es eine neue globale beste Position gefunden durch Zufall.

An dieser Stelle alle Schleifen ausgeführt wurden und der BFO-Algorithmus zeigt die beste Lösung gefunden mit einer Hilfsmethode mit dem Namen ShowVector Programm definiert:

Console.WriteLine("\n\nAll BFO processing complete");
    Console.WriteLine("\nBest cost (minimum function value) found = " +
      bestCost.ToString("F4"));
    Console.Write("Best position/solution = ");
    ShowVector(bestPosition);
    Console.WriteLine("\nEnd BFO demo\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal: " + ex.Message);
  }
} // Main
...

Was ist der Sinn?

BFO ist ein relativ neuer Ansatz um ungefähre Lösungen für numerische Optimierungsprobleme, die nicht mit traditionelle mathematische Techniken verarbeitet werden können.BFO ist meiner Meinung nach eine Alternative zu genetischen Algorithmen und Partikel Schwarm Optimierung.Es gibt wenig Forschungsergebnisse zur Beantwortung der Frage wie effektive BFO ist oder nicht.

Wie kann die BFO werden verwendet?Es gibt viele Möglichkeiten im Zusammenhang mit Software-testen und auch Optimierung im Allgemeinen.Zum Beispiel stellen Sie vor, dass Sie versuchen, etwas sehr schwieriges, wie kurzfristige Änderungen der Preise für einige Lager an der New York Stock Exchange vorherzusagen.Sie sammeln einige historischen Daten und kommen mit einigen komplexe mathematische Gleichung Aktienkurs, die Ihre eingegebenen Daten betrifft, aber Sie müssen die Parameter Ihrer Gleichung bestimmen.Potenziell können BFO Sie um die Werte der Parameter zu schätzen wo die Kostenfunktion wird als Prozentsatz der falsche Vorhersagen durch Ihre Gleichung.

BFO ist ein meta-heuristic, d. h. es ist nur einen konzeptionellen Rahmen, die verwendet werden kann, um einen bestimmten Algorithmus zu entwerfen.Die Version des BFO, die ich hier vorgestellt habe ist nur eine von vielen Möglichkeiten und sollte als Ausgangspunkt für Experimente eher als das letzte Wort zum Thema.In der Tat, um die Größe dieses Artikels überschaubar zu halten, entfernt habe ich Bakterien schwärmen Feature, das in der ursprünglichen BFO Forschung Artikel dargestellt ist.

Dr. James McCaffrey arbeitet für Volt Information Sciences Inc., wo er technische Schulungen für Softwareentwickler bei der Microsoft in Redmond, Washington, Campus. Er war an verschiedenen Microsoft-Produkten, einschließlich Internet Explorer und MSN Search. Dr. McCaffrey ist Autor von ".NET Test Automation Recipes"(Apress, 2006) und kann erreicht werden unter jammc@microsoft.com.

Dank der folgenden technischen Experten für die Überprüfung dieses Artikels: Paul Koch, Dan Liebling, Anne Loomis Thompson und Shane Williams