Dolphin Echolocation Algorithm (DEA)
580
0
Contents
Introduction
With each new article, we get closer to our goal: finding a suitable algorithm for solving optimization problems with our trading robots. We will explore another nature-inspired algorithm based on the echolocation capabilities of some marine animals.
Imagine a dolphin hunting in the dark depths of the ocean. Visibility is practically zero, but this does not prevent it from successfully finding prey. The secret lies in an amazing ability: the dolphin emits a series of clicks and, using the reflected echo, creates an accurate picture of the surrounding space. An interesting fact is that the frequency of these clicks varies: rare clicks during a general search and frequent ones when the target is close. It is this unusual strategy that forms the basis of the DEA (Dolphin Echolocation Algorithm).
In the world of optimization, we often face a similar challenge: finding the best solution in a vast space of possibilities without having the full picture. Like a dolphin in the ocean, we start with a broad search and gradually focus on the most promising areas.
Implementation of the algorithm
To better understand how the algorithm works, let's imagine the following situation. You and your friends are looking for gold on a large beach, armed with metal detectors. At the beginning of the search, it makes sense to spread out across the entire area — this way you have a better chance of stumbling upon something interesting. But as soon as one of you hears a strong signal, they inform the others, and gradually the whole team begins to concentrate in promising places. By the end of the search, everyone is digging near the strongest signal. This is the essence of the dolphin echolocation algorithm.
In the algorithm, the role of dolphins is played by search agents - points in the solution space. Each such "dolphin" represents a potential solution to the problem. For example, if we are looking for the minimum of a simple function y = x², then one dolphin may be at the point x = -3 (where y = 9), another at the point x = 1 (where y = 1), and the third will randomly end up at the point x = 0 (where y = 0) - this will be our champion.
But how do dolphins exchange information? This is where the concept of effective radius, denoted as "Re", comes into play. Think about how far the light from a flashlight spreads. At Re = 1 we have a narrow beam that illuminates only the immediate area. At Re = 3, the light spreads wider, covering more space. At Re = 5 or above, the search behaves more like a floodlight. In the context of the algorithm, this means that information about a good solution spreads to neighboring areas, and the strength of this influence decreases with distance.
All this information is accumulated in the form of a "prospectivity map", which the algorithm calls the accumulated fitness (AF). Imagine a heat map of a city, where "hot" zones indicate areas of high activity. In our case, "hot" zones are areas where dolphins have found good solutions (prey). The more successful finds in a particular area, the "hotter" it becomes, attracting other dolphins.
However, the algorithm is smarter than simply clustering in one place. It uses a parameter called Predetermined Probability (PP) which controls the balance between exploring new areas and exploiting good spots already found. At the beginning, when PP is low, around 0.1, the algorithm experiments, and then, when PP is around 0.5, it relies more on proven approaches, and, as PP approaches 1, it uses only the most effective methods.
Let's look at a specific example of how the algorithm works. Let's say we are looking for the highest point in a hilly area. At the beginning of the search, our dolphins are randomly scattered throughout the area - some in the valley, some on the slopes, and some are lucky enough to be on top of a hill. After evaluating the height of each position, the algorithm determines that the dolphin at the top has found the best spot. Now something interesting happens: the area around this lucky dolphin becomes more attractive to the others, but – and this is the key point – the very point where the leader is located is temporarily "zeroed out". This forces other dolphins to explore nearby areas rather than congregate in one spot. This approach helps to avoid premature convergence and find other potentially good solutions.
As the algorithm works, the picture changes. At iteration 50, we see that the dolphins begin to cluster in hilly areas, but still retain some diversity. By the 100th iteration, most of them are concentrated at the highest points of the terrain, and at the end, all dolphins are concentrated at the global maximum. The efficiency of the algorithm depends on the correct configuration of the parameters.
The choice of the effective Re radius is important to balance between local and global search. At Re = 1, we get a very precise but narrowly focused search – as if we were looking for a needle in a haystack with a magnifying glass. Increasing Re to 3-4 gives a balanced approach, similar to searching with a flashlight. And when Re is greater than 5, the algorithm works like a spotlight, covering larger areas, but losing accuracy.
The Power parameter determines how abruptly the algorithm switches from exploration to exploitation. At Power = 1 this transition is smooth and gradual. A Power value of 2 (recommended) produces a more pronounced transition, while Power values of 3 and higher produce a sharper transition, which can be useful for certain types of tasks.
The initial probability of PP1 sets the starting balance between exploration and exploitation. A low value (0.05) means aggressive exploration of the space, the standard value of 0.1 provides a good balance, and a high value (0.5) leads to a quick focus on the solutions found.
The main advantage of DEA is its adaptability — the algorithm automatically adjusts the balance between exploring new areas and delving into promising zones. Yet it remains relatively simple, requiring only four settings to be configured. The mechanism of information propagation through accumulated fitness allows for the efficient use of knowledge about the search space, and zeroing the AF for the best positions helps avoid getting stuck in local optima.
Of course, the algorithm has some limitations. It requires additional memory to store the accumulated fitness of all alternatives, which can be a problem for very large search spaces. And perhaps one more thing: the efficiency of the algorithm depends on the correct choice of the Re effective radius. Below is a schematic illustration of the algorithm operation.
Figure 1. DEA algorithm in operation
The main stages of the DEA algorithm are shown in the figure:
- Initial exploration - dolphins (search agents) in random positions with Re echolocation radius.
- Accumulated fitness (AF) distribution - How "AF" accumulates around dolphin positions.
- The convergence process consists of three sub-stages that show the transition from exploration to exploitation.
The illustration helps us understand how dolphins use echolocation to find the optimum, how information is disseminated through accumulated fitness, how the parameter "Re" affects the search width, and how "PP" controls the balance between exploration and exploitation. Key concepts — formulas for PP (predetermined probability) and AF. Algorithm flow chart — basic steps with a cycle. Influence of the Re parameter — visualization of narrow, medium and wide radius of influence.
The color scheme in the figure: blue - normal dolphins, red - the best solution, blue gradients - accumulated fitness levels, gray - search space.
Now that we have some idea of the algorithm, we can move on to writing detailed pseudocode.
Inputs:
- Number of dolphins (search agents)
- Effective echolocation radius
- Degree of convergence curve
- Initial predetermined probability
- Search space boundaries and sampling step for each dimension
Initialization:
Creating a space of alternatives:
- For each dimension of the search space, generate a set of possible alternatives
- If a sampling step is specified, create alternatives with this step from minimum to maximum
- If step is not specified, generate 500 uniformly distributed alternatives
- Check the effective radius: it should not exceed a quarter of the number of alternatives
Initial placement of dolphins:
- Randomly place all dolphins in the search space
- For each dolphin, calculate the quality of its position (fitness)
- Initialize the accumulated fitness to zero for all alternatives
Basic optimization loop:
Repeat for a specified number of iterations:
Phase 1. Calculating the predetermined probability
Calculate the probability of maintaining the best position at the current iteration. At the beginning of the process, this probability is equal to the initial value, then gradually increases according to a power function up to unity by the end of optimization.
Phase 2. Calculation of the dynamic adaptation coefficient
Calculate the coefficient that determines the balance between local and global search. The coefficient is equal to the ratio of the difference between the best and worst solutions to the sum of the deviations of all solutions from the best. When the population is diverse, the coefficient is high; when it converges, it is low.
Phase 3. Accumulation of information on fitness
For each dolphin:
- Normalize its fitness relative to the current range in the population
- For each coordinate, find the closest alternative to the dolphin's position
- Spread quality information within the echolocation radius of this alternative
- The strength of influence decreases linearly with distance from the center
- Apply reflection at the boundaries of space to preserve information
- Add a small value to all accumulated fitnesses to avoid zero probabilities
Step 4. Resetting information for a better position
Find the dolphin with the best solution and reset the accumulated fitness for the alternatives corresponding to its coordinates. This prevents the search from becoming too concentrated in one point.
Step 5. Selecting new positions
For each dolphin and each of its coordinates:
- If this is the best dolphin and there is a chance to save the position, leave the coordinate unchanged
- Otherwise, if there is accumulated information about fitness, select a new alternative in proportion to this information using the roulette method
- If the accumulated information is missing or insufficient:
- with a probability equal to the dynamic coefficient, perform a local search within the echolocation radius
- otherwise, perform a global search by selecting a random alternative
- Apply search space constraints and discretization
Stage 6. Evaluation of new positions
Calculate the quality of the solution for each dolphin in its new position.
Stage 7. Global information update
Update the records of the best and worst solutions in the population. If a solution is found that is better than the current global optimum, we should keep it.
Completion:
After completing all iterations, return the best solution found and its quality.
Let us now proceed to the DEA implementation.
Let's write the S_Alternative structure. It stores information about an alternative in the decision-making process for optimization and contains "value" (the value characterizing this alternative, an assessment of the effectiveness and AF) - the accumulated fitness for this alternative, this is necessary for assessing the quality of the alternative when it is necessary to apply an iterative process.
//———————————————————————————————————————————————————————————————————— struct S_Alternative { double value; // alternative value double AF; // accumulated fitness for this alternative }; //————————————————————————————————————————————————————————————————————
The S_Coordinate structure is intended to represent a set of alternatives associated with a specific coordinate, "alt" is an array of alternatives, each of which corresponds to a coordinate, "count" is a variable indicating the current number of alternatives actually stored in the "alt" array.
//———————————————————————————————————————————————————————————————————— struct S_Coordinate { S_Alternative alt []; // array of alternatives for a given coordinate int count; // number of alternatives }; //————————————————————————————————————————————————————————————————————
Next, we move on to the description of the class that directly implements the optimization algorithm (DEA). The C_AO_DEA class is an inheritor of the C_AO base class. When creating a class object, the main parameters of the algorithm are initialized:
- popSize — initializes the population size (number of "dolphins" or locations).
- Re — initial value of the effective search radius.
- Power — convergence curve degree.
- PP1 — initializes the convergence factor for the first iteration.
The SetParams method is designed to update the internal parameters of the algorithm based on the values written in the params array. After extracting popSize, Re, Power, PP1 values, a validation check is performed.
Methods:
- Init is designed to initialize the algorithm, accepting minimum, maximum values and steps for each parameter, as well as the total number of epochs (iterations).
- Moving is responsible for moving the "dolphins" in the search space; this is part of the main optimization loop.
- Revision adjusts population positions and parameters after movement.
The following fields are used internally to run the algorithm and are not accessible from outside the class.
- PP is a floating-point number representing a predefined probability for the current iteration, used for stochastic decisions, currentEpoch is a value tracking the current epoch (iteration) of the algorithm.
- totalEpochs is a value that stores the total scheduled number of epochs.
- coeffA is a dynamic coefficient used to select positions.
- coordData is an array of structures, where each S_Coordinate contains an array of alternatives and their number for a particular coordinate.
- CalculatePP is used to calculate the PP value (predetermined probability) at the current iteration.
- CalculateAccumulativeFitness calculates the accumulated fitness for each alternative.
- ResetAFforBestLocation resets the accumulated fitness values for best locations.
- SelectNextLocations selects the next locations for the dolphins based on the current state.
- FindNearestAlternative finds the nearest alternative based on the given coordinates and value.
- CalculateCoefficientA calculates the coeffA dynamic coefficient.
In general, the C_AO_DEA class is ready to be used for finding solutions in multidimensional space. It has public methods for initializing and performing the main optimization steps, as well as private methods and data that implement the internal logic of the algorithm.
//———————————————————————————————————————————————————————————————————— class C_AO_DEA : public C_AO { public: //---------------------------------------------------------- ~C_AO_DEA () { } C_AO_DEA () { ao_name = "DEA"; ao_desc = "Dolphin Echolocation Algorithm"; ao_link = "https://www.mql5.com/en/articles/18495"; popSize = 100; // NL - number of locations (dolphins) Re = 2; // effective search radius Power = 2.0; // convergence curve power PP1 = 1.0; // first iteration convergence factor ArrayResize (params, 4); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "Re"; params [1].val = Re; params [2].name = "Power"; params [2].val = Power; params [3].name = "PP1"; params [3].val = PP1; } void SetParams () { popSize = (int)params [0].val; Re = (int)params [1].val; Power = params [2].val; PP1 = params [3].val; // Check the parameters validity if (Re < 0) Re = 0; if (PP1 < 0.0) PP1 = 0.0; if (PP1 > 1.0) PP1 = 1.0; if (Power < 0.1) Power = 0.1; } 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 (); //------------------------------------------------------------------ int Re; // effective search radius double Power; // convergence curve power double PP1; // first iteration convergence factor private: //--------------------------------------------------------- double PP; // predefined probability for the current iteration int currentEpoch; // current epoch int totalEpochs; // total number of epochs double coeffA; // dynamic coefficient used to select positions S_Coordinate coordData []; // coordinate data (alternatives and AF) void CalculatePP (); void CalculateAccumulativeFitness (); void ResetAFforBestLocation (); void SelectNextLocations (); int FindNearestAlternative (int coord, double value); void CalculateCoefficientA (); }; //————————————————————————————————————————————————————————————————————
The Init method of the C_AO_DEA class initializes the algorithm (DEA). It takes the minimum and maximum values for each variable, the steps to change each variable, and the total number of epochs to optimize as inputs. The method first calls the base StandardInit method to perform standard initialization of the algorithm common parameters and, if this initialization fails, returns 'false'. Then variables that track the current and total epochs of the algorithm execution are initialized.
After this, the coordData data structure is created to store information about each coordinate (variable) of the search space. For each coordinate, the number of possible alternative values is determined. If a step change is specified for a coordinate, the number of alternatives is calculated based on the boundaries and the step. If the step is not specified (equal to zero), the coordinate is assumed to be continuous and a fixed number of alternatives is set for it.
Then the Re parameter (search radius) is checked and, if necessary, adjusted so that it does not exceed a quarter of the number of alternatives for each coordinate. After this, memory is allocated to store alternative values for each coordinate.
Finally, the loop fills an array of alternative values for each coordinate, distributing them evenly between the minimum and maximum values. If a step is specified, alternative values are calculated using that step. If the step is not specified, discretization of the space between the specified boundaries is used. Also, for each alternative, the associated AF (accumulated fitness) value is initialized to zero. If all initialization steps are successfully completed, the method returns 'true'.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_DEA::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ currentEpoch = 0; totalEpochs = epochsP; // Initialize the data structure for coordinates ArrayResize (coordData, coords); // Create alternatives for each coordinate for (int c = 0; c < coords; c++) { if (rangeStep [c] != 0) { coordData [c].count = (int)((rangeMax [c] - rangeMin [c]) / rangeStep [c]) + 1; } else { coordData [c].count = 500; } // Check that Re is not too large for the number of alternatives if (Re > coordData [c].count / 4) Re = coordData [c].count / 4; ArrayResize (coordData [c].alt, coordData [c].count); // Fill in the alternatives for (int i = 0; i < coordData [c].count; i++) { if (rangeStep [c] != 0) { coordData [c].alt [i].value = rangeMin [c] + i * rangeStep [c]; } else { coordData [c].alt [i].value = rangeMin [c] + (rangeMax [c] - rangeMin [c]) * i / (coordData [c].count - 1); } coordData [c].alt [i].AF = 0.0; } } return true; } //————————————————————————————————————————————————————————————————————
The Moving method implements one main step of the algorithm (DEA) corresponding to a certain iteration of the optimization process. If this is the first iteration detected using the "revision" flag, an initial random assignment of population coordinates occurs. For each section (population element) and for each variable in the range, random values are assigned. These values are adjusted taking into account the boundaries and the step of change to ensure acceptable solutions. After this, the flag is set, initialization is done, and the method exits this loop.
Once the initialization is done, the current epoch (iteration) counter is incremented by one. The key steps of the algorithm are then performed: performance metrics are determined for each solution in the current population, which indicate how well they fit the problem. The "a" coefficient is calculated. Based on the quality indicators, a generalized measure of the fitness of each solution is determined and the "AF" index is reset for it, which allows focusing the search in the area of the best solutions. Based on current information and calculated coefficients, the next locations (positions) are selected for updating and moving candidate solutions in the search space.
In general, the Moving method implements one iteration cycle of the DEA algorithm, sequentially performing key steps of updating and improving solutions in the process of searching for the optimum.
//———————————————————————————————————————————————————————————————————— //--- The main step of the algorithm (according to Algorithm 1) void C_AO_DEA::Moving () { // Initial 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]); a [p].cB [c] = a [p].c [c]; } } revision = true; return; } // Increase the epoch counter currentEpoch++; // Steps of the DEA algorithm according to Algorithm 1: // 1. Calculate PP for the current iteration CalculatePP (); // 2. We calculate the 'a' dynamic coefficient CalculateCoefficientA (); // 3. Calculate accumulated fitness CalculateAccumulativeFitness (); // 4. Find the best location and reset AF for it ResetAFforBestLocation (); // 5. Select the next positions SelectNextLocations (); } //————————————————————————————————————————————————————————————————————
The CalculatePP method computes the predetermined probability (PP), which is used in the decision-making process within the algorithm. If the total number of epochs (iterations) is equal to one or less, then the probability is set equal to a predetermined initial value (PP1). In this case, no further calculation is required and the method terminates.
If the number of epochs is greater than one, then the PP value is calculated based on a given formula that takes into account the current epoch and includes the following logic: the power, which is a function of the current epoch raised to the power (Power), is calculated, and one is subtracted from this, similarly the power is calculated for the total number of epochs.
The PP value is updated using a formula that gradually approaches 1, taking into account the current progress across epochs. Specifically, a portion proportional to the progress adjusted by the degree and the given Power and totalEpochs parameters is added to the initial PP1 value. If the overall exponent is non-zero, division occurs to obtain the current probability; otherwise, the value remains equal to the initial PP1.
Ultimately, the method dynamically changes the probability value during the execution of the algorithm, ensuring a balance between the initial and more "progressive" values as the epochs progress.
//———————————————————————————————————————————————————————————————————— //--- Calculate the predetermined probability (according to the formula 5) void C_AO_DEA::CalculatePP () { if (totalEpochs <= 1) { PP = PP1; return; } // PP = PP1 + (1 - PP1) * ((Loop^Power - 1) / (LoopsNumber^Power - 1)) double iterPower = MathPow ((double)currentEpoch, Power) - 1.0; double totalPower = MathPow ((double)totalEpochs, Power) - 1.0; if (totalPower != 0) { PP = PP1 + (1.0 - PP1) * iterPower / totalPower; } else { PP = PP1; } } //————————————————————————————————————————————————————————————————————
CalculateCoefficientA computes the 'a' dynamic coefficient used to regulate the search process. The method goes through the entire current population of solutions and for each solution calculates the difference between the maximum possible fB fitness and the current fitness of the particular solution (a[i].f). These differences accumulate into a sum.
After accumulating the sum of values, the 'a' coefficient is obtained as the ratio of the difference between fB and the minimum fW fitness to the resulting sum. This allows us to define a dynamic coefficient that adapts depending on the current state of the population and helps balance the rate of convergence or exploration of the search space.This method thus creates a scaling parameter that takes into account the fitness distribution of solutions and influences their updating and moving strategy in subsequent iterations of the algorithm.
//———————————————————————————————————————————————————————————————————— //--- Calculate the dynamic 'a' coefficient void C_AO_DEA::CalculateCoefficientA () { double sumFitness = 0.0; for (int i = 0; i < popSize; i++) { sumFitness += fB - a [i].f; } coeffA = (fB - fW) / sumFitness; } //————————————————————————————————————————————————————————————————————
The FindNearestAlternative method is designed to find the nearest alternative to a given value within a specific coordinate and takes two arguments: the "coord" coordinate index and the "value" we need the nearest alternative for. Initial values for "nearest" (the index of the nearest alternative) and "minDist" (the minimum distance) are initialized and set.
The loop goes through all alternatives associated with the given coord coordinate. For each alternative, the distance between the given "value" and the alternative value (coordData[coord].alt[i].value) is calculated, and if the calculated distance is less than the current minimum distance (minDist), then "minDist" is updated with the new, smaller distance value, and "nearest" is updated with the index of the current alternative.
After the loop is completed, the index of the alternative that was closest to the given "value" within the given coordinate is returned. Thus, the method determines which of the available alternatives for the specified coordinate is closest to the given real value.
//———————————————————————————————————————————————————————————————————— //--- Search for the closest alternative int C_AO_DEA::FindNearestAlternative (int coord, double value) { int nearest = 0; double minDist = DBL_MAX; for (int i = 0; i < coordData [coord].count; i++) { double dist = MathAbs (value - coordData [coord].alt [i].value); if (dist < minDist) { minDist = dist; nearest = i; } } return nearest; } //————————————————————————————————————————————————————————————————————
The CalculateAccumulativeFitness method is designed to calculate the accumulated fitness (AF) for alternatives according to Algorithm 2. Before starting the calculations, all accumulated fitness values for each alternative in each coordinate are cleared and set to zero. The range of fitnesses in the current population of solutions is found, calculated as the difference between the maximum possible fitness (fB) and the minimum (fW).
Then, for each agent (dolphin), its fitness is normalized relative to the range, and for each search coordinate, the closest alternative is determined, and in the radius "Re" around this alternative, the accumulated fitness for the alternative is updated, taking into account the reflective nature of the boundaries. This is done by weighted addition of contributions, where the weights are formed based on the distance from the nearest alternative (taking into account reflective boundaries), and include a coefficient associated with the current step in radius "Re".
As a result of the method operation, accumulated fitness values are formed for each alternative in each coordinate, taking into account the contribution of neighboring alternatives.
//———————————————————————————————————————————————————————————————————— //--- Calculate the accumulated fitness (according to Algorithm 2) void C_AO_DEA::CalculateAccumulativeFitness () { // Clear the accumulated fitness for all alternatives for (int c = 0; c < coords; c++) { for (int i = 0; i < coordData [c].count; i++) { coordData [c].alt [i].AF = 0.0; } } double rangeFF = fB - fW; if (rangeFF == 0.0) rangeFF = DBL_EPSILON; // For each agent (dolphin) for (int i = 0; i < popSize; i++) { // Normalize 'fitness' for this agent double normalizedFitness = (a [i].f - fW) / rangeFF; for (int c = 0; c < coords; c++) { // Find the closest alternative for the current coordinate int nearestAlt = FindNearestAlternative (c, a [i].c [c]); // Update the accumulated fitness in Re radius // According to Algorithm 2: AF(A+k)j = (1/Re) * (Re - |k|) * fitness(i) + AF(A+k)j for (int k = -Re; k <= Re; k++) { int altIndex = nearestAlt + k; // Boundary check taking into account reflection (reflective characteristic) if (altIndex < 0) { altIndex = -altIndex; // reflection from the lower border } else if (altIndex >= coordData [c].count) { altIndex = 2 * (coordData [c].count - 1) - altIndex; // reflection from the upper border } if (altIndex >= 0 && altIndex < coordData [c].count) { double weight = (1.0 / (double)(Re + 1)) * (Re - MathAbs (k) + 1); coordData [c].alt [altIndex].AF += weight * normalizedFitness; } } } } // Add a small epsilon value to all AFs to avoid zero probabilities double epsilon = 0.0001; for (int c = 0; c < coords; c++) { for (int i = 0; i < coordData [c].count; i++) { coordData [c].alt [i].AF += epsilon; } } } //————————————————————————————————————————————————————————————————————
The ResetAFforBestLocation method is designed to reset the accumulated fitness (AF) for alternatives corresponding to the location of the best solution (agent) in the population. First, the method determines the index of the best solution (agent) in the current population. It iterates through all solutions, finding the solution with the maximum fitness value. The index of the solution with the highest fitness is stored in the bestIndex variable.
For each 'c' coordinate of the best solution, the method determines the nearest alternative to the coordinate value of the best solution at that coordinate using the FindNearestAlternative function, and if the found alternative exists (the index is within the acceptable range), then the accumulated fitness value AF for that particular alternative is reset to zero.
Thus, the method resets AF only for those alternatives that most closely match the coordinates of the best solution. This is done to reduce the influence of these alternatives on subsequent stages of the search, potentially encouraging exploration of other areas of the search space.
As a result, the fitness of those coordinates that best correspond to the best solution is "zeroed/reset" to stimulate the search for other, possibly more optimal solutions.
//———————————————————————————————————————————————————————————————————— //--- Reset AF for the best location (according to Algorithm 3) void C_AO_DEA::ResetAFforBestLocation () { // Find the index of the best solution int bestIndex = 0; double bestFitness = a [0].f; // Search for a solution with maximum fitness (since we always maximize normalized fitness) for (int i = 1; i < popSize; i++) { if (a [i].f > bestFitness) { bestFitness = a [i].f; bestIndex = i; } } // Reset AF for ALL alternatives corresponding to the coordinates of the best solution for (int c = 0; c < coords; c++) { // Find the closest alternative to the coordinate of the best solution int nearestAlt = FindNearestAlternative (c, a [bestIndex].c [c]); // Reset AF only for this alternative if (nearestAlt >= 0 && nearestAlt < coordData [c].count) { coordData [c].alt [nearestAlt].AF = 0.0; } } } //————————————————————————————————————————————————————————————————————
The SelectNextLocations method is designed to select the next position for each solution in the population (for each dolphin) based on probabilistic considerations and taking into account both the accumulated fitness (AF) and the strategy for maintaining the best position. The method first determines the best solution in the current population based on its fitness value. The best solution index is saved for further use.
For each solution and each of its coordinates, the following set of actions is performed: if the current solution is the best, and the random number is less than the PP probability, the current coordinate of this solution is kept unchanged. This preserves the previous best solution. However, if the current solution is not the best, or if the position is not preserved under PP, then all AF values for the alternatives at the current coordinate are summed up. If the total AF sum is greater than a small number (epsilon), indicating the presence of non-zero fitness values, a roulette is performed: a random number is chosen proportional to the AF sum, and the solution coordinate is chosen based on the cumulative AF sum of the alternatives, allowing solutions to move towards locations with greater fitness.
If the sum of AF is close to zero (all values of AF are very small), a local search is performed if the random number is less than the coeffA dynamic coefficient. In this case, a random offset (-Re...+Re) relative to the current value is selected, and the coordinate is updated with the nearest value. Boundaries are taken into account.
Global search (random selection) if random number is greater than coeffA. In this case, a completely random alternative for the coordinate is selected. At the end of the method, the obtained coordinate value is limited to the allowed range (rangeMin, rangeMax) and discretized with the given rangeStep step to ensure that the value is within the allowed range and corresponds to the allowed values.
As a result of this method, the coordinates of each solution are updated taking into account the probability weights based on the accumulated fitness, the PP (preserve the best) strategy, dynamic local and global search, which allows the algorithm to effectively explore the search space and find optimal solutions.
//———————————————————————————————————————————————————————————————————— //--- Select next positions based on probabilities void C_AO_DEA::SelectNextLocations () { // First we find the index of the best solution int bestIndex = 0; double bestFitness = a [0].f; for (int i = 1; i < popSize; i++) { if (a [i].f > bestFitness) { bestFitness = a [i].f; bestIndex = i; } } for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { // For the best agent, apply PP if (i == bestIndex && u.RNDprobab () < PP) { // Save the current value of the coordinate of the best solution with PP probability continue; } // Select based on accumulated fitness double totalAF = 0.0; for (int alt = 0; alt < coordData [c].count; alt++) { totalAF += coordData [c].alt [alt].AF; } if (totalAF > DBL_EPSILON) // Check that there are non-zero AFs { // Choose an alternative based on roulette double rnd = u.RNDprobab () * totalAF; double cumSum = 0.0; for (int alt = 0; alt < coordData [c].count; alt++) { cumSum += coordData [c].alt [alt].AF; if (cumSum >= rnd) { a [i].c [c] = coordData [c].alt [alt].value; break; } } } else { // If all AFs are almost zero, use random selection // with the dynamic coeffA coefficient for the local search probability if (u.RNDprobab () < coeffA) // Use the dynamic coefficient { // Local search - stay close to the current position int currentAlt = FindNearestAlternative (c, a [i].c [c]); int shift = u.RNDminusOne (2 * Re + 1) - Re; // random offset within Re int newAlt = currentAlt + shift; // Check boundaries if (newAlt < 0) newAlt = 0; if (newAlt >= coordData [c].count) newAlt = coordData [c].count - 1; a [i].c [c] = coordData [c].alt [newAlt].value; } else { // Global search - completely random selection int randAlt = u.RNDminusOne (coordData [c].count); a [i].c [c] = coordData [c].alt [randAlt].value; } } // Bounds checking and discretization a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
The Revision method is used to update information about the best and worst solutions in the current population. The index of the best solution is specified, and the variable storing the best fitness is assigned the value of the worst of the current one. This creates an initial status for searching for new extremes. All solutions in the current population are searched: the solution with the maximum fitness value (the best solution) is determined. Its value is saved and the stored index is updated. We also search for the solution with the minimum fitness value (the worst solution). If a truly best solution has been found, its coordinates are copied into a special array or variable designed to store the current best solution.
As a result of the method execution, the coordinates of the best and worst solutions in the population are known exactly at the current moment in time. This allows the algorithm to track the search dynamics and use this data in decision making to better find optimal solutions.
//———————————————————————————————————————————————————————————————————— //--- Update the best solution void C_AO_DEA::Revision () { int bestIND = -1; fW = fB; // Find the best and worst solutions in the current population for (int i = 0; i < popSize; i++) { // Update the best solution if (a [i].f > fB) { fB = a [i].f; bestIND = i; } // Update the worst solution if (a [i].f < fW) { fW = a [i].f; } } // Copy the coordinates of the best solution if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
Test results
Now let's look at the results. It can be immediately noted that the algorithm copes well and fast with various types of tasks.
DEA|Dolphin Echolocation Algorithm|100.0|2.0|2.0|1.0|
=============================5 Hilly's; Func runs: 10000; result: 0.7599517883429889
25 Hilly's; Func runs: 10000; result: 0.6757192867862007
500 Hilly's; Func runs: 10000; result: 0.34170057553968197
=============================
5 Forest's; Func runs: 10000; result: 0.8958173952258406
25 Forest's; Func runs: 10000; result: 0.6422393144820473
500 Forest's; Func runs: 10000; result: 0.23940903266305935
=============================
5 Megacity's; Func runs: 10000; result: 0.6153846153846154
25 Megacity's; Func runs: 10000; result: 0.4403076923076923
500 Megacity's; Func runs: 10000; result: 0.15115384615384736
=============================
All score: 4.76168 (52.91%)
The visualization shows a spread of results for low-dimensional functions (green), and good results for medium-dimensional functions (blue).
DEA on the Hilly test function
DEA on the Forest test function
DEA on the Megacity test function
Based on its results, the DEA algorithm occupies 25th place in the ranking table.
| # | 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 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | (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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | CGO | chaos game optimization | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 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
The main advantages of the algorithm are: adaptive search control: the predetermined probability gradually increases, shifting the balance from exploration to exploitation, dynamic adaptation, collective memory: accumulated fitness preserves and disseminates information about promising areas, diversity mechanism: resetting information for the best positions stimulates exploration of new areas.
The strength of the algorithm lies in its adaptive nature. The dynamic coefficient makes the algorithm responsive to the population state and adapts to the rhythm of the task. When the dolphins are scattered across the search space, the algorithm encourages local exploration. When they begin to converge on a goal, it pushes them to new horizons, preventing them from getting stuck in the illusion of local success.
Accumulated fitness is the collective memory of the flock, where every discovery leaves an echo in the solution space. But unlike simple accumulation, the algorithm can forget — zeroing out the best positions paradoxically leads to even better discoveries.
This is not just a metaphor - it is a philosophy of optimization, where every click of the echolocator carries information about the space of possibilities.
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)
DEA pros and cons:
Pros:
- Good convergence on medium- and high dimensional functions.
- Small number of external parameters.
Cons:
- There is some tendency to get stuck on low-dimensional problems.
- Resource intensity on high-dimensional functions.
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.
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_DEA.mq5 | Script | DEA test stand |
Translated from Russian by MetaQuotes Ltd.
Original article: https://www.mql5.com/ru/articles/18495
Warning: All rights to these materials are reserved by MetaQuotes Ltd. Copying or reprinting of these materials in whole or in part is prohibited.
This article was written by a user of the site and reflects their personal views. MetaQuotes Ltd is not responsible for the accuracy of the information presented, nor for any consequences resulting from the use of the solutions, strategies or recommendations described.
Features of Custom Indicators Creation
Market Simulation (Part 21): First Steps with SQL (IV)
Features of Experts Advisors
From Basic to Intermediate: Indicator (V)
- Free trading apps
- Over 8,000 signals for copying
- Economic news for exploring financial markets
You agree to website policy and terms of use