Population optimization algorithms: Boids Algorithm

Contents

1. Introduction
2. Algorithm description
3. Test results

1. Introduction

Observing the flock behavior of animals in nature, we involuntarily admire their well-coordinated and effective interaction. As if under the control of an invisible force, they synchronously re-arrange themselves as a single organism, overcoming obstacles and finding the most optimal paths. This fascinating harmony of movements, based on simple rules of interaction, has inspired the creation of many metaheuristic optimization algorithms.

By studying the complex migratory routes of flocks of birds, scientists have discovered that they follow principles similar to swarm intelligence algorithms. Thus, schools of fish, like living cells, form pulsating structures reminiscent of optimization methods based on cellular automata. The herd behavior of hoofed mammals, their coordinated responses to danger, and the synchronized flight of a group of starlings represent the incredible abilities of animals to coordinate joint actions.

These fascinating examples from the natural world have inspired powerful optimization tools that can solve complex problems, from planning logistics routes to designing efficient control systems.

Boids algorithm (short for "bird" and "oid" - similarity) is a computer algorithm created by Craig Reynolds in 1986 that models the behavior of flocks of animals, particularly birds. This algorithm was designed to mimic the natural behavior of flocks, where each individual moves according to simple rules, which eventually leads to the emergence of collective behavior. It is based on the following three rules:

1. Separation. Each object (or "boid") tries to minimize the possibility of collision with nearby objects.
2. Alignment. Each object strives to ensure that its direction of movement is the average direction of movement of nearby objects.
3. Cohesion. Each object strives to have its position close to the average position of nearby objects.

These three simple rules allow us to model the complex behavior of a flock of birds or a swarm of insects. The Boids algorithm is widely used in computer graphics to create animations of a flock of birds, a swarm of insects, or a school of fish.

The original Boids algorithm had several goals and applications:

1. Creating realistic animations. The Boids algorithm allows for the creation of realistic animations of flocks of animals, which has served as an important direction for the development of computer graphics and animation.
2. Behavior modeling. Boids allows simulating complex collective behavior based on simple rules for each individual. This finds application in various fields such as animal behavior research, robotics, traffic management and others.

Boids algorithm has inspired the development of other algorithms, such as particle swarm optimization (PSO) and crowd behavior modeling algorithms.

The Boids algorithm remains a popular tool for modeling collective behavior and continues to be the subject of research and development in various fields of science and technology.

In the animation below, we can see the behavior of those same boids, which can gather into compact groups, fly apart, and also synchronize their speed relative to their neighbors. When recording the animation, the algorithm settings were changed on the fly, which made it possible to see the effect of the corresponding settings on the behavior of the boids.

Boids algorithm visualization

The Boids algorithm settings window, called by pressing the F3 key. The #reset parameter allows us to restart the algorithm by applying the value "1"

2. Algorithm

The Boids algorithm, developed by Craig Reynolds, was originally designed to model any flocking behavior of animals, such as flocks of birds, swarms of insects, and others. However, due to its flexibility and adaptability, this algorithm has found application in various fields, including optimization and search. In the context of optimization and search, the Boids algorithm can be used to solve problems related to the coordinated behavior of a group of agents. For example, it can be used to model the behavior of a swarm exploring an unknown territory.

It is worth noting, however, that the Boids algorithm itself is not a search algorithm in the traditional sense of the term. It is not designed to find an optimal solution in a given space of possible solutions, as is done, for example, by gradient descent algorithms or genetic algorithms. Instead, the Boids algorithm models the behavior of a group of agents based on a set of simple rules, which allows it to model complex and coordinated behavior at the group level.

The Boids algorithm can be adapted for distributed search of the extremum of a function. In this context, each "boid" represents a search agent that moves through the space of possible solutions. Instead of simply following other "boids", each agent can use the value of the function at its current position to adjust its movement or take into account the fitness of other boids in the population.

Craig Reynolds' work on the Boids algorithm, which simulates swarming behavior, inspired the concept of swarm intelligence. Swarm intelligence describes the collective behavior of a decentralized self-organizing system and includes the PSO algorithm.

Swarm intelligence systems typically consist of multiple agents (boids) interacting locally with each other and with the environment. Behavioral ideas typically come from nature, and especially from biological systems. Each boid follows very simple rules. Although there is no centralized behavior control system telling each of them what to do, local and somewhat random interactions result in intelligent group behavior that is beyond the control of individual boids.

