Population optimization algorithms: Shuffled Frog-Leaping algorithm (SFL)

MetaTrader 5 — Examples | 31 January 2024, 13:07

3 911

Andrey Dik

1. Introduction
2. Algorithm
3. Test results

1. Introduction

The Shuffled Frog Leaping Algorithm (SFL) was proposed by М. Eusuff and other authors in 2003. This algorithm combines the principles of the memetic algorithm and the particle swarm algorithm, and its design was inspired by the behavior of a group of frogs during the foraging process.

The SFL algorithm was originally developed as a metaheuristic method for solving combinatorial optimization problems. It is based on the use of mathematical functions and informed heuristic search.

The SFL algorithm consists of several interacting virtual populations of frogs called memeplexes. Virtual frogs act as hosts or carriers of memes, where a meme represents a unit of cultural evolution. Each memeplex undergoes an independent local search using a method similar to particle swarm optimization, but with an emphasis on local search.

To support global exploration, virtual frogs are periodically shuffled and reorganized into new memeplexes using a method similar to the shuffled complex evolution algorithm. In addition, random virtual frogs are generated and replaced in the population to allow improved information to be generated randomly.

The shuffled frog-leaping is an effective method for solving complex optimization problems. It can achieve optimal solutions in various application domains. In this article, we will look at the basic principles and applications of this algorithm, as well as its advantages and limitations.

2. Algorithm

Memetics is an approach to models of evolutionary information transfer based on the concept of memes. Memes, which are analogues of genes, serve as units of cultural information spread between people through imitation, learning and other means. The concept of the meme and the basics of memetics were developed by C.R. Dawkins in 1976. Memes can be transmitted vertically - from predecessors, parents, educators, books, cultural artifacts, etc. Horizontal transmission of memes from person to person and from culture to culture is also possible. Even though memes are pure information, their functioning leads to significant changes in human behavior.

Memetic algorithms (M-algorithms) are defined as hybrid population metaheuristic search engine optimization algorithms based on the concept of the meme and the neo-Darwinian principle of evolution. In the context of M-algorithms, a meme is an implementation of a local optimization algorithm that refines current solutions at each iteration or after a certain number of iterations. M-algorithms can be viewed as a hybridization of one of the population-based global search algorithms and one or more classical or population-based local optimization algorithms. Initially, M-algorithms were proposed as one of the options for increasing the efficiency of genetic algorithms.

The efficiency of M-algorithms largely depends on the values of their free parameters. A number of studies have shown that the choice of memes used has a very large impact on the efficiency of these algorithms. Therefore, this problem occupies one of the central places in works devoted to M-algorithms.

Memes represent one of the revolutionary ideas that imply the similarity between the evolution of genes and the evolution of human culture. According to Dawkins, a meme is a unit of cultural exchange, the equivalent of a gene in culture. A meme can be a gesture, a word, or an idea. Any unit of cultural information that can be transferred from person to person through imitation learning is a meme.

Memetic algorithms, unlike genetic ones, imitate the process of cultural evolution. Moscato's approach uses an analogy with the evolution of memes. The memetic algorithm consists of the following stages: local search, cooperation, competition and search termination criterion. A memetic class is a wide class of algorithms united by a common idea: the inclusion of individual learning of individuals in the genetic algorithm and the use of information about the structure of the space of possible solutions. The problem of balancing population and local search can be viewed as a general problem of maintaining a balance between extensive and intensive exploration of the search space.

The memetic algorithm broadly includes the following components:

1. Local search. To implement it, we can use a simulated annealing and lifting algorithms.
2. Cooperation. The exchange of information between individuals can be carried out through a procedure similar to the use of the two-point crossing operator in genetic algorithms.
3. Competition. Selection is similar to that in genetic algorithms and usually consists of selecting the fittest individuals in the population and excluding the less fit from it.
4. Search end criterion. In memetic algorithms, this may include estimating the diversity of individuals, in addition to counting the number of iterations and assessing the improvement in the result.

Memetic algorithms are a broad class of algorithms united by the common idea of individual learning of individuals and the use of information about the structure of the space of possible solutions.

Memes, like genes, are replicators, that is, objects capable of self-reproduction. For memes, survival and reproduction depend on the presence of a host that spreads the meme. Memes can change, forming new memes, and participate in the struggle for resources - people's minds.

