Este artículo proviene de un motor de traducción automática.

Ejecución de pruebas

Optimización de la recolección bacteriana

James McCaffrey

Descargar el ejemplo de código

Optimización de forrajeo bacteriana (BFO) es una fascinante técnica de inteligencia artificial (IA) que puede utilizarse para encontrar soluciones aproximadas a extremadamente difíciles o imposibles numéricos maximización o minimización de problemas.La versión de BFO que describo en este artículo se basa en el libro de 2002, "Biomimicry de bacteriana alimentándose de distribuido optimización y Control," por el Dr..Kevin Passino.(Este documento puede encontrarse a través de la búsqueda en Internet, pero se requiere suscripción). BFO es una técnica probabilística que modela el comportamiento buscando comida y reproducción de las bacterias comunes tales como e.coli para resolver problemas de optimización numérica donde no hay ningún efectivo enfoque determinista.La mejor manera para usted para tener una idea de lo que es BFO y ver donde yo estoy encabezada en este artículo es examinar figura 1 y figura 2.

Figura 1 el problema de la función Rastrigin

Figura 2 mediante la optimización de forrajeo bacteriana

Figura 1 es un gráfico de la función Rastrigin, que a menudo se utiliza como un problema de referencia estándar para probar la eficacia de los algoritmos de optimización.El objetivo es encontrar los valores de x e y que minimizan la función.Puede ver que hay muchos valles que son soluciones de mínimos locales.Sin embargo, hay sólo una solución global en x = 0.0 y y = 0.0 donde el valor de la función es 0.0.

Figura 2 es una captura de pantalla de BFO intentando resolver la función Rastrigin.El programa establece varios parámetros, incluido el número de bacterias simulados (100 en este ejemplo).Cada bacteria tiene una posición que representa una posible solución.Inicialmente, todas las bacterias se establecen en posiciones aleatorias.Cada posición tiene un costo asociado que representa el valor de la función Rastrigin.Como se ejecuta el bucle principal de procesamiento, diferentes bacterias encuentran soluciones sucesivamente mejores.Al final del tratamiento, la mejor solución encontrada es 0,0002 cuando x =-0.0010 e y = 0.0005 — muy cerca pero no la solución óptima.

En el resto de este artículo voy a explicar en detalle el algoritmo BFO y guiará a través del programa se muestra que se ejecutan en figura 2.Codifica el programa de demostración en C#, pero usted debe ser capaz de adaptarse fácilmente el código presentado aquí a otro idioma como Visual Basic.NET o Windows PowerShell.El código fuente completo del programa está disponible en archive.msdn.microsoft.com/mag201203TestRun.Este artículo se supone que tienes intermedio o avanzado de habilidades con un lenguaje moderno procedimiento de codificación pero no asume que nada saben sobre BFO o relacionados conexos técnicas de inteligencia artificial.

Comportamiento real de bacterias

Bacterias como e.coli se encuentran entre los organismos más exitosos del planeta.Las bacterias tienen semirrígidos apéndices llamados flagelos.Cuando todos los flagelos giran en sentido antihorario, se crea un efecto de la hélice y una bacteria se nadar en dirección recta más o menos.

Las bacterias tienden a nadar cuando está mejorando en algún sentido, como al encontrar un gradiente creciente de nutrientes, por ejemplo.Cuando todos los flagelos giran en sentido horario, una bacteria secadora rápidamente y apuntan en una dirección nueva.Las bacterias tienden a secadora cuando encuentran una sustancia nociva o cuando están en un degradado que no está mejorando.Reproducción de bacterias sobre cada 20 minutos o dividiendo asexualmente en dos hijas idénticas.Las bacterias saludables tienden a reproducir más bacterias menos saludables.

Estructura general del programa

La estructura general del programa para la demostración BFO cotiza en figura 3.

Figura 3 estructura de programa BFO de General

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

He utilizado Visual Studio para crear una aplicación de consola de C# llamada BacterialForagingOptimization. Cambió el nombre del archivo Program.cs a BacterialForagingOptimizationProgram.cs y eliminado todo plantilla generados mediante declaraciones excepto para la referencia al espacio de nombres System.

