Algoritmos naturales

Use algoritmos de colonias de abejas para solucionar problemas imposibles

James McCaffrey

Descargar el ejemplo de código

Los algoritmos de simulación de colonias de abejas mielíferas (SBC) crean modelos del comportamiento de abejas y se pueden usar para descubrir soluciones para problemas de combinatoria difíciles o imposibles. En este artículo, explicaré qué son los algoritmos de SBC, describiré los tipos de problemas que se pueden solucionar usando algoritmos de SBC y presentaré un ejemplo completo, de punta a cabo, que usa un algoritmo de SBC para resolver el problema del viajante.

Una buena manera de acercarse a los algoritmos de SBC y de ver hacia dónde vamos en este artículo es examinar el programa de demostración que se ejecuta en la figura 1. El programa de demostración usa un algoritmo de SBC para analizar un conjunto de 20 ciudades (designados por las letras de la A a la T) para determinar el camino más corto para visitar cada ciudad exactamente una sola vez. Los datos de las ciudades son construcciones artificiales, de manera que la mejor ruta comienza desde la ciudad A y avanza hasta la ciudad T en orden. La mejor ruta tiene un largo de 19,0 unidades.

Figura 1 Demostración de la simulación de colonia de abejas

Tras bambalinas, el algoritmo de SBC crea una instancia de una colmena de 100 abejas simuladas, cada una de las cuales tiene potencialmente una solución aleatoria. En un principio, la mejor de las soluciones aleatorias tenía una extensión de ruta de 95,0 unidades. El algoritmo de SBC entra en un bucle de procesamiento, lo cual se indica en la barra de progreso basada en texto, lo cual simula el comportamiento de las abejas mielíferas comunes en búsqueda de comida. Al final del proceso de SBC, la mejor solución conseguida tiene 16 posiciones de ciudad correcta de 20 y la ruta final tiene una extensión total de 26,5. Cerca, pero no es la solución óptima.

A los algoritmos de SBC frecuentemente se les llama meta heurística, puesto que, más que proporcionar fundamentos de solución altamente detallados, proporcionan un marco general y un conjunto de instrucciones para crear soluciones a problemas. Este artículo presenta un ejemplo de uso de SBC para solucionar un problema específico. En cuanto se comprende cómo se puede usar una SBC para solucionar un problema, se puede adaptar el algoritmo de SBC que se muestra aquí para solucionar sus problemas. Como demostrará este artículo, los algoritmos de SBC son sumamente adecuados para solucionar problemas de combinatoria complejos que no tienen soluciones deterministas prácticas.

Este artículo presupone que cuenta con habilidades de programación de nivel intermedio. El ejemplo en este artículo está codificado usando C#, pero se escribió todo el código de manera que se pueda volver a factorizar como otro lenguaje de programación. Creo que encontrará interesante el artículo y que considerará la habilidad de usar algoritmos de SBC como una adición útil a sus competencias personales.

Sobre las abejas

Las abejas mielíferas comunes, como la Apis mellifera, toman distintos roles dentro de la columna a medida que pasa el tiempo. Una colmena común puede tener entre 5.000 a 20.000 abejas. Las abejas adultas (de 20 a 40 días de edad) usualmente se transforman en recolectoras. Las abejas recolectoras generalmente ocupan una de tres funciones: recolectoras activas, recolectoras exploradoras y recolectoras inactivas.

Las abejas recolectoras activas viajan a una fuente de alimento, examinan las fuente de alimento cercanas, las toman y regresan a la colmena.

Las abejas exploradoras investigan el área que rodea a la colmena, con lo que frecuentemente llegan a cubrir áreas de 80 kilómetros cuadrados, y buscan fuentes nuevas y atractivas de alimento. Aproximadamente el 10 por ciento de las abejas exploradoras en una colmena se desempeñan como exploradoras.

En todo momento hay una parte de las abejas recolectoras que están inactivas. Estas recolectoras inactivas esperan cerca de la entrada de la colmena. Cuando las recolectoras activas y las exploradoras regresan a la colmena, según la calidad de la fuente de alimentos que visitaron, se menean frente a las abejas inactivas con movimientos parecidos a un baile. Hay pruebas sólidas que indican que este baile contiene información que se comunica a las abejas inactivas acerca de la ubicación y calidad de la fuente alimenticia. Las recolectoras inactivas reciben esta información de dicho baile y pueden pasar a ser recolectoras activas.

En general, una abeja recolectora inactiva sigue recolectando alimento de una fuente alimenticia específica hasta que se agota. En ese momento, la abeja se vuelve una recolectora inactiva.

El problema del viajante

El problema del viajante (Traveling Salesman Problem, TSP por sus siglas en inglés) es uno de los problemas más estudiados en la investigación del área informática. Existen muchas variaciones del TSP pero, informalmente, el problema es encontrar la ruta más corta que visita cada ciudad una sola vez en un conjunto de ciudades dado.

Si observa la figura 1, podrá ver que el programa de demostración de SBC usa un conjunto de 20 ciudades denominadas de forma arbitraria de la A a la T. Una ruta válida consiste en un conjunto ordenado de 20 etiquetas de ciudades en los que cada ciudad se visita sólo una vez. Por lo tanto, son un total de 20! = 2.432.902.008.176.640.000 rutas posibles.

Detrás de bambalinas, existe un valor de distancia asociado a cada par de ciudades. Por un asunto de simpleza, si ciudad c1 < ciudad c2, la distancia entre c1 y c2 es sólo 1,0 veces la distancia ordinal entre las etiquetas de ciudad. Si c1 > c2, la distancia es 1,5 veces la distancia ordinal entre c1 y c2. Por lo tanto, la distancia de A hasta B es 1,0 unidades arbitrarias, la distancia desde B hasta A es 1,5 unidades, la distancia desde A hasta C es 2,0 unidades, etc. Por lo tanto, la mejor ruta para visitar cada ciudad exactamente una vez es A -> B -> C -> … -> T y la mejor extensión de camino (la más corta) es (20-1) * 1,0 =19,0.

En la mayor parte de los escenarios de TSP, la distancia entre ciudades no se puede calcular artificialmente. En lugar de eso, las distancias se almacenan en alguna clase de estructura de datos de búsqueda. Algunas variaciones de TSP suponen que todas las ciudades están conectadas al resto de las ciudades, mientras que otros problemas suponen que las ciudades no están conectadas totalmente. Además, algunas variaciones de TSP suponen que la distancia entre una ciudad c1 a una ciudad c2 es la misma que la distancia desde la ciudad c2 a la c1, mientras que otras variaciones del problema no hacen ese supuesto bidireccional.