Memes are often combined into complexes, or memeplexes, to enhance the struggle for carriers. Memeplexes are analogous to the symbiotic collections of genes that make up the genetic codes of biological organisms. An example of a memeplex is religion. Memeplexes have a profound influence on shaping individual and social behavior.

Let's move directly to Shuffled Frog-Leaping algorithm. The main idea of the algorithm is to divide the entire population of frogs with a global leader G into memes. Each meme (group) has a leader L (Figure 1).

frogs1

Figure 1. A population of frogs with a global leader (G), divided into memes with their local leader (L)

Within each meme, frogs tend to move in the direction of the local leader. The leadership is updated if the position of one of the frogs improves. Memes are not separated in the search space and may have overlaps. Thus, a frog located in the territory of one meme may well belong to another. This creates a dynamic environment where frogs can move spatially from one meme to another depending on changes in their positions in the search space.

We consider a global conditional optimization problem, in which the fitness function is subject to maximization. The SFL algorithm includes the following basic steps.

1.0 Algorithm initialization
1.1 Creation of an initial population of frogs with random coordinates.
1.2 Determining the fitness of each frog.
1.3 Creation of memeplexes (subpopulations), distribution of frogs among memeplexes.

2.0 Cycle of searching for the optimal solution
2.1 For each memeplex:
    2.1.1 Determine the best frog.
    2.1.2 Move the remaining frogs towards the best frog in the memeplex.
2.2 If moving the frog does not improve its fitness:
    2.2.1 Move it towards the globally better frog.
    2.2.2 If this does not improve fitness, move the frog to a random place on the field.

3.0 Measuring frog fitness
3.1 Measure fitness for each frog in the population.
3.2 Update information about the best frog in each memeplex and in the population as a whole.

4.0 Determining the globally best frog and updating memeplexes
4.1 Determine the globally best frog for the entire population.
4.2 If this is the last cycle:
    4.2.1 Reset the memeplex cycle counter.
    4.2.2 Generate random indices for frogs.
    4.2.3 Copy frogs to memeplexes using new indices.
    4.2.4 Determine the best frog in each memeplex.
    4.2.5 Reset frogs fitness and step.
4.3 If this is not the last cycle:
    4.3.1 Copy the fitness and coordinates of frogs from the population to the corresponding memeplex frogs.
    4.3.2 Determine the best frog in each memeplex.
    4.3.3 Determine the direction of the next jump for each frog depending on its fitness.

Thus, the basis of the SFL algorithm is a combination of local search within each of the memeplexes and global search by exchanging information about the positions of the best memeplex agents.
This algorithm is a modification of the SFL algorithm, in which at the local search stage the agent moves not exactly in the direction of the best agent of the corresponding memeplex, but in some randomly perturbed direction. Both sequential and parallel hybridizations of the algorithm with many population algorithms are known (including the artificial immune system algorithm).

frog2

Figure 2. Frog leaps. If the previous move was unsuccessful, then the next jump will be made from the same place

The logical unit of the SFL optimization algorithm is the frog. It can be described by the S_Frog structure, which represents an agent in the search space.

The S_Frog structure contains the following fields:

c - array of coordinates of the frog's current position.
cPrev - array of coordinates of the frog's previous position.
f - fitness function for the frog's current position.
fPrev - fitness function for the frog's previous position.
frogStep - number of the step the frog is located on.

