Backtracking Search Algorithm (BSA)

Contents

1. Introduction
2. Implementation of the algorithm
3. Test results

Introduction

In the endless labyrinth of possibilities, where every turn can lead to either triumph or a dead end, the wise traveler leaves behind invisible traces —something ephemeral, yet more reliable: the memory of the paths traveled. This idea (looking back to see the future) lies at the heart of the optimization algorithm. Every step into the unknown is taken with an eye on past experience, where history becomes a compass, and memory becomes a map.

In this article, I will consider the algorithm that I found very interesting due to its search concept. The Backtracking Search Algorithm (BSA) is a new evolutionary algorithm (EA) for solving real-valued numerical optimization problems, proposed by Pinar Civicioglu in 2013. It is a method of finding the best solution that can "learn from past experience". 

Implementation of the algorithm

BSA works on the principle of evolutionary algorithms, but has unique features, using two populations:

• current population (P) - an actively evolving population
• historical population (oldP) - a randomly selected population from past generations

BSA uses a random mutation strategy that produces only one directional solution for each target individual. Mutation formula:

Mutant = P + F × (oldP - P)

where F is the amplitude factor that controls the search step size.

The BSA crossover process involves two steps. The first strategy uses "mixrate". The second strategy allows only one randomly selected coordinate to be altered in each trial vector. Imagine that you and your friends (that is our population) are looking for the best pizzeria in town. 

Initial situation:

• you have 10 friends (population size),
• everyone starts searching in a random area of the city,
• everyone has a smartphone with a map of past trips (historical memory).

Day 1: Everyone went out into the city. The first friend found a pizzeria with a 7/10 rating, the second friend found a pizzeria with a 5/10 rating, the third discovered a pizzeria with an 8/10 rating...and so on.

Day 2: Using the accumulated experience.

Step 1: "Remembering the past" (Selection-I). Algorithm: "Let's flip a coin!" If it lands on heads, then "Remember where everyone was yesterday" (update history), if it lands on tails, "Use old memories" (do not update), then "Shuffle memories" (like a deck of cards).

Step 2: "Follow the trail" (Mutation). Every friend thinks: "Where am I now? (current position) and where was I before? (historical position). Then the formula for movement will be: New place = Current place + Random step × (Old place - Current place). For example: the first friend is now on A street, 10, his “ghost from the past” was on B street, 20, random step = 2. New location = A.,10 + 2 × (B.,20 - A.,10) = movement towards B street, but 2 times further!

"Correcting the route" (Crossover). The algorithm tosses a coin and chooses a strategy. Strategy A: "Partial change". The first friend planned to go to a certain address, but the algorithm says: "Change only the street, leave the house as it was". Result: okay, we change the street, but keep the house. Strategy B: "Minimal change". The first friend planned to go to a certain address, but the algorithm says: "Stay at the old place, but change only the house number." Result: ok, we change the house number.

"Check the overall result" (Selection-II). Friend 1 came to a new place:

• If the new pizzeria is better (rating 9/10): "Great, I'm staying here!"
• If worse (rating 4/10): "No, I'm coming back!"

The figure below illustrates how the algorithm works.

Figure 1. BSA algorithm phases

This illustration shows how the BSA algorithm searches for an optimal solution in a two-dimensional space. Imagine you are looking at a topographic map from above, where the goal is to find the highest point (red center).

The illustration is divided into three panels showing the evolution of the search: Iteration 1 – Random Initialization. The square search field with contour lines (like a topographic map) has a red dot in the center representing the global optimum (the best solution), and four blue dots (P1, P2, P3, P4) are the initial random positions of the "explorers". The algorithm randomly places four agents throughout the search space. At this stage, oldP = P (the historical population copies the current one), and this is the starting point of the search.

Iteration 2 - Mutation Step. Blue dots are the current positions of agents, green translucent dots are positions from historical memory (mixed), red arrows are the directions of movement during mutation.

Key elements: The red arrows show the mutation formula in action: M = P + F × (oldP - P). Each agent moves relative to its "historical counterpart". Some arrows point towards historical positions, others away from them (depending on the F sign). Formula in red box: F = 3 × randn(); M = P + F × (oldP - P). This is the key formula for the BSA mutation.

Iteration 3 - After Crossover & Selection. Purple dots are new positions after the crossover (Trial population), translucent blue dots are previous positions (for comparison), and green arrows show only improvements (where the new position is better than the old one). Crossover: The algorithm combined information from the mutant and current populations. Greedy selection kept only those moves that improved the solution. The population has approached the optimum (red center).

BSA Process Summary, the full algorithm cycle as a sequence of colored circles:

1. Init (blue) - random start
2. Select-I (green) - memory update with a 50% probability
3. Mutate (red) - application of the mutation formula
4. Crossover (purple) – combination of solutions
5. Evaluate (orange) - fitness calculation
6. Select-II (turquoise) - greedy selection of the best

