Algoritmos de optimización de la población: Colonia de abejas artificiales (Artificial Bee Colony - ABC)

Contenido:

1. Introducción
2. Descripción del algoritmo
3. Versión modificada
4. Resultados de la prueba
   

1. Introducción

Los insectos sociales son insectos altamente evolucionados que realizan multitud de tareas complejas que no hacen muchos insectos por separado. La comunicación, la construcción de nidos complejos, el control del entorno, la protección y la división del trabajo son solo algunos de los comportamientos que las abejas melíferas han desarrollado para prosperar en las colonias sociales.
Las abejas pertenecen a los representantes de enjambres y también son capaces de demostrar habilidades extraordinarias para encontrar soluciones óptimas. En la naturaleza, encuentran acumulaciones de flores para recolectar néctar y polen cerca de la colmena, aunque, en ocasiones, el radio de búsqueda puede aumentar a varios kilómetros. Luego informan sobre el paradero a las otras abejas mediante un baile improvisado.

A primera vista, parece que esto es imposible, pero son capaces de transmitirse entre ellas información sobre la posición geográfica usando movimientos rítmicos. Al mismo tiempo, en función de la intensidad de la danza, las abejas pueden sacar conclusiones sobre el número de flores, la cantidad estimada de néctar en un punto específico en el espacio, y cuanto más alimento potencial, más activamente se lleva a cabo la danza. Este fenómeno inusual fue descubierto a mediados del siglo XX por el investigador y etólogo Karl von Frisch.

Durante muchos años, solo los biólogos científicos investigaron los métodos de búsqueda de las abejas, pero con el creciente interés en el comportamiento de los enjambres en la naturaleza como modelo para crear nuevos algoritmos de optimización, en 2005 el profesor Dervis Karaboga se interesó en los resultados de la investigación. Así, publicó un artículo científico en el que por primera vez se describía un modelo de inteligencia de enjambre inspirado por la danza de las abejas. El modelo se denominó colonia de abejas artificiales (Artificial Bee Colony).

2. Descripción del algoritmo

Existen muchas implementaciones de la colonia de abejas artificiales que difieren en los principios de gestión de las abejas en una colmena y las reglas para explorar áreas. En este artículo hablaremos sobre mi interpretación de la versión clásica del algoritmo.

La idea del algoritmo está tomada, como podrá adivinar por el nombre, de las abejas, es decir, de su comportamiento al buscar los lugares donde pueda obtener la mayor cantidad de néctar posible. Primero, todas las abejas salen volando de la colmena en una dirección aleatoria, actuando como exploradoras que tratan de encontrar áreas donde haya néctar. Después de ello, las abejas regresan a la colmena y les comunican a las demás de una forma especial dónde y cuánto néctar han encontrado.

Las abejas obreras son enviadas a las áreas encontradas, y cuanto más néctar se suponga que hay en esta área, más abejas volarán en dicha dirección; así, las exploradoras volverán a volar para buscar otras zonas, pero ya en las inmediaciones de las zonas encontradas. Como se desprende de lo dicho, todas las abejas se dividen en 2 tipos: las abejas obreras recolectoras de néctar y las abejas exploradoras que buscan nuevas áreas. Las áreas de recolección tendrán un valor que se corresponderá con la cantidad de néctar en ellas. Además, existe una regla según la cual las áreas de rango inferior se desplazarán con respecto a una área de rango superior a lo largo de una línea que pasará por los centros de las áreas.

Esquemáticamente, la distribución de las abejas obreras por áreas se puede visualizar en la Figura 1.

Figura 1. Número de abejas en las áreas dependiendo de su rango.

En la figura, el área 1 tiene un rango más alto (contiene mayor cantidad de néctar), por lo que más abejas tenderán a volar allí. Según el número de abejas, podemos determinar visualmente que el área 4 tiene el rango (valor) más bajo. La información sobre el valor de cada área con abejas se comunicará en forma de baile especial. Cabe mencionar que cada colmena tiene su propio baile característico en el cual se codifica la dirección y la cantidad de néctar en el área.

Ahora, imaginemos que la ubicación del extremo global es el área donde hay más néctar, y esta área es la única, es decir, hay néctar en otros lugares, pero menos. Además, las abejas no viven en un plano, donde basta conocer dos coordenadas para determinar la ubicación de los sectores, sino en un espacio multidimensional en el que cada coordenada representa un parámetro de la función a optimizar. La cantidad de néctar encontrada será el valor de la función objetivo en este punto (si buscamos un máximo global; si buscamos un mínimo global, bastará con multiplicar la función objetivo por -1).

