Cet article a fait l'objet d'une traduction automatique.

Série de tests

Optimisation du vieillissement bactérien

James McCaffrey

Télécharger l'exemple de code

Optimisation de nourriture bactérienne (BFO) est une technique fascinante d'intelligence artificielle (IA) qui peut être utilisée pour trouver des solutions aux problèmes extrêmement difficiles, voire impossibles de maximisation ou minimisation numériques approximatives. La version du BFO je décris dans cet article est basée sur le livre de 2002, « Biomimétisme de bactérienne nourriture pour distribué Optimisation et contrôle, » par Dr. Kevin Passino. (Ce document se trouve via une recherche sur Internet, mais l'abonnement est requis.) BFO est une technique probabiliste qui modélise le comportement de recherche de nourriture et de reproduction des bactéries courantes telles qu'e. coli afin de résoudre les problèmes d'optimisation numérique où il n'y a aucune approche déterministe efficace. La meilleure façon pour vous d'obtenir une sensation pour ce qui est BFO et de voir où je suis dirigé dans cet article est d'examiner Figure 1 et Figure 2.

Figure 1 le problème de la fonction Rastrigin

La figure 2 à l'aide d'optimisation nourriture bactérienne

La figure 1 est un graphe de la fonction Rastrigin, qui est souvent utilisé comme un problème de norme de référence pour tester l'efficacité des algorithmes d'optimisation. Le but est de trouver les valeurs de x et y qui réduisent au minimum la fonction. Vous pouvez voir qu'il y a plusieurs vallées, qui sont des solutions minima locaux. Cependant, il y a seulement une solution globale à x = 0,0 et y = 0,0 où la valeur de la fonction est 0,0.

La figure 2 est une capture d'écran de BFO pour tenter de résoudre la fonction Rastrigin. Le programme définit plusieurs paramètres, notamment le nombre de bactéries simulées (100 dans cet exemple). Chaque bactérie a un poste qui représente une solution possible. Au départ, toutes les bactéries sont définies sur des positions aléatoires. Chaque position a un coût associé qui représente la valeur de la fonction Rastrigin. Comme la boucle de traitement principale s'exécute, différentes bactéries trouvent successivement les meilleures solutions. À la fin du traitement, la meilleure solution trouvée est de 0,0002 lorsque x =-0.0010 et y = 0,0005 — très proche mais pas tout à fait la solution optimale.

Dans le reste de cet article, je vais expliquer en détail l'algorithme BFO et vous guiderai dans le programme en cours d'exécution Figure 2. J'ai codé le programme de démonstration en c#, mais vous devriez être capable de s'adapter facilement le code présenté ici dans une autre langue tel que Visual Basic.NET ou Windows PowerShell. Le code source complet du programme est disponible à archive.msdn.microsoft.com/mag201203TestRun. Cet article suppose que vous avez intermédiaires ou avancées de codage des compétences avec un langage procédural modern mais n'est pas assumer que vous en savez quelque chose sur BFO ou techniques connexes de AI.

Comportement réel de bactéries

Bactéries comme e. coli est parmi les organismes les plus prospères de la planète. Les bactéries ont des appendices semi-rigides appelés flagelles. Lorsque tous les flagelles tournent dans le sens antihoraire, un effet de l'hélice est créé et une bactérie va nager dans une direction rectiligne plus ou moins.

Les bactéries ont tendance à nager lorsqu'ils vous améliorer dans un certain sens, comme lors de la recherche un gradient des nutriments augmentant, par exemple. Lorsque tous les flagelles tournent dans le sens des aiguilles d'une montre, une bactérie va tomber rapidement et point dans une nouvelle direction. Les bactéries ont tendance à tomber lorsqu'ils rencontrent une substance nocive ou lorsqu'ils sont dans un dégradé qui ne s'améliore pas. Les bactéries se reproduisent toutes les 20 minutes ou par division asexuée en deux filles identiques. Bactéries saines ont tendance à se reproduire plus de bactéries moins sains.

Structure globale du programme

La structure globale du programme pour la démo BFO est répertoriée dans Figure 3.

Figure 3 Structure BFO programme global

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

J'ai utilisé Visual Studio pour créer une application de console c# nommée BacterialForagingOptimization. J'ai renommé le fichier Program.cs à BacterialForagingOptimizationProgram.cs et supprimé tout modèle-généré à l'aide des déclarations sauf pour la référence à l'espace de noms System.