//——————————————————————————————————————————————————————————————————————————————
struct S_Frog
{
  void Init (int coords)
  {
    ArrayResize (c,     coords);
    ArrayResize (cPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
    frogStep = 0;
  }
  double c     []; //coordinates
  double cPrev []; //previous coordinates
  double f;        //fitness
  double fPrev;    //previous fitness
  int    frogStep; //frog step
};
//——————————————————————————————————————————————————————————————————————————————

The S_Memeplex structure describes the memeplex in the algorithm. It contains the following fields:

frogs - array of frogs that make up the memeplex.
fBest - best value of the fitness function among all frogs in the memeplex.
cBest - array of coordinates corresponding to the best value of the fitness function in the memeplex.

//——————————————————————————————————————————————————————————————————————————————
struct S_Memeplex
{
  S_Frog frogs [];
  double fBest;     //best fitness
  double cBest [];  //best coordinates
};
//——————————————————————————————————————————————————————————————————————————————

The C_AO_SFL class provides methods for initializing the algorithm, moving frogs and revising the population. It also contains auxiliary methods for converting values and generating random numbers.

Let's write the SFL algorithm class that includes the following fields:

cB - array storing the best coordinates;
fB - variable storing the fitness function value for the best coordinates;
frogs - array storing all frogs in the population;
mems - array storing memeplexes (groups of frogs);
rangeMax - array storing the maximum values for each search coordinate;
rangeMin - array storing the minimum values for each search coordinate;
rangeStep - array storing search steps for each coordinate.

Public class methods:

Init - method for initializing algorithm parameters accepts the following parameters:
coordinatesNumberP - number of search coordinates;
populationSizeP - population size (number of frogs);
numbMemsP - number of memeplexes (groups of frogs);
numbCyclesP - number of cycles in the memeplex;
frogStepsToLocalMaxP - number of frog steps to the local maximum;
movConstantP - displacement constant (search step) of frogs.

Moving - method that implements the movement of frogs in the search space.
Revision - method that implements a revision of the frog population and updates the best coordinates.
SeInDiSp - auxiliary method that converts a value from one range to another with a given step.
RNDfromCI - auxiliary method that generates a random number in a given interval.

Description of private class fields:

coordinatesNumber - number of search coordinates;
frogsNumber - number of frogs in the population;
numbMems - number of memeplexes (groups of frogs);
numbCycles - number of cycles in the memeplex;
frogStepsToLocalMax - number of frog steps to the local maximum;
movConstant - displacement constant (search step) of frogs;
memsFrogs - number of frogs in each memeplex;
numbCyclesCNT - cycle counter;
vect - array storing a vector;
indexes - array storing indices;
revision - flag indicating the need for a population revision.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SFL
{
  //----------------------------------------------------------------------------
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates
  public: S_Frog frogs     []; //all frogs
  public: S_Memeplex mems  []; //memeplexes

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search


  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP);        //movement step (0.0 .. 1.0)

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber;   //coordinates number
  private: int    frogsNumber;         //frogs number
  private: int    numbMems;            //number of memeplexes
  private: int    numbCycles;          //number of cycles in the memeplex
  private: int    frogStepsToLocalMax; //frog steps to the local maximum
  private: double movConstant;         //movement step (0.0 .. 1.0)
  private: int    memsFrogs;           //number of frogs in the memplex
  private: int    numbCyclesCNT;       //cycle counter

  private: double vect    [];          //vector
  private: int    indexes [];          //indexes
  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

To initialize the algorithm, we will use the Init initialization method, which has several parameters:

coordinatesNumberP - number of coordinates
populationSizeP - population size
numbMemsP - number of memeplexes
numbCyclesP - number of cycles in the memeplex
frogStepsToLocalMaxP - number of frog steps to the local maximum
movConstantP - movement step (from 0.0 to 1.0)

First, the method resets the random number generator and sets the initial value of the fB (-DBL_MAX) and revision (false) variables.
Next, the method creates the rangeMax, rangeMin, rangeStep, vect, indexes, cB, frogs and mems arrays with the required dimensions.
The method initializes each frog in the frogs array and every frog in every memeplex in the mems array using the Init method passing the number of coordinates.
The method then sets the initial value of the fBest variable of each memeplex in -DBL_MAX and creates the cBest array for each memeplex with the required size.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP)         //movement step (0.0 .. 1.0)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber   = coordinatesNumberP;
  frogsNumber         = populationSizeP;
  numbMems            = numbMemsP;
  numbCycles          = numbCyclesP;
  frogStepsToLocalMax = frogStepsToLocalMaxP;
  movConstant         = movConstantP;
  memsFrogs           = frogsNumber / numbMems;

  numbCyclesCNT       = 0;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (vect,      coordinatesNumber);
  ArrayResize (indexes,   frogsNumber);

  ArrayResize (cB, coordinatesNumber);

  ArrayResize (frogs, frogsNumber);
  for (int i = 0; i < frogsNumber; i++)
  {
    frogs [i].Init (coordinatesNumber);
  }

  ArrayResize (mems, numbMems);
  for (int i = 0; i < numbMems; i++)
  {
    ArrayResize (mems [i].frogs, memsFrogs);
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      mems [i].frogs [frgs].Init (coordinatesNumber);
    }

    mems [i].fBest = -DBL_MAX;
    ArrayResize (mems [i].cBest, coordinatesNumber);
  }
}
//——————————————————————————————————————————————————————————————————————————————