The dotted arrow shows that the process is repeated until convergence. This image clearly demonstrates why BSA is effective: it "remembers" where it has been before and uses that information to search more intelligently than a simple random walk.

We can now move on to the BSA pseudocode.

Preparation for work

Initial parameters:

• Set the population size 
• Set the mixrate crossover parameter 
• Create empty containers for:
  • current population
  • historical population
  • mutant population
  • trial population
  • crossover maps for each individual

Initialization:

• Place all individuals of the historical population randomly in the search space
• Take into account discretization if the step is given
• Set the "selection required" flag to "no"

The main loop of the algorithm

STEP 1: First launch

If this is the first iteration:

• Place the current population randomly
• Apply discretization to coordinates
• Mark that initialization is complete
• Exit and wait for fitness to be calculated

STEP 2: Greedy selection (if required)

If the "selection required" flag is set:

• For each individual, compare:
  • if the new solution is worse than the saved one, we return the old coordinates and fitness
  • if it is better, we leave the new one.
• Reset selection flag

STEP 3: Saving the current state

For each individual:

• Save the current fitness
• Save the copy of the current coordinates

STEP 4: Updating historical memory (Selection-I)

• Toss a coin (50% chance)
• If the coin lands on heads:
  • copy the entire current population into historical memory
  • preserve their fitness
• Shuffle the historical population like a deck of cards:
  • go from the last individual to the first
  • for each, select a random position for exchange
  • swap

STEP 5: Mutation

• Generate a motion factor F from a normal distribution
  • average = 0, range from -3 to +3
  • like a dice roll, but with a bell-shaped distribution
• For each individual and each coordinate:
  • New position = Current + F × (Historical - Current)
  • if F is positive → movement to the historical position
  • if F is negative → movement from the historical position

STEP 6: Crossover

• Copy the mutant population into the trial population
• Toss a weighted coin (40% / 60%)

If the 40% branch is selected (Strategy 1): 

For each individual:

• determine how many coordinates to change (from 0 to all, using mixrate)
• randomly select the coordinates
• for the selected coordinates, take values from the current population
• leave the rest from the mutant one

If 60% is rolled (Strategy 2):

For each individual:

• choose only one random coordinate
• replace it with a value from the current population
• leave all the rest from the mutant one

STEP 7: Boundary control

For each individual of the trial population:

• Check each coordinate
• If we go beyond the boundaries:
  • toss a coin (50/50)
  • if "heads" → generate a new random value within the bounds
  • if "tails" → place on the nearest border
• Apply discretization if step is specified

STEP 8: Prepare for the assessment

• Copy the trial population to the main population for evaluation
• Set the "selection required" flag to "yes"
• Pass control to fitness calculation

After calculating the fitness 

• Find the individual with the best fitness
• If you find something better than the global record:
  • update the global record
  • save the coordinates of the best solution

Repetition

Return to STEP 2 and continue until:

• convergence is reached
• or the iteration limit is exceeded

Now that we understand the main points, let's start writing the algorithm code. The C_AO_BSA_Backtracking class will be an implementation of the BSA backtracking algorithm for solving optimization problems. It will inherit the C_AO base class, which defines a common interface for optimization algorithms. 

Main characteristics and purpose:

Optimization parameters:

• popSize - the population size, the number of "agents" or "solutions" that the algorithm considers simultaneously. 
• mixrate - a crossover parameter that controls the degree of "mixing" of information between agents when creating new solutions. 

Initialization:

• The class constructor initializes the base parameters and adds popSize and mixrate to the params array, which is used to control the algorithm parameters.
• The SetParams method allows you to update the internal parameters of the algorithm based on the values obtained from the params array. It also includes basic checks for value validity.

Algorithm life cycle (methods):

• Init — for the initial setup of the algorithm, including setting the ranges of change of variables (minimum, maximum values and steps) and the number of optimization epochs.
• Moving — describes the main iteration of the algorithm, responsible for generating new "candidates" or "moving" solutions based on the current population.
• Revision — evaluates the generated solutions and updates the population based on their quality.

Internal data structures for the algorithm:

• oldP - an array representing the "historical" or previous population of agents.
• M - an array for the population resulting from mutation.
• T - an array for the "trial" population, used for comparison with the current population before making decisions.
• F — amplitude factor for mutation, which influences the magnitude of change upon mutation.
• needSelection — flag indicating the need to perform the second stage of selection.
• prevFitness — array for storing the fitness values of agents from the previous iteration.
• S_Map — auxiliary structure containing a binary map, used during the crossover process to determine, which agent variables will be "mixed" from different parents.
• map — an array of these binary maps, one for each agent.

The main steps of the algorithm (internal methods):