Como las áreas de recolección de néctar posee un cierto valor, solo el área con el rango más alto tendrá derecho a moverse (desplazamiento del centro) al punto con la mayor concentración de néctar. Las áreas de menor rango se desplazarán al centro de mayor concentración, pero se comprobarán en la intersección con un área de mayor rango. De esta manera, no se permitirá la concentración de abejas en un área pequeña y estrecha, y las abejas obreras servirán en el espacio de búsqueda de la forma más eficiente posible, evitando así el agotamiento de la fuente de alimento. En términos de optimización, esto eliminará o minimizará el atascamiento en los extremos locales. Después de que las áreas se dispersen y se desplacen entre sí por la cadena de rango hacia sus valores óptimos, las abejas exploradoras investigarán adicionalmente las zonas vecinas para determinar el diámetro.

Muchos apicultores recomiendan enviar abejas exploradoras a áreas aleatorias del espacio de búsqueda, pero mi experiencia muestra que el valor práctico de dicha "exploración" es cercano a cero y solo resulta útil para espacios de una y dos dimensiones, es decir, si hablamos de espacios multidimensionales, los grados de libertad aumentarán geométricamente, y será increíblemente difícil tropezar accidentalmente con una fuente de néctar más valiosa, así, los recursos de la colmena solo se desperdiciarán. Resulta mucho más útil enviar exploradores a áreas de búsqueda ya conocidas, pero no exactamente en la misma localización, sino fuera, en zonas limitadas por el radio de reconocimiento. Entonces las coordenadas no estarán dispersas, sino que se concentrarán específicamente en las zonas de las posibles fuentes de néctar.

Si las áreas se cruzan, deberemos desplazar el centro para que las áreas toquen solo los bordes. Esto se puede ver en la Figura 2.

Figura 2. El área con un rango inferior, deberá ser desplazada.

El rango de las áreas no se establecerá de forma estricta, sino que se formará dinámicamente; los hallazgos de las abejas exploradoras se asignarán al área en cuyas cercanías han volado. Si se descubre una fuente de alimento más valiosa, el centro del área se trasladará allí e incluso es posible que se convierta en el nuevo mejor centro de recolección de néctar. Entonces, las áreas restantes se desplazarán respecto a él: en otras palabras, se desplazarán en relación con él por la cadena de rango.

El método de transmisión de la información, que como ya sabemos se denomina baile de las abejas, es un elemento esencial de la estrategia de la colmena en su conjunto. Como tendremos que distribuir más racionalmente los recursos de la colmena disponibles para el procesamiento de las áreas, el número de abejas enviadas deberá ser proporcional al valor del área. Entonces, se enviará un número igual de abejas a las áreas con el mismo valor.

Vamos a ver el algoritmo en sí. Los pasos de ejecución se enumeran a continuación:

1. Todas las abejas vuelan de forma aleatoria por el espacio de búsqueda como exploradoras.
2. Medimos la cantidad de néctar obtenido de cada abeja.
3. Clasificamos las abejas.
4. Asignamos las áreas según la información de las abejas sobre la cantidad de néctar.
5. Enviamos las abejas obreras a la zona; cuanto más néctar haya en la zona, más abejas se enviarán.
6. Enviamos las abejas exploradoras en las cercanías de un área seleccionada al azar.
   
7. Medimos la cantidad de néctar obtenido de cada abeja.
8. Clasificamos las áreas según la cantidad de néctar.
   
9. Repetimos el paso 4 hasta que se cumpla el criterio de parada.

Para facilitar la percepción visual, hemos creado un esquema de bloques del algoritmo en la Figura 3.

Figura 3. Esquema de bloques del algoritmo.

Vamos a describir con más detalle el código del algoritmo Bee Colony.

La unidad lógica elemental y básica del algoritmo es una abeja, y se puede describir mediante una estructura. Recordemos que la ubicación de la abeja se indica usando las coordenadas pertenecientes a la zona en la que se ha recolectado el néctar y la cantidad de néctar. Las abejas de la colmena serán entonces representadas por un array; el acceso a ellas se podrá obtener según su índice.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bee
{
  double c []; //coordinates
  int    aInd; //area index
  double n;    //nectar
};
//——————————————————————————————————————————————————————————————————————————————

La segunda unidad lógica más grande será el área de recolección de néctar, que estará definida por el centro y el punto de mayor concentración de néctar, además de la cantidad de néctar que determinará el valor del área. En el área de mayor rango (la primera de la lista), coincidirán las coordenadas del centro y de la mayor concentración de néctar. Es posible que las áreas del segundo y el último rango de la lista no coincidan, ya que se han desplazado. La inicialización del área consistirá en resetear el indicador de la cantidad de néctar y distribuir las coordenadas en el número correspondiente de parámetros de la función que estamos optimizando.