The Boids algorithm has quite a lot of external parameters, and each of them significantly affects the nature of the movement of the boids. Let's look at these parameters:

1. cohesionWeight - cohesion weight determines the force of attraction of the flock members to each other.
2. cohesionDist - cohesion distance determines the distance between members of a flock, at which they begin to be attracted to each other.
3. separationWeight - separation weight determines how strongly the flock members repel each other.
4. separationDist - separation distance determines the distance between flock members, at which they begin to repel each other.
5. alignmentWeight - alignment weight determines how strongly the flock members will align themselves with each other's movement direction.
6. alignmentDist - alignment distance determines the distance between flock members, at which they begin to align themselves in the direction of each other's movement.
   
7. minSpeed - minimum speed for preventing boids from stopping.
   
8. maxSpeed - maximum boid speed.
   

It is important to conduct a series of experiments to adjust these parameters to obtain the desired flock behavior. You can start with the suggested values and gradually adjust them to see how they affect the flock behavior. Please note that there are no "correct" or "best" parameter values for the Boids algorithm in an absolute sense. It all depends on the specific task and scenario.

Let's move on to writing the code for the Boids algorithm. To describe each agent, define the S_Boids_Agent structure. Let's look at what is going on here:

1. The structure contains the following fields:

• x[] - array for storing the current agent coordinates.
• dx[] - array of current agent speeds.
• m - agent mass.
  

2. Init - S_Boids_Agent structure method initializing the structure fields. It takes the "coords" integer argument used to resize the "x" and "dx" arrays using the ArrayResize function.

This code represents the basic data structure for agents in the Boids algorithm and initializes their fields when a new agent is created. This allows each agent to have its own coordinates and velocities, which is a key aspect of the Boids algorithm. The "m" field was added on my initiative to take into account the fitness function surface when moving boids, where mass is the fitness value.

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

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

Let's define the C_AO_Boids class of the Boids algorithm, which is an inheritor of the base class of C_AO population algorithms and contains the following fields and methods:

1. Public fields:

• ao_name - optimization algorithm name.
• ao_desc - optimization algorithm description.
• popSize - population size.
• params - array of algorithm parameters.
• cohesionWeight - cohesion weight.
• cohesionDist - cohesion distance.
• separationWeight - separation weight.
• separationDist - separation distance.
• alignmentWeight - alignment weight.
• alignmentDist - alignment distance.
• maxSpeed - maximum speed.
• minSpeed - minimum speed.
• agent - vector of agents.

2. The options available are:

• C_AO_Boids - class constructor that initializes the class fields.
• SetParams - method for setting algorithm parameters.
• Init - method for initializing the algorithm. The method accepts minimum and maximum search ranges, search step and number of epochs.
• Moving - method for moving agents.
• Revision - method for revising agents.

3. Private fields:

• distanceMax - maximum possible Euclidean distance in the search space.
• speedMax - maximum speed.

//——————————————————————————————————————————————————————————————————————————————
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/en/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);
};
//——————————————————————————————————————————————————————————————————————————————

The Init method of the C_AO_Boids class is used to initialize class variables based on the passed parameters. This method performs standard initialization using the StandardInit method, which takes the minimum and maximum search ranges as well as the search step.

If the standard initialization is successful, the method resizes the "agent" to the "popSize" size. The Init method is called with the "coords" parameter for each element in "agent".

The method then calculates the maximum distance and maximum speed, which are used in the Boids algorithm to determine the movement of agents.

The method then sets global variables for various parameters of the Boids algorithm, such as cohesion weight, cohesion distance, separation weight, separation distance, alignment weight, alignment distance, maximum speed and minimum speed.

The method returns "true" if initialization was successful, and "false" otherwise.

This method performs the initial setup of the Boids optimization algorithm with given parameters and prepares it to perform optimization.

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

The Moving method of the C_AO_Boids class is used to move agents during optimization. The method does the following:

1. The value of the global variable "reset" is checked. If it is 1.0, the "revision" flag is set to "false". The value of the global "reset" variable is set to 0.0, and the method exits.
2. The values of the algorithm parameters are extracted from global variables.
3. If the "revision" flag is "false", then the coordinates and velocities of agents are initialized with random values in the specified ranges. The "revision" flag is then set to "true" and the method exits.
4. If the "revision" flag is not "false", then the following actions are performed for each agent:

• The CalculateMass, Cohesion, Separation, Alignment, LimitSpeed and KeepWithinBounds methods are called to update the agent velocities.
• The agent coordinates are updated based on its speeds.
• The agent coordinates are copied to the corresponding element of the "a" array.

/——————————————————————————————————————————————————————————————————————————————
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]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

The CalculateMass method of the C_AO_Boids class is used to calculate the "mass" of each agent in the Boids algorithm. Here is what happens in this method:

1. The variables "maxMass" and "minMass" are initialized to store the maximum and minimum values of the fitness function among all agents.
2. For each agent in the population, it is checked whether its "a[i].f" fitness function is greater than the current maximum "maxMass" value and less than the current minimum "minMass" value. If the conditions are met, the corresponding maximum and minimum values are updated.
3. After all agents have been tested, each agent's "mass" is calculated as the scaled value of its fitness function relative to the minimum and maximum values.

This method provides the calculation of the "mass" of each agent in the Boids algorithm, which is absent in the original algorithm logic. It allows us to take into account the "surface" of the terrain the boids move on.

//——————————————————————————————————————————————————————————————————————————————
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);
  }
}
//——————————————————————————————————————————————————————————————————————————————

The Cohesion method of the C_AO_Boids class is used to implement the "cohesion" behavior in the Boids algorithm. This behavior causes agents to move toward the "center of mass" of their neighbors. The method performs the following tasks:

1. The "centerX" array is initialized to store the coordinates of the center of mass, while the "numNeighbors" variable counts the number of neighbors.
2. For each agent in the population, it is checked whether it is not itself (since the agent should not consider itself a neighbor) and whether it is located within a certain distance (defined as "distanceMax * cohesionDist"). If both conditions are met, the agent coordinates are added to "centerX" and "numNeighbors" is incremented by 1.
3. If at least one neighbor was found, the "centerX" coordinates are divided by the number of neighbors to obtain the coordinates of the neighbors' center of mass. The velocity of the agent "boid.dx" is then adjusted towards the center of mass taking into account the "cohesionWeight" cohesion weight.

This method implements the "cohesion" behavior in the Boids algorithm, which helps agents move together as a group.

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

The Separation method of the C_AO_Boids class is used to implement the "separation" behavior in the Boids algorithm. This behavior causes agents to move in the opposite direction from neighbors that are too close to avoid collisions. Here is what happens in this method:

1. The "moveX" array is initialized to store changes in the agent coordinates.
2. For each agent in the population, it is checked whether it is not itself (since the agent should not consider itself a neighbor) and whether it is located within a certain distance (defined as "distanceMax * separationDist"). If both conditions are met, then the difference between the coordinates of the current agent and its neighbor is added to "moveX".
3. After all neighbors have been checked, the "boid.dx" agent's speed is adjusted in the opposite direction to "moveX" by taking into account the "separationWeight" separation weight.

This method implements the "separation" behavior in the Boids algorithm, which helps agents avoid colliding with each other.

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

The Alignment method of the C_AO_Boids class is used to implement the "alignment" behavior in the Boids algorithm. This behavior causes agents to move in the same direction as their neighbors. In this method:

1. The array "avgDX" is initialized to store the average speed of neighbors and the "numNeighbors" variable is initialized to count the number of neighbors.
2. For each agent in the population, it is checked whether it is not itself (since the agent should not consider itself a neighbor) and whether it is located within a certain distance (defined as "distanceMax * alignmentDist"). If both conditions are met, the neighbor's speed is added to "avgDX" and "numNeighbors" is increased by 1.
3. If at least one neighbor was found, the "avgDX" speeds are divided by the number of neighbors to obtain the average speed. The speed of the "boid.dx" agent is then adjusted towards the average speed, taking into account the "alignmentWeight" alignment weight.

This method implements the "alignment" behavior in the Boids algorithm, which helps agents move together in the same direction.

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

The LimitSpeed method of the C_AO_Boids class is used to limit the speed of agents in the Boids algorithm. This behavior prevents agents from increasing their speed infinitely, which is unnatural for real animals. The method does the following:

1. The "speed" variable is initialized to store the current speed of the agent and the "d" variable is initialized to store data temporarily.
2. The current speed of the agent is calculated based on its speeds for each coordinate.
3. The following actions are performed for each agent coordinate:

• "d" is calculated as the difference between the maximum and minimum range values, multiplied by the minimum speed factor. 
• The speed of the "boid.dx" agent is adjusted according to the "speedMax" maximum possible speed and the "maxSpeed" maximum speed factor.
• If the absolute value of the agent velocity is less than "d", then the agent velocity is set equal to "d" (preserving the sign).

This method implements the "speed limit" behavior in the Boids algorithm, which helps control the agents' speed of movement and prevents boids from stopping.

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

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

The KeepWithinBounds method of the C_AO_Boids class is used to restrict the movement of agents within the specified boundaries in the Boids algorithm. This behavior prevents agents from going beyond the specified boundaries.

1. For each agent coordinate, it is checked whether it is outside the specified boundaries (defined as "rangeMin" and "rangeMax").
2. If the agent coordinate is less than "rangeMin", then it is set to "rangeMax", moving the agent to the opposite side of the boundary.
3. If the agent coordinate is greater than "rangeMax", then it is set equal to "rangeMin", moving the agent to the opposite side of the boundary.

This method provides "boundary constraint" in the Boids algorithm, which helps agents stay within the given boundaries.

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

The Distance method of the C_AO_Boids class is used to calculate the Euclidean distance between two agents in the Boids algorithm.

1. The "dist" variable is initialized to store the distance.
2. For each agent coordinate, the square of the difference between their coordinates is calculated and then added to "dist".
3. At the end, the method returns the square root of "dist", which corresponds to the Euclidean distance between agents.

This method provides the calculation of the distance between agents in the Boids algorithm, which is used to determine their interaction with each other.

//——————————————————————————————————————————————————————————————————————————————
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);
}
//——————————————————————————————————————————————————————————————————————————————

The Revision method of the C_AO_Boids class is used to update the best solution in the Boids algorithm.

1. The variable "ind" is initialized using the value of -1. This variable will be used to store the index of the agent with the best solution.
2. For each agent in the population, it is checked whether its fitness function "a[i].f" is less than the current best solution "fB". If yes, "ind" is set to the agent index.
3. If an agent with a better solution was found ("ind" is not equal to -1), then the best solution "fB" and the best coordinates "cB" are updated with the values of this agent.

This method provides an update of the best solution in the Boids algorithm, which helps the algorithm focus on the most promising areas of the solution space.

//——————————————————————————————————————————————————————————————————————————————
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. Test results

I would like to dwell in more detail on the results of the Boids algorithm on various sets of functions. Boids' overall score across all test functions was 2.22889, which is 24.77% of the maximum possible score. This result indicates low efficiency of the algorithm. Based on this, we can conclude that the Boids algorithm has little potential for solving optimization problems on various functions.

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%)

The Boids algorithm took 28 th place in the ranking table, next to its "brother" in swarm intelligence systems, the PSO algorithm.

#	AO	Description	Hilly			Hilly final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result	% of 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

Summary

Despite the weak results on the test functions, it is worth noting that on the Forest and Megacity functions with 1000 variables the results are quite decent and correspond to the results of the algorithms in the upper half of the table. This may indicate that the Boids algorithm may be more efficient when dealing with larger numbers of variables. Overall, these results show that it would be difficult to expect more potential from the Boids algorithm.

Figure 1. Color gradation of algorithms according to relevant tests Results greater than or equal to 0.99 are highlighted in white

Figure 2. The histogram of algorithm test results (on a scale from 0 to 100, the more the better,

where 100 is the maximum possible theoretical result, the archive features a script for calculating the rating table)

Boids pros and cons:

Advantages:

1. Realistic flocking behavior simulation.
   

Disadvantages:

1. Low convergence.
2. High computational complexity.
   
3. Low scalability on smooth functions such as Hilly (problems with high dimensionality tasks).

The article is accompanied by an archive with the current code versions. The author of the article is not responsible for the absolute accuracy in the description of canonical algorithms. Changes have been made to many of them to improve search capabilities. The conclusions and judgments presented in the articles are based on the results of the experiments.