MetaTrader 5 / Ejemplos
English Русский Deutsch 日本語 Português
preview
Algoritmos de optimización de la población: Algoritmo Boids, o algoritmo de comportamiento de bandada (Algoritmo Boids, Boids)

Algoritmos de optimización de la población: Algoritmo Boids, o algoritmo de comportamiento de bandada (Algoritmo Boids, Boids)

MetaTrader 5 — Ejemplos | 24 septiembre 2024, 16:33
58 0
Andrey Dik
Andrey Dik

Contenido:

1. Introducción
2. Descripción del algoritmo
3. Resultados de las pruebas


1. Introducción

Al observar el comportamiento gregario de los animales en la naturaleza, admiramos casi sin percibirlo su coordinación coherente y eficaz. Como controlados por una fuerza invisible, se reorganizan sincrónicamente en un solo organismo, superando obstáculos y encontrando los caminos más óptimos. Esta fascinante armonía de movimientos basada en sencillas reglas de interacción ha servido de inspiración a numerosos algoritmos de optimización metaheurística.

Estudiando las complejas rutas migratorias de las bandadas de aves, los científicos han descubierto que siguen principios similares a los algoritmos de la inteligencia de enjambre. Así, los bancos de peces, como células vivas, forman estructuras pulsantes que recuerdan a los métodos de optimización basados en autómatas celulares. El comportamiento en manada de los ungulados, sus reacciones coordinadas ante el peligro y el vuelo sincronizado de un grupo de estorninos representan la increíble capacidad de los animales para trabajar juntos de forma coordinada.

Estos fascinantes ejemplos del mundo natural han inspirado la creación de potentes herramientas de optimización capaces de resolver problemas complejos, desde la planificación de rutas logísticas hasta el desarrollo de sistemas de gestión eficaces.

El algoritmo Boids (del inglés "boid" - abreviatura de "pájaro" y "oid", similitud, semejanza) es un algoritmo informático creado por Craig Reynolds en 1986, que simula el comportamiento de enjambres de animales, en particular, de bandadas de aves. El algoritmo se diseñó para imitar el comportamiento natural de los enjambres, en los que cada individuo se mueve siguiendo reglas sencillas, lo cual da lugar a un comportamiento colectivo. Se basa en las tres reglas que siguen:

1. Separación (Separation). Cada objeto (o "boid") intenta minimizar la posibilidad de colisión con los objetos cercanos.
2. Alineación (Alignment). Cada objeto tiende a que su dirección de movimiento sea la dirección media de movimiento de los objetos de su entorno.
3. Cohesión (Cohesion). Cada objeto tiende a tener una posición cercana a la posición media de los objetos de su entorno.

Estas tres sencillas reglas permiten modelar el complejo comportamiento de una bandada de pájaros o un enjambre de insectos. El algoritmo Boids se usa ampliamente en los gráficos de computadora para crear la animación de una bandada de pájaros, un enjambre de insectos o un banco de peces.

Inicialmente, la creación del algoritmo Boids tenía varios objetivos y aplicaciones:

1. Creación de animaciones realistas. El algoritmo Boids permite crear animaciones realistas de una manada de animales, lo cual ha servido como importante orientación para el desarrollo de los gráficos y la animación de computadora.
2. Modelación del comportamiento. Boids permite modelar comportamientos colectivos complejos a partir de reglas sencillas para cada individuo. Esto tiene aplicaciones en diversas esferas, como la investigación del comportamiento animal, la robótica o la gestión del tráfico, entre otras.

Un hecho interesante es que el algoritmo Boids ha servido de inspiración para el desarrollo de otros algoritmos: por ejemplo, el enjambre de partículas (PSO) y los algoritmos de modelado del comportamiento de las multitudes.

El algoritmo Boids es una herramienta popular para modelar el comportamiento colectivo y continúa siendo objeto de investigación y desarrollo en diversos campos de la ciencia y la tecnología.

En la siguiente animación podemos ver el comportamiento de esos mismos boids, que pueden agruparse en grupos compactos, volar separados y sincronizar su velocidad respecto a la de sus vecinos. Durante la grabación de la animación, los ajustes del algoritmo se han modificado sobre la marcha, lo cual nos ha permitido ver el efecto de los respectivos ajustes en el comportamiento de los boids.

Boids

Visualización del funcionamiento del algoritmo Boids.

config

Ventana de configuración del algoritmo Boids. Podemos acceder a ella usando la tecla F3. El parámetro "#reset" permite reiniciar el algoritmo aplicando un valor igual a "1".


2. Descripción del algoritmo

El algoritmo Boids, desarrollado por Craig Reynolds, se diseñó originalmente para modelar cualquier comportamiento de enjambre de animales, como bandadas de pájaros, enjambres de insectos y otros. Sin embargo, gracias a su flexibilidad y adaptabilidad, este algoritmo ha encontrado aplicaciones en diversos campos, como la optimización y la búsqueda. En el contexto de la optimización y la búsqueda, el algoritmo Boids puede usarse para resolver problemas que impliquen el comportamiento coordinado de un grupo de agentes. Por ejemplo, puede usarse para modelar el comportamiento de un enjambre que explora un territorio desconocido.

Sin embargo, debemos señalar que el algoritmo Boids no es en sí mismo un algoritmo de búsqueda en el sentido tradicional del término. No está diseñado para encontrar la solución óptima en un espacio dado de posibles soluciones, como hacen, por ejemplo, los algoritmos de descenso de gradiente o los algoritmos genéticos. En cambio, el algoritmo Boids modela el comportamiento de un grupo de agentes basándose en un conjunto de reglas simples, lo cual permite modelar comportamientos complejos y coordinados a nivel de grupo.