//——————————————————————————————————————————————————————————————————————————————
struct S_Area
{
  void Init (int coordinatesNumber)
  {
    n = -DBL_MAX;

    ArrayResize (cC, coordinatesNumber);
    ArrayResize (cB, coordinatesNumber);
  }

  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

El baile de las abejas lo describiremos como una estructura cuyo array se corresponderá con el número de áreas.

//——————————————————————————————————————————————————————————————————————————————
struct S_BeeDance
{
  double start;
  double end;
};
//——————————————————————————————————————————————————————————————————————————————

La colmena se describirá como una clase. Aquí se establecerán: las áreas de búsqueda, las abejas, las mejores coordenadas y la mayor cantidad de néctar encontrada en todas las iteraciones. Además, aquí definiremos todos los métodos necesarios para clasificar las abejas y las áreas (para ellas existirán sus propias clasificaciones), así como para desplazar las abejas en áreas y las áreas entre sí. Aquí podemos ver las declaraciones de las funciones ya familiares para los algoritmos anteriores: la generación de números aleatorios distribuidos uniformemente, el escalado a un rango y la selección de un número de un rango con un paso.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ABC //Bees Hive
{
  //============================================================================
  public: S_Area areas     []; //nectar collection areas
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Bee  bees      []; //all the bees of the hive
  public: double cB        []; //best coordinates
  public: double nB;           //nectar of the best coordinates

  public: void InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP); //scout area radius

  public: void TasksForBees ();
  public: void CollectingNectar ();