Salvo en situaciones triviales, un acercamiento de fuerza bruta para encontrar la ruta más corta no es factible. Por ejemplo, con 20 ciudades, incluso si pudiese evaluar 1 millón de rutas por segundo, examinar todas las 20! rutas posibles tomaría más de 77.000 años. Esta clase de problema de optimización combinatoria de altísima dificultad es el tipo de problema que los algoritmos de SBC están preparados para enfrentar.

El problema TSP de prueba está implementado en una clase denominada CitiesData, la cual se muestra en la figura 2. El código fuente completo para el programa de demostración de SBC está disponible en code.msdn.microsoft.com/mag0411BeeColony.

Figura 2 La definición de clase CitiesData

class CitiesData {
  public char[] cities;

  public CitiesData(int numberCities) {
    this.cities = new char[numberCities];
    this.cities[0] = 'A';
    for (int i = 1; i < this.cities.Length; ++i)
      this.cities[i] = (char)(this.cities[i - 1] + 1);
  }

  public double Distance(char firstCity, char secondCity) {
    if (firstCity < secondCity)
      return 1.0 * ((int)secondCity - (int)firstCity);
    else
      return 1.5 * ((int)firstCity - (int)secondCity);
  }

  public double ShortestPathLength() {
    return 1.0 * (this.cities.Length - 1);
  }

  public long NumberOfPossiblePaths() {
    long n = this.cities.Length;
    long answer = 1;
    for (int i = 1; i <= n; ++i)
      checked { answer *= i; }
    return answer;
  }

  public override string ToString() {
    string s = "";
    s += "Cities: ";
    for (int i = 0; i < this.cities.Length; ++i)
      s += this.cities[i] + " ";
    return s;
  }
}

La definición de la clase o estructura de datos que represente a su problema en específico será diferente a la que se muestra aquí. Sin embargo, como regla general, los problemas adecuados para soluciones mediante algoritmos de SBC usualmente se pueden representar como una matriz no numérica o una matriz escalonada de matrices.

El constructor CitiesData acepta un valor para el número de ciudades y asigna a la primera ciudad una etiqueta A, a la segunda una etiqueta B, etc.

El método Distance se define unidireccionalmente como describí anteriormente y supone que, sin importar la ciudad de origen, se puede llegar a cualquier ciudad.

El método ShortestPathLength devuelve el largo de ruta óptimo que entrega la definición Distance. En la mayor parte de los casos de SBC no tendrá la información necesaria para implementar un método que devuelva la solución óptima.

El método NumberOfPossiblePaths sólo calcula n!, donde n es el número de ciudades. En algunos escenarios de TSP, el número de rutas posibles es n-1! (si no importa la ciudad inicial) y en otros escenarios el número de rutas posibles es n/2! (si no importa la dirección de la ruta).

El método ToString usa concatenaciones de cadenas en lugar de la clase StringBuilder (que es más eficaz) para ensamblar una cadena con datos descriptivos. La concatenación de cadenas se usa para simplificar el proceso de volver a factorizar otros lenguajes de programación.

En este artículo, para mantener relativamente corto y limpio al código, usaré accesos directos que no se usan en el código de producción, como la eliminación de comprobaciones de errores. Por ejemplo, el método NumberOfPossiblePaths no resuelve el desbordamiento numérico que ocurre si el resultado es mayor a long.MaxValue.

Estructura de programa de SBC

El algoritmo de SBC que se muestra en la figura 1 está implementado en una aplicación de consola de C#. La estructura general del programa está listada en la figura 3. Observe que la estructura de programa de SBC es relativamente simple y usa sólo el nombre de espacio básico System. Existen tres clases: la clase Program, que contiene tan solo a un método Main; la clase Hive, que contiene todas las lógicas de algoritmo de SBC y la clase CitiesData que se presentó en la sección anterior de este artículo. La clase Hive se designa Hive (“colmena”) de forma genérica, en lugar de darle un nombre más específico como TravelingSalesmanHive (“colmena de viajeros”), pese a que las implementaciones de algoritmo de SBC son sumamente dependientes del problema específico que están diseñados para resolver.

Figura 3 Estructura general de programa

using System;
namespace SimulatedBeeColony {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("\nBegin Simulated Bee Colony algorithm demo\n");
      . . . 
      Console.WriteLine("End Simulated Bee Colony demo");
    } 
  } 

  class Hive {
    public class Bee {
      . . . 
    }

    // Hive data fields here

    public override string ToString() { . . . }
    
    public Hive(int totalNumberBees, int numberInactive,
      int numberActive, int numberScout, int maxNumberVisits,
      int maxNumberCycles, CitiesData citiesData) {
      . . .      
    } 

    public char[] GenerateRandomMemoryMatrix() { . . . }
    
    public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) { . . . }
    
    public double MeasureOfQuality(char[] memoryMatrix) { . . . }
    
    public void Solve() { . . . }

    private void ProcessActiveBee(int i) { . . . }

    private void ProcessScoutBee(int i) { . . . }

    private void ProcessInactiveBee(int i) { . . . }

    private void DoWaggleDance(int i) { . . . }
  } 

  class CitiesData {
    . . .
  }

} // ns

El método Main es bastante simple. Después de mostrar un mensaje de inicio, se hace una instancia del objeto CitiesData:

Console.WriteLine(
  "Loading cities data for SBC Traveling Salesman Problem analysis");
CitiesData citiesData = new CitiesData(20);
Console.WriteLine(citiesData.ToString());
Console.WriteLine("Number of cities = " + citiesData.cities.Length);
Console.WriteLine("Number of possible paths = " + 
  citiesData.NumberOfPossiblePaths().ToString("#,###"));
Console.WriteLine("Best possible solution (shortest path) length = " + 
  citiesData.ShortestPathLength().ToString("F4"));

En muchos escenarios de SBC, los datos del problema estarán ubicados en almacenamiento externo, como archivos de texto o bases de datos de SQL, y cargará los datos del problema mediante algún constructor de carga o método de carga similar a myProblemData.Load(dataFile).

A continuación, se prepara y se llama al constructor Hive:

int totalNumberBees = 100;
int numberInactive = 20;
int numberActive = 50;
int numberScout = 30;
int maxNumberVisits = 100; 
int maxNumberCycles = 3460;
       