The Moving method is designed to move frogs through the search space. The method is quite large, so we will analyze it in parts.

At the beginning of the code, we check the value of the revision variable. If 'false', the following block of code is executed:

- Set the fB variable initial value, which represents the best estimate of the function. In this case, the -DBL_MAX value (negative infinity) is assigned to it.
- Launch the cycle, in which each frog is initialized. For each frog:
- Launch the cycle for each c coordinate.
- Generate a random value for the c coordinate using the RNDfromCI function, which returns a random number within a given range.
- c coordinate value is converted to the range using the SeInDiSp function, which allows you to shift a value within a range with a certain step.
- The f function value for the frog is set to -DBL_MAX.
- Set the value of the previous fPrev function value for a frog to -DBL_MAX.
- frogStep is set to 0.

- Launch the cycle for each c coordinate.
- Calculate vect[c], which is the product of the difference between the maximum and minimum value of the movConstant range.
- The revision variable is set to 'true' to indicate that initialization has been completed.
- The numbCyclesCNT variable is set to 0.

Thus, this code initializes the frogs, sets the initial values of the function and other parameters, and also calculates the vect[c] value for each c coordinate.

if (!revision)
{
  fB = -DBL_MAX;

  for (int frgs = 0; frgs < frogsNumber; frgs++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      frogs [frgs].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      frogs [frgs].c [c] = SeInDiSp (frogs [frgs].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      frogs [frgs].f        = -DBL_MAX;
      frogs [frgs].fPrev    = -DBL_MAX;
      frogs [frgs].frogStep = 0;
    }
  }

  for (int c = 0; c < coordinatesNumber; c++)
  {
    vect [c] = (rangeMax [c] - rangeMin [c]) * movConstant;
  }

  revision      = true;
  numbCyclesCNT = 0;
}

If revision flag is 'true', this means that the algorithm has entered the stage of moving frogs. We have already become familiar with method variables, so we will not dwell on them in detail. This part of the code implements the frog leaps in accordance with the individual step for each frog. On the first step, the frog leaps towards the local leader, the attempt is counted if the frog's position has improved, otherwise the step counter is increased. In other words, a fixed number of attempts are allocated for leaping towards the local leader according to the external parameters of the algorithm.

For the leader frog, a different principle of movement is used, unlike all others in the memeplex. The leader simply jumps in a random direction in a small vicinity of his position.

Unlike the leader, all other frogs leap towards the leader according to the following equation:

coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);

The equation shows that the new coordinate of the frog will be obtained by moving towards the leader by the distance between them, normalized to the Euclidean distance for all coordinates, while introducing the rnd random component.

