Algoritmos de optimización de la población: Optimización de colonias de hormigas (ACO)

El gran secreto de cualquier comportamiento es el comportamiento social...

F. Bartlett

Contenido:

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

1. Introducción

En 1992, el investigador belga Marco Dorigo creó un modelo matemático que describe científicamente el proceso de inteligencia colectiva en una colonia de hormigas. Ese mismo año, lo publicó en su tesis doctoral y lo implementó como un algoritmo.

La optimización de colonias de hormigas (ACO) es un método de búsqueda estocástica basado en la población que se encarga de resolver una amplia gama de problemas de optimización combinatoria. El ACO se basa en el concepto de estigmergia. En 1959, Pierre-Paul Grassé inventó la teoría de la estigmergia para explicar el comportamiento de las termitas a la hora de construir sus nidos. La estigmergia consta de dos palabras griegas: stigma - signo y ergon - acción.

La definición canónica es un tipo indirecto de interacción entre los miembros de una población, prolongada en el tiempo, mediante la interacción con el medio ambiente. Es decir, uno de los agentes deja un rastro o de alguna manera modifica el local para que, al entrar en su área, otro agente reciba alguna información. Para las hormigas, la estigmergia son las feromonas. Un ejemplo de estigmergia es la comunicación de las hormigas durante la búsqueda de alimento: las hormigas se comunican indirectamente entre sí, dejando rastros de feromonas en el suelo y, por lo tanto, influyen en los procesos de toma de decisiones de otras hormigas. Esta forma simple de comunicación entre hormigas individuales da lugar a un comportamiento complejo y juega un papel clave en las capacidades de la colonia como un todo.

Las hormigas son insectos sociales, viven en colonias, y su comportamiento se basa en la búsqueda de comida. Durante esa búsqueda, las hormigas deambulan por sus colonias, desplazándose repetidamente de un lugar a otro en busca de alimento y depositando en el suelo un compuesto orgánico llamado feromona. Así, las hormigas se comunican entre sí usando rastros de feromonas.

Cuando una hormiga encuentra algo de comida, se lleva consigo todo lo que puede cargar. De regreso, deposita feromonas por el camino, dependiendo de la cantidad y calidad de los alimentos. Las hormigas son capaces de olor las feromonas, y como resultado, pueden detectar dicho olor y seguir la ruta marcada. Cuanto mayor sea el nivel de feromonas, mayor será la probabilidad de elegir ese camino concreto, y cuantas más hormigas pasen por un camino en particular, mayor será la presencia de feromonas en dicha ruta.

Veamos esto con un ejemplo. Supongamos que existen dos formas de obtener la comida para la colonia. Primero, sin feromonas en la tierra. Entonces, la probabilidad de elegir estos dos caminos será igual, lo cual implicará un 50%. Supongamos que dos hormigas eligen dos caminos diferentes para comer (la probabilidad de elegir estos caminos es de cincuenta y cincuenta), y las distancias de estos dos caminos son diferentes. La hormiga que toma la ruta más corta llegará a la comida antes que la otra. Cuando encuentre comida, se llevará una parte y regresará a la colonia. Mientras sigue su camino de regreso, depositará feromonas en el suelo. La hormiga que tome el camino más corto llegará antes a la colonia.

Cuando la tercera hormiga quiera salir en busca de alimento, tomará el camino con la distancia más corta, dependiendo del nivel de feromonas en el suelo. Como el camino más corto tiene más feromonas que el más largo, la tercera hormiga seguirá el camino con más feromonas. Para cuando la hormiga, siguiendo el camino más largo, regrese a la colonia, muchas más hormigas ya habrán pasado por el camino con niveles más altos de feromonas. Luego, cuando otra hormiga intente llegar a su destino (la comida) desde la colonia, encontrará que cada camino tiene el mismo nivel de feromonas, así que elegirá uno al azar. Repitiendo este proceso una y otra vez, después de un tiempo, el camino más corto tendrá más feromonas que los demás y mostrará una mayor probabilidad de ser seguido, y todas las hormigas tomarán el camino más corto la próxima vez.