Hive hive = new TravelingSalesmanHive(totalNumberBees,
  numberInactive, numberActive, numberScout, maxNumberVisits,
  maxNumberCycles, citiesData);

Como verá en más detalle en las siguientes secciones de este artículo, un algoritmo SBC usa tres tipos de abejas. activas, inactivas y exploradoras. Aunque los recuentos de cada uno de esos tipos de abejas se pueden integrar como parte del código, en la mayor parte de los casos es mejor pasar esos recuentos como parámetros del constructor Hive, de manera que el algoritmo pueda ajustarse para un mejor rendimiento más fácilmente.

El valor de la variable totalNumberBees se puede derivar de las otras tres variables, pero la variable adicional mejora la lectura del código en esta parte. El número total de abejas dependerá de su problema en específico. Entra más abejas tenga será mejor, pero esto hará que se ralentice la ejecución del programa. En cuanto a las razones, ciertas investigaciones sugieren que el mejor porcentaje de abejas activas, inactivas y exploradoras ronda entre el 75 por ciento, el 10 por ciento y el 15 por ciento, respectivamente. 

Explicaremos en seguida el valor 100 que se usó para la variable maxNumberVisits, pero está relacionado con el número de soluciones de vecinos relacionadas con un problema específico.

La variable maxNumberCycles se usa para controlar cuantas veces se repetirá la rutina Solve. Esto es necesario debido a que en los escenarios de algoritmos de SBC generalmente no se sabe cuando se llegó a una solución óptima: si conoce la solución óptima, en realidad no hay un problema por resolver. En este caso, el valor de maxNumberCycles se limitó a 3.460 sólo para que el algoritmo de SBC no produjera un resultado perfecto. El punto es que, si bien los algoritmos de SBC pueden generar resultados óptimos, generalmente no habrá manera de saberlo y deberá estar dispuesto a conformarse, por lo tanto, con un resultado “bueno”.

Cuando el constructor se ejecuta, crea una colección de abejas, cada una de las cuales tiene una solución aleatoria. El objeto Hive sigue la mejor (la más corta) de las rutas que haya encontrado alguna de las abejas en la colmena y la extensión de la ruta correspondiente a dicha solución.

Después de llamar al constructor Hive, el método Main concluye usando un método ToString para mostrar los valores de Hive iniciales generados aleatoriamente, lo que llama al método Solve con un parámetro que indica que se debe imprimir una barra de progreso basada en texto y después muestra la mejor ruta que se haya encontrado, junto con la extensión de la ruta correspondiente:

...
  Console.WriteLine("\nInitial random hive");
  Console.WriteLine(hive);

  bool doProgressBar = true;
  hive.Solve(doProgressBar);

  Console.WriteLine("\nFinal hive");
  Console.WriteLine(hive);
  Console.WriteLine("End Simulated Bee Colony demo");
}

La clase Bee

Como se muestra en la Figura 3, la clase Hive contiene una definición de clase Bee anidada. Los detalles de la definición Bee se indican en la figura 4.

Figura 4 Definición de la clase Bee

public class Bee {
  public int status;
  public char[] memoryMatrix;
  public double measureOfQuality; 
  public int numberOfVisits;

  public Bee(int status, char[] memoryMatrix, 
    double measureOfQuality, int numberOfVisits) {
    this.status = status;
    this.memoryMatrix = new char[memoryMatrix.Length];
    Array.Copy(memoryMatrix, this.memoryMatrix, memoryMatrix.Length);
    this.measureOfQuality = measureOfQuality;
    this.numberOfVisits = numberOfVisits;
  }

  public override string ToString() {
    string s = "";
    s += "Status = " + this.status + "\n";
    s += " Memory = " + "\n";
    for (int i = 0; i < this.memoryMatrix.Length-1; ++i)
      s += this.memoryMatrix[i] + "->";
    s += this.memoryMatrix[this.memoryMatrix.Length-1] + "\n";
    s += " Quality = " + this.measureOfQuality.ToString("F4");
    s += " Number visits = " + this.numberOfVisits;
    return s;
  }
}

La clase Bee tiene tres campos de datos comunes a todas las implementaciones de SBC y un campo de datos de problemas específicos. El campo de problema específico se denomina memoryMatrix. Cada implementación de SBC debe tener alguna manera de representar una solución. En el caso del TSP en este artículo, una solución se puede representar por una matriz de tipo char. Enfatizaré en que el objeto que representa la solución es altamente dependiente del problema y cada programa se debe analizar por separado para producir una representación de solución significativa.

El campo denominado status contiene un valor int que indica el tipo de objeto de Bee: 0 para inactivas, 1 para activas y 2 para exploradoras. Si está escribiendo código en un lenguaje que compatible con tipos de enumeración, deseará volver a factorizar el campo status como una enumeración.

El campo measureOfQuality contiene un valor doble que representa los beneficios de memoryMatrix del objeto Bee. En el caso de TSP, una medida natural de la calidad de la solución es la extensión de la ruta representada por el objeto memoryMatrix. Observe que, en esta solución, las extensiones de ruta más cortas son mejores que aquellas más largas, por lo tanto, la designación de valores pequeños en el campo measureOfQuality representan mejores soluciones que aquellas con valores mayores. Cada implementación de SBC debe contar con alguna manera de calcular una medida de calidad de solución. En muchas situaciones, esta medida se representa de mejor manera mediante un valor de tipo double.

El tercer campo de datos común en la clase Bee se llama numberOfVisits. Este campo contiene un valor int que representa el número de ocasiones en los que el objeto Bee visitó una fuente de alimento/solución de problema sin encontrar una mejor solución de vecinos. Este campo se usó para simular a una abeja que visita una fuente de alimento hasta que esta se acaba. Una abeja activa, cuando el valor del campo numberOfVisits supera un valor umbral, habrá agotado en la práctica la fuente de alimentación y pasará al estado inactivo (y una abeja inactiva pasará a estar activa).

El constructor Bee acepta valores para los cuatro campos de datos, status, memoryMatrix, measureOfQuality y numberOfVisits. Observe que el constructor Bee debe aceptar un valor para measureOfQuality, puesto que una Bee no puede calcular esto directamente desde el campo memoryMatrix. La definición de la medida de calidad depende de la información almacenada en el objeto para problemas específicos CitiesData.