J'ai déclaré un objet aléatoire de classe-portée nommé aléatoire ; BFO est un algorithme probabiliste, comme vous le verrez sous peu. À l'intérieur de la méthode Main, j'ai déclaré plusieurs variables clés. Variable dim est le nombre de dimensions dans le problème. Parce que le but de cet exemple est de trouver x et y pour la fonction Rastrigin, j'ai défini dim à 2. Les variables minValue et maxValue établissent des limites arbitraires de x et de y. Variable s est le nombre de bactéries. J'ai utilisé les noms de variables légèrement peu descriptifs tels que s et Nc parce que ce sont les noms utilisés dans l'article de recherche, donc vous pouvez plus facilement utilisent cet article comme une référence.

Nc variable est le nombre d'étapes chimiotactiques soi-disant. Vous pouvez considérer cela comme un compteur qui représente la durée de vie de chaque bactérie. Variables Ns est le nombre maximal de fois où une bactérie va nager dans la même direction. RN variable est le nombre d'étapes de la reproduction. Vous pouvez considérer cela comme le nombre de générations de bactéries. Ned variable est le nombre d'étapes de dispersion. De temps en temps l'algorithme BFO disperse aléatoirement certaines bactéries nouveaux postes, et modéliser les effets de l'environnement externe sur les bactéries réels. Ped variable est la probabilité d'une bactérie particulière étant dispersée. Ci variable est la longueur de la base de la natation pour chaque bactérie. Lors de la baignade, les bactéries seront déplaceront plus Ci en une seule étape. Variable t est un compteur de temps pour suivre les progrès BFO. BFO étant relativement nouveau, très peu est connu sur les effets d'en utilisant différentes valeurs pour les paramètres BFO.

Le traitement d'algorithme BFO principal se compose de plusieurs boucles imbriquées. Contrairement à la plupart des algorithmes d'IA comme les algorithmes génétiques qui sont contrôlés par un compteur de temps unique, BFO est contrôlée par plusieurs compteurs de boucle.

Le programme utilise une fonction de coût statique. C'est la fonction que vous essayez de réduire au minimum ou maximum. Dans cet exemple, le coût fonction est simplement la fonction Rastrigin. L'entrée est un tableau de double qui représente la position d'une bactérie, qui à son tour représente une solution possible. Dans cet exemple, la fonction de coût est définie comme :

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;

Vous pouvez trouver plus d'informations sur la fonction Rastrigin en faisant une recherche sur Internet, mais le point est que la fonction de coût accepte la position d'une bactérie et renvoie la valeur que vous essayez de réduire au minimum ou maximum.

Les Classes de la colonie et la bactérie

Le programme BFO définit une classe colonie, qui représente une collection de bactéries, avec une classe imbriquée de bactérie qui définit une bactérie individuelle. La classe imbriquée de la bactérie est répertoriée dans Figure 4.

Figure 4 classe de la bactérie

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;
  }
}

Bactérie de la classe dérive de l'interface IComparable afin que les deux objets de la bactérie peuvent être triées par leur état de santé lorsqu'ils déterminent les bactéries survivent à la génération suivante.

Le champ position représente une solution. Le champ de coût est le coût associé à la position. PrevCost champ est le coût associé à la position précédente d'une bactérie ; Cela permet une bactérie savoir si elle s'améliore ou non, et donc si elle doit nager ou tumble. Le domaine de la santé est la somme des coûts cumulés d'une bactérie pendant la durée de vie de la bactérie. Parce que le but est de réduire les coûts, les petites valeurs de santé sont mieux que grandes valeurs.

Le constructeur de la bactérie Initialise un objet de bactérie à une position aléatoire. Le champ de coût n'est pas explicitement défini par le constructeur. La méthode CompareTo ordres objets de bactérie de santé plus petite à la plus grande santé.

Figure 5 montre la classe simple de la colonie.

Figure 5 classe de la colonie

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>
  {
    // ...
}
}

La classe de la colonie est essentiellement une collection d'objets de la bactérie. Le constructeur de la colonie crée une collection de bactérie où chaque bactérie est assignée une position au hasard en appelant le constructeur de la bactérie.

L'algorithme de

Après avoir configuré les BFO variables s et Nc, l'algorithme BFO Initialise la colonie de bactéries comme suit :

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;
}
...

Parce que la fonction de coût est externe à la colonie, le coût pour chaque objet de la bactérie est défini à l'extérieur du constructeur de la colonie à l'aide de la fonction de coût.

Après l'initialisation, la bactérie meilleure dans la colonie est déterminée, gardant à l'esprit que les coûts sont mieux que des coûts plus élevés dans le cas de minimiser la fonction Rastrigin :

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"));
...