El algoritmo ACO es una especie de algoritmo de inteligencia de enjambre: modelando el proceso de búsqueda de alimento de una colonia de hormigas, se establece el camino más corto en varios entornos usando el mecanismo de transferencia de información interna de la colonia de hormigas. Durante su actividad, las hormigas dejarán feromonas y las siguientes hormigas podrán elegir un camino según las feromonas dejada por las hormigas anteriores. Cuanto mayor sea la concentración de las feromonas que quedan en el camino, mayor será la probabilidad de que la hormiga elija este camino. Al mismo tiempo, la concentración de la feromona se volatilizará con el tiempo. Por lo tanto, gracias al comportamiento de la colonia de hormigas, sus individuos aprenden y optimizan constantemente un mecanismo de retroalimentación para determinar la ruta de alimentación más corta. Según las características del algoritmo ACO, este se utiliza ampliamente en la planificación de rutas.

2. Principios del algoritmo

En el ACO, un conjunto de agentes de software llamados hormigas artificiales buscan soluciones buenas a un problema de optimización dado. Para aplicar el ACO, el problema de optimización se convierte en el problema de encontrar el mejor camino en un gráfico ponderado. Las hormigas artificiales (en lo sucesivo denominadas hormigas) construyen soluciones gradualmente, moviéndose a lo largo del gráfico. El proceso de construcción de una solución es estocástico y dependerá del modelo de feromonas, es decir, el conjunto de parámetros asociados a los componentes del gráfico (nodos o aristas), cuyos valores serán modificados por las hormigas durante la ejecución.

Vamos a analizar el algoritmo para el problema del viajante de comercio. Se nos ofrece un conjunto de ubicaciones (por ejemplo, ciudades) y las distancias entre ellas. El problema consiste en hallar un camino cerrado de longitud mínima que visite cada ciudad una sola vez, un gráfico definido por la asociación de un conjunto de ciudades con un conjunto de vértices del gráfico. Este gráfico se llama gráfico de construcción. Como resulta posible moverse de cualquier ciudad dada a cualquier otra ciudad, el gráfico de construcción estará completamente conectado y el número de vértices será igual al número de ciudades. Nosotros tenemos que establecer las longitudes de borde entre los vértices proporcionales a las distancias entre las ciudades representadas por esos vértices, y asociar los valores de las feromonas y los valores heurísticos con los bordes de gráfico. Los valores de las feromonas cambiarán en tiempo de ejecución y representarán la experiencia acumulada de la colonia de hormigas, mientras que los valores heurísticos serán valores dependientes del problema.

Las hormigas construirán soluciones de la forma siguiente. Cada hormiga partirá de una ciudad seleccionada al azar (parte superior del gráfico de construcción). Luego, en cada paso de la construcción, se moverá a lo largo de los bordes del gráfico. Cada hormiga almacenará la memoria de su camino y, en los pasos posteriores, elegirá entre los bordes que no conducen a los vértices ya visitados. La hormiga habrá construido una solución tan pronto como haya visitado todos los vértices del gráfico. En cada paso de la construcción, la hormiga elegirá de forma probabilística un borde a seguir de entre los que conducen a los vértices aún no visitados. La regla probabilística se basa en los valores de las feromonas y la información heurística: cuanto mayor sea la feromona y el valor heurístico asociado con un borde, mayor será la probabilidad de que la hormiga elija ese borde en particular. Una vez todas las hormigas hayan completado su viaje, las feromonas en los bordes se actualizarán. Cada uno de los valores de las feromonas se reducirá inicialmente en un determinado porcentaje. Este procedimiento se repetirá hasta que se cumpla el criterio de finalización.

La comunicación basada en feromonas es uno de los métodos de comunicación más eficaces y extendidos en la naturaleza. La feromona es utilizada por insectos sociales como abejas, hormigas y termitas para la comunicación entre agentes. Debido a su viabilidad, las feromonas artificiales se han adoptado en sistemas de robots múltiples y enjambres.

¿Cómo podremos entender que nuestras hormigas realmente han encontrado el camino más corto? Existe un magnífico ejemplo para comprobar esto: los puntos dispuestos en un círculo. Para estos, el camino más corto siempre será el mismo: un círculo.  

El primer algoritmo ACO se denominó sistema de hormigas y estaba destinado a resolver el problema del viajante de comercio, cuyo objetivo era encontrar el camino más corto de ida y vuelta para conectar varias ciudades. El algoritmo general resulta relativamente simple y se basa en un conjunto de hormigas, cada una de las cuales efectúa una de las posibles rondas de ciudades. En cada etapa, la hormiga elegirá un camino de una ciudad a otra según algunas reglas:

1. Deberá visitar cada ciudad exactamente una vez;
2. Resultará menos probable que se seleccione una ciudad distante (visibilidad);
3. Cuanto más intenso sea el rastro de feromonas depositado en el límite entre dos ciudades, más probable resultará que se elija este límite;
4. Tras completar su camino, la hormiga depositará más feromonas en todos los bordes que ha recorrido si el camino es corto;
5. Después de cada iteración, los rastros de feromonas se evaporarán.

Figura 1. Ejemplo de caminos posibles en cinco puntos nodales.

3. Versión modificada

Se conocen varias de las variantes populares de los algoritmos ACO. Vamos a enumerarlas:

Sistema de hormigas (AS).
El sistema de hormigas es el primer algoritmo ACO.

Sistema de colonias de hormigas (ACS).
En el algoritmo del sistema de colonias de hormigas, el sistema de hormigas original se ve modificado en tres aspectos:
1. La selección de los bordes está desplazada hacia la explotación (es decir, favorece la probabilidad de elegir los bordes más cortos con más feromonas);
2. Al construir una solución, las hormigas cambian el nivel de feromonas en los bordes elegidos aplicando una regla de actualización de feromona local;
3. Al final de cada iteración, solo la mejor hormiga puede actualizar los rastros aplicando la regla de actualización de feromona global modificada.

Sistema de hormigas de élite.
En este algoritmo, la mejor solución global deposita la feromona en su rastro después de cada iteración (incluso si el rastro no se ha revisado) junto con todas las demás hormigas. El objetivo de la estrategia de élite consiste en dirigir la búsqueda de todas las hormigas para construir una solución que contenga enlaces a la mejor ruta actual.

Sistema de hormigas Max-Min (MMAS).
Este algoritmo controla el número máximo y mínimo de feromonas en cada rastro: solo el mejor tour global o el mejor tour repetido pueden añadir feromonas a su rastro. Para evitar el estancamiento del algoritmo de búsqueda, el rango de posibles cantidades de feromonas en cada rastro se ve limitado por el intervalo [τ max ,τ min]. Todos los bordes se inicializan con τ max para acelerar la investigación de la solución. Los rastros se reinicializan a τ max cuando se acercan al estancamiento.

Sistema de hormigas basado en rangos (Asrank).
Todas las soluciones se clasifican en función de su longitud. Solo un número fijo de las mejores hormigas en esta iteración puede actualizar sus experiencias. La cantidad de feromonas depositada se pondera para cada solución, de modo que las soluciones con caminos más cortos depositen más feromonas que las soluciones con caminos más largos.

Optimización de colonias de hormigas paralelas (PACO).
Se ha desarrollado un sistema de colonias de hormigas (ACS) con estrategias de comunicación.
Las hormigas artificiales se dividen en varios grupos. Se ofrecen siete métodos de comunicación para actualizar los niveles de feromonas entre los grupos de la ACS que trabajan en el problema del viajante de comercio.

Colonia de hormigas ortogonales continuas (COAC).
El mecanismo de depósito de feromonas COAC permite a las hormigas buscar soluciones de forma colaborativa y eficiente. Usando el método de diseño ortogonal, las hormigas en el área permitida pueden explorar rápida y eficazmente las áreas elegidas con capacidades de búsqueda global y precisión mejoradas. El método de diseño ortogonal y el método de ajuste adaptativo del radio también se pueden extender a otros algoritmos de optimización para ofrecer ventajas más amplias en la resolución de problemas prácticos.

Optimización recursiva de la colonia de hormigas.
Esta es una forma recursiva de colonias de hormigas que divide toda el área de búsqueda en varios subdominios y resuelve el problema en estos subdominios. En esta optimización, se comparan los resultados de todos los subdominios y los mejores pasan al siguiente nivel. Los subdominios correspondientes a los resultados seleccionados se subdividen aún más y el proceso se repite hasta obtener un resultado con la precisión deseada. Este método se ha probado en problemas de inversión geofísica incorrecta y funciona bien.