La definición de la clase Bee contiene un método ToString, que expone los valores de los cuatro campos de datos. El método Bee.ToString no es absolutamente necesario, pero puede ser bastante útil en el desarrollo de SBC para brindar ayuda en la detección de errores mediante declaraciones WriteLine.

Los campos de datos Hive

El código de la clase Hive se presenta en la Figura 5. Existen 14 campos de datos en Hive. La comprensión de la finalidad de cada una es fundamental para entender cómo implementar un algoritmo SBC específico.

Figura 5 Los 14 campos de datos de Hive

static Random random = null;

public CitiesData citiesData;

public int totalNumberBees; 
public int numberInactive; 
public int numberActive;
public int numberScout;

public int maxNumberCycles;
public int maxNumberVisits; 

public double probPersuasion = 0.90;
public double probMistake = 0.01; 

public Bee[] bees;
public char[] bestMemoryMatrix;
public double bestMeasureOfQuality;
public int[] indexesOfInactiveBees;

Para una mayor simpleza y facilidad de depuración con declaraciones WriteLine, los 14 campos de datos están definidos con un ámbito público. Es posible que desee restringir los campos a un ámbito privado y crear propiedades para esos campos a los que necesita tener acceso fuera de la definición de clase.

El primer campo es denominado random y es tipo Random. Los algoritmos de SBC son probabilísticos, y el objeto random se usa para generar números pseudo aleatorios para varios fines. Se creará una instancia del objeto Random en el constructor Hive.

El segundo campo de datos es un objeto denominado CitiesData. La implementación de SBC necesita saber los detalles del problema que está en resolución. En la mayor parte de los casos, como ocurre en este, los datos del problema se representan como un objeto. Recuerde que CitiesData tiene una lista de etiquetas de seguridad y un método que devuelve la distancia entre dos ciudades.

Desde el tercer campo hasta el sexto son variables int que contienen el número total de abejas, el número de abejas inactivas, el número de abejas activas y el número de abejas exploradoras. Cómo se mencionó antes, dado que cada abeja representa una solución potencial, entre más abejas haya en la colmena, mejor. Sin embargo, los números grandes de abejas disminuyen el rendimiento del programa.

El séptimo campo de datos, maxNumberCycles, es un valor umbral que se usa para limitar la duración de la ejecución del método Solve. Un ciclo representa el procesamiento de cada abeja en la colmena.

El octavo campo de datos, maxNumberVisits, es un valor umbral usado para evitar que una abeja permanezca demasiado tiempo en una solución específica. En cada iteración del bucle de procesamiento principal en el método Solve, si una abeja no encuentra una fuente de alimento cercana de mayor calidad, el contador numberOfVisits de la abeja aumenta. Si el número del contador de numberOfVisits de una abeja supera el valor umbral maxNumberVisits, la abeja cambia al estado de inactividad.

El noveno campo de datos, probPersuasion, es un umbral probabilístico que se usa para determinar si se convence a una abeja inactiva que observa el baile de una abeja que volvió a la colmena con una mejor solución a que actualice su memoria con ella.

El valor de probPersuasion está integrado como parte del código con el valor 0,90, lo que significa que una abeja inactiva ser verá persuadida a aceptar una mejor solución el 90 por ciento de las ocasiones. El valor 0,90 para probPersuasion está basado en hallazgos obtenidos por investigaciones, pero probablemente deseará experimentar con otros valores. Valores mayores producirán un algoritmo de SBC que conducirá a una solución de forma más expedita, con un mayor riesgo de que pueda conducir a una solución no óptima.

El décimo campo de datos, probMistake, es un valor umbral probabilístico que se usa para determinar si una abeja activa cometerá un error; es decir, que rechace incorrectamente una solución de vecino mejor que la solución actual de la abeja o que acepte incorrectamente una solución de vecino peor que su solución actual. El valor de probMistake está integrado como parte del código con el valor 0,01, lo que significa que una abeja activa se equivocará en la evaluación de una solución de vecino el 1 por ciento de las ocasiones.

El enésimo campo de datos, bees, es una matriz del objeto Bee. Recuerde que cada abeja tiene un estado (activa, inactiva, exploradora), una solución (memoryMatrix), una medida de la calidad de la solución (measureOfQuality) y un recuento del número de ocasiones en las que una fuente de alimentos específica fue visitada sin encontrar una mejor fuente de alimento de vecino (numberOfVisits). Puesto que Bee está definido como una clase, cada entrada en la matriz de abejas es una referencia al objeto Bee.

El duodécimo campo de datos, bestMemoryMatrix, es una matriz de char y representa la mejor solución de la matriz de abejas. Recuerde que, debido a que las colonias de abejas simuladas son implementaciones específicas de una meta heurística, la representación de una solución de problema variará según el problema. Un enfoque de diseño alternativo para integrar como parte del código una definición de tipo de solución es parametrizar este campo de datos como un tipo genérico. Al usar un algoritmo de SBC, generalmente se está intentando resolver un problema específico, por lo que prefiero volver a escribir el código de cadena nueva implementación de SBC desde cero.

El decimotercer campo, bestMeasureOfQuality, es la medida de calidad correspondiente a la solución bestMemoryMatrix.

El último campo de datos de colmena, indexesOfInactiveBees es una matriz de int. Esta matriz contiene los índices de las abejas en la colmena que están inactivos actualmente. Recuerde que las abejas activas pueden hacer una transición al estado de inactividad y viceversa. Una implementación de algoritmo de SBC debe identificar frecuentemente cuáles abejas están inactivas cuando una abeja activa realiza un baile virtual y almacenar los índices de abejas inactivas mejora el rendimiento en comparación a la otra alternativa, que es hacer iteraciones en toda la matriz de abejas y comprobar el campo de datos status de cada abeja.

Se muestra una representación visual de un posible objeto Hive en la figura 6. La colmena que se muestra tiene 10 abejas: 5 activas, 2 exploradoras y 3 inactivas. Las abejas inactivas actualmente están en los índices 2, 7 y 4 de la matriz de abejas. El objeto CitiesData tiene cinco ciudades. La mejor solución actual es:

A->B->E->C-D

La solución tiene un largo de ruta, medido en unidades de distancia, de:

1.0 + (3 * 1.0) + (2 * 1.5) + 1.0 = 8.0

Observe que el campo citiesData es una referencia al objeto CitiesData definido afuera del objeto Hive.

Figura 6 La representación de la colmena

El constructor Hive