  //============================================================================
  private: void   BeeFlight      (double &cC [] , S_Bee &bee);
  private: void   ScoutBeeFlight (double &cC [] , S_Bee &bee);
  private: void   MarkUpAreas    ();
  private: void   SortingBees    ();
  private: void   SortingAreas   ();
  private: double SeInDiSp       (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI      (double Min, double Max);
  private: double Scale          (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool Revers);

  private: int    coordinates;      //coordinates number
  private: int    beesNumber;       //the number of all bees
  private: int    workerBeesNumber; //worker bees number
  private: int    areasNumber;      //areas number
  private: S_Bee  beesT       [];   //temporary, for sorting
  private: S_Area areasT      [];   //temporary, for sorting
  private: int    indA        [];   //array for indexes when sorting
  private: double valA        [];   //array for nectar values when sorting
  private: int    indB        [];   //array for indexes when sorting
  private: double valB        [];   //array for nectar values when sorting
  private: double areasRadius [];   //radius for each coordinate
  private: double scoutRadius [];   //scout radius for each coordinate

  private: double collectionRadius;   //collection radius
  private: double scoutAreaRadius;    //scout area radius
  private: double hypersphereRadius;  //hypersphere radius
  private: double distHyperspCenters; //distance hyperspheres centers
  private: double scoutHyperspRadius; //scout hypersphere radius
  private: bool   scouting;           //scouting flag

  private: S_BeeDance beeDance [];    //bee dance
};
//——————————————————————————————————————————————————————————————————————————————

Cada nueva optimización deberá necesariamente comenzar con la inicialización de la clase: restableceremos el valor de la cantidad de néctar para toda la colmena y para las abejas por separado, así como para las áreas.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP)  //scout area radius
{
  MathSrand (GetTickCount ());
  scouting = false;
  nB       = -DBL_MAX;

  coordinates      = coordinatesP;
  beesNumber       = beesNumberP;
  workerBeesNumber = workerBeesNumberP;
  areasNumber      = areasNumberP < 3 ? 3 : areasNumberP;

  collectionRadius = collectionRadiusP; //collection radius
  scoutAreaRadius  = scoutAreaRadiusP;  //scout area radius

  ArrayResize (areas,  areasNumber);
  ArrayResize (areasT, areasNumber);
  for (int i = 0; i < areasNumber; i++)
  {
    areas  [i].Init (coordinates);
    areasT [i].Init (coordinates);
  }

  ArrayResize (beeDance, areasNumber);

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (indA, areasNumber);
  ArrayResize (valA, areasNumber);

  ArrayResize (areasRadius, coordinates);
  ArrayResize (scoutRadius, coordinates);
  for (int i = 0; i < coordinates; i++)
  {
    areasRadius [i] = (rangeMax [i] - rangeMin [i]) * collectionRadius;
    scoutRadius [i] = (rangeMax [i] - rangeMin [i]) * scoutAreaRadius;
  }

  double sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += areasRadius [i] * areasRadius [i];
  hypersphereRadius  = MathSqrt (sqr) * collectionRadius;

  distHyperspCenters = hypersphereRadius * 2.0;

  sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += scoutRadius [i] * scoutRadius [i];
  scoutHyperspRadius = MathSqrt (sqr) * scoutAreaRadius;

  ArrayResize (indB, beesNumber);
  ArrayResize (valB, beesNumber);

  ArrayResize (bees,  beesNumber);
  ArrayResize (beesT, beesNumber);
  for (int i = 0; i < beesNumber; i++)
  {
    ArrayResize (bees  [i].c, coordinates);
    ArrayResize (beesT [i].c, coordinates);
    bees  [i].n = -DBL_MAX;
    beesT [i].n = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método de clase más simple y también abierto será la distribución de tareas para las abejas. Aquí todo será muy simple, si las áreas aún no se han explorado, restableceremos el valor de néctar para toda la colmena, e inmediatamente comenzaremos a marcar las áreas. Luego llamaremos al método en cada época hasta obtener el valor de la función de aptitud.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::TasksForBees ()
{
  if (!scouting)
  {
    nB = -DBL_MAX;
  }
  MarkUpAreas ();
}
//——————————————————————————————————————————————————————————————————————————————

El segundo método público llamado en cada época realiza la inicialización tras obtener el valor de la función de aptitud. En este caso, si aún no se ha realizado el reconocimiento, clasificaremos las abejas según el valor del néctar y copiaremos las coordenadas y la cantidad de néctar de las primeras abejas de la lista en las áreas correspondientes. Si ya se realizado la exploración, copiaremos las coordenadas y la cantidad de néctar en el área de donde se ha recolectado el néctar, respectivamente, siempre que los resultados hayan mejorado, y también actualizaremos los mejores resultados para la colmena al completo.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::CollectingNectar ()
{
  if (!scouting)
  {
    SortingBees ();

    for (int a = 0; a <areasNumber; a++)
    {
      ArrayCopy (areas [a].cB, bees [a].c, 0, 0, WHOLE_ARRAY);
      areas [a].n = bees [a].n;
    }

    scouting = true;
  }
  else
  {
    //transfer the nectar to the hive---------------------------------------------
    for (int b = 0; b < beesNumber; b++)
    {
      if (bees [b].n > areas [bees [b].aInd].n)
      {
        ArrayCopy (areas [bees [b].aInd].cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        areas [bees [b].aInd].n = bees [b].n;
      }

      if (bees [b].n > nB)
      {
        ArrayCopy (cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        nB = bees [b].n;
      }
    }

    SortingAreas ();
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método MarkUpAreas () merece un análisis detallado, así que dividiremos el código en partes.

Antes de explorar las áreas y disponer de información sobre la búsqueda de flores para recolectar néctar, enviaremos las abejas de toda la colmena en un reconocimiento preliminar. En esta etapa, todas las abejas jugarán el papel de exploradoras. Como no hay información sobre el néctar, enviaremos a las exploradoras en una dirección aleatoria, generando números aleatorios distribuidos uniformemente en el rango de coordenadas.

//if the areas is not scouting - send all the bees to scouting----------------
if (!scouting)
{
  for (int b = 0; b < beesNumber; b++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      bees [b].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      bees [b].c [c] = SeInDiSp  (bees [b].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Después de explorar las áreas, deberemos copiar las coordenadas de la máxima concentración de néctar en el centro del área. En otras palabras, trasladaremos el área al mejor lugar. Una vez realizada esta acción, deberemos asegurarnos de que el área no se cruce con un área de rango superior. Podremos verificar la intersección de las áreas midiendo la distancia entre sus centros. Las áreas se cruzarán si la distancia entre los centros es inferior a dos radios (uno de los parámetros del algoritmo). Si detectamos una intersección, el área se transferirá a un punto a una distancia de dos radios, mientras que las coordenadas del mejor resultado logrado (las coordenadas de la máxima concentración de néctar) permanecerán en el mismo lugar. Por consiguiente, las áreas estarán en constante movimiento. Las mejores áreas obligarán al resto a cambiar, y el resto, cambiando, podrá alcanzar una fuente de alimento más rica, convirtiéndose en la mejor después de la clasificación, que sucederá en el siguiente método.

for (int s = 0; s < areasNumber; s++)
{
  //move the center of the area to the best point in with more nectar-------
  ArrayCopy (areas [s].cC, areas [s].cB, 0, 0, WHOLE_ARRAY);

  //ordinary area-----------------------------------------------------------
  if (s != 0)
  {
    //check if there is no intersection of a region with a region of higher rank
    //measure the distance from the centers of the regions
    double centersDistance = 0.0;

    for (int c = 0; c < coordinates; c++) centersDistance += pow (areas [s].cC [c] - areas [s - 1].cC [c], 2.0);
    centersDistance = MathSqrt (centersDistance);

    //the areas intersect, then need to move the current area
    if (centersDistance < distHyperspCenters)
    {
      double incrementFactor = (distHyperspCenters - centersDistance) / centersDistance;
      double coordDistance   = 0.0;

      for (int c = 0; c < coordinates; c++)
      {
        coordDistance = areas [s].cC [c] - areas [s - 1].cC [c];
        areas [s].cC [c] = areas [s].cC [c] + (coordDistance * incrementFactor);

        areas [s].cC [c] = SeInDiSp (areas [s].cC [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}

Aquí es donde ocurrirá el mencionado baile de las abejas. Usando la información sobre la dirección y la cantidad de néctar en las áreas, y utilizando además un componente aleatorio, marcaremos el área de distribución de un número aleatorio de tal forma que la probabilidad de que una abeja elija un área en la siguiente iteración sea proporcional a la cantidad de néctar en dicha área. En palabras simples, en una recta numérica, trazaremos segmentos cuyas longitudes se corresponderán con la diferencia entre el valor de néctar de cada área y la peor área.

//send bees to the marked areas-----------------------------------------------
double r = 0.0;

beeDance [0].start = bees [0].n;
beeDance [0].end   = beeDance [0].start + (bees [0].n - bees [areasNumber - 1].n);

for (int a = 1; a < areasNumber; a++)
{
  if (a != areasNumber - 1)
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a].n - bees [areasNumber - 1].n);
  }
  else
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a - 1].n - bees [a].n) * 0.1;
  }
}

En esta parte del código del método, tendrá lugar una selección aleatoria del área, con la probabilidad transmitida por los bailes de las abejas para las abejas no obreras. Para ello, generaremos un número aleatorio en el rango que se ha creado marcando con un baile en la recta numérica. Para las exploradoras, en cambio, los bailes no importarán, ya que volarán en cualquier caso con el mismo grado de probabilidad en las cercanías de cualquiera de las áreas, ampliando así las capacidades de búsqueda de la estrategia de abejas de la colmena en su conjunto. Al igual que en la naturaleza, cada miembro de la colmena tendrá un cierto valor al desempeñar su papel.

for (int b = 0; b < beesNumber; b++)
{
  if (b < workerBeesNumber)
  {
    r = RNDfromCI(beeDance [0].start, beeDance [areasNumber - 1].end);
        
    for (int a = 0; a < areasNumber; a++)
    {
      if (beeDance [a].start <= r && r < beeDance [a].end)
      {
        bees [b].aInd = a;
        break;
      }
    }

    BeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
  else
  {
    //choose the area to send the bees there
    r = RNDfromCI (0.0, areasNumber - 1);

    bees [b].aInd = (int)r; //area index

    ScoutBeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
}

Este método privado implementará el vuelo de una abeja. Aunque a primera vista todo parezca incomprensible y complicado, aquí todo es bastante sencillo. La abeja volará a la zona con un desplazamiento de probabilidad cúbico más cercano al centro. Es decir, la probabilidad decrecerá desde el centro hacia los límites del área. Tenga en cuenta que este será el centro del área y no la mejor posición anteriormente encontrada. Incluso en esta simple acción, podremos monitorear la estrategia de las abejas, lo cual garantizará una búsqueda continua de nuevas fuentes de alimento.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::BeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (0.0, 1.0);
    r  = r * r * r;
    r = Scale (r, 0.0, 1.0, 0.0, areasRadius [c], false);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

A diferencia del método anterior, aquí se describe el vuelo de la abeja exploradora. La abeja vuela fuera del área dentro del radio especificado en los ajustes del algoritmo. A pesar de que los ajustes son los mismos, los radios se calcularán de antemano al inicializarse la clase, ya que los rangos de coordenadas podrían diferir, por lo que los radios serán los correspondientes. Para iniciar el vuelo de una abeja exploradora, deberemos generar un número aleatorio en el rango que va desde el radio del área hasta la suma del radio del área y el radio de exploración; luego simplemente sumaremos el valor resultante al centro del área. Con este método tan simple, la abeja exploradora se encontrará en las inmediaciones de la zona por casualidad, mientras que las coordenadas no estarán dispersas por todo el espacio de búsqueda.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::ScoutBeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (areasRadius [c], areasRadius [c] + scoutRadius [c]);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Existen dos métodos específicos en el algoritmo: la clasificación de abejas y la clasificación de áreas. No tiene sentido describirlos, se trata de una clasificación de burbuja simple. Suelo usarlo en casi todos los algoritmos de optimización (donde se requiere clasificación), porque este método es simple y fácil de modificar para tareas específicas, ofreciendo la mismo tiempo una de las mejores velocidades entre todos los métodos de clasificación.

//——————————————————————————————————————————————————————————————————————————————
//Sorting of bees
void C_AO_ABC::SortingBees ()
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Sorting of areas
void C_AO_ABC::SortingAreas ()
//——————————————————————————————————————————————————————————————————————————————

Ha llegado el momento de recopilar y compilar todo el código analizado. Ejecutando el banco de pruebas, podremos ver las siguientes animaciones que muestran el comportamiento del algoritmo de la abeja. Las abejas se observan claramente en áreas separadas: se ve cómo las áreas se desplazan, reemplazándose unas a otras. La precisión y el número de "enjambres" peculiares dependerán de los ajustes del algoritmo.

ABC en la función de prueba Skin.

ABC en la función de prueba Forest.

ABC en la función de prueba Megacity.

Aquí tenemos los resultados del algoritmo en las funciones de prueba:

2022.11.21 13:14:06.669    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:14:28.483    Test_AO_ABC1 (EURUSD,M1)    1 Skin's; Func runs 1000 result: 14.018634225602678; Func runs 10000 result: 14.06060189007221
2022.11.21 13:14:28.483    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.99772; Score2: 1.00000
2022.11.21 13:14:50.310    Test_AO_ABC1 (EURUSD,M1)    20 Skin's; Func runs 1000 result: 7.459929501115262; Func runs 10000 result: 8.320771456653533
2022.11.21 13:14:50.310    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.64085; Score2: 0.68769
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.69267387794685; Func runs 10000 result: 4.838631770950824
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.49029; Score2: 0.49823
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:15:51.880    Test_AO_ABC1 (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.063567301715784; Func runs 10000 result: 15.912087696850861
2022.11.21 13:15:51.880    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.94435; Score2: 0.99755
2022.11.21 13:16:13.721    Test_AO_ABC1 (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.0207584941876133; Func runs 10000 result: 4.1918977577943295
2022.11.21 13:16:13.721    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.18937; Score2: 0.26279
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.2004991531402736; Func runs 10000 result: 1.288357831462411
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.07526; Score2: 0.08077
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:17:23.227    Test_AO_ABC1 (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 10.4; Func runs 10000 result: 15.0
2022.11.21 13:17:23.227    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.69333; Score2: 1.00000
2022.11.21 13:17:44.936    Test_AO_ABC1 (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.5499999999999998; Func runs 10000 result: 2.31
2022.11.21 13:17:44.936    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.10333; Score2: 0.15400
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    500 Megacity's; Func runs 1000 result: 0.6180000000000001; Func runs 10000 result: 0.6568
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.04120; Score2: 0.04379
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    All score for C_AO_ABC: 0.49447371765340953

En la impresión de los resultados podemos ver que el algoritmo ha convergido al 100% para las dos funciones de prueba de las dos variables, lo cual supone un excelente indicador de convergencia. Aun así, resulta prematuro juzgar el resto de los resultados, es mejor poner los resultados en una tabla y sacar conclusiones en comparación con otros algoritmos de optimización.

3. Versión modificada

Vamos a hablar ahora de un momento interesante. Al desarrollar y diseñar cualquier algoritmo de optimización, siempre nos surge la pregunta: "¿Funcionará el algoritmo según lo previsto o habrá un error en alguna parte del código?". El hecho es que el proceso de búsqueda estocástica resulta aleatorio por su propia naturaleza, así que no está claro si los resultados de la optimización han sido fruto del algoritmo o algún error se nos has escapado por alguna parte, y el resultado es realmente no aleatorio. Entonces, al escribir el algoritmo de la colonia de abejas, encontré un fenómeno similar. Durante la primera prueba de las cinco en el conjunto de prueba, el algoritmo obviamente se atascó en los lugares desde los que inició la búsqueda, sin intentar converger en absoluto. Lo interesante es que este error se resolvió de una manera completamente increíble desde el punto de vista de la lógica. Bastó con inicializar la clase de colmena una segunda vez adicional en la primera época, y esto a pesar de que la clase ya había sido inicializada antes del comienzo de las épocas (p. 142 en el archivo Test_AO_ABC.mq5). Si alguien logra desentrañar este misterio, estaré encantado de escuchar la solución en los comentarios al artículo.

En parte por lo anterior, y en parte por los resultados no completamente satisfactorios de las primeras pruebas (aunque luego quedó claro que necesitaba experimentar con la configuración del algoritmo), se me ocurrió la idea de cambiar la estrategia de búsqueda de las abejas. En la versión original, las abejas volaban en una cantidad proporcional al valor del área, mientras que en el nuevo algoritmo, debería haber un número fijo de abejas en cada área. Es decir, independientemente del rango de la zona, cada una de ellas tendrá siempre el mismo número de abejas. Por lo tanto, el área se ha transformado lógicamente en el concepto de "Enjambre de abejas".

Ahora, en lugar de la estructura del área, tendremos una estructura así:

//——————————————————————————————————————————————————————————————————————————————
struct S_BeesSwarm
{
  void Init (int coordinatesNumber, int beesNumber)
  {
    ArrayResize (bees, beesNumber);

    for (int i = 0; i < beesNumber; i++)
    {
      ArrayResize (bees [i].c, coordinatesNumber);
      bees [i].n = -DBL_MAX;
    }

    n = -DBL_MAX;

    ArrayResize     (cC, coordinatesNumber);
    ArrayInitialize (cC, -DBL_MAX);
  }

  S_Bee  bees []; //bees
  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Esta estructura también tiene una función de inicialización, pero además existe el array bees[].

En general, el resto del código es muy similar a la versión clásica y no nos centraremos demasiado en él: podrá leer el código completo en el archivo adjunto al artículo. Merece la pena prestar especial atención a las diferencias en la lógica de los algoritmos. Paso a paso, se verá así:

1. Creamos un centro para el primer enjambre y colocamos las abejas alrededor del centro.
2. Creamos un centro para los enjambres posteriores y verificamos que la distancia del centro a los enjambres anteriores sea mayor o igual a R * 2 (dos radios); a continuación, colocamos las abejas en los alrededores del centro.
3. Enviamos las abejas de un enjambre de exploradoras para que cada una de las abejas esté más lejos que los otros enjambres en una distancia mayor o igual a R (radio).
4. Obtenemos el valor de la función de aptitud para todas las abejas.
5. Clasificamos los enjambres.
6. Colocamos las abejas alrededor del centro de cada enjambre.
7. Repetimos desde el punto 4 hasta que se cumpla el criterio de parada.

Podemos ver que existe una diferencia fundamental en la estrategia de búsqueda. Mientras que en la versión clásica cada área puede tener un número diferente de abejas, aquí los enjambres son siempre del mismo tamaño, esto se hace para garantizar que las áreas continúen siendo exploradas incluso si la fuente de alimento se seca, proporcionando así una exploración más completa de la superficie en el hiperespacio. Las pruebas han confirmado la legitimidad de este enfoque, los resultados están mejorando. Las abejas exploradoras no vuelan en las proximidades de las áreas, sino que entran en áreas libres del espacio, además, siguiendo las reglas de las áreas, como en la versión clásica. Para ser completamente precisos, debemos señalar que en la versión clásica de las abejas, las exploradoras no se comportan como se describe, porque las abejas se dispersan en una dirección completamente aleatoria sin importarles que puedan meterse en áreas previamente exploradas, perdiendo de esta forma su función básica de exploración. El último enjambre de la matriz es el enjambre explorador. Para este enjambre, también se aplica la regla "no entres en el espacio ajeno", pero no para el enjambre en su conjunto, sino para las abejas exploradoras personalmente.

Aquí tenemos las impresiones de los resultados de la versión modificada:

2022.11.21 21:53:19.695    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:53:25.104    Test_AO_ABCm (EURUSD,M1)    1 Skin's; Func runs 1000 result: 14.009060385607679; Func runs 10000 result: 14.060603974847265
2022.11.21 21:53:25.104    Test_AO_ABCm (EURUSD,M1)    Score1: 0.99720; Score2: 1.00000
2022.11.21 21:53:30.452    Test_AO_ABCm (EURUSD,M1)    20 Skin's; Func runs 1000 result: 7.826824877236677; Func runs 10000 result: 8.735832346695558
2022.11.21 21:53:30.452    Test_AO_ABCm (EURUSD,M1)    Score1: 0.66082; Score2: 0.71028
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.645933304640949; Func runs 10000 result: 4.844246724239038
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    Score1: 0.48774; Score2: 0.49853
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:53:45.363    Test_AO_ABCm (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.44507700105064; Func runs 10000 result: 15.662273922787355
2022.11.21 21:53:45.363    Test_AO_ABCm (EURUSD,M1)    Score1: 0.96827; Score2: 0.98188
2022.11.21 21:53:50.697    Test_AO_ABCm (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.6397442648278924; Func runs 10000 result: 4.759146560755886
2022.11.21 21:53:50.697    Test_AO_ABCm (EURUSD,M1)    Score1: 0.22818; Score2: 0.29836
2022.11.21 21:54:01.111    Test_AO_ABCm (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.2349621811342104; Func runs 10000 result: 1.4191098624570897
2022.11.21 21:54:01.111    Test_AO_ABCm (EURUSD,M1)    Score1: 0.07742; Score2: 0.08897
2022.11.21 21:54:01.112    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:54:06.434    Test_AO_ABCm (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 12.0; Func runs 10000 result: 15.0
2022.11.21 21:54:06.434    Test_AO_ABCm (EURUSD,M1)    Score1: 0.80000; Score2: 1.00000
2022.11.21 21:54:11.768    Test_AO_ABCm (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.7; Func runs 10000 result: 2.35
2022.11.21 21:54:11.768    Test_AO_ABCm (EURUSD,M1)    Score1: 0.11333; Score2: 0.15667
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    500 Megacity's; Func runs 1000 result: 0.572; Func runs 10000 result: 0.67
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    Score1: 0.03813; Score2: 0.04467
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    All score for C_AO_ABCm: 0.508357869056105

Por la impresión, podemos ver que el algoritmo modificado ha repetido el éxito en dos funciones con dos variables, mostrando una convergencia del 100%. En general, los resultados han mejorado, y la puntuación final ha aumentado: 0.50836. Desafortunadamente, esto no supone una mejora cardinal en los resultados. Los problemas de convergencia en funciones con un gran número de variables son comparables a la versión clásica de la implementación del algoritmo.

Por cierto, no ocurre el bug que provoca el reinicio de la colmena en la versión modificada.

4. Resultados de la prueba

AO	Runs	Skin			Forest			Megacity (discrete)			Final result
		2 params (1 F)	40 params (20 F)	1000 params (500 F)	2 params (1 F)	40 params (20 F)	1000 params (500 F)	2 params (1 F)	40 params (20 F)	1000 params (500 F)
ACOm	1000	0,99502	0,69826	0,50498	0,99087	0,22374	0,08408	0,78667	0,11667	0,04224	0,54688
	10000	0,99599	0,86403	0,58800	0,99302	0,65571	0,17442	0,78667	0,26133	0,08208
RND	1000	0,98744	0,61852	0,49408	0,89582	0,19645	0,14042	0,77333	0,19000	0,14283	0,51254
	10000	0,99977	0,69448	0,50188	0,98181	0,24433	0,14042	0,88000	0,20133	0,14283
ABCm	1000	0,99720	0,66082	0,48774	0,96827	0,22818	0,07742	0,80000	0,11333	0,03813	0,50836
	10000	1,00000	0,71028	0,49853	0,98188	0,29836	0,08897	1,00000	0,15667	0,04467
ABC	1000	0,99772	0,64085	0,49029	0,94435	0,18937	0,07526	0,69333	0,10333	0,04120	0,49447
	10000	1,00000	0,68769	0,49823	0,99755	0,26279	0,08077	1,00000	0,15400	0,04379
PSO	1000	0,98436	0,72243	0,65483	0,71122	0,15603	0,08727	0,53333	0,08000	0,04085	0,47695
	10000	0,99836	0,72329	0,65483	0,97615	0,19640	0,09219	0,82667	0,10600	0,04085

Vamos a resumir. Sorprendentemente, el algoritmo de la colonia de abejas ha mostrado una convergencia del 100% en las cinco pruebas en las dos funciones de prueba, tanto Skin suavizada como Megacity discreta, demostrando así una velocidad y una calidad de convergencia fenomenales. Eso sí, esto solo se aplica a funciones con dos variables. En términos de escalabilidad, el algoritmo se muestra menos capaz que otros participantes en la tabla de calificación: las funciones con muchas variables en la colonia de abejas se le dan con dificultad, como podemos ver tanto en la animación del banco de pruebas como en los resultados de la tabla.

El algoritmo ABC requiere que el usuario opere con varios ajustes paramétricos, como el tamaño del enjambre, la cantidad de abejas exploradoras y los radios del área. Si estos ajustes no se eligen adecuadamente para una aplicación en particular, el algoritmo puede converger prematuramente o no converger en absoluto. Además, el algoritmo ABC tiene desventajas como la convergencia lenta en funciones complejas, la captura de soluciones locales y propiedades de búsqueda mediocres.

Ventajas:
1. Es relativamente rápido.
2. Muestra una convergencia fenomenal para funciones suaves y discretas con pocas variables.

Desventajas:
1. Los parámetros del algoritmo ejercen una fuerte influencia en el resultado.
2. No es universal.
3. Se queda atrapado en los extremos locales.
4. Escalabilidad media.