El algoritmo Boids puede adaptarse para la búsqueda distribuida de extremos de funciones. En este contexto, cada boid representa un agente de búsqueda que se desplaza por el espacio de posibles soluciones. En lugar de limitarse a seguir a otros boids, cada agente puede usar el valor de la característica en su posición actual para ajustar su movimiento o tener en cuenta la adaptabilidad de otros boids de la población.

Los trabajos de Craig Reynolds sobre el algoritmo Boids, que modela el comportamiento de los enjambres, inspiraron el concepto de inteligencia de enjambre. La inteligencia de enjambre describe el comportamiento colectivo de un sistema autoorganizado descentralizado y entre ellos se encuentra el algoritmo PSO.

Los sistemas de inteligencia de enjambre suelen estar formados por múltiples agentes (boids) que interactúan de forma local entre sí y con el entorno. Las ideas de comportamiento suelen proceder de la naturaleza y, concretamente, de los sistemas biológicos. Cada boid sigue unas reglas muy sencillas y, aunque no existe un sistema centralizado de control del comportamiento que indique a cada uno de ellos lo que debe hacer, las interacciones locales y, hasta cierto punto, aleatorias dan lugar a un comportamiento grupal inteligente no controlado por boids individuales.

El algoritmo Boids tiene bastantes parámetros externos, y cada uno de ellos influye significativamente en la naturaleza del movimiento de los boids. Veamos esos parámetros:

  1. cohesionWeight- peso de cohesión, determina la fuerza de atracción de los miembros de la manada entre sí.
  2. cohesionDist- distancia de cohesión, define la distancia entre los miembros de la manada a partir de la cual empiezan a sentirse atraídos entre sí.
  3. separationWeight - peso de separación, determina cuánto se alejarán entre sí los miembros de la manada.
  4. separationDist - distancia de separación, define la distancia entre los miembros de la manada a partir de la cual empezarán a alejarse unos de otros.
  5. alignmentWeight - peso de alineación, determina cuánto se alinearán los miembros de la manada en la dirección de movimiento de cada uno.
  6. alignmentDist - distancia de alineación, define la distancia entre los miembros de la manada en la que empezarán a alinearse en la dirección del movimiento de cada uno.
  7. minSpeed - velocidad mínima, el parámetro es necesario para evitar que los boids se detengan.
  8. maxSpeed - velocidad máxima a la que puede moverse un boid.

Es importante realizar una serie de experimentos para mejorar estos parámetros y obtener el comportamiento de enjambre deseado. Podemos empezar con los valores sugeridos e ir ajustándolos gradualmente para ver cómo afectan al comportamiento de la manada. Recuerde que no hay valores de parámetros "correctos" o "mejores" para el algoritmo Boids en un sentido absoluto, todo dependerá de la tarea y el escenario específicos.

Vamos ahora a escribir el código del algoritmo Boids. Para describir cada agente, definiremos la estructura "S_Boids_Agent". Vamos a desglosar lo que ocurre aquí:


1. La estructura contiene los siguientes campos:

  • x[] - array para almacenar las coordenadas actuales del agente.
  • dx[] - array de velocidades actuales del agente.
  • m - masa del agente.

2. Init - método de la estructura "S_Boids_Agent", inicializa los campos de la estructura. Toma un argumento entero "coords" que se utilizará para redimensionar los arrays "x" y "dx" usando la función "ArrayResize".

Este código representa la estructura básica de datos para los agentes en el algoritmo Boids e inicializará sus campos cuando se cree un nuevo agente. Esto permitirá que cada agente tenga sus propias coordenadas y velocidades, que es un aspecto clave del algoritmo Boids. El campo "m" lo he añadido por propia iniciativa, para tener en cuenta la función de aptitud de la superficie cuando los boids se mueven, donde la masa es el valor de aptitud. 

//——————————————————————————————————————————————————————————————————————————————
struct S_Boids_Agent
{
    double x  [];
    double dx [];
    double m;

    void Init (int coords)
    {
      ArrayResize (x,  coords);
      ArrayResize (dx, coords);
    }
};
//——————————————————————————————————————————————————————————————————————————————

Ahora vamos a definir la clase "C_AO_Boids" del algoritmo Boids, que es la sucesora de la clase básica de algoritmos poblacionales "C_AO" y contendrá los siguientes campos y métodos:

1. Campos públicos:

  • ao_name - nombre del algoritmo de optimización.
  • ao_desc - descripción del algoritmo de optimización.
  • popSize - tamaño de la población.
  • params - array de parámetros del algoritmo.
  • cohesionWeight - peso de cohesión.
  • cohesionDist - distancia de cohesión.
  • separationWeight - peso de la separación.
  • separationDist - distancia de separación.
  • alignmentWeight - peso de la alineación.
  • alignmentDist - distancia de alineación.
  • maxSpeed - velocidad máxima.
  • minSpeed - velocidad mínima.
  • agente - vector de agentes.

2. Métodos:

  • C_AO_Boids - constructor de clase que inicializa los campos de la clase.
  • SetParams - método para establecer los parámetros del algoritmo.
  • Init - método para inicializar el algoritmo. Soporta rangos de búsqueda mínimo y máximo, paso de búsqueda y número de épocas.
  • Moving - método para desplazar a los agentes.
  • Revision - método para revisar a los agentes.