• SelectionI — the first stage of selection, responsible for choosing agents to create new solutions.
• Mutation — apply the mutation operation to the selected agents.
• Crossover — perform a crossover (mixing) operation between agents to create new "test" solutions.
• BoundaryControl — check that the agent parameter values remain within the specified limits (minimum and maximum).
• ShufflePopulation — method for randomly mixing a population.

Thus, the C_AO_BSA_Backtracking class implements an evolutionary optimization algorithm that uses the concepts of population, mutation, and crossover, as well as BSA-specific mechanisms such as backtracking, to solve optimization problems.

//————————————————————————————————————————————————————————————————————
class C_AO_BSA_Backtracking : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_BSA_Backtracking () { }
  C_AO_BSA_Backtracking ()
  {
    ao_name = "BSA";
    ao_desc = "Backtracking Search Algorithm";
    ao_link = "https://www.mql5.com/en/articles/18568";

    popSize = 10;     // population size
    mixrate = 1.0;    // crossover parameter

    ArrayResize (params, 2);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "mixrate"; params [1].val = mixrate;
  }

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

    // Check the parameters validity
    //if (popSize < 2) popSize = 2;
    if (mixrate < 0.0) mixrate = 0.0;
    if (mixrate > 1.0) mixrate = 1.0;
  }

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

  void Moving   ();
  void Revision ();

  //------------------------------------------------------------------
  double mixrate;        // crossover parameter

  private: //---------------------------------------------------------
  S_AO_Agent oldP [];    // historical population
  S_AO_Agent M    [];    // mutant population (Mutant)
  S_AO_Agent T    [];    // trial population (Trial)

  double F;              // amplitude factor for mutation
  bool   needSelection;  // flag for the necessity of executing Selection-II
  double prevFitness []; // array for storing previous fitness

  // Auxiliary structures for crossover
  struct S_Map
  {
      int val [];      // binary map for crossover

      void Init (int size)
      {
        ArrayResize (val, size);
        ArrayInitialize (val, 0);
      }
  };

  S_Map map [];        // array of binary maps for each agent

  // Algorithm methods
  void SelectionI        ();
  void Mutation          ();
  void Crossover         ();
  void BoundaryControl   (S_AO_Agent &agent);
  void ShufflePopulation (S_AO_Agent &pop []);
};
//————————————————————————————————————————————————————————————————————

The Init method is responsible for preparing the algorithm for operation before starting optimization. First of all, the basic initialization function is called, which sets the basic parameters related to the ranges of variable values (minimum, maximum values and step of change). If this basic step fails, the method aborts and returns failure.

Next, the internal data structures specific to the BSA algorithm are allocated and prepared. In particular, population arrays are created and brought to the required size: the historical population oldP, the mutant population M, the trial population T, as well as an array of binary maps for crossover "map" and the prevFitness array for storing the previous fitness values of each agent. The flag for the need for additional selection is initially set to 'false'.

After this, initialization methods are called for each agent in the population, which prepare the internal structures of each agent in accordance with the number of task parameters.

Then the historical population is filled with initial values. For each agent and each parameter in its set, a random value is generated within a given range, after which this value is adjusted according to a given change step. If all these steps are successfully completed, the method returns a value indicating that the algorithm object has been successfully initialized and is ready for further optimization.

//————————————————————————————————————————————————————————————————————
//--- Initialization
bool C_AO_BSA_Backtracking::Init (const double &rangeMinP  [],
                                  const double &rangeMaxP  [],
                                  const double &rangeStepP [],
                                  const int epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //------------------------------------------------------------------
  // Initialize additional BSA structures
  ArrayResize (oldP, popSize);
  ArrayResize (M,    popSize);
  ArrayResize (T,    popSize);
  ArrayResize (map,  popSize);
  ArrayResize (prevFitness, popSize);

  needSelection = false;

  for (int i = 0; i < popSize; i++)
  {
    oldP [i].Init (coords);
    M    [i].Init (coords);
    T    [i].Init (coords);
    map  [i].Init (coords);
  }

  // Initialize oldP historical population
  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }

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

The Moving method describes the main step of the BSA optimization algorithm and is responsible for generating new solution candidates in the population. On the first call of the method, when the "revision" flag is 'false', the active population "a" is initially populated. For each agent in the population and for each of its parameters, a random value is generated within a given range (minimum and maximum). This random value is then adjusted according to the specified parameter change step. After initialization, the "revision" flag is set to 'true' (so that this block is not executed on subsequent calls), and the needSelection flag is cleared. The method terminates.

Implementing greedy selection (Selection-II) (performed if required): if needSelection is 'true', it means that a new population was generated in the previous step, and now its fitness needs to be compared with the fitness of the previous solutions. Iteration occurs for each agent in the population. The current fitness value of the "a[i].f" agent (which was calculated for the "trial" solution) is compared with its fitness at the previous step stored in prevFitness[i]. If the "trial" solution a [i] turned out to be worse than the previous one, then the coordinate values of the current "a [i].c" agent are restored from "a [i].cP" (the coordinates of the agent at the previous step), and its "a [i].f" fitness is also restored to prevFitness [i]. This ensures that the population does not deteriorate. After the selection is completed, the needSelection flag is reset.