Declaró un objeto aleatorio de ámbito de clase el nombre aleatorio; BFO es un algoritmo probabilista, como verá en poco tiempo. Dentro del método Main había declarado varias variables claves. Dim variable es el número de dimensiones del problema. Porque el objetivo de este ejemplo es encontrar x e y para la función Rastrigin, configurar dim a 2. Las variables minValue y maxValue establecen límites arbitrarios para x e y. Variable s es el número de bacterias. Usé ligeramente nondescriptive nombres de variables tales como s y CN porque estos son los nombres utilizados en el artículo de investigación, por lo que más fácilmente se puede utilizan este artículo como referencia.

CN variable es el número de pasos de quimiotaxis llamados. Puede considerar esto como un contador que representa la duración de cada bacteria. Variables Ns es el número máximo de veces que una bacteria se nadar en la misma dirección. Nre variable es el número de pasos de reproducción. Se puede considerar como el número de generaciones de bacterias. Ned variable es el número de pasos de dispersión. Cada algoritmo BFO dispersa aleatoriamente algunas bacterias a nuevas posiciones, los efectos del entorno externo en bacterias reales de modelado. Ped variable es la probabilidad de que una bacteria particular se dispersaron. Ci variable es la longitud de nado básico para cada bacteria. Al nadar, bacterias no moverá IC que supere en ningún paso a paso. Variable t es un contador de tiempo para controlar el progreso BFO. Porque BFO es relativamente nuevo, muy poco se sabe acerca de los efectos de utilizar distintos valores para los parámetros de BFO.

El procesamiento de algoritmo BFO principal consta de varios bucles anidados. A diferencia de la mayoría AI algoritmos como algoritmos genéticos que están controlados por un contador de tiempo único, BFO es controlado por varios contadores de bucle.

El programa utiliza una función estática de costo. Ésta es la función que está intentando minimizar o maximizar. En este ejemplo el costo función es sólo la función de Rastrigin. La entrada es una matriz de doble representa la posición de una bacteria, que a su vez representa una posible solución. En este ejemplo, la función de costo se define como:

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;

Puede encontrar más información acerca de la función Rastrigin haciendo una búsqueda en Internet, pero el punto es que la función de costo acepta la posición de una bacteria y devuelve el valor que intenta minimizar o maximizar.

La bacteria y clases de Colonia

El programa BFO define una clase Colonia, lo que representa una colección de bacterias, con una clase anidada de bacteria que define una bacteria individual. La clase anidada de bacteria cotiza en figura 4.

Figura 4 la clase de bacteria

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

Bacteria de clase se deriva de la interfaz IComparable para que dos objetos de la bacteria pueden ordenarse por su salud, al determinar que las bacterias sobrevivirán a la próxima generación.

El campo posición representa una solución. El campo de costo es el costo asociado con la posición. Campo prevCost es el costo asociado con la posición anterior de una bacteria; Esto permite una bacteria saber si está mejorando o no, y por lo tanto, si debe nadar o secadora. El campo de la salud es la suma de los costos acumulados de una bacteria durante la duración de la vida de la bacteria. Porque el objetivo es minimizar el costo, pequeños valores de salud son mejores que los grandes valores.

El constructor de bacteria Inicializa un objeto de la bacteria a una posición aleatoria. El campo costo no se ha configurado explícitamente por el constructor. El método CompareTo ordena objetos de bacteria más pequeña de salud para la salud más grande.

Figura 5 muestra la clase de Colonia simple.

Figura 5 la clase de Colonia

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 clase de Colonia es esencialmente una colección de objetos de la bacteria. El constructor de Colonia crea una colección de bacteria donde cada bacteria es asignado a una posición aleatoria por llamar al constructor de la bacteria.

El algoritmo

Después de configurar las variables BFO como s y CN, el algoritmo BFO inicializa la colonia de bacterias como tal:

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

Porque la función de costo es externa a la colonia, el costo para cada objeto de bacteria se establece fuera el constructor de Colonia mediante la función de costo.

Después de la inicialización, se determina la bacteria mejor en la colonia, teniendo en cuenta que los costos son mejores que los costos más elevados en el caso de minimizar la función 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"));
...

A continuación, se configuran los múltiples bucles del procesamiento de BFO principal:

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

El bucle exterior con índice l maneja las medidas de dispersión. El siguiente bucle con índice k maneja los pasos de reproducción. El tercer bucle con índice j maneja los pasos quimiotácticos que representan la vida de cada bacteria. Dentro del bucle quimiotáctico, una nueva generación de bacterias se sólo ha generado, por lo que la salud de cada bacteria se restablece a 0. Después de restablecer las bacterias salud valores dentro del bucle quimiotáctico, cada bacteria tumbles para determinar una nueva dirección y, a continuación, se mueve en la nueva dirección, así:

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