3. Campos privados:

  • distanceMax - distancia euclidiana máxima posible en el espacio de búsqueda.
  • speedMax - velocidad máxima.
//——————————————————————————————————————————————————————————————————————————————
class C_AO_Boids : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_Boids () { }
  C_AO_Boids ()
  {
    ao_name = "Boids";
    ao_desc = "Boids Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/14576";

    popSize          = 50;   //population size

    cohesionWeight   = 0.6;
    cohesionDist     = 0.001;

    separationWeight = 0.005;
    separationDist   = 0.03;

    alignmentWeight  = 0.1;
    alignmentDist    = 0.1;

    maxSpeed         = 0.001;
    minSpeed         = 0.0001;

    ArrayResize (params, 9);

    params [0].name = "popSize";          params [0].val = popSize;

    params [1].name = "cohesionWeight";   params [1].val = cohesionWeight;
    params [2].name = "cohesionDist";     params [2].val = cohesionDist;


    params [3].name = "separationWeight"; params [3].val = separationWeight;
    params [4].name = "separationDist";   params [4].val = separationDist;

    params [5].name = "alignmentWeight";  params [5].val = alignmentWeight;
    params [6].name = "alignmentDist";    params [6].val = alignmentDist;

    params [7].name = "maxSpeed";         params [7].val = maxSpeed;
    params [8].name = "minSpeed";         params [8].val = minSpeed;
  }

  void SetParams ()
  {
    popSize          = (int)params [0].val;

    cohesionWeight   = params [1].val;
    cohesionDist     = params [2].val;

    separationWeight = params [3].val;
    separationDist   = params [4].val;

    alignmentWeight  = params [5].val;
    alignmentDist    = params [6].val;

    maxSpeed         = params [7].val;
    minSpeed         = params [8].val;
  }

  bool Init (const double &rangeMinP  [], //minimum search range
             const double &rangeMaxP  [], //maximum search range
             const double &rangeStepP [], //step search
             const int     epochsP = 0);  //number of epochs

  void Moving   ();
  void Revision ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  double cohesionWeight;   //cohesion weight
  double cohesionDist;     //cohesion distance

  double separationWeight; //separation weight
  double separationDist;   //separation distance

  double alignmentWeight;  //alignment weight
  double alignmentDist;    //alignment distance

  double minSpeed;         //minimum velocity
  double maxSpeed;         //maximum velocity

  S_Boids_Agent agent [];

  private: //-------------------------------------------------------------------
  double distanceMax;
  double speedMax [];

  void   CalculateMass    ();
  void   Cohesion         (S_Boids_Agent &boid, int pos);
  void   Separation       (S_Boids_Agent &boid, int pos);
  void   Alignment        (S_Boids_Agent &boid, int pos);
  void   LimitSpeed       (S_Boids_Agent &boid);
  void   KeepWithinBounds (S_Boids_Agent &boid);
  double Distance         (S_Boids_Agent &boid1, S_Boids_Agent &boid2);
};
//——————————————————————————————————————————————————————————————————————————————

El método "Init" de la clase "C_AO_Boids" se utilizará para inicializar las variables de la clase usando como base los parámetros transmitidos. Este método realizará una inicialización estándar usando el método "StandardInit", que admite los rangos de búsqueda mínimo y máximo, así como el paso de búsqueda.

Si la inicialización estándar tiene éxito, el método redimensionará el array "agent" a "popSize". Para cada elemento del "agente", se llamará al método "Init" con el parámetro "coords".

A continuación, el método calculará la distancia máxima y la velocidad máxima que se utilizarán en el algoritmo Boids para determinar el movimiento de los agentes.

Luego el método establecerá variables globales para diversos parámetros del algoritmo Boids, como el peso de cohesión, la distancia de cohesión, el peso de separación, la distancia de separación, el peso de alineación, la distancia de alineación, la velocidad máxima y la velocidad mínima.

El método retornará "true" si la inicialización se ha realizado correctamente y "false" en caso contrario.

Este método realizará la configuración inicial del algoritmo de optimización Boids con los parámetros especificados y lo preparará para realizar la optimización.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_Boids::Init (const double &rangeMinP  [], //minimum search range
                       const double &rangeMaxP  [], //maximum search range
                       const double &rangeStepP [], //step search
                       const int     epochsP = 0)   //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (agent, popSize);
  for (int i = 0; i < popSize; i++) agent [i].Init (coords);

  distanceMax = 0;
  ArrayResize (speedMax, coords);

  for (int c = 0; c < coords; c++)
  {
    speedMax [c] = rangeMax [c] - rangeMin [c];
    distanceMax += pow (speedMax [c], 2);
  }

  distanceMax = sqrt (distanceMax);

  GlobalVariableSet ("#reset", 1.0);

  GlobalVariableSet ("1cohesionWeight",   params [1].val);
  GlobalVariableSet ("2cohesionDist",     params [2].val);

  GlobalVariableSet ("3separationWeight", params [3].val);
  GlobalVariableSet ("4separationDist",   params [4].val);

  GlobalVariableSet ("5alignmentWeight",  params [5].val);
  GlobalVariableSet ("6alignmentDist",    params [6].val);

  GlobalVariableSet ("7maxSpeed",         params [7].val);
  GlobalVariableSet ("8minSpeed",         params [8].val);


  return true;
}
//——————————————————————————————————————————————————————————————————————————————