else
{
  int cnt = 0;
  double eDistance = 0.0; //euclidean distance
  double coordDiff = 0.0; //the difference in coordinates

  for  (int m = 0; m < numbMems; m++)
  {
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      //2.1 move the frogs towards the best one in the memeplex-----------------
      if (mems [m].frogs [frgs].frogStep < frogStepsToLocalMax)
      {
        if (mems [m].frogs [frgs].fPrev != -DBL_MAX && mems [m].fBest != -DBL_MAX)
        {
          if (mems [m].frogs [frgs].fPrev == mems [m].fBest)
          {
            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * 0.2;
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
          else
          {
            eDistance = 0.0;
            coordDiff = 0.0;

            //calculate Euclidean distance----------------------------------
            for (int c = 0; c < coordinatesNumber; c++)
            {
              coordDiff  = mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c];
              coordDiff *= coordDiff;
              eDistance += coordDiff;
            }

            eDistance = sqrt (eDistance);

            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
        }
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c];
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }
      else
      {
        //2.2 move towards global if the move is worse than the previous one-----
        if (mems [m].frogs [frgs].frogStep /*==*/ >= frogStepsToLocalMax)
        {
          eDistance = 0.0;
          coordDiff = 0.0;

          //calculate Euclidean distance------------------------------------
          for (int c = 0; c < coordinatesNumber; c++)
          {
            coordDiff  = cB [c] - mems [m].frogs [frgs].cPrev [c];
            coordDiff *= coordDiff;
            eDistance += coordDiff;
          }

          eDistance = sqrt (eDistance);

          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((cB [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
        //2.3 move randomly across the field --------------------------------
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);

            coord    = RNDfromCI (rangeMin [c], rangeMax [c]);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }

      frogs [cnt] = mems [m].frogs [frgs];
      cnt++;
    }
  }


  //--------------------------------------------------------------------------
  numbCyclesCNT++;
}

The Revision method is designed to determine the global leader at each iteration of the algorithm and determine local leaders. If the number of cycles allocated for the movement of frogs within each memeplex is exhausted, then we perform a shuffle - we reassign frogs to memeplexes randomly, thereby exchanging information between memeplexes. This method also takes into account the corresponding leap steps - the direction the frog will move at the next iteration (towards the local or global leader or in a random direction in the search space).

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Revision ()
{
  //4.1 determine the globally best one by population-------------------------------
  for (int i = 0; i < frogsNumber; i++)
  {
    if (frogs [i].f > fB)
    {
      fB = frogs [i].f;
      ArrayCopy (cB, frogs [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  int cnt = 0;

  //if the last loop=========================================================
  if (numbCyclesCNT >= numbCycles)
  {
    //4.2.0 reset the memeplex cycle counter-----------------------------------
    numbCyclesCNT = 0;

    //4.2.1 generate random indices--------------------------------------
    for (int i = 0; i < frogsNumber; i++) indexes [i] = i;

    Shuffle (indexes, frogsNumber);

    //4.2.2 copy to memeplexes accidentally------------------------------------
    for  (int m = 0; m < numbMems; m++)
    {
      mems [m].fBest = -DBL_MAX;

      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs] = frogs [indexes [cnt]];
        cnt++;

        //4.2.3 determine the best one in each memeplex---------------------------
        if (mems [m].frogs [frgs].f > mems [m].fBest)
        {
          mems [m].fBest = mems [m].frogs [frgs].f;
          ArrayCopy (mems [m].cBest, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
        }

        //4.2.4 reset frogs' fitness and step------------------------
        mems [m].frogs [frgs].f        = -DBL_MAX;
        mems [m].frogs [frgs].fPrev    = -DBL_MAX;
        mems [m].frogs [frgs].frogStep = 0;
      }
    }
  }
  //if NOT the last cycle======================================================
  else
  {
    for  (int m = 0; m < numbMems; m++)
    {
      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs].frogStep++;

        //4.3.1 copy the fitness and coordinates of frogs from the population to the
        //corresponding frog memeplexes
        mems [m].frogs [frgs].f = frogs [cnt].f;
        ArrayCopy (mems [m].frogs [frgs].c, frogs [cnt].c, 0, 0, WHOLE_ARRAY);

        //4.3.2 determine the best one in each memeplex---------------------------
        if (frogs [cnt].f > mems [m].fBest)
        {
          mems [m].fBest = frogs [cnt].f;
          ArrayCopy (mems [m].cBest, frogs [cnt].c, 0, 0, WHOLE_ARRAY);
        }

        //4.3.3 determine the direction of the next jump------------------------
        if (mems [m].frogs [frgs].frogStep <= frogStepsToLocalMax)
        {
          if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
          {
            mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
            ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
            mems [m].frogs [frgs].frogStep = 0;
          }
        }
        else
        {
          if (mems [m].frogs [frgs].frogStep >= frogStepsToLocalMax + 1)
          {
            if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
            {
              mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
              ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
              mems [m].frogs [frgs].frogStep = 0;
            }
          }
          else
          {
            mems [m].frogs [frgs].f        = -DBL_MAX;
            mems [m].frogs [frgs].fPrev    = -DBL_MAX;
            mems [m].frogs [frgs].frogStep = 0;
          }
        }

        cnt++;
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

In the SFL optimization algorithm, we will need to randomly mix frogs between memeplexes. The random shuffling problem is interesting because its algorithmic solution is non-trivial, but Ronald Fisher and Frank Yates offered an effective and fast algorithm. Previously, we did not use a similar concept, since there was no need for it. It is widely used in computer science, especially in the fields of genetic algorithms, cryptography and statistics.

The main advantages of the Fisher-Yates algorithm:
1. Ease of implementation: The Fisher-Yates algorithm is easy to implement in any programming language. It does not require complex mathematical calculations or special libraries.
2. Efficiency: The Fisher-Yates algorithm runs in linear time. In other words, the execution time depends on the number of elements that need to be rearranged. This makes it very efficient for large data sets.
3. Randomness: The Fisher-Yates algorithm ensures highly random permutations. This is important for many applications such as random tests, encryption, and simulations.
4. Input independence: The Fisher-Yates algorithm can be applied to any set of data without the need to know its structure or properties. This makes it a versatile tool for many tasks.
5. Pseudo-randomness: The Fisher-Yates algorithm generates pseudo-random permutations that can be used in many applications where randomness (but not necessarily true randomness) is required.

In general, the Fisher-Yates algorithm is simple, efficient and versatile. It is a useful tool for many problems involving randomness and data permutations.

//——————————————————————————————————————————————————————————————————————————————
void Shuffle (int & arr [], int size)
{
  int index, temp;
  for (int i = size - 1; i > 0; i--)
  {
    index = MathRand () % (i + 1);
    temp = arr [i];
    arr [i] = arr [index];
    arr [index] = temp;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Test results

SFL test stand results:

C_AO_SFL:50;25;15;5;0.7
=============================
5 Rastrigin's; Func runs 10000 result: 66.52578871476199
Score: 0.82429
25 Rastrigin's; Func runs 10000 result: 52.38937199890908
Score: 0.64913
500 Rastrigin's; Func runs 10000 result: 44.5591163558836
Score: 0.55211
=============================
5 Forest's; Func runs 10000 result: 0.5762718670482314
Score: 0.32597
25 Forest's; Func runs 10000 result: 0.16329693292687839
Score: 0.09237
500 Forest's; Func runs 10000 result: 0.04968320483668511
Score: 0.02810
=============================
5 Megacity's; Func runs 10000 result: 3.1599999999999997
Score: 0.26333
25 Megacity's; Func runs 10000 result: 1.016
Score: 0.08467
500 Megacity's; Func runs 10000 result: 0.3004
Score: 0.02503
=============================
All score: 2.84501

When observing the animation of the SFL algorithm, no clustering or grouping by individual memes is detected, although the opposite was expected. Optimization agents (points) are distributed chaotically across the field, and there are no patterns in the movement of particles. The low quality of convergence of the algorithm is immediately noticeable, which, manifests itself in getting stuck in local extrema, which can be determined by long smooth sections on the convergence graph. However, with an increase in the number of optimized parameters, the "stepping" decreases.

SFL on the Rastrigin test function.

SFL on the Forest test function.

SFL on the Megacity test function.

It is time for conclusions. According to the results table, SFL algorithm shows below average results in terms of optimization. Although SFL has some advantage on the smooth Rastrigin function, it is not enough to recommend it as the preferred algorithm for smooth functions. On Forest and Megacity bended functions, SFL shows worse results compared to smooth functions. This can be explained by the fact that on flat sections of the optimized function, leaping frogs do not improve their position and constantly return to their original place, without being able to "catch" on the terrain.

AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
AO	Description	10 params (5 F)	50 params (25 F)	1000 params (500 F)	Rastrigin final	10 params (5 F)	50 params (25 F)	1000 params (500 F)	Forest final	10 params (5 F)	50 params (25 F)	1000 params (500 F)	Megacity final	Final result
SSG	saplings sowing and growing	1.00000	1.00000	0.55665	2.55665	0.72740	0.94522	1.00000	2.67262	0.76364	0.85977	1.00000	2.62340	100.000
HS	harmony search	0.99676	0.95282	0.48178	2.43136	1.00000	0.98931	0.44806	2.43736	1.00000	1.00000	0.41537	2.41537	92.329
ACOm	ant colony optimization M	0.34611	0.17985	0.17044	0.69640	0.86888	1.00000	0.77362	2.64249	1.00000	0.88930	0.05606	1.94536	65.347
IWO	invasive weed optimization	0.95828	0.67083	0.29807	1.92719	0.70773	0.46349	0.31773	1.48896	0.80000	0.42067	0.33289	1.55356	61.104
COAm	cuckoo optimization algorithm M	0.92400	0.46794	0.26004	1.65199	0.58378	0.34034	0.16526	1.08939	0.72727	0.33025	0.17083	1.22835	47.612
FAm	firefly algorithm M	0.59825	0.33980	0.17135	1.10941	0.51073	0.42299	0.49790	1.43161	0.34545	0.28044	0.35258	0.97847	41.537
ABC	artificial bee colony	0.78170	0.32715	0.20822	1.31707	0.53837	0.21455	0.13344	0.88636	0.56364	0.26569	0.13926	0.96858	36.849
GSA	gravitational search algorithm	0.70167	0.45217	0.00000	1.15384	0.31660	0.36416	0.33204	1.01280	0.59395	0.35054	0.00000	0.94448	36.028
BA	bat algorithm	0.40526	0.63761	0.84451	1.88738	0.20841	0.17477	0.25989	0.64308	0.29698	0.09963	0.17371	0.57032	35.888
BFO	bacterial foraging optimization	0.67203	0.30963	0.11813	1.09979	0.39702	0.26623	0.20652	0.86976	0.52122	0.33211	0.18932	1.04264	34.693
EM	electroMagnetism-like algorithm	0.12235	0.46278	1.00000	1.58513	0.00000	0.03498	0.34880	0.38377	0.00000	0.00000	0.10924	0.10924	22.091
SFL	shuffled frog-leaping	0.40072	0.23739	0.26548	0.90360	0.20153	0.04147	0.02652	0.26952	0.27273	0.05535	0.06639	0.39446	15.203
MA	monkey algorithm	0.33192	0.33451	0.14644	0.81287	0.10012	0.07891	0.08932	0.26836	0.21818	0.04243	0.10720	0.36781	13.603
FSS	fish school search	0.46812	0.25337	0.11302	0.83451	0.12840	0.05013	0.06516	0.24369	0.16971	0.04796	0.08283	0.30050	12.655
PSO	particle swarm optimisation	0.20449	0.08200	0.07160	0.35809	0.18895	0.10486	0.21738	0.51119	0.23636	0.05903	0.01957	0.31496	10.031
RND	random	0.16826	0.09743	0.08019	0.34589	0.13496	0.04810	0.04715	0.23021	0.16971	0.03875	0.04922	0.25767	5.302
GWO	grey wolf optimizer	0.00000	0.00000	0.02256	0.02256	0.06570	0.00000	0.00000	0.06570	0.32727	0.07378	0.02557	0.42663	1.000

Summary

SFL is more of a "superstructure" for other optimization algorithms that can be used as logic for moving agents in memeplexes. SFL was originally invented as a technique for improving the optimization quality of existing algorithms. As a stand-alone optimization algorithm, SFL demonstrates below-average results among the population algorithms discussed earlier. SFL has great potential for experimentation with combining logical steps in an algorithm to enhance both exploration and exploitation. SFL is highly flexible and adaptable, making it suitable for specific use in specific optimization problems.

The histogram of the algorithm test results is provided below (on a scale from 0 to 100, the more the better, in the archive there is a script for calculating the rating table using the method described in this article).

chart

Figure 3. Histogram of the final results of testing algorithms

Pros and cons of the shuffled frog-leaping (SFL) algorithm:

Pros:
1. A small number of external parameters.
2. The originality of the algorithm architecture, the ability to use other optimization algorithms in memes.

Cons:
1. High computational complexity.
2. Poor results on smooth and discrete functions.
3. Getting stuck on functions with flat horizontal "pads".

Each article features an archive that contains updated current versions of the algorithm codes for all previous articles. The article is based on the accumulated experience of the author and represents his personal opinion. The conclusions and judgments are based on the experiments.

Translated from Russian by MetaQuotes Ltd.
Original article: https://www.mql5.com/ru/articles/13366

Attached files |

Download ZIP

17_The_world_of_AO_SFL.zip (143.2 KB)

Warning: All rights to these materials are reserved by MetaQuotes Ltd. Copying or reprinting of these materials in whole or in part is prohibited.

Population optimization algorithms: Shuffled Frog-Leaping algorithm (SFL)

Contents

1. Introduction

2. Algorithm

3. Test results

Summary

Other articles by this author