Basic steps of the BSA algorithm (after initialization or selection): before generating new solutions, the current fitness values of all agents from "a" are saved in prevFitness for later use in Selection-II and the current coordinates of agents from "a [i].c" are copied to "a [i].cP" to allow for rollback if the new solutions turn out to be worse.

The internal SelectionI method is called. This step is responsible for selecting or preparing the "archive" oldP operation that will be used for mutation. The internal Mutation method is called. In this step, a "mutant" M population is generated based on the active and/or archived populations. The Crossover internal method is called. At this step, the M mutant population is mixed with the current 'a' active population, resulting in the formation of a "test" T population.

The coordinates of agents from the generated T trial population are copied into the active 'a' population. Now 'a' contains new "test" solutions whose fitness needs to be calculated. The needSelection flag is set to 'true'. This signals that greedy selection (Selection-II) should be performed on the next Moving call (after the fitness of the new solutions in 'a' has been calculated).

Thus, the Moving method encapsulates one complete iteration or "epoch" of the BSA algorithm, including initialization, selection, mutation, crossover, and preparation for result comparison.

//————————————————————————————————————————————————————————————————————
//--- The main step of the algorithm
void C_AO_BSA_Backtracking::Moving ()
{
  // Initial population setup
  if (!revision)
  {
    for (int p = 0; p < popSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [p].c  [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [p].c  [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision      = true;
    needSelection = false;
    return;
  }

  // If you want to perform greedy selection after calculating fitness
  if (needSelection)
  {
    // Selection-II: Greedy selection
    for (int i = 0; i < popSize; i++)
    {
      // If the current solution (from T) is worse than the previous one, return the previous one
      if (a [i].f < prevFitness [i])
      {
        ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY);
        a [i].f = prevFitness [i];
      }
    }

    needSelection = false;
  }

  //--- BSA basic steps:

  // Save current fitness before generating a new population 
  for (int i = 0; i < popSize; i++)
  {
    prevFitness [i] = a [i].f;
    ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY);
  }

  // 1. Selection-I
  SelectionI ();

  // 2. Mutation
  Mutation ();

  // 3. Crossover
  Crossover ();

  // 4. Copy the trial population T into the 'a' main population to calculate fitness
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Set the flag to execute Selection-II after calculating fitness
  needSelection = true;
}
//————————————————————————————————————————————————————————————————————

The SelectionI method implements the first stage of selection in the BSA algorithm and is responsible for choosing the historical population that is subsequently used for mutation.

Probabilistic update of the historical population: with the probability of 50% (or, more simply, with equal probability) the oldP historical population is updated by the 'a' current population. If a random number is generated that is less than a given threshold (0.5), then the contents ('c', coordinates) of each agent from the current 'a' population are copied to the corresponding agent in the oldP historical population, and the 'f' fitness of the agent is also copied.

Shuffling historical population: Regardless of whether the historical population was updated in the previous step or not, the ShufflePopulation(oldP) method is called to shuffle the agents in the historical population. This is done to introduce randomness into the mutation. Shuffling ensures that agents in the historical population are selected in a random order, rather than in the order in which they were originally located.

Thus, SelectionI either updates the archive population with current candidate solutions or maintains its previous state, and then, in either case, shuffles the agents in the archive population, which allows for diversification of the search during subsequent mutation.

//————————————————————————————————————————————————————————————————————
//--- Selection-I: select a historical population
void C_AO_BSA_Backtracking::SelectionI ()
{
  // Update the historical population with a 50% probability 
  if (u.RNDprobab () < 0.5) // equivalent to if (a < b) where a,b ~ U(0,1)
  {
    // Copy the current population to the historical one
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY);
      oldP [i].f = a [i].f;
    }
  }

  // Shuffle the historical population
  ShufflePopulation (oldP);
}
//————————————————————————————————————————————————————————————————————

The ShufflePopulation method is designed to randomly shuffle elements in a given population of agents (represented by the S_AO_Agent structure). It takes as input an array of pop[] agents and performs in-place shuffling, i.e. changes the order of elements directly in the passed array.

Mixing algorithm: The method uses the Fisher-Yates shuffle algorithm to randomly mix elements in a population, the algorithm ensures that each permutation (order) of the elements has equal probability.