El método "Moving" de la clase "C_AO_Boids" se utilizará para mover los agentes durante el proceso de optimización. El método efectuará las siguientes acciones:

  1. Después se comprobará el valor de la variable global "reset". Si es 1.0, la bandera "revision" se establecerá en "false", el valor de la variable global "reset" se pondrá a 0.0, y el método finalizará.
  2. Los valores de los parámetros del algoritmo se extraerán de las variables globales.
  3. Si la bandera de "revisión" es "false", las coordenadas y velocidades de los agentes se inicializarán con valores aleatorios dentro de los rangos especificados. A continuación, la bandera "revisión" se establecerá en "true" y el método finalizará.
  4. Si el indicador de revisión no es igual a "false", se realizarán las siguientes acciones para cada agente:
    • Los métodos "CalculateMass", "Cohesion", "Separation", "Alignment", "LimitSpeed" y "KeepWithinBounds" se llamarán para actualizar las velocidades del agente.
    • Las coordenadas del agente se actualizarán en función de sus velocidades.
    • Las coordenadas del agente se copiarán en el elemento "a" del array correspondiente.
/——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Moving ()
{
  double reset = GlobalVariableGet ("#reset");
  if (reset == 1.0)
  {
    revision = false;
    GlobalVariableSet ("#reset", 0.0);
  }

  cohesionWeight   = GlobalVariableGet ("1cohesionWeight");
  cohesionDist     = GlobalVariableGet ("2cohesionDist");

  separationWeight = GlobalVariableGet ("3separationWeight");
  separationDist   = GlobalVariableGet ("4separationDist");

  alignmentWeight  = GlobalVariableGet ("5alignmentWeight");
  alignmentDist    = GlobalVariableGet ("6alignmentDist");

  maxSpeed         = GlobalVariableGet ("7maxSpeed");
  minSpeed         = GlobalVariableGet ("8minSpeed");

  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        agent [i].x [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        agent [i].dx [c] = (rangeMax [c] - rangeMin [c]) * u.RNDfromCI (-1.0, 1.0) * 0.001;

        a [i].c [c] = u.SeInDiSp  (agent [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    CalculateMass    ();
    Cohesion         (agent [i], i);
    Separation       (agent [i], i);
    Alignment        (agent [i], i);
    LimitSpeed       (agent [i]);
    KeepWithinBounds (agent [i]);

    for (int c = 0; c < coords; c++)
    {
      agent [i].x [c] += agent [i].dx [c];
      a [i].c [c] = u.SeInDiSp  (agent [i].x [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "CalculateMass" de la clase "C_AO_Boids" se utilizará para calcular la "masa" de cada agente en el algoritmo Boids. Eso es lo que ocurrirá con este método:

  1. Las variables "maxMass" y "minMass" se inicializarán para almacenar los valores máximo y mínimo de la función de aptitud entre todos los agentes.
  2. Para cada agente de la población, se comprobará si su función de aptitud "a[i].f" es mayor que el valor máximo actual "maxMass" y menor que el valor mínimo actual "minMass". En caso afirmativo, se actualizarán los valores máximo y mínimo correspondientes.
  3. Una vez probados todos los agentes, se calculará la "masa" de cada uno de ellos como el valor escalado de su función de aptitud en relación con los valores mínimo y máximo.

Este método ofrecerá un cálculo de la "masa" de cada agente en el algoritmo Boids; este no se encuentra en la lógica original del algoritmo Boids, y permite tener en cuenta la "superficie" del terreno sobre el que se desplazan los boids.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::CalculateMass ()
{
  double maxMass = -DBL_MAX;
  double minMass =  DBL_MAX;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > maxMass) maxMass = a [i].f;
    if (a [i].f < minMass) minMass = a [i].f;
  }

  for (int i = 0; i < popSize; i++)
  {
    agent [i].m = u.Scale (a [i].f, minMass, maxMass, 0.0, 1.0);
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "Cohesion" de la clase "C_AO_Boids" se utilizará para implementar el comportamiento "cohesion" en el algoritmo Boids. Este comportamiento hará que los agentes se desplacen hacia el "centro de masa" de sus vecinos. El método ejecutará las siguientes acciones:

  1. La inicialización del array "centerX" para almacenar las coordenadas del centro de masa y la variable "numNeighbors" para contar el número de vecinos.
  2. Para cada agente de la población, se comprobará si no es él mismo (ya que un agente no debe considerarse a sí mismo como vecino) y si se encuentra a una distancia determinada (definida como "distanceMax * cohesionDist"). Si se cumplen ambas condiciones, las coordenadas del agente se añadirán a "centreX" y "numNeighbors" se incrementará en 1.
  3. Si se ha encontrado al menos un vecino, las coordenadas "centerX" se dividirán por el número de vecinos para obtener las coordenadas del centro de masa de los vecinos. La velocidad del agente "boid.dx" se corregirá entonces hacia el centro de masa para tener en cuenta el peso de cohesión "cohesionWeight".

Este método reforzará el comportamiento de "cohesión" del algoritmo Boids, que ayudará a los agentes a moverse juntos como grupo.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Cohesion (S_Boids_Agent &boid, int pos)
{
  double centerX [];
  ArrayResize     (centerX, coords);
  ArrayInitialize (centerX, 0.0);

  int    numNeighbors = 0;

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * cohesionDist)
      {
        for (int c = 0; c < coords; c++)
        {
          centerX [c] += agent [i].x [c];
        }

        numNeighbors++;
      }
    }
  }

  for (int c = 0; c < coords; c++)
  {
    centerX [c] /= numNeighbors;
    boid.dx [c] += (centerX [c] - boid.x [c]) * cohesionWeight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "Separation" de la clase "C_AO_Boids" se utilizará para implementar el comportamiento de "separación" en el algoritmo Boids. Este comportamiento hará que los agentes se muevan en dirección opuesta a los vecinos que están demasiado cerca para evitar colisiones. Eso es lo que ocurrirá con este método:

  1. El array "moveX" se inicializará para almacenar los cambios en las coordenadas del agente.
  2. Para cada agente de la población, se comprobará si no es él mismo (ya que un agente no debe considerarse a sí mismo como vecino) y si se encuentra a una distancia determinada (definida como "distanceMax * separationDist"). Si se cumplen ambas condiciones, la diferencia entre las coordenadas del agente actual y el vecino se añadirá a "moveX".
  3. Una vez comprobados todos los vecinos, se ajustará la velocidad del agente "boid.dx" en sentido contrario a "moveX", teniendo en cuenta el peso de separación "separationWeight".

Este método reforzará el comportamiento de "separación" del algoritmo Boids, que ayudará a los agentes a evitar colisiones entre sí.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Separation (S_Boids_Agent &boid, int pos)
{
  double moveX [];
  ArrayResize     (moveX, coords);
  ArrayInitialize (moveX, 0.0);

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * separationDist)
      {
        for (int c = 0; c < coords; c++)
        {
          moveX [c] += boid.x [c] - agent [i].x [c];
        }
      }
    }
  }

  for (int c = 0; c < coords; c++)
  {
    boid.dx [c] += moveX [c] * separationWeight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "Alignment" de la clase "C_AO_Boids" se utilizará para implementar el comportamiento de "alineación" en el algoritmo Boids. Este comportamiento hará que los agentes se muevan en la misma dirección que sus vecinos. En este método se realizarán las siguientes acciones:

  1. La inicialización del array "avgDX" para almacenar la velocidad media de los vecinos y la variable "numVecinos" para contar el número de vecinos.
  2. Para cada agente de la población, se comprobará si no es él mismo (ya que un agente no debe considerarse a sí mismo como vecino) y si se encuentra a una distancia determinada (definida como "distanceMax * alignmentDist"). Si se cumplen ambas condiciones, la velocidad del vecino se añadirá a "avgDX" y "numNeighbors" se incrementará en 1.
  3. Si se ha encontrado al menos un vecino, las velocidades "avgDX" se dividirán por el número de vecinos para obtener la velocidad media. La velocidad del agente "boid.dx" se ajustará entonces en la dirección de la velocidad media para tener en cuenta el peso de alineación "alignmentWeight".

Este método reforzará el comportamiento de "alineación" del algoritmo Boids, que ayudará a los agentes a moverse juntos en la misma dirección.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Alignment (S_Boids_Agent &boid, int pos)
{
  double avgDX [];
  ArrayResize     (avgDX, coords);
  ArrayInitialize (avgDX, 0.0);

  int numNeighbors = 0;

  for (int i = 0; i < popSize; i++)
  {
    if (pos != i)
    {
      if (Distance (boid, agent [i]) < distanceMax * alignmentDist)
      {
        for (int c = 0; c < coords; c++)
        {
          avgDX [c] += agent [i].dx [c];
        }

        numNeighbors++;
      }
    }
  }

    for (int c = 0; c < coords; c++)
    {
      avgDX   [c] /= numNeighbors;
      boid.dx [c] += (avgDX [c] - boid.dx [c]) * alignmentWeight;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "LimitSpeed" de la clase "C_AO_Boids" se utilizará para limitar la velocidad de los agentes en el algoritmo Boids. Este comportamiento impedirá que los agentes aumenten infinitamente su velocidad, lo cual no es natural para los animales reales. En este método ocurrirá lo siguiente:

  1. Se inicializará la variable "speed" para almacenar la velocidad actual del agente y la variable "d" para almacenar temporalmente los datos.
  2. Se calculará la velocidad actual del agente a partir de sus velocidades en cada coordenada.
  3. Para cada coordenada de agente, se realizarán los siguientes pasos:
    • Se calculará "d" como la diferencia entre los valores máximo y mínimo del rango multiplicado por el factor de velocidad mínima. 
    • La velocidad del agente "boid.dx" se ajustará según la velocidad máxima posible "speedMax" y el factor de velocidad máxima "maxSpeed".
    • Si el valor absoluto de la velocidad del agente es inferior a "d", la velocidad del agente se fijará en "d" (manteniendo el signo).

Este método impondrá un comportamiento de "limitación de velocidad" en el algoritmo Boids que ayudará a controlar la velocidad de los agentes y evitará que los boids dejen de moverse.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::LimitSpeed (S_Boids_Agent &boid)
{
  double speed = 0;

  for (int c = 0; c < coords; c++)
  {
    speed += boid.dx [c] * boid.dx [c];
  }

  speed = sqrt (speed);

  double d = 0;

  for (int c = 0; c < coords; c++)
  {
    d = (rangeMax [c] - rangeMin [c]) * minSpeed;

    boid.dx [c] = (boid.dx [c] / speed) * speedMax [c] * maxSpeed;

    if (fabs (boid.dx [c]) < d)
    {
      if (boid.dx [c] < 0.0) boid.dx [c] = -d;
      else                   boid.dx [c] =  d;
    }

  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "KeepWithinBounds" de la clase "C_AO_Boids" se utilizará para restringir el movimiento de los agentes dentro de los límites especificados en el algoritmo Boids. Este comportamiento impedirá que los agentes sobrepasen los límites especificados.

  1. Para cada coordenada del agente, se comprobará si está dentro de los límites especificados (definidos como "rangeMin" y "rangeMax").
  2. Si la coordenada del agente es menor que "rangeMin", se establecerá igual a "rangeMax", desplazando el agente al lado opuesto del límite.
  3. Si la coordenada del agente es mayor que "rangeMax", se establecerá igual a "rangeMin", moviendo el agente al lado opuesto del límite.

Este método impondrá una "restricción de límites" en el algoritmo Boids que ayudará a los agentes a mantenerse dentro de los límites dados.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::KeepWithinBounds (S_Boids_Agent &boid)
{
  for (int c = 0; c < coords; c++)
  {
    double margin     = 0; //(rangeMax [c] - rangeMin [c])* 0.00001;
    double turnFactor = (rangeMax [c] - rangeMin [c]) * 0.0001;

    /*
    if (boid.x [c] < rangeMin [c] + margin)
    {
      boid.dx [c] += turnFactor;
    }
    if (boid.x [c] > rangeMax [c] - margin)
    {
      boid.dx [c] -= turnFactor;
    }
    */
    if (boid.x [c] < rangeMin [c]) 
    {
      //boid.x [c] = rangeMax [c];
      boid.dx [c] *= -1;
      
    }
    if (boid.x [c] > rangeMax [c])
    {
      //boid.x [c] = rangeMin [c];
      boid.dx [c] *= -1;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

El método "Distance" de la clase "C_AO_Boids" se utilizará para calcular la distancia euclídea entre dos agentes en el algoritmo Boids.

  1. La variable "dist" se inicializará para almacenar la distancia.
  2. Para cada coordenada de los agentes, se calculará el cuadrado de la diferencia de sus coordenadas, que luego se sumará a "dist".
  3. Al final, el método retornará la raíz cuadrada de "dist", que se corresponderá con la distancia euclidiana entre los agentes.

Este método proporcionará un cálculo de la distancia entre los agentes en el algoritmo Boids que se utilizará para determinar cómo interactúan entre sí.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_Boids::Distance (S_Boids_Agent &boid1, S_Boids_Agent &boid2)
{
  double dist = 0;

  for (int c = 0; c < coords; c++)
  {
    dist += pow (boid1.x [c] - boid1.x [c], 2);
  }

  return sqrt (dist);
}
//——————————————————————————————————————————————————————————————————————————————

El método "Revision" de la clase "C_AO_Boids" se utilizará para actualizar la mejor solución en el algoritmo Boids.

  1. La variable "ind" se inicializará con el valor -1. Esta variable se usará para almacenar el índice del agente con la mejor solución.
  2. Para cada agente de la población, se comprobará si su función de aptitud "a[i].f" es superior a la mejor solución actual "fB". Si es así, "ind" se establecerá igual al índice de este agente.
  3. Si se ha encontrado un agente con la mejor solución (es decir, "ind" no es igual a -1), entonces la mejor solución "fB" y las mejores coordenadas "cB" se actualizarán con los valores de ese agente.

Este método garantizará la actualización de la mejor solución en el algoritmo Boids, lo cual ayudará al algoritmo a centrarse en las regiones más prometedoras del espacio de soluciones.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_Boids::Revision ()
{
  int ind = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) ind = i;
  }

  if (ind != -1)
  {
    fB = a [ind].f;
    ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————


3. Resultados de las pruebas

Me gustaría profundizar en los resultados del algoritmo Boids con diferentes conjuntos de características. La puntuación total de Boids en todas las funciones de la prueba ha sido de 2,22889, lo cual se corresponde con el 24,77% de la puntuación máxima posible. Este resultado indica que la eficacia del algoritmo es baja. Basándonos en esto, podemos concluir que el algoritmo Boids posee poco potencial para resolver problemas de optimización de varias funciones.

Boids|50.0|0.05|0.002|0.01|0.01|0.0001|0.01|0.001|0.0001|
=============================
5 Hilly's; Func runs: 100000; result: 0.43339505349362384
25 Hilly's; Func runs: 100000; result: 0.3058074706767012
500 Hilly's; Func runs: 100000; result: 0.2542539219446322
=============================
5 Forest's; Func runs: 100000; result: 0.35717696198531945
25 Forest's; Func runs: 100000; result: 0.20160005990319796
500 Forest's; Func runs: 100000; result: 0.15708435238635948
=============================
5 Megacity's; Func runs: 100000; result: 0.2784615384615384
25 Megacity's; Func runs: 100000; result: 0.14276923076923081
500 Megacity's; Func runs: 100000; result: 0.09833846153846236
=============================
All score: 2.22889 (24.77%)

El algoritmo Boids ocupa el puesto 28 en la tabla de clasificación, junto a su "compañero" de inteligencia de enjambre, el algoritmo PSO.

№ AO Description Hilly Hilly final Forest Forest final Megacity (discrete) Megacity final Final result % de MAX
10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F)
1 BGA binary genetic algorithm 0,99992 0,99484 0,50483 2,49959 1,00000 0,99975 0,32054 2,32029 0,90667 0,96400 0,23035 2,10102 6,921 76,90
2 (P+O)ES (P+O) evolution strategies 0,99934 0,91895 0,56297 2,48127 1,00000 0,93522 0,39179 2,32701 0,83167 0,64433 0,21155 1,68755 6,496 72,18
3 SDSm stochastic diffusion search M 0,93066 0,85445 0,39476 2,17988 0,99983 0,89244 0,19619 2,08846 0,72333 0,61100 0,10670 1,44103 5,709 63,44
4 ESG evolution of social groups 0,99906 0,79654 0,35056 2,14616 1,00000 0,82863 0,13102 1,95965 0,82333 0,55300 0,04725 1,42358 5,529 61,44
5 SIA simulated isotropic annealing 0,95784 0,84264 0,41465 2,21513 0,98239 0,79586 0,20507 1,98332 0,68667 0,49300 0,09053 1,27020 5,469 60,76
6 DE differential evolution 0,95044 0,61674 0,30308 1,87026 0,95317 0,78896 0,16652 1,90865 0,78667 0,36033 0,02953 1,17653 4,955 55,06
7 BSA bird swarm algorithm 0,90857 0,73661 0,25767 1,90285 0,90437 0,81619 0,16401 1,88457 0,61692 0,54154 0,10951 1,26797 5,055 56,17
8 HS harmony search 0,86509 0,68782 0,32527 1,87818 0,99999 0,68002 0,09590 1,77592 0,62000 0,42267 0,05458 1,09725 4,751 52,79
9 SSG saplings sowing and growing 0,77839 0,64925 0,39543 1,82308 0,85973 0,62467 0,17429 1,65869 0,64667 0,44133 0,10598 1,19398 4,676 51,95
10 (PO)ES (PO) evolution strategies 0,79025 0,62647 0,42935 1,84606 0,87616 0,60943 0,19591 1,68151 0,59000 0,37933 0,11322 1,08255 4,610 51,22
11 WOAm whale optimization algorithm M 0,84521 0,56298 0,26263 1,67081 0,93100 0,52278 0,16365 1,61743 0,66308 0,41138 0,11357 1,18803 4,476 49,74
12 ACOm ant colony optimization M 0,88190 0,66127 0,30377 1,84693 0,85873 0,58680 0,15051 1,59604 0,59667 0,37333 0,02472 0,99472 4,438 49,31
13 BFO-GA bacterial foraging optimization - ga 0,89150 0,55111 0,31529 1,75790 0,96982 0,39612 0,06305 1,42899 0,72667 0,27500 0,03525 1,03692 4,224 46,93
14 MEC mind evolutionary computation 0,69533 0,53376 0,32661 1,55569 0,72464 0,33036 0,07198 1,12698 0,52500 0,22000 0,04198 0,78698 3,470 38,55
15 IWO invasive weed optimization 0,72679 0,52256 0,33123 1,58058 0,70756 0,33955 0,07484 1,12196 0,42333 0,23067 0,04617 0,70017 3,403 37,81
16 Micro-AIS micro artificial immune system 0,79547 0,51922 0,30861 1,62330 0,72956 0,36879 0,09398 1,19233 0,37667 0,15867 0,02802 0,56335 3,379 37,54
17 COAm cuckoo optimization algorithm M 0,75820 0,48652 0,31369 1,55841 0,74054 0,28051 0,05599 1,07704 0,50500 0,17467 0,03380 0,71347 3,349 37,21
18 SDOm spiral dynamics optimization M 0,74601 0,44623 0,29687 1,48912 0,70204 0,34678 0,10944 1,15826 0,42833 0,16767 0,03663 0,63263 3,280 36,44
19 NMm Nelder-Mead method M 0,73807 0,50598 0,31342 1,55747 0,63674 0,28302 0,08221 1,00197 0,44667 0,18667 0,04028 0,67362 3,233 35,92
20 FAm firefly algorithm M 0,58634 0,47228 0,32276 1,38138 0,68467 0,37439 0,10908 1,16814 0,28667 0,16467 0,04722 0,49855 3,048 33,87
21 GSA gravitational search algorithm 0,64757 0,49197 0,30062 1,44016 0,53962 0,36353 0,09945 1,00260 0,32667 0,12200 0,01917 0,46783 2,911 32,34
22 BFO bacterial foraging optimization 0,61171 0,43270 0,31318 1,35759 0,54410 0,21511 0,05676 0,81597 0,42167 0,13800 0,03195 0,59162 2,765 30,72
23 ABC artificial bee colony 0,63377 0,42402 0,30892 1,36671 0,55103 0,21874 0,05623 0,82600 0,34000 0,14200 0,03102 0,51302 2,706 30,06
24 BA bat algorithm 0,59761 0,45911 0,35242 1,40915 0,40321 0,19313 0,07175 0,66810 0,21000 0,10100 0,03517 0,34617 2,423 26,93
25 SA simulated annealing 0,55787 0,42177 0,31549 1,29513 0,34998 0,15259 0,05023 0,55280 0,31167 0,10033 0,02883 0,44083 2,289 25,43
26 IWDm intelligent water drops M 0,54501 0,37897 0,30124 1,22522 0,46104 0,14704 0,04369 0,65177 0,25833 0,09700 0,02308 0,37842 2,255 25,06
27 PSO particle swarm optimisation 0,59726 0,36923 0,29928 1,26577 0,37237 0,16324 0,07010 0,60572 0,25667 0,08000 0,02157 0,35823 2,230 24,77
28 Boids boids algorithm 0,43340 0,30581 0,25425 0,99346 0,35718 0,20160 0,15708 0,71586 0,27846 0,14277 0,09834 0,51957 2,229 24,77
29 MA monkey algorithm 0,59107 0,42681 0,31816 1,33604 0,31138 0,14069 0,06612 0,51819 0,22833 0,08567 0,02790 0,34190 2,196 24,40
30 SFL shuffled frog-leaping 0,53925 0,35816 0,29809 1,19551 0,37141 0,11427 0,04051 0,52618 0,27167 0,08667 0,02402 0,38235 2,104 23,38
31 FSS fish school search 0,55669 0,39992 0,31172 1,26833 0,31009 0,11889 0,04569 0,47467 0,21167 0,07633 0,02488 0,31288 2,056 22,84
32 RND random 0,52033 0,36068 0,30133 1,18234 0,31335 0,11787 0,04354 0,47476 0,25333 0,07933 0,02382 0,35648 2,014 22,37
33 GWO grey wolf optimizer 0,59169 0,36561 0,29595 1,25326 0,24499 0,09047 0,03612 0,37158 0,27667 0,08567 0,02170 0,38403 2,009 22,32
34 CSS charged system search 0,44252 0,35454 0,35201 1,14907 0,24140 0,11345 0,06814 0,42299 0,18333 0,06300 0,02322 0,26955 1,842 20,46
35 EM electroMagnetism-like algorithm 0,46250 0,34594 0,32285 1,13129 0,21245 0,09783 0,10057 0,41085 0,15667 0,06033 0,02712 0,24412 1,786 19,85


Conclusiones

A pesar de los decepcionantes resultados en las funciones de prueba, cabe destacar que en las funciones Forest y Megacity con 1 000 variables los resultados resultan bastante decentes y coinciden con los resultados de los algoritmos de la mitad superior de la tabla. Este hecho puede indicarnos que el algoritmo Boids podría resultar más eficiente cuando trabajamos con un gran número de variables. En general, estos resultados muestran que sería difícil esperar más potencial del algoritmo Boids.

tab

Figura 1. Gradación por colores de los algoritmos según sus respectivas pruebas. Los resultados superiores o iguales a 0,99 aparecen resaltados en blanco.

chart

Figura 2. Histograma con los resultados de las pruebas de los algoritmos (en una escala de 0 a 100, cuanto mayor, mejor),

donde 100 es el máximo resultado teórico posible; hay un script para calcular la tabla de puntuación en el archivo).

Ventajas e inconvenientes del algoritmo de comportamiento de bandada (Boids):

Ventajas:

  1. Modelización realista del comportamiento de bandada.

Desventajas:

  1. Baja convergencia.
  2. Alta complejidad computacional.
  3. Baja escalabilidad en funciones suaves como Hilly (problemas con tareas de alta dimensionalidad).

Adjunto al artículo hay un archivo con las versiones actuales de los códigos. El autor de este artículo no se responsabiliza de la exactitud absoluta de la descripción de los algoritmos canónicos, muchos de ellos han sido modificados para mejorar las capacidades de búsqueda. Las conclusiones y juicios presentados en los artículos se basan en los resultados de los experimentos realizados.

Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/14576

Archivos adjuntos |
Descargar ZIP
Boids.zip (28.61 KB)
Advertencia: todos los derechos de estos materiales pertenecen a MetaQuotes Ltd. Queda totalmente prohibido el copiado total o parcial.

Otros artículos del autor

Pasar a la discusión en el foro de los operadores
Algoritmos de optimización de la población: Algoritmo de enjambre de aves (Bird Swarm Algorithm, BSA) Algoritmos de optimización de la población: Algoritmo de enjambre de aves (Bird Swarm Algorithm, BSA)
El artículo analiza un algoritmo BSA basado en el comportamiento de las aves, que se inspira en las interacciones colectivas de bandadas de aves en la naturaleza. Las diferentes estrategias de búsqueda de individuos en el BSA, que incluyen el cambio entre el comportamiento de vuelo, la vigilancia y la búsqueda de alimento, hacen que este algoritmo sea multidimensional. El algoritmo usa los principios del comportamiento de las bandadas, la comunicación, la adaptabilidad, el liderazgo y el seguimiento de las aves para encontrar con eficacia soluciones óptimas.
Características del Wizard MQL5 que debe conocer (Parte 18): Búsqueda de arquitectura neural con vectores propios Características del Wizard MQL5 que debe conocer (Parte 18): Búsqueda de arquitectura neural con vectores propios
Búsqueda de arquitectura neuronal, un enfoque automatizado para determinar la configuración ideal de la red neuronal, puede ser una ventaja cuando se enfrentan muchas opciones y grandes conjuntos de datos de prueba. Analizamos cómo, cuando se combinan vectores propios, este proceso puede resultar aún más eficiente.
Red neuronal en la práctica: Pseudo inversa (II) Red neuronal en la práctica: Pseudo inversa (II)
Por esta razón, dado que estos artículos tienen un propósito didáctico y no están enfocados en mostrar cómo implementar una funcionalidad específica, haremos algo un poco diferente aquí. En lugar de mostrar cómo implementar la factorización para obtener la inversa de una matriz, nos centraremos en cómo factorizar la pseudo inversa. El motivo es que no tiene sentido mostrar cómo factorizar algo de forma genérica si podemos hacerlo de manera especializada. Y mejor aún, será algo que podrás entender mucho más profundamente, comprendiendo por qué las cosas son como son. Así que veamos por qué, con el tiempo, un hardware sustituye a un software.
Redes neuronales: así de sencillo (Parte 83): Algoritmo de convertidor espacio-temporal de atención constante (Conformer) Redes neuronales: así de sencillo (Parte 83): Algoritmo de convertidor espacio-temporal de atención constante (Conformer)
El algoritmo de Conformer que le mostraremos hoy se desarrolló para la previsión meteorológica, una esfera del saber que, por su constante variabilidad, puede compararse con los mercados financieros. El Conformer es un método completo que combina las ventajas de los modelos de atención y las ecuaciones diferenciales ordinarias.