El código del constructor Hive se presenta en la Figura 7. El constructor Hive acepta siete parámetros de entrada. Seis de los parámetros son escalares y uno es un objeto (citiesData). El parámetro totalNumberBees es redundante en cuanto se puede determinar de numberInactive, numberActive y numberScout, pero creo que la mejora de la legibilidad justifica la escritura adicional de código.

Figura 7 El constructor Hive

public Hive(int totalNumberBees, int numberInactive,
  int numberActive, int numberScout, int maxNumberVisits,
  int maxNumberCycles, CitiesData citiesData) {

  random = new Random(0);
      
  this.totalNumberBees = totalNumberBees;
  this.numberInactive = numberInactive;
  this.numberActive = numberActive;
  this.numberScout = numberScout;
  this.maxNumberVisits = maxNumberVisits;
  this.maxNumberCycles = maxNumberCycles;

  this.citiesData = citiesData;

  this.bees = new Bee[totalNumberBees];
  this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
  this.bestMeasureOfQuality = 
    MeasureOfQuality(this.bestMemoryMatrix);

  this.indexesOfInactiveBees = new int[numberInactive]; 

  for (int i = 0; i < totalNumberBees; ++i) {
    int currStatus; 
    if (i < numberInactive) {
      currStatus = 0; // inactive
      indexesOfInactiveBees[i] = i; 
    }
    else if (i < numberInactive + numberScout)
      currStatus = 2; // scout
    else
      currStatus = 1; // active
    
    char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
    double mq = MeasureOfQuality(randomMemoryMatrix);
    int numberOfVisits = 0;

    bees[i] = new Bee(currStatus, 
      randomMemoryMatrix, mq, numberOfVisits); 
        
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix, 
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    }
  } 
}

Se crea una instancia del objeto Random, el cual se establece con un ámbito que abarca toda la clase, con un valor de inicialización de 0. Al proporcionar un valor inicial, se permite reproducir los resultados. A continuación, se copian seis valores de parámetro de entrada a los campos de datos de Hive. El objeto Hive tiene un total de 14 campos de datos, el valor umbral probPersuasion y probMistake se integran como parte del código.

El constructor Hive toma la entrada del parámetro citiesData y asigna el campo citiesData al parámetro como referencia. Una alternativa a este enfoque “referencial” es hacer una nueva copia de los datos del problema, como el siguiente:

int n = citiesData.cities.Length;
this.citiesData = new CitiesData(n);

Este enfoque consume más memoria, pero evita posibles errores que puedan generarse como efecto secundario. La otra alternativa de enfoque se puede usar si está volviendo a factorizar el código que se muestra aquí para un lenguaje de programación que no es compatible con punteros o referencias.

En este punto, en el constructor Hive, todas las entradas de la matriz de abejas será nula. A continuación, el constructor inicializa la mejor solución global (es decir, la mejor solución de todas las abejas en la colmena y la correspondiente calidad de solución:

this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
this.bestMeasureOfQuality = 
  MeasureOfQuality(this.bestMemoryMatrix);

El método auxiliar GenerateRandomMemoryMatrix genera una solución aleatoria. El método auxiliar MeasureOfQuality acepta la solución generada aleatoriamente y calcula su cualidad. Analizaré el código de esos dos métodos de ayuda posteriormente en el artículo.

Después de inicializar la solución global óptima y su calidad respectiva, el constructor Hive designa la matriz de abejas indexesOfInactiveBees mediante el valor en el campo numberInactive. En este punto, todos los valores en estos índices será 0.

La siguiente parte del código constructor se itera en cada objeto Bee de la matriz de abejas y se genera una instancia de él usando el constructor Bee. La lógica en este bucle supone que las primeras celdas numberInactive en la matriz de abejas son abejas inactivas, las siguientes celdas de numberScout son abejas exploradoras y las celdas restantes son abejas activas.

Por ejemplo, si hay cinco abejas activas, dos inactivas y tres abejas exploradoras, el constructor inicializa una matriz de abejas de un tamaño de 10 y crea instancias de las células. Lo que es más, la matriz indexesOfInactiveBees tendrá tamaño 2 e inicialmente contendrá valores 0 y 1.

Después de que se determine el estado de las abejas actuales según la variable de índice de bucle, se crea una solución aleatoriamente generada y se calcula su calidad correspondientes, el contador del número de visitas se establece explícitamente como 0 y se llama al constructor Bee:

char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
double mq = MeasureOfQuality(randomMemoryMatrix);
int numberOfVisits = 0;
bees[i] = new Bee(currStatus, randomMemoryMatrix, 
  mq, numberOfVisits);

Después de que se crea una instancia para cada abeja, se revisa si la calidad de la solución generada aleatoriamente por la abeja es mejor que la solución global óptima. Si es así, la solución actual de la abeja y la calidad correspondiente se copian en los campos de bestMemoryMatrix y bestMeasureOfQuality. Observe al confirmar la calidad de la solución global óptima que un valor inferior es mejor a uno superior, puesto que el valor de calidad representa largos de ruta y en TSP se busca minimizar el largo de la ruta.

En lugar de explícitamente copiar una memoria de abeja en la matriz bestMemoryMatrix, un enfoque alternativo es asignarlo por referencia. Este enfoque mejora el rendimiento, con el contra que aumenta la complejidad.

Tres métodos de SBC esenciales

Cada implementación del algoritmo de SBC debe tener tres métodos para problemas específicos: un método para generar una solución aleatoria, un método para generar una solución de vecino relacionada a un método dado y un método para calcular la calidad de una solución dada. En este ejemplo de TSP cada método se implementa en una manera personalizada y que depende totalmente del problema.

Una alternativa de diseño es definir interfaces e implementarlas. La programación mediante interfaces tiene varias ventajas y desventajas en contraste al enfoque no asociado a interfaz, pero mi opinión es que se trata en el fondo de un asunto de preferencias personales. Aquí se muestra GenerateRandomMemoryMatrix, el método que genera una solución aleatoria:

public char[] GenerateRandomMemoryMatrix() {
  char[] result = new char[this.citiesData.cities.Length];
  Array.Copy(this.citiesData.cities, result,
    this.citiesData.cities.Length);      
  for (int i = 0; i < result.Length; i++) {
    int r = random.Next(i, result.Length);
    char temp = result[r];
    result[r] = result[i];
    result[i] = temp;
  }
  return result;
}

Puesto que una solución al problema de TSP es una matriz de char donde cada char representa una etiqueta de ciudad, el método GenerateRandomMemoryMatrix devuelve una matriz de char. El tamaño de la matriz local de resultado está basado en el objeto CitiesData de Hive y el identificador de ciudad que se almacena en la referencia de Hive al objeto CitiesData se copia en la matriz de resultado. El orden de estos valores en la matriz de resultado después se aleatoriza mediante el objeto Random, con un ámbito que abarca toda la clase, y el algoritmo de aleatorización de Fisher-Yates (el cual a veces recibe el nombre de aleatorización de Knuth).

Al principio, puede parecer que el método GenerateRandomMemoryMatrix debiera pertenecer, por relación conceptual, al objeto Bee. Sin embargo, dado que generar una solución aleatoria depende en parte de datos de problemas específicos (en este caso, de CitiesData), es mucho mejor en términos de diseño ubicar el método de generación de solución aleatoria en la definición general de Hive.

El método para generar una solución de vecino, GenerateNeighborMemoryMatrix, se presenta en la figura 8.

Figura 8 Generar una solución de vecino

public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) {
  char[] result = new char[memoryMatrix.Length];
  Array.Copy(memoryMatrix, result, memoryMatrix.Length);

  int ranIndex = random.Next(0, result.Length);
  int adjIndex;
  if (ranIndex == result.Length - 1)
    adjIndex = 0;
  else
    adjIndex = ranIndex + 1;

  char tmp = result[ranIndex];
  result[ranIndex] = result[adjIndex];
  result[adjIndex] = tmp;  return result;
}