The "for" loop starts at the last element of the array (popSize - 1) and goes in reverse order to the second element (index 1). The first element (index 0) does not need to be shuffled, since by that time it will already have been "moved" during the algorithm. For each element with index i, a random index j is selected in the range from 0 to i inclusive. This is done using the u.RNDminusOne(i+1) function, which returns a random integer in the specified range (including"0 and excluding i+1).

Elements with i and j indices are swapped. For this purpose, the 'temp' temporary variable of the S_AO_Agent type is used. Since S_AO_Agent contains the 'c' array (coordinates), the array is copied. The f fitness value is also copied. The coordinate and fitness values of the pop[i] element are stored in the temp temporary variable, and the coordinate and fitness values of the pop[j] element are copied to pop[i]. The saved values from 'temp' (the original value of pop[i]) are copied to pop[j]. As a result, after the loop is completed, the order of elements in the pop[] array will be random.

//————————————————————————————————————————————————————————————————————
//--- Shuffle population
void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop [])
{
  for (int i = popSize - 1; i > 0; i--)
  {
    int j = u.RNDminusOne (i + 1);

    // Swap i and j elements
    S_AO_Agent temp;
    temp.Init (coords);

    ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY);
    temp.f = pop [i].f;

    ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY);
    pop [i].f = pop [j].f;

    ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY);
    pop [j].f = temp.f;
  }
}
//————————————————————————————————————————————————————————————————————

The Mutation method is responsible for generating the mutant population, which is a key step in the BSA algorithm. It is based on the difference between the current population and the historical population.

First, a random amplitude factor of F is generated, which determines the magnitude of the impact of the historical population on the current one. Then, for each agent in the population and for each coordinate within that agent, a new value for the coordinate in the mutant population is calculated. This is done by adding to the current coordinate the product of the F amplitude factor and the difference between the corresponding coordinate in the historical population and the current coordinate. Thus, a mutant population is created by shifting the current population in the direction determined by the historical population, with an amplitude depending on the F factor.

//————————————————————————————————————————————————————————————————————
//--- Mutation: generation of a mutant population
void C_AO_BSA_Backtracking::Mutation ()
{
  // Generate the amplitude factor
  F = u.GaussDistribution (0.0, -3.0, 3.0, 2);

  // Apply mutation: M = P + F * (oldP - P)
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

The Crossover method is involved in forming a trial population based on the current mutant population using the selected crossover strategy. This process aims to combine the features of inherited solutions to find more optimal options.

Initially, a trial population is copied from the mutant one to provide a basis for further modifications. Then a choice of crossing-over strategy occurs: with a 40% probability the first strategy is used, otherwise the second one.

If the first option is chosen, the mixrate strategy is implemented. In this case, for each agent, the number of elements (within the coordinates) that will be taken from the current agent is determined, taking into account the specified mixrate coefficient. These elements are selected randomly, without repetition. After this, the corresponding coordinates from the current solution are copied from the selected indices to the agent of the trial population.

If the second strategy is chosen, then for each agent one random element (coordinate) is selected, and in the trial population in the corresponding position this element is replaced by its value from the current solution.

After crossing over is completed, bounds checking is performed for each agent in the trial population to ensure that all decisions are valid and meet the range requirements.

//————————————————————————————————————————————————————————————————————
//--- Crossover: trial population generation
void C_AO_BSA_Backtracking::Crossover ()
{
  // Initialize the trial population as a copy of the mutant one
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Select a crossover strategy
  if (u.RNDprobab () < 0.4)
  {
    //--- STRATEGY 1: Using mixrate
    for (int i = 0; i < popSize; i++)
    {
      // Reset the map
      ArrayInitialize (map [i].val, 0);

      // Define the number of elements for the crossover
      int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords);

      // Generate unique indices for the crossover
      for (int n = 0; n < numElements; n++)
      {
        int idx;
        do
        {
          idx = u.RNDminusOne (coords);
        }
        while (map [i].val [idx] == 1); // until we find an unused index

        map [i].val [idx] = 1;
      }

      // Apply crossover
      for (int j = 0; j < coords; j++)
      {
        if (map [i].val [j] == 1)
        {
          T [i].c [j] = a [i].c [j];
        }
      }
    }
  }
  else
  {
    //--- STRATEGY 2: Mutation of only one element
    for (int i = 0; i < popSize; i++)
    {
      // Select one random element
      int randomIndex = u.RNDminusOne (coords);
      T [i].c [randomIndex] = a [i].c [randomIndex];
    }
  }

  // Boundary control for all agents in the trial population
  for (int i = 0; i < popSize; i++)
  {
    BoundaryControl (T [i]);
  }
}
//————————————————————————————————————————————————————————————————————

The BoundaryControl method is designed to check and adjust the agent's parameter values to ensure they remain within acceptable limits, as well as to convert the decisions to the desired discrete format.

For each element of the agent's coordinates, a check is performed: if the value goes beyond the established minimum or maximum limits, then this output is processed in accordance with the selected strategy. If the probability is randomly selected below 50%, a random regeneration of a value within the acceptable range occurs. Otherwise, the value is set to the nearest boundary - either the minimum or the maximum.