Los algoritmos de colonia de hormigas analizados anteriormente se desarrollaron originalmente para resolver problemas de optimización en gráficos. El problema se integra en dichos algoritmos y las condiciones del problema se dan como parámetros del algoritmo: las coordenadas de los nodos del gráfico. Por consiguiente, los algoritmos basados en los principios ACO son altamente especializados. Estos algoritmos no resultan aplicables para nuestras tareas, pues no usamos coordenadas fijas, pueden ser cualquiera, incluidas las mismas. Para resolver una amplia gama de problemas de optimización en el campo del comercio con instrumentos financieros, incluido el entrenamiento de redes neuronales, necesitaremos desarrollar un nuevo algoritmo, universal, para que pueda superar nuestras pruebas especiales, es decir, deberá ser un ACO nuevo y sin análogos.

Vamos a reflexionar sobre el concepto básico del algoritmo. Al igual que en la versión canónica, tendremos una colonia de hormigas. No podremos marcar con feromonas los caminos recorridos: las hormigas pueden ir a cualquier parte de un espacio multidimensional, memorizar y guardar rutas, y sobre todo con un paso continuo no parece adecuado, porque la probabilidad de ir por la misma ruta tiende a cero. Además, no resulta necesario memorizar nodos en absoluto, ya que no existe la tarea del paso secuencial sin repeticiones; es necesario eliminar el problema del algoritmo. Entonces, ¿qué hacemos? Teniendo en cuenta lo que acabamos de mencionar, en esta etapa no está del todo claro en qué dirección avanzar en el desarrollo del concepto.

Bueno, una vez más, vamos a marcar para nosotros mismos los puntos principales que distinguen nuestro nuevo algoritmo del canónico:

1. No hay puntos fijos en el espacio.

2. No tenemos necesidad de recorrer el camino solo en un cierto orden.

3. Como no hay caminos, no hay nada que debamos marcar con feromonas.

Luego, en orden, averiguaremos qué tenemos, considerando la idea de una colonia de hormigas. Podemos marcar con feromonas los mismos puntos donde estuvieron las hormigas, y no el camino recorrido por estas. Tomaremos el valor de la función de adecuación como el número de feromonas en la ubicación de la hormiga en el momento de la iteración actual. Luego las hormigas tendrán que moverse hacia las coordenadas donde hayan más feromonas. No obstante, podemos encontrarnos con un problema cuando todas las hormigas simplemente corren hacia un punto, el que tiene más feromonas, y esta no es necesariamente la mejor solución al problema, considerando que los puntos son las variables de la función optimizada. Recordamos que en el ACO clásico también importa la longitud del camino al nodo: cuanto más corto sea el camino elegido, mejor. Así que deberemos calcular la distancia desde la ubicación actual hasta donde debe ir la hormiga, y el siguiente lugar será donde se encuentren las otras hormigas, es decir, aceptaremos el concepto según el cual las hormigas se mueven unas hacia otras con cierta aleatoriedad.

¿Qué tipo de aleatoriedad podremos añadir al movimiento?

• Primero, añadiremos un factor aleatorio al elegir la siguiente posición, PheromoneEffect_P.
• En segundo lugar, añadiremos un factor aleatorio, considerando la distancia a la siguiente posición, PathLengthEffect_P (cuanto menor sea la distancia, más preferible resultará la elección).

Así, tenemos dos criterios para elegir la siguiente posición, la cantidad de feromona en cada posición específica donde se ubican las hormigas y la distancia entre todos estos puntos en pares. No obstante, incluso si hacemos esto usando solo dichos criterios de selección, las hormigas se moverán en el espacio por los bordes de una figura imaginaria, cuyos nodos serán su propia ubicación, y no habrá progreso en encontrar un lugar mejor.

En este caso, añadiremos el radio de influencia de la feromona PheromoneRadius_P (coeficiente de la distancia entre puntos), dentro del cual las hormigas pueden percibir esta; luego las hormigas podrán deslizarse más allá del punto al que se han desplazado. Esto conferirá un grado adicional de libertad a las hormigas al moverse en un espacio multidimensional.

Y para que las hormigas exploren nuevas áreas, les deberemos permitir desviarse del vector de dirección a lo largo de cualquiera de las coordenadas; para ello, introduciremos el coeficiente PathDeviation_P, que ofrecerá una desviación respecto al incremento en una coordenada específica. Como tenemos un espacio multidimensional, siguiendo el vector de desplazamiento, algunas coordenadas podrán tener un incremento positivo, mientras que otras podrán tener uno negativo, y los incrementos podrán tener diferentes valores de módulo. Este coeficiente solo permitirá tener en cuenta estos momentos y ofrecerá cierto grado de libertad a las hormigas en la búsqueda de alimento (el extremo de la función).