Un concepto fundamental de los algoritmos de SBC es la idea de que cada fuente de alimento virtual que representa una solución tiene alguna clase de vecino. Sin el concepto de vecino, toda la idea de un algoritmo basado en el comportamiento de las abejas se desmorona. En el caso del TSP, donde una solución se puede representar como una matriz de identificadores de ciudad que representan una ruta de ciudad a ciudad, una solución natura de vecino relacionada a una solución actual es una permutación de la solución actual, en la cual se intercambiaron dos ciudades adyacentes.

Por ejemplo, si una solución de TSP actual es A,B,C,D,E, entonces una solución de vecino razonable es A,C,B,D,E. Esto no es tan evidente si una permutación donde se intercambian dos ciudades cualquieras (en contraste a dos ciudades adyacentes) representa una solución de vecino razonable. Para el ejemplo anterior, ¿es acaso A,D,C,B,E una solución de vecino razonable? La decisión respecto a la definición es una solución de vecino que depende del problema y generalmente involucra criterios subjetivos.

El concepto de la solución de vecino también sirve para ilustrar en parte por qué es especialmente adecuado recurrir a soluciones de algoritmos de SBC para los problemas de combinatoria no numérica. Si un problema es inherentemente numérico, la idea de un vecino generalmente es difícil de definir de forma satisfactoria. Si un problema está inherentemente relacionado con combinatoria, habitualmente el concepto de vecino se puede definir adecuadamente mediante alguna clase de combinación o permutación matemática.

El método GenerateNeighborMemoryMatrix acepta una representación de solución actual de memoryMatrix de una abeja como un parámetro de entrada y la copia en una matriz de resultado. El método selecciona un índice aleatorio para la matriz de resultado actual mediante el objeto Random con un ámbito que alcanza toda la clase. Si el índice aleatorio indica la última celda, entonces los identificadores de la primera y de la última celda se intercambian, de otra forma, si el índice aleatorio indica cualquier celda que no sea la última, se intercambian los identificadores indicados por el índice Random y el siguiente índice se intercambian.

El concepto de solución de vecino está asociado al valor maxNumberVisits. Ciertas investigaciones han revelado que un buen valor para maxNumberVisits toma alrededor de cinco veces el número de soluciones vecinas posibles para cualquier solución dada. Por ejemplo, para tres ciudades (A,B,C), si una solución vecina se define como el intercambio de cualquier par de ciudades adyacentes, entonces existen tres posibles vecinos (intercambio de A y B, de B y C y de A y C). Por lo tanto, para 20 ciudades, un valor razonable de maxNumberVisits es de alrededor de 20 * 5 = 100.

El método para evaluar la calidad de la solución de una abeja, MeasureOfQuality, es el siguiente:

public double MeasureOfQuality(char[] memoryMatrix) {
  double answer = 0.0;
  for (int i = 0; i < memoryMatrix.Length - 1; ++i) {
    char c1 = memoryMatrix[i];
    char c2 = memoryMatrix[i + 1];
    double d = this.citiesData.Distance(c1, c2);
    answer += d;
  }
  return answer;
}

Para solucionar un problema mediante un algoritmo SBC, una característica esencial del problema es que cualquier solución debe poder evaluarse para arrojar una medida de la calidad de la solución. En términos conceptuales, un problema de optimización de combinatoria del mundo real casi siempre tiene alguna medida de calidad inherente y sensata. Sin embargo, en términos prácticos, el cálculo de medidas de calidad como solución puede ser difícil, además de que puede tomar mucho tiempo.

En este ejemplo, el método MeasureOfQuality simplemente se itera a través de cada par de identificadores consecutivos de ciudad en la solución representada por el parámetro memoryMatrix, determina la distancia entre cada par mediante el método Distance del objeto CitiesData y acumula la distancia total. Recuerde que los datos de la ciudad se construyeron artificialmente, de manera que la distancia entre dos ciudades, cualesquiera que estas sean, se pueden calcular rápida y fácilmente mediante la distancia ordinal entre dos identificadores de ciudad. Sin embargo, en un problema real, la distancia entre dos ciudades tendría que buscarse en alguna clase de estructura de datos. En las implementaciones de SBC, el método MeasureOfQuality es generalmente la rutina que domina el tiempo de ejecución del programa. Por lo tanto, generalmente vale la pena asegurarse de que este método esté optimizado en términos de rendimiento, en la medida que esto sea posible, dados los recursos de memoria del sistema host.

El método Solve

El método Solve contiene toda la lógica que simula el comportamiento de las abejas recolectoras destinada para resolver el problema. El método Solve es moderadamente complejo y usa tres métodos auxiliares, ProcessActiveBee, ProcessScoutBee y ProcessInactiveBee. Los métodos ProcessActiveBee y ProcessScoutBee usan, a su vez, el método auxiliar DoWaggleDance. El método Solve se muestra en la figura 9.

Figura 9 El método Solve