After this, each coordinate value is discretized — that is, converted into the closest acceptable value corresponding to the specified range and discretization step. This ensures that the solution meets the data type and range requirements.

//————————————————————————————————————————————————————————————————————
//--- Boundary control
void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent)
{
  for (int j = 0; j < coords; j++)
  {
    if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j])
    {
      // Select a boundary handling strategy
      if (u.RNDprobab () < 0.5)
      {
        // Random regeneration
        agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
      }
      else
      {
        // Set to the boundary
        if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j];
        else agent.c [j] = rangeMax [j];
      }
    }

    // Discretization
    agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
  }
}
//————————————————————————————————————————————————————————————————————

The Revision method is responsible for selecting and updating the best solution found in the current population. Going through all the solutions, it searches for the one with the maximum value of the evaluation function (fitness). If such a solution is found, it is stored as the current best result, and its coordinates are copied into a separate array designed to store the best solution at the moment. The method thus provides continuous tracking and updating of the optimal solution found during the algorithm iterations.

//————————————————————————————————————————————————————————————————————
//--- Selection-II and updating the best solution
void C_AO_BSA_Backtracking::Revision ()
{
  int bestIND = -1;

  for (int i = 0; i < popSize; i++)
  {
    // Update the global best solution
    if (a [i].f > fB)
    {
      fB = a [i].f;
      bestIND = i;
    }
  }

  // Copy the coordinates of the best solution
  if (bestIND != -1)
  {
    ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY);
  }
}
//————————————————————————————————————————————————————————————————————

The GaussDistribution method generates a random number with a Gaussian (normal) distribution centered around a given input value and bounded by a certain range, using the Box-Muller method for producing normally distributed random variables.

First, it generates two uniformly distributed random variables. Then, based on these values, a standard normally distributed random variable is calculated, which can be used to obtain a Gaussian distribution.

The method then checks whether the generated value is within the specified deviation range defined by the sigma parameter. If the generated value is outside these limits, the method is called recursively again to generate a new value until it falls within the allowed range.

Finally, the generated normally distributed variance is scaled to fit within the given output range (from outMin to outMax) relative to the In input value. This allows us to shift and scale the distribution to match your desired parameters. The result is a Gaussian distributed number centered at In, but subject to constraints on the minimum and maximum output value.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma)
{
  double logN = 0.0;
  double u1   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);
  double u2   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);

  logN = u1 <= 0.0 ? 0.000000000000001 : u1;

  double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2);

  double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma;
  
  // If z0 is outside the range [-sigmaN, sigmaN], generate anew
  if (z0 >= sigmaN || z0 <= -sigmaN) 
  {
    return GaussDistribution(In, outMin, outMax, sigma); // Recursive call
  }

  if (z0 >= 0.0) z0 =  Scale (z0,        0.0, sigmaN, 0.0, outMax - In, false);
  else           z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false);
  
  return In + z0;
}
//——————————————————————————————————————————————————————————————————————————————

Test results

BSA algorithm shows very good results.

BSA|Backtracking Search Algorithm|10.0|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9730917210619289
25 Hilly's; Func runs: 10000; result: 0.5453406317593932
500 Hilly's; Func runs: 10000; result: 0.2909827609772065
=============================
5 Forest's; Func runs: 10000; result: 0.9999986842258451
25 Forest's; Func runs: 10000; result: 0.5854340780208712
500 Forest's; Func runs: 10000; result: 0.21747482800959225
=============================
5 Megacity's; Func runs: 10000; result: 0.8476923076923077
25 Megacity's; Func runs: 10000; result: 0.3695384615384615
500 Megacity's; Func runs: 10000; result: 0.12978461538461658
=============================
All score: 4.95934 (55.10%)

In the visualization of the BSA algorithm, one can notice the spread of values in the results for functions of small and medium dimensions; however, with an increase in the population size parameters, the spread decreases, but for better convergence, it is necessary to increase the number of iterations.

BSA on the Hilly test function

BSA on the Forest test function

BSA on the Megacity test function

The BSA algorithm ranks 20th in the ranking table of population-based optimization algorithms.