Entonces, ¿qué es el vector de desplazamiento y cómo mediremos la distancia que debe recorrer la hormiga? Para ello, utilizaremos la fórmula para calcular la distancia entre dos puntos en el espacio tridimensional:

Podemos obtener una representación visual del vector de desplazamiento observando la Figura 2.

Figura 2. Vector de desplazamiento de hormigas.

Para espacios n-dimensionales, el cálculo será similar.

La hormiga se mueve del punto A al punto B en una iteración (época), con un posible deslizamiento al punto R. La distancia al punto R desde el punto B dependerá del coeficiente PheromoneRadius_P y se podrá calcular de la forma siguiente: BR = AB x PheromoneRadius_P.

La probabilidad de una nueva ubicación en la línea AR se muestra esquemáticamente (no a escala) en la Figura 2, como un área gris. Por lo tanto, resultará más probable que la nueva ubicación de la hormiga tienda a la vecindad del punto B. Ya analizamos el desplazamiento del cambio de probabilidad en el artículo anterior.

El algoritmo incluye los siguientes pasos en cada iteración:

1) La disposición aleatoria de hormigas en el espacio.
2) La determinación del valor de la cantidad de feromonas (función de adecuación) para las hormigas.
3) El cálculo de la distancia de cada hormiga respecto a cada una.
4) El cálculo de la elección del punto preferido por donde se desplazará la hormiga.
5) El cálculo de la probabilidad de un punto en el vector AR.
6) El cálculo de las coordenadas del punto obtenido sobre el vector AR.
7) La repetición desde el punto 2) hasta que se cumpla la condición de parada.

Vamos a pasar a la descripción del código del algoritmo. En primer lugar, escribiremos una estructura que contenga una descripción de la hormiga, donde:

• c[] - serán sus coordenadas, 
• cLast [] - serán las coordenadas anteriores,
• cB [] - serán las mejores coordenadas para todas las iteraciones,
• f - será valor actual de feromonas,
• fB - será el valor máximo de feromonas alcanzado en todas las iteraciones.

En el constructor de la estructura de hormigas, inicializaremos el valor de f y fB con el valor mínimo posible que pueda ser representado por el tipo double.

//——————————————————————————————————————————————————————————————————————————————
struct S_Ants
{
    double cLast  []; //last coordinates
    double c      []; //coordinates
    double cB     []; //best coordinates

    double f;     //pheromone of the current coordinates
    double fB;    //pheromone of the best coordinates