public void Solve(bool doProgressBar) {
  bool pb = doProgressBar;
  int numberOfSymbolsToPrint = 10; 
  int increment = this.maxNumberCycles / numberOfSymbolsToPrint;
  if (pb) Console.WriteLine("\nEntering SBC Traveling Salesman Problem algorithm main processing loop\n");
  if (pb) Console.WriteLine("Progress: |==========|");
  if (pb) Console.Write("           ");
  int cycle = 0;
      
  while (cycle < this.maxNumberCycles) {
    for (int i = 0; i < totalNumberBees; ++i) {
      if (this.bees[i].status == 1)
        ProcessActiveBee(i);
      else if (this.bees[i].status == 2)
        ProcessScoutBee(i);
      else if (this.bees[i].status == 0)
        ProcessInactiveBee(i);
    } 
    ++cycle;

    if (pb && cycle % increment == 0)
      Console.Write("^");
  } 

  if (pb) Console.WriteLine("");
}

La mayor parte del trabajo es recopilado por los métodos auxiliares ProcessActiveBee, ProcessScoutBee y ProcessInactiveBee. Se pasa un parámetro de entrada booleano a Solve para indicar si se debe imprimir una barra de progreso rudimentaria basada en texto. Esto es útil en el desarrollo de algoritmos de SBC para supervisar la velocidad de la implementación y para revelar cuellos de botella de rendimiento. Este enfoque presupone que el método Solve es parte de una aplicación de consola.

El valor del parámetro booleano se transfiere a una variable booleana pb, denominada así tan solo para tener un nombre de corto con el cual trabajar. Se establece numberOfSymbolsToPrint en 10, de manera que cada incremento de la barra de estado represente un 10 por ciento del progreso total, lo cual está determinado por el valor de maxNumberCycles (la variable de incremento se usa para determinar cuántos ciclos representan progresos de 10 por ciento).

Después de que la variable de control de bucle, cycle, se inicializa en 0, se usa un bucle while para procesar cada abeja de la colmena. También puede usarse con el mismo grado de facilidad un bucle for. En cada ciclo, la matriz de abejas se itera mediante un bucle for y cada objeto Bee se procesa por el método auxiliar adecuado. Después de procesar a cada abeja, si el parámetro booleano doProgressBar es verdadero, el código usa el operador de módulo, %, para confirmar si es el momento de imprimir una actualización en la barra de progreso mediante un carácter ^.

El método ProcessActiveBee

El método ProcessActiveBee es el núcleo de un algoritmo de SBC y es el método más complejo en términos de tamaño de código y de bifurcación. El método ProcessActiveBee se presenta en la figura 10.

Figura 10 El método ProcessActiveBee

private void ProcessActiveBee(int i) {
  char[] neighbor = GenerateNeighborMemoryMatrix(bees[i].memoryMatrix);
  double neighborQuality = MeasureOfQuality(neighbor); 
  double prob = random.NextDouble();
  bool memoryWasUpdated = false;
  bool numberOfVisitsOverLimit = false; 

  if (neighborQuality < bees[i].measureOfQuality) { // better
    if (prob < probMistake) { // mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
    else { // No mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0; 
      memoryWasUpdated = true; 
    }
  }
  else { // Did not find better neighbor
    if (prob < probMistake) { // Mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0;
      memoryWasUpdated = true; 
    }
    else { // No mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
  }

  if (numberOfVisitsOverLimit == true) {
    bees[i].status = 0; 
    bees[i].numberOfVisits = 0;
    int x = random.Next(numberInactive); 
    bees[indexesOfInactiveBees[x]].status = 1; 
    indexesOfInactiveBees[x] = i; 
  }
  else if (memoryWasUpdated == true) {
    if (bees[i].measureOfQuality < this.bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length); 
      this.bestMeasureOfQuality = bees[i].measureOfQuality
    }
    DoWaggleDance(i);
  }
  else {
    return;
  }
}

El método ProcessActiveBee acepta una sola entrada de parámetro, i, la cual es el índice de la abeja en la matriz de abejas. La abeja activa primero obtiene una solución de vecino relacionada a su solución actual, la cual está almacenada en memoryMatrix, y después determina la calidad de dicho vecino:

char[] neighbor =
  GenerateNeighborMemoryMatrix(bees[i].memoryMatrix); 
double neighborQuality = MeasureOfQuality(neighbor);

A continuación, el algoritmo configura tres variables locales que se usarán posteriormente:

double prob = random.NextDouble();)
bool memoryWasUpdated = false; 
bool numberOfVisitsOverLimit = false;

La variable prob tiene un valor de entre 0,0 y 1,0 y se comparará contra el valor del campo probMistake para definir si la abeja comete un error al evaluar la solución vecina; es decir, si rechaza una mejor solución vecina o acepta una peor solución de vecino.

El valor booleano memoryWasUpdated se usará para definir si la abeja activa debe realizar un baile para las abejas inactivas (si es verdadero) o si no debe hacerlo (si el falso). El valor booleano numberOfVisitsOverLimit se comparará con el campo maxNumberVisits para definir si la abeja agotó una fuente de alimento específica sin encontrar una solución de vecino más adecuada y si se debe pasar del estado activo al pasivo.

Si la abeja actual encuentra una mejor solución de vecino, el algoritmo define si la abeja comete un error y rechaza al vecino más óptimo o si lo acepta. De igual manera, si la abeja actual no encuentra una mejor solución de vecino, el algoritmo determina si la abeja comete un error y acepta la solución de peor vecino o si no hace un error y lo rechaza.

Observe que hay dos tipos posibles de errores, pero que ambos tipos de errores tienen la misma posibilidad, probMistake = 0,01. Ciertas investigaciones sugieren que usar dos probabilidades diferentes para dos tipos distintos de errores no mejora la efectividad de los algoritmos de SBC, pero quizás usted querrá experimentar con dos valores de umbral distintos.

Después de que la abeja activa actual acepte o rechace la opción de vecino, el algoritmo confirma si el contador de número de visitas superó el umbral maxNumberVisits. De ser así, el estado actual de la abeja se vuelve inactivo, una abeja inactiva seleccionada al azar pasa al estado activo y se actualiza la matriz indexesOfInactiveBees. A continuación, el algoritmo confirma si se actualizó la memoria de la abeja. Si tal cosa ocurrió, se revisa la nueva solución para determinar si es una nueva solución global óptima y después se llama a un método privado auxiliar, DoWaggleDance, para simular que la abeja regresa a la colmena y transporta información sobre la nueva fuente de alimentación a las abejas inactivas.