#	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	ANS	across neighbourhood search	0.94948	0.84776	0.43857	2.23581	1.00000	0.92334	0.39988	2.32323	0.70923	0.63477	0.23091	1.57491	6.134	68.15
2	CLA	code lock algorithm (joo)	0.95345	0.87107	0.37590	2.20042	0.98942	0.91709	0.31642	2.22294	0.79692	0.69385	0.19303	1.68380	6.107	67.86
3	AMOm	animal migration ptimization M	0.90358	0.84317	0.46284	2.20959	0.99001	0.92436	0.46598	2.38034	0.56769	0.59132	0.23773	1.39675	5.987	66.52
4	(P+O)ES	(P+O) evolution strategies	0.92256	0.88101	0.40021	2.20379	0.97750	0.87490	0.31945	2.17185	0.67385	0.62985	0.18634	1.49003	5.866	65.17
5	CTA	comet tail algorithm (joo)	0.95346	0.86319	0.27770	2.09435	0.99794	0.85740	0.33949	2.19484	0.88769	0.56431	0.10512	1.55712	5.846	64.96
6	TETA	time evolution travel algorithm (joo)	0.91362	0.82349	0.31990	2.05701	0.97096	0.89532	0.29324	2.15952	0.73462	0.68569	0.16021	1.58052	5.797	64.41
7	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
8	BOAm	billiards optimization algorithm M	0.95757	0.82599	0.25235	2.03590	1.00000	0.90036	0.30502	2.20538	0.73538	0.52523	0.09563	1.35625	5.598	62.19
9	AAm	archery algorithm M	0.91744	0.70876	0.42160	2.04780	0.92527	0.75802	0.35328	2.03657	0.67385	0.55200	0.23738	1.46323	5.548	61.64
10	ESG	evolution of social groups (joo)	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
11	SIA	simulated isotropic annealing (joo)	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
12	BBO	biogeography based optimization	0.94912	0.69456	0.35031	1.99399	0.93820	0.67365	0.25682	1.86867	0.74615	0.48277	0.17369	1.40261	5.265	58.50
13	ACS	artificial cooperative search	0.75547	0.74744	0.30407	1.80698	1.00000	0.88861	0.22413	2.11274	0.69077	0.48185	0.13322	1.30583	5.226	58.06
14	DA	dialectical algorithm	0.86183	0.70033	0.33724	1.89940	0.98163	0.72772	0.28718	1.99653	0.70308	0.45292	0.16367	1.31967	5.216	57.95
15	BHAm	black hole algorithm M	0.75236	0.76675	0.34583	1.86493	0.93593	0.80152	0.27177	2.00923	0.65077	0.51646	0.15472	1.32195	5.196	57.73
16	ASO	anarchy society optimization	0.84872	0.74646	0.31465	1.90983	0.96148	0.79150	0.23803	1.99101	0.57077	0.54062	0.16614	1.27752	5.178	57.54
17	RFO	royal flush optimization (joo)	0.83361	0.73742	0.34629	1.91733	0.89424	0.73824	0.24098	1.87346	0.63154	0.50292	0.16421	1.29867	5.089	56.55
18	AOSm	atomic orbital search M	0.80232	0.70449	0.31021	1.81702	0.85660	0.69451	0.21996	1.77107	0.74615	0.52862	0.14358	1.41835	5.006	55.63
19	TSEA	turtle shell evolution algorithm (joo)	0.96798	0.64480	0.29672	1.90949	0.99449	0.61981	0.22708	1.84139	0.69077	0.42646	0.13598	1.25322	5.004	55.60
20	BSA	backtracking_search_algorithm	0.97309	0.54534	0.29098	1.80941	0.99999	0.58543	0.21747	1.80289	0.84769	0.36953	0.12978	1.34700	4.959	55.10
21	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
22	SRA	successful restaurateur algorithm (joo)	0.96883	0.63455	0.29217	1.89555	0.94637	0.55506	0.19124	1.69267	0.74923	0.44031	0.12526	1.31480	4.903	54.48
23	CRO	chemical reaction optimization	0.94629	0.66112	0.29853	1.90593	0.87906	0.58422	0.21146	1.67473	0.75846	0.42646	0.12686	1.31178	4.892	54.36
24	BIO	blood inheritance optimization (joo)	0.81568	0.65336	0.30877	1.77781	0.89937	0.65319	0.21760	1.77016	0.67846	0.47631	0.13902	1.29378	4.842	53.80
25	BSA	bird swarm algorithm	0.89306	0.64900	0.26250	1.80455	0.92420	0.71121	0.24939	1.88479	0.69385	0.32615	0.10012	1.12012	4.809	53.44
26	DEA	dolphin_echolocation_algorithm	0.75995	0.67572	0.34171	1.77738	0.89582	0.64223	0.23941	1.77746	0.61538	0.44031	0.15115	1.20684	4.762	52.91
27	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
28	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
29	BCOm	bacterial chemotaxis optimization M	0.75953	0.62268	0.31483	1.69704	0.89378	0.61339	0.22542	1.73259	0.65385	0.42092	0.14435	1.21912	4.649	51.65
30	ABO	african buffalo optimization	0.83337	0.62247	0.29964	1.75548	0.92170	0.58618	0.19723	1.70511	0.61000	0.43154	0.13225	1.17378	4.634	51.49
31	(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
32	FBA	Fractal-Based Algorithm	0.79000	0.65134	0.28965	1.73099	0.87158	0.56823	0.18877	1.62858	0.61077	0.46062	0.12398	1.19537	4.555	50.61
33	TSm	tabu search M	0.87795	0.61431	0.29104	1.78330	0.92885	0.51844	0.19054	1.63783	0.61077	0.38215	0.12157	1.11449	4.536	50.40
34	BSO	brain storm optimization	0.93736	0.57616	0.29688	1.81041	0.93131	0.55866	0.23537	1.72534	0.55231	0.29077	0.11914	0.96222	4.498	49.98
35	WOAm	wale 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
36	AEFA	artificial electric field algorithm	0.87700	0.61753	0.25235	1.74688	0.92729	0.72698	0.18064	1.83490	0.66615	0.11631	0.09508	0.87754	4.459	49.55
37	AEO	artificial ecosystem-based optimization algorithm	0.91380	0.46713	0.26470	1.64563	0.90223	0.43705	0.21400	1.55327	0.66154	0.30800	0.28563	1.25517	4.454	49.49
38	CAm	camel algorithm M	0.78684	0.56042	0.35133	1.69859	0.82772	0.56041	0.24336	1.63149	0.64846	0.33092	0.13418	1.11356	4.444	49.37
39	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
40	CMAES	covariance_matrix_adaptation_evolution_strategy	0.76258	0.72089	0.00000	1.48347	0.82056	0.79616	0.00000	1.61672	0.75846	0.49077	0.00000	1.24923	4.349	48.33
41	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
42	SOA	simple optimization algorithm	0.91520	0.46976	0.27089	1.65585	0.89675	0.37401	0.16984	1.44060	0.69538	0.28031	0.10852	1.08422	4.181	46.45
43	ABHA	artificial bee hive algorithm	0.84131	0.54227	0.26304	1.64663	0.87858	0.47779	0.17181	1.52818	0.50923	0.33877	0.10397	0.95197	4.127	45.85
44	ACMO	atmospheric cloud model optimization	0.90321	0.48546	0.30403	1.69270	0.80268	0.37857	0.19178	1.37303	0.62308	0.24400	0.10795	0.97503	4.041	44.90
45	ADAMm	adaptive moment estimation M	0.88635	0.44766	0.26613	1.60014	0.84497	0.38493	0.16889	1.39880	0.66154	0.27046	0.10594	1.03794	4.037	44.85
	RW	random walk	0.48754	0.32159	0.25781	1.06694	0.37554	0.21944	0.15877	0.75375	0.27969	0.14917	0.09847	0.52734	2.348	26.09

Summary

BSA represents a compromise between ease of implementation and search efficiency, occupying a stable position in the middle of the ranking table of population-based optimization algorithms. Its main advantage is the interesting concept of historical memory, which allows the algorithm to avoid premature convergence without complicating the computational scheme. Unlike many modern metaheuristics, which are overloaded with parameters and complex operators, BSA requires only a minimal set of settings, making it an attractive choice for practitioners who do not want to spend time fine-tuning external parameters.

The only significant parameter (mixrate) is intuitive and does not require a deep understanding of the internal mechanics of the algorithm. At the same time, BSA demonstrates stable performance on a wide class of problems - from simple unimodal functions to complex multi-extreme landscapes with multiple local optima. The algorithm does not claim to be a champion in terms of convergence speed or solution accuracy, but its reliability and predictability make it a workhorse. What is particularly valuable is that, as the population grows, BSA is weakly susceptible to stagnation — the mechanism of random renewal of the historical population ensures a constant influx of diversity even in the late stages of the search.

Its position in the middle of the rankings is not a sign of mediocrity, but rather a testament to its versatility and practicality, since solving real-world problems does not always require the most complex and modern tool. Sometimes a robust algorithm with clear operating logic that produces good results without the need for expert tuning is sufficient, and BSA successfully fills this niche.

Figure 2. Color gradation of algorithms according to the corresponding tests

Figure 3. Histogram of algorithm testing results (scale from 0 to 100, the higher the better, where 100 is the maximum possible theoretical result, in the archive there is a script for calculating the rating table)

BSA pros and cons:

Pros:

1. Good convergence across the tested functions.
2. Besides population size, there is only one additional external parameter.

Cons:

1. There is some tendency to get stuck on low-dimensional problems with small populations.

The article is accompanied by an archive with the current versions of the algorithm codes. 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.

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Programs used in the article

#	Name	Type	Description
1	#C_AO.mqh	Include	Parent class of population optimization algorithms
2	#C_AO_enum.mqh	Include	Enumeration of population optimization algorithms
3	TestFunctions.mqh	Include	Library of test functions
4	TestStandFunctions.mqh	Include	Test stand function library
5	Utilities.mqh	Include	Library of auxiliary functions
6	CalculationTestResults.mqh	Include	Script for calculating results in the comparison table
7	Testing AOs.mq5	Script	The unified test stand for all population optimization algorithms
8	Simple use of population optimization algorithms.mq5	Script	A simple example of using population optimization algorithms without visualization
9	Test_AO_BSA.mq5	Script	BSA test stand