En primer lugar, para cada componente de la posición de bacteria actual, se genera un valor aleatorio entre -1,0 y + 1,0. A continuación se calcula el producto de raíz del vector resultante. Y, a continuación, la nueva posición de la bacteria se calcula tomando la posición antigua y moviendo una fracción del valor de la variable de Ci.

Después de volteretas, la bacteria actual se actualiza y, a continuación, la bacteria se comprueba para ver si encuentran una nueva solución global mejor:

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

A continuación, la bacteria entra en un bucle de natación donde se nadar en la misma dirección como está mejorando por encontrar una mejor posición:

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 es un contador de nadar para limitar el número máximo de nada consecutivo en la misma dirección que el valor de la variable Ns. Después de nadar, se incrementa el contador de tiempo y termina el bucle quimiotáctico.

En este momento, todas las bacterias han vivido su vida dada por CN y vivirá la mitad más sana de la colonia y la mitad menos saludable va a morir:

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

Porque un objeto bacteria deriva de IComparable, el método Array.Sort clasificará automáticamente de salud más pequeño (menor es mejor) para la salud más grande por lo que son las bacterias mejores en las células de S/2 izquierdas de la matriz de la colonia. La mitad más débil de la bacteria en las células de la colonia derecha efectivamente mueren copiando los datos de la mitad de la mejor de la matriz de bacterias en la mitad derecha más débil. Observe que esto implica que el número total de bacterias, S, debe ser un número divisible por 2.

En este punto hayan terminado los bucles de quimiotaxis y reproducción, por lo que el algoritmo BFO entra en la fase de dispersión:

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

Se examina cada bacteria. Genera un valor aleatorio y compara Ped variable para determinar si la bacteria actual se moverá a una ubicación aleatoria. Si en realidad se dispersa una bacteria, se comprueba para ver si encuentran una nueva posición mejor global por pura casualidad.

En este punto se han ejecutado todos los bucles y el algoritmo BFO muestra la mejor solución encontrada usando un método de auxiliares definidas por el programa denominado 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
...

¿Cuál es el punto?

BFO es un enfoque relativamente nuevo para encontrar soluciones aproximadas a problemas de optimización numérica que no pueden resolverse mediante las técnicas tradicionales de matemáticas. En mi opinión, BFO es una alternativa a los algoritmos genéticos y optimización de enjambre de partículas. Hay poca evidencia de investigación para responder a la pregunta de cuán eficaz BFO es o no.

¿Cómo podría utilizarse BFO? Hay muchas posibilidades relacionadas con pruebas de software y también a la optimización en general. Por ejemplo, imagine que intenta predecir algo muy difícil, como los cambios a corto plazo en el precio de algunas acciones en la bolsa de valores de Nueva York. Reunir algunos datos históricos y topar con algunas ecuaciones matemáticas complejas que relaciona el precio de las acciones a los datos de entrada, pero es necesario determinar los parámetros de la ecuación. Potencialmente podría utilizar BFO para calcular los valores de los parámetros que la función de costo es un porcentaje de predicciones incorrectas hechas por su ecuación.

BFO es un meta-heuristic, lo que significa que es sólo un marco conceptual que puede utilizarse para el diseño de un algoritmo específico. La versión de BFO que he presentado aquí es sólo una de muchas posibilidades y debe considerarse un punto de partida para la experimentación en lugar de la última palabra sobre el tema. De hecho, a fin de mantener manejable el tamaño de este artículo, me quitaron una bacteria pulula la característica que se presenta en el artículo de investigación original de BFO.

Dr.James McCaffrey trabaja para Volt Information Sciences Inc., donde administra capacitación técnica para ingenieros de software que trabaja en el Microsoft Redmond, Washington, campus. Trabajó en varios productos de Microsoft, Internet Explorer y MSN Search. Dr. McCaffrey es el autor de ".Recetas de automatización de prueba NET"(Apress, 2006) y puede ser contactado en jammc@microsoft.com.

Gracias al siguiente experto técnico por su ayuda en la revisión de este artículo: Paul Koch, Dan Liebling, Anne Loomis Thompson and Shane Williams