    S_Ants ()
    {
      f  = -DBL_MAX;
      fB = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Necesitaremos una estructura cuyo array nos permita almacenar las distancias por pares entre todas las hormigas.

struct S_Paths
{
    double a [];
};

Luego escribiremos nuestro algoritmo ACO modificado como una clase en la que todavía tendremos solo tres métodos públicos, suficientes y necesarios en el marco del concepto desarrollado de construcción de algoritmos de optimización discutido en artículos anteriores, InitAnts (), Preparation () y Dwelling () Aparecerán los métodos privados GenerateRNDants() y AntsMovement(), así como otros métodos privados que ya se han convertido en estándar para nuestros algoritmos. El array de estructuras ants [] será la colonia de hormigas.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ACO
{
  public:
  //----------------------------------------------------------------------------
  S_Ants ants      []; //ants
  double rangeMax  []; //maximum search range
  double rangeMin  []; //manimum search range
  double rangeStep []; //step search
  double cB        []; //best coordinates
  double fB;           //pheromone of the best coordinates

  void InitAnts (const int    coordinatesP,       //number of opt. parameters
                 const int    antHillSizeP,
                 double       pheromoneEffectP,
                 double       pathLengthEffectP,
                 double       pheromoneRadiusP,
                 double       pathDeviationP);

  void Preparation ();
  void Dwelling ();

  private:
  //----------------------------------------------------------------------------
  S_Paths paths [];
  int coordinates;        //number of coordinates
  int antHillSize;        //ant hill size

  double goals     [];

  double pheromoneEffect;
  double pathLengthEffect;
  double pheromoneRadius;
  double pathDeviation;
  bool   dwelling;

  void   GenerateRNDants ();
  void   AntsMovement    ();

  double SeInDiSp             (double in, double inMin, double inMax, double step);
  double RNDfromCI            (double min, double max);
  double Scale                (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

En el método de inicialización, asignaremos valores iniciales a las variables y el tamaño de los arrays.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::InitAnts (const int    coordinatesP,       //number of opt. parameters
                         const int    antHillSizeP,
                         double       pheromoneEffectP,
                         double       pathLengthEffectP,
                         double       pheromoneRadiusP,
                         double       pathDeviationP)
{
  fB = -DBL_MAX;

  coordinates      = coordinatesP;
  antHillSize      = antHillSizeP;
  pheromoneEffect  = pheromoneEffectP;
  pathLengthEffect = pathLengthEffectP;
  pheromoneRadius  = pheromoneRadiusP;
  pathDeviation    = pathDeviationP;

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

  dwelling = false;

  ArrayResize (ants,  antHillSize);
  ArrayResize (paths, antHillSize);

  for (int i = 0; i < antHillSize; i++)
  {
    ArrayResize (ants  [i].c,      coordinates);
    ArrayResize (ants  [i].cLast,  coordinates);
    ArrayResize (ants  [i].cB,     coordinates);
    ArrayResize (paths [i].a,      antHillSize);
  }

  ArrayResize (cB,    coordinates);
  ArrayResize (goals, antHillSize);
}
//——————————————————————————————————————————————————————————————————————————————

El método Preparation () se llamará primero en cada iteración.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Preparation ()
{
  if (!dwelling)
  {
    fB = -DBL_MAX;
    GenerateRNDants ();
    dwelling = true;
  }
  else AntsMovement ();
}
//——————————————————————————————————————————————————————————————————————————————

El método GenerateRNDants() se encargará de crear una colonia aleatoria de hormigas, las coordenadas de las hormigas se asignarán aleatoriamente dentro de los límites especificados.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::GenerateRNDants ()
{
  for (int s = 0; s < antHillSize; s++)
  {
    for (int k = 0; k < coordinates; k++)
    {
      ants [s].c     [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      ants [s].c     [k] = SeInDiSp (ants [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      ants [s].cLast [k] = ants [s].c [k];
      ants [s].cB    [k] = ants [s].c [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Vamos a recordar las coordenadas actuales de las hormigas en el método Dwelling () y, al mismo tiempo, a actualizar los valores máximos de feromonas obtenidos en el momento de la iteración actual.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Dwelling ()
{
  for (int i = 0; i < antHillSize; i++)
  {
    ArrayCopy (ants [i].cLast, ants [i].c, 0, 0, WHOLE_ARRAY);

    //remember the best coordinates for the ant
    if (ants [i].f > ants [i].fB)
    {
      ants [i].fB = ants [i].f;
      ArrayCopy (ants [i].cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }

    //remember the best coordinates for the anthill
    if (ants [i].f > fB)
    {
      fB = ants [i].f;
      ArrayCopy (cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método principal del algoritmo será AntsMovement(). Realizará las siguientes acciones: calcular la distancia de cada hormiga respecto a cada una, calcular la selección de un punto preferido donde se moverá la hormiga, calcular la probabilidad de un punto en el vector AR. Cálculo de las coordenadas del punto obtenido sobre el vector AR.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::AntsMovement ()
{
  double rndPh;
  double rndPt;
  double summCoordinates = 0.0;
  double scores [];
  ArrayResize (scores, antHillSize);

  double maxPh = -DBL_MAX;
  double minPh =  DBL_MAX;
  double maxPt = -DBL_MAX;
  double minPt =  DBL_MAX;
  double goal;
  double goalBest = -DBL_MAX;
  int    goalInd  = 0;

  //measure the distance between all the ants-----------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    for (int k = 0; k < antHillSize; k++)
    {
      if (i == k)
      {
        paths [i].a [k] = DBL_MAX;
        continue;
      }
         
      for (int c = 0; c < coordinates; c++) summCoordinates += pow (ants [i].cLast [c] - ants [k].cLast [c], 2.0);

      paths [i].a [k] = pow (summCoordinates, 0.5);

      if (maxPt < paths [i].a [k]) maxPt = paths [i].a [k];
      if (minPt > paths [i].a [k]) minPt = paths [i].a [k];
    }
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    maxPh = -DBL_MAX;
    minPh =  DBL_MAX;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        if (maxPh < ants [k].f) maxPh = ants [k].f;
        if (minPh > ants [k].f) minPh = ants [k].f;
      }
    }

    goalBest = -DBL_MAX;
    goalInd  = 0;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        rndPh = RNDfromCI (0.0, pheromoneEffect);
        rndPt = RNDfromCI (0.0, pathLengthEffect);

        goal = Scale (ants  [k].f,     minPh, maxPh, 0.0, 1.0, false) * rndPh *
               Scale (paths [i].a [k], minPt, maxPt, 0.0, 1.0, true)  * rndPt;

        if (goalBest < goal)
        {
          goalBest = goal;
          goalInd  = k;
        }
      }
    }
    
    double wayToGoal      = paths [i].a [goalInd];
    double radiusNearGoal = wayToGoal * pheromoneRadius;
    double endWay         = wayToGoal + radiusNearGoal;

    double x = RNDfromCI (-1.0, 1.0);
    double y = x * x;
    
    if (x > 0.0) y = Scale (y, 0.0, 1.0, wayToGoal, endWay,    false);
    else         y = Scale (y, 0.0, 1.0, 0.0,       wayToGoal, true);

    for (int j = 0; j < coordinates; j++)
    {
      double incrementFactor = y / wayToGoal;
      double coordDistance = ants [goalInd].cLast [j] - ants [i].cLast [j];
      
      ants [i].c [j] =  ants [i].cLast [j] + (coordDistance * incrementFactor);
      double w = coordDistance * RNDfromCI (-1.0, 1.0) * pathDeviation;
      ants [i].c [j] += w;
      
      ants [i].c [j] = SeInDiSp (ants [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Merece la pena prestar atención a la función de escalado de un número de un rango numérico a otro. Ya nos hemos encontrado con ella en artículos anteriores; esta vez ampliaremos su funcionalidad. El parámetro de entrada revers cambiará la dirección de escalado como se muestra en la figura a continuación.

Figura 3. Ejemplo de cómo escalar un número de un rango numérico a otro.

1) Escalado directo; 2) Escalado inverso.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_ACO::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return revers ? OutMAX : OutMIN;
    if (In > InMAX) return revers ? OutMIN : OutMAX;

    double res = (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);

    if (!revers) return res;
    else         return OutMAX - res;
  }
}
//——————————————————————————————————————————————————————————————————————————————

4. Resultados de la prueba

ACO en la función de prueba Skin.

ACO en la función de prueba Forest.

ACO en la función de prueba Megacity.

Entonces, es momento de resumir. Por un lado, el algoritmo clásico de colonia de hormigas no es aplicable a problemas de optimización para el comercio con instrumentos financieros y no podría ser considerado aquí. Sin embargo, un poco de imaginación nos ha permitido evitar las limitaciones de la versión clásica y escribir una nueva versión original. Hemos sido testigo del surgimiento de un concepto completamente nuevo del algoritmo de colonia de hormigas, dentro del cual es posible la dirección de un mayor desarrollo del ACO. Dicho algoritmo ya se puede aplicar a una amplia gama de problemas, incluido el problema del viajante de comercio.

Además, hemos conseguido un nuevo líder de la tabla de rating. Vamos a analizar los resultados con más detalle. Primero, prestaremos atención a los resultados del banco de pruebas:

2022.10.27 16:46:28.678    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    1 Skin's; Func runs 1000 result: 13.969156176320473; Func runs 10000 result: 13.986949123110085
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    Score1: 0.99502; Score2: 0.99599
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    20 Skin's; Func runs 1000 result: 8.514904198298202; Func runs 10000 result: 11.56159524595023
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    Score1: 0.69826; Score2: 0.86403
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.962716036996786; Func runs 10000 result: 6.488619274853463
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    Score1: 0.50498; Score2: 0.58800
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.805601165115196; Func runs 10000 result: 15.839944455892518
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    Score1: 0.99087; Score2: 0.99302
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.568897096569507; Func runs 10000 result: 10.45940001108266
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    Score1: 0.22374; Score2: 0.65571
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.3412234994286016; Func runs 10000 result: 2.7822130728041756
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    Score1: 0.08408; Score2: 0.17442
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 11.8; Func runs 10000 result: 11.8
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    Score1: 0.78667; Score2: 0.78667
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.75; Func runs 10000 result: 3.9200000000000004
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    Score1: 0.11667; Score2: 0.26133
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    500 Megacit 's; Func runs 1000 result: 0.6335999999999999; Func runs 10000 result: 1.2312
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    Score1: 0.04224; Score2: 0.08208

2022.10.27 16:49:41.075    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    All score for C_AO_ACO: 0.5468768583006471

El algoritmo se ha desempeñado bien en la función Skin suave, demostrando una excelente convergencia y buenas capacidades de escalado, estando especialmente por delante en las pruebas de función 20 y 500. En la función Forest suave con rupturas pronunciadas, la separación resulta aún más notable; el algoritmo continúa la búsqueda incluso al alcanzar los extremos locales. En la función discreta Megacity, el algoritmo cede ante el algoritmo aleatorio RND solo en el problema con 500 funciones.

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
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
PSOm	1000	0,96678	0,64727	0,57654	0,80616	0,13388	0,06800	0,53333	0,08067	0,04211	0,45144
	10000	0,99505	0,64986	0,57654	0,90401	0,18194	0,07104	0,74667	0,10400	0,04211

Conclusiones

El algoritmo tiene muchas configuraciones, por lo que será posible obtener resultados aún mejores. Posibilidad de ajuste con tipos específicos de tareas. Vamos a detenernos en esto con más detalle. El primer parámetro PheromoneEffect_P influye directamente en la tasa de convergencia, y resulta especialmente positivo para funciones monótonas suaves; por ejemplo, respecto a una parábola, la convergencia será del 100%, pero también contribuirá al atascamiento en los extremos locales en funciones discretas si lo establecemos muy grande.

El segundo parámetro PathLengthEffect_P, muestra el grado de pereza de las hormigas; con un valor alto de este parámetro, se seleccionarán los objetivos más próximos para el movimiento. Es necesario equilibrar este parámetro con el primer parámetro para obtener el mejor resultado. Este parámetro está diseñado para ofrecer un contrapeso al deseo de la hormiga de ir a un punto donde haya más comida, en lugar de elegir a veces los objetivos más cercanos para un examen más detallado de las áreas pequeñas, lo cual puede resultar muy útil, como en el ejemplo de la función Forest, donde el mejor punto puede encontrarse inesperadamente cerca.

El logro más importante: hemos logrado deshacernos del problema principal del ACO canónico, a saber, la capacidad de resolver solo problemas combinatorios discretos. Ahora el algoritmo de colonia de hormigas se puede usar para entrenar redes neuronales.

Visualmente, el banco de pruebas es muy interesante de observar gracias a una cierta agrupación, las hormigas se concentran en las medición de una función multidimensional de cierta forma, destacando los grupos característicos de los extremos locales. Quizás este efecto pueda utilizarse para resolver problemas específicos, pero esto requerirá de investigación adicional.

El algoritmo tiene una propiedad interesante: al resolver un problema con dos variables, la probabilidad de atascarse en un extremo local resulta algo mayor que al optimizar 40 variables. El algoritmo continúa buscando soluciones cuando hay muchas variables; supongo que este es el efecto de usar un vector como medio para vincular todas las coordenadas del espacio de búsqueda. Como ejemplo, si una hormiga se trasladara a un nuevo lugar mejor, entonces todas las coordenadas cambiarían espacialmente para mejor, y no algunas de ellas por separado.

El algoritmo creado es nuevo y todavía inexplorado en detalle, por lo que agradeceré a los usuarios si comparten en los comentarios al artículo una configuración del algoritmo con la que el banco de pruebas muestre un valor final superior a 0.6, para actualizar así los resultados del recuadro. Por cierto, esta solicitud también se aplica a los algoritmos analizados con anterioridad.

Ventajas:
1. El algoritmo es bastante rápido.
2. Su versatilidad. Se puede usar en una amplia variedad de problemas de optimización.
3. La capacidad de no centrarse solo en los extremos locales.
4. Una convergencia bastante buena para funciones suaves y discretas.
5. Escalamos.

Desventajas:
1. Quizás se requieran más iteraciones para la convergencia que las realizadas con el mismo PSO para funciones uniformes, pero esto se compensa parcialmente con la capacidad de continuar buscando incluso donde el PSO ya se ha detenido.
2. Una fuerte influencia de los parámetros del algoritmo en el resultado.