El método DoWaggleDance

El método auxiliar DoWaggleDance simula el regreso de una abeja activa o exploradora a la colmena y realiza un baile para las abejas inactivas con la finalidad de proporcionar información respecto a la ubicación y calidad de una fuente de alimentos. Este es el método DoWaggleDance:

private void DoWaggleDance(int i) {
  for (int ii = 0; ii < numberInactive; ++ii) {
    int b = indexesOfInactiveBees[ii]; 
    if (bees[i].measureOfQuality < bees[b].measureOfQuality) {
      double p = random.NextDouble(); 
      if (this.probPersuasion > p) {
        Array.Copy(bees[i].memoryMatrix, bees[b].memoryMatrix,
          bees[i].memoryMatrix.Length);
        bees[b].measureOfQuality = bees[i].measureOfQuality;
      } 
    } 
  } 
}

El parámetro de entrada i es el índice de la abeja actual que está realizando el baile virtual. La medida de calidad de la solución de la abeja actual se compara con la medida de calidad de cada abeja inactiva. Si la solución actual de la abeja es mejor y la abeja que actualmente está inactiva se convence (con una probabilidad de probPersuasion = 0,90), se copia la memoria de la abeja actual a la memoria de la abeja inactiva.

Observe que existen varias oportunidades para insertar confirmación de errores en el código que se presenta en este artículo. Por ejemplo, dentro del bucle for en DoWaggleDance, es posible que desee confirmar el estado de las abejas inactivas con lo siguiente:

if (bees[b].status != 0) throw new Exception(. . .);

O quizás quiera comprobar el número del contador de visitas de la abeja:

if (bees[b].numberOfVisits != 0) throw new Exception(. . .);

ProcessScoutBee y ProcessInactiveBee

El método auxiliar ProcessScoutBee que usa el método Solve simula la acción de una abeja exploradora que busca aleatoriamente fuentes de alimento atractivas. El método ProcessScoutBee se presenta en la figura 11.

Figura 11 El método ProcessScoutBee

private void ProcessScoutBee(int i) {
  char[] randomFoodSource = GenerateRandomMemoryMatrix();
  double randomFoodSourceQuality = 
    MeasureOfQuality(randomFoodSource);
  if (randomFoodSourceQuality < bees[i].measureOfQuality {
    Array.Copy(randomFoodSource, bees[i].memoryMatrix,
      randomFoodSource.Length);
    bees[i].measureOfQuality = randomFoodSourceQuality;
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    } 
    DoWaggleDance(i);
  }
}

El parámetro de entrada i representa el índice de una abeja exploradora en la matriz de abejas. Una abeja exploradora genera una solución aleatoria, comprueba si la solución aleatoria es mejor que la actual en la memoria y, de ser así, copia la solución aleatoria en la memoria. Recuerde que es mejor cuando los valores de calidad son menores. Si la abeja exploradora encontró una mejor solución, el algoritmo confirma si la nueva solución es una solución global óptima.

Observe que, a diferencia de las abejas activas, en esta implementación de SBC, las abejas exploradoras jamás cometen errores al evaluar la calidad de una fuente de alimentos. No existen investigaciones respecto al efecto de los errores de las abejas exploradoras.

El método ProcessInactiveBee es el siguiente:

`private void ProcessInactiveBee(int i) {
  return;
}
private void ProcessInactiveBee(int i) {
  return;
}

En esta implementación de SBC, las abejas inactivas están exactamente como se indica: inactivas. De tal manera, el método ProcessInactiveBee es simplemente un marcador de posición en caso que desee implementar alguna lógica que dependa del problema en una abeja inactiva. Otra modificación posible es mutar aleatoriamente la memoria de una abeja inactiva con una probabilidad ínfima.

Conclusión

El proceso general de la implementación de un algoritmo de SBC comienza en la identificación del problema. Los problemas de optimización de combinatoria complejos que no están asociados a números y que no tienen soluciones deterministas prácticas generalmente son buenos candidatos para una solución SBC. El problema objetivo debe tener algún modo en el que se pueda representar una solución (generalmente mediante una matriz) y cada solución debe contar con alguna clase de solución de vecino y una medida de calidad de solución.

Por ejemplo, considere el problema de dividir un gráfico en dos partes, de manera que el número de conexiones de cada parte se maximice y el número de conexión entre las dos partes se minimice. Este problema de partición de gráfico es un asunto de combinatoria y no hay un algoritmo rápido que revele la solución óptima (aunque existen algoritmos deterministas que son buenos para identificar soluciones casi óptimas). Existen varios otros problemas NP-completos y NP-complejos que se pueden abordar usando un SBC.

Los algoritmos SBC están basados en el comportamiento de los sistemas naturales. Existen otros algoritmos, los cuales incluyen a los algoritmos genéticos (GA), que se basan en la selección natural y la evolución, la optimización de colonias de hormigas, que se basa en el comportamiento de las hormigas y el recocido simulado (SA), que se basa en las propiedades físicas de los metales en proceso de enfriamiento.

Los algoritmos basados en sistemas naturales generalmente son fáciles de implementar con relación a los enfoques deterministas. Sin embargo, los algoritmos basados en sistemas naturales habitualmente exigen la especificación de valores para varios parámetros que tienden a tener impacto en su efecto en la velocidad de convergencia de solución y en la precisión de solución. En el caso de una SBC, los parámetros sensibles que se deben ajustar para cada problema incluyen el número de cada tipo de abeja, el número máximo de visitas antes de que se agote una fuente de alimento, los umbrales de probabilidad de persuasión de abejas inactivas y la probabilidad de error de las abejas activas.

Si bien los algoritmos de SBC no son aplicables a cada problema, en algunos escenarios pueden ser herramientas extremadamente poderosas. 

El Dr. James McCaffreytrabaja en Volt Information Sciences Inc., donde administra el entrenamiento técnico de los ingenieros informáticos que trabajan en el campus de Microsoft en Redmond, Washington. Ha trabajado en varios productos Microsoft, lo que incluye Internet Explorer y MSN Search. El Dr. McCaffrey es el autor de “.NET Test Automation Recipes” (Apress, 2006) y puede ponerse en contacto con él en la dirección de correo electrónico jammc@microsoft.com.

Gracias a los siguientes expertos técnicos por su ayuda en la revisión de este artículo: Dan Liebling y Anne Loomis Thompson, integrantes de Microsoft Research