Ensuite, les boucles multiples du traitement BFO principaux sont mis en place :

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
      {
        ...

La boucle ultrapériphérique avec l index gère les mesures de dispersion. La prochaine boucle avec indice k gère les étapes de la reproduction. La troisième boucle avec indice j gère les étapes chimiotactiques qui représentent la durée de vie de chaque bactérie. À l'intérieur de la boucle chimiotactique, une nouvelle génération de bactéries a été générée, donc la santé de chaque bactérie est réinitialisée à 0. Après la remise à zéro de bactéries santé des valeurs à l'intérieur de la boucle chimiotactique, chaque bactérie atteindre afin de déterminer une nouvelle direction et se déplace ensuite dans la nouvelle direction, comme suit :

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;
}
...

Tout d'abord, pour chaque composant de position de la bactérie actuelle, une valeur aléatoire entre -1,0 et + 1,0 est générée. Ensuite le produit de la racine du vecteur qui en résulte est calculé. Et puis la nouvelle position de la bactérie est calculée en prenant l'ancienne position et en déplaçant une fraction de la valeur de la variable de la Ci.

Après séchage par culbutage, la bactérie actuelle est mise à jour et puis la bactérie est vérifiée pour voir si il trouve une nouvelle solution plue globale :

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);
}
...

Ensuite, la bactérie pénètre dans une boucle de nage où il va nager tant qu'il s'améliore en trouvant une meilleure position dans la même direction :

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
...

M variable est un compteur de nage afin de limiter le nombre maximal de nage consécutives dans le même sens de la valeur dans la variable Ns. Après la natation, le compteur de temps est incrémenté et met fin à la boucle chimiotactique.

À ce stade, toutes les bactéries ont vécu leur durée de vie donnée par Nc et la moitié plus saine de la colonie vivra et mourra la moitié moins saine :

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
...

Parce qu'un objet de bactérie dérive de IComparable, la méthode Array.Sort triera automatiquement la santé plus petit (plus petit est mieux) pour la santé plus grande donc les meilleures bactéries sont dans les cellules S/2 gauche du tableau de la colonie. La moitié moindre de bactéries dans les cellules de droite de la colonie sont effectivement tué en copiant les données de la moitié du meilleur de la gamme de bactéries dans la moitié droite plus faible. Notez que ceci implique que le nombre total de bactéries, S, doit être un nombre uniforme divisible par 2.

À ce stade, les boucles chimiotactiques et reproduction ont fini, donc l'algorithme BFO entre dans la phase de dispersion :

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
...

Chaque bactérie est examiné. Une valeur aléatoire est générée et comparée aux Ped variable afin de déterminer si la bactérie actuelle est déplacée vers un emplacement aléatoire. Si une bactérie est dispersée en fait, il est vérifié pour voir si il trouve un nouveau poste de meilleur mondial par pur hasard.

À ce stade, toutes les boucles ont été exécutés, et l'algorithme BFO affiche la meilleure solution trouvée à l'aide d'une méthode définie par programme d'assistance nommée ShowVector :

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
...

Quel est le Point ?

BFO est une approche relativement nouvelle de trouver des solutions à des problèmes d'optimisation numérique qui ne peut pas être gérées à l'aide de techniques mathématiques traditionnelles approximatives. À mon avis, BFO est une alternative aux algorithmes génétiques et l'optimisation de l'essaim de particules. Il n'y a guère de recherche pour répondre à la question du BFO combien efficace est ou n'est pas.

Comment BFO peut-être être utilisée ? Il y a beaucoup de possibilités liées aux tests logiciels et également à l'optimisation en général. Par exemple, imaginez que vous essayez de prévoir quelque chose de très difficile, tels que les changements à court terme du prix de certaines actions à la bourse de New York. Recueillir des données historiques et de venir avec quelques équation mathématique complexe qui concerne vos données boursières, mais vous devez déterminer les paramètres de votre équation. Vous pouvez éventuellement utiliser BFO pour estimer les valeurs de vos paramètres où la fonction de coût est un pourcentage de prédictions erronées faites par votre équation.

BFO est un meta-heuristic, signifie qu'elle est juste un cadre conceptuel qui peut être utilisé pour la conception d'un algorithme spécifique. La version de BFO j'ai présenté ici n'est qu'une des nombreuses possibilités et envisager un point de départ pour l'expérimentation plutôt que le dernier mot sur le sujet. En fait, afin de maintenir la taille de cet article facile à gérer, j'ai enlevé une bactérie essaimage caractéristique qui est présenté dans l'article original de recherche BFO.

Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant à la Microsoft Redmond, Wash., campus de. Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et MSN Search. Dr. McCaffrey est l'auteur de ".NET Test Automation Recipes » (Apress, 2006) et peut être contacté à jammc@microsoft.com.

Merci aux experts techniques suivants d'avoir relu cet article: Paul Koch, Dan Liebling, Anne Loomis Thompson and Shane Williams