FLW-HD: Optimisation based on Follow-the-Leader and random Walk in High Dimensions

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)

WHAT IS IT?

This is an agent-based model designed to search for the global minimum (or optimal) solution of a continuous value optimization problem (or cost function) defined in a high-dimensional search space (i.e., one with many variables or dimensions, d > 2).

Given a real-valued mathematical function, optimization refers to the task of finding a set of input values (or solution) that minimize the corresponding output value of that function. Many algorithms have been designed to search for the minimal solution within an input domain defined by a set of bounded constraints (also known as a search space). The number of input variables determines the dimensions or dimensionality of the search space. Algorithms that only use the evaluation of the function to guide the search in said space, without relying on other of its mathematical properties, are called metaheuristics.

This model implements a metaheuristic to optimize real-valued problems in continuous domains using the Netlogo language. The optimization algorithm operates on the basis of two search operators, Follow the Leader and Random Walk, and is capable of solving problems in High Dimensional spaces (d > 2) (hence its name, FLW-HD). To read more about the technical details underlying the algorithm, the reader is referred to the paper [1].

HOW IT WORKS

The algorithm works as a multi-agent system, where each agent explores a location in the search space consisting of a vector of coordinates in each dimension (x1, x2, ..., x_d), and the value of the cost function evaluated at said location. Since the goal of the algorithm is to minimize the cost function, the lower the value of an agent, the higher its quality as a candidate solution for the chosen problem. Furthermore, each agent can belong to one of three subsets: LEADERs (agents that guide the search), FOLLOWERs (agents that follow their leaders), or WALKERs (independent scouting agents).

In each iteration of the algorithm, the agents explore the search space according to their roles. They are initially located at random locations within the search space. The algorithm is assigned a budget of evaluations of the cost function (MAX-EVALS); an evaluation is calculated (and therefore discounted from the budget) each time an agent changes its location. The execution ends when MAX-EVALS is reached, or if the optimum of the problem is discovered first.

The FLW-HD algorithm search strategy consists of a combination of the following operators, which can be enabled/disabled at any time during the algorithm execution:

• Follow-the-leader: LEADERs are high-quality candidate solutions, and therefore each LEADER has an (equally larger) pool of FOLLOWERs. FOLLOWERs try to resemble their LEADERs by jumping within close range of their locations with random step lengths (local exploitation). When a FOLLOWER discovers a more promising region of the search space (a location with a lower cost function value), he becomes the LEADER of his group (in practice, since all agents are homogeneous, they simply swap places). The algorithm supports single-leader or multi-leader modes of operation. The TOP-LEADER would be the best among all the leaders in a particular iteration. The final solution reported by the algorithm would be the BEST-EVER location (the one with the lowest cost function value) discovered by any TOP-LEADER agent during the entire run.

• Random Walk: WALKERS move randomly around their current positions without any guidance (global exploration). When a WALKER accidentally becomes a more promising candidate solution than the current LEADERs, the TOP-LEADER is asked to move into that position. The length of the WALKER movement is determined by a normally distributed random step with SIGMA deviation, that can be sampled uniformly randomly or adaptively adjusted by the agents (depending on the strategy defined by the STEP-SAMPLING chooser).

• Elitism: this component aims to intensify the search around the best candidate solution discovered so far. The model allows three strategies to define the elite (as determined by the ELITISM chooser): select one WALKER to be relocated to the location of the BEST-EVER candidate solution, or move all WALKERS to said location, or finally, relocate all the WALKERs and all the LEADERs to such location.

• Warm Restarts: to prevent premature convergence to local minima, when the average diversity within the groups of LEADERs/FOLLOWERs is too small or when agents have aged a predefined number of iterations, the coordinates of the entire population are reset to random locations within the search space, according to the strategy defined in the LOCATION-SAMPLING chooser: either UNIFORM, where each coordinate is independently sampled with a uniform random distribution within the bounds of the search space, or LATIN-HYPERCUBE, where the coordinates are randomly sampled in such a way that the agents do not intersect in any of the dimensions, resulting in a more evenly dispersed coverage of the search space. Note that the chosen strategy will also be used for the initialization of the population at the beginning of the simulation.

HOW TO USE IT

First, select one from the suite of available testbed real-valued cost functions using the PROBLEM chooser (SPHERE, RASTRIGIN, ROSENBROCK, HIMMELBLAU, EGGHOLDER or variations; HIMMELBLAU and EGGHOLDER are defined for 2D search spaces only, whereas for the other functions you can set the dimensionality of the search space with the DIMENSIONS chooser; see TESTBED PROBLEMS section below for further information).

Then choose the number of search agents with the POP-SIZE slider, the percentage of WALKERS in the population with the WALKERS-RATE slider, and the number of N-LEADERS within the population. Also, choose the function evaluations budget with the MAX-EVALS slider. For example, to solve the RASTRIGIN problem in a 30D search space with a population of 20 agents, including 4 leaders with 3 followers each, plus 4 walkers, set up the simulation parameters as follows:

• PROBLEM: rastrigin

• DIMENSIONS: 30

• MAX-EVALS: 300000 (by default, this is set to DIMENSIONS x 10000)

• POP-SIZE: 20

• N-LEADERS: 4

• WALKERS-RATE: 0.2

• ELITISM: any walker

• RESETS?, FOLLOW?, WALK?: on

• LOCATION-SAMPLING: latin hypercube

• STEP-SAMPLING: adaptive

Now you can run the algorithm using the buttons in the control panel:

• SETUP: Creates the population, locates the agents randomly within the limits of the search space according to the chosen LOCATION-SAMPLING strategy, and initializes the algorithm global variables.

• STEP: Executes an iteration (a single tick) of the main procedure of the algorithm.

• GO: Repeatedly executes the main procedure of the algorithm until finding the optimum or until reaching MAX-EVALS.

• RESET: Relocates the population of agents using the LOCATION-SAMPLING strategy and clears the SIGMA-EFFECTIVENESS histogram (SIGMA refers to the step length used in WALKERs movements, as described above).

Besides, remember that the SPEED slider at the top of the window can be used to control how fast the display area is updated on each iteration (note that the update operation slows down the execution of the algorithm). Disable VIEW-UPDATES for maximum speed.

Once you start running the simulation, the output monitors allow you to inspect the algorithm's emergent behavior as the search evolves:

• OPTIMUM: The value of the problem cost function evaluated at the optimal solution (only for validation purposes, so this information is not revealed to the algorithm).

• BEST-SOLUTION-EVER: The value of the problem cost function evaluated in the best TOP-LEADER ever found during execution.

• CURRENT-TOP-LEADER: The value of the problem cost function at the TOP-LEADER coordinates in the current iteration.

• SOLUTION-DISTANCE-TO-OPTIMUM: The Euclidean distance of BEST-SOLUTION to OPTIMUM-SOLUTION coordinates.

• VALUE-OF-LEADERS: Historical plot of the leaders' values throughout the simulation. A different colour is used for each leader.

• VALUE-OF-BEST-SOLUTION-EVER: Historical plot of the value of the best solutions discovered throughout the simulation. Note that the range of the plot is clipped regularly to allow better visualization of changes in the scale of the discovered solutions.

• DIVERSITY-PER-LEADER: Historical plot of the average diversity measure of the groups of agents within the population. A different color is used for each leader.

• SIGMA-EFFECTIVENESS: Histogram that shows to what extent each step deviation of WALKERs movements has contributed to improve the value of the best solutions (each bar corresponds to the following deviations: 10, 1, 0.1, 0.01, 1E-3, 1E-4, 1E-5). Notice that the plot is cleared each time the RESET operation is carried out (either automatically or when activated with the corresponding button).

• MEAN-DIVERSITY: The average diversity of all groups led by leaders.

• RUNTIME: Total execution time of the simulation run (in seconds).

• EVALUATIONS-COUNT: Counter of the overall evaluations of the cost function carried out by the algorithm up to the current iteration. Note that if the algorithm can reach the optimal value (and thus stop before MAX-EVALS), these last two monitors will add a "!!!" sign to the values in their text boxes.

• VALUE OF LEADERS: A text box that shows the value of the cost function for the location of each leader.

TESTBED PROBLEMS

The mathematical expressions of these cost functions are defined in the COMPUTE-VALUE procedure, found in the CODE tab. In addition, the bound constraints for each dimension in the input space of each function are defined in the SETUP-PROBLEM procedure, also in the CODE tab, as follows:

• SPHERE, SHIFTED-SPHERE: [-5.12, 5.12].

• RASTRIGIN, SHIFTED-RASTRIGIN, BIPOLAR-RASTRIGIN: [-5.12, 5.12].

• ROSENBROCK: [-2.048, 2.048].

• HIMMELBLAU: [-5.12, 5.12].

• EGGHOLDER: [-512, 512].

The ground-truth optima of these problems are also defined in the SETUP-PROBLEM procedure, as follows (we note that this information is hidden from the algorithm, since it is only used to evaluate its performance):

• SPHERE: (0, 0, ..., 0) (the optimum is at the origin, that is, zero in all DIMENSIONS).

• SHIFTED-SPHERE: (-2.5, -2.5, ..., -2.5) (the optimum is shifted to the 3rd hyper-quadrant).

• RASTRIGIN: (0, 0, ..., 0) (the optimum is at the origin, that is, zero in all DIMENSIONS).

• SHIFTED-RASTRIGIN: (1.123, 1.123, ..., 1.123) (the optimum is shifted to the 1st hyper-quadrant).

• BIPOLAR-RASTRIGIN: (1, -1, 1,..., -1) (the optimum alternates between 1 and -1 in each dimension)

• ROSENBROCK: (1, 1, ..., 1) (the optimum is in the far right corner of the unit hypersquare).

• HIMMELBLAU: Any of *(3.0, 2.0), (-2.805118, 3.131312),
  (-3.779310, -3.283186), or *(3.584428 -1.848126).

• EGGHOLDER: (512.0 404.2319).

DISPLAY AREA

The usual representation of the display area of Netlogo simulations as a discrete 2D grid of cells (patches) where agents move around, is not suitable for our purposes, since our model deals with continuous values in higher dimensions (d > = 2). Therefore, the display area of our model was designed as an informative visual depiction of the algorithm's dynamics.

Instead of showing movements, the display visualises a series of color heatmaps that represent the coordinate vectors and cost function values of some of the agents in the population. The OPTIMUM solution is represented in the top row of the display area, as a guide to compare how similar are the candidate solutions discovered by the algorithm. The next two rows correspond to the current BEST-EVER and TOP-LEADER solutions, while the remaining bottom rows show the solutions from the LEADERs set (each row is labeled with its corresponding name on top of it).

The color intensity of each patch in the heatmap is scaled to a range defined by the search space boundary constraints. Therefore, they range from black for the lower limit, white for the upper limit, and graduated shades of orange for the mid-range values (for example, if the BEST is at the coordinates with the value 0, it will be displayed as pure orange). As a simple test to illustrate the use of these conventions, we suggest performing the following set of actions and comparing the differences (make sure to set multiple N-LEADERS > 2 and that the VIEW-UPDATEs checkbox is on):

DIMENSIONS: 30 -> PROBLEM: rastrigin -> SETUP -> PROBLEM: bipolar-rastrigin -> SETUP.

Notice that the patch column at the right edge of the display area shows the value of the cost function or quality associated to the corresponding solution; these patches are scaled to a range between 100 (black) and the OPTIMUM value (white). Besides, notice that the display area would be automatically resized when the DIMENSIONS chooser is changed.

THINGS TO TRY

The behavior of the algorithm is determined by the application of its four search components: RESETS?, FOLLOW? WALK? and ELITISM; You can try to solve each problem in the testbed suite with different configurations of these components and see their effect in the patterns that emerge on the monitor plots and in the display area. You can repeat these experiments many times (press the buttons SETUP->GO as many times as you like) and verify the success rate for each problem (i.e., what percentage of the total number of iterations was the FLW algorithm able to discover the OPTIMUM?). Also check the efficiency of each mode/configuration, in terms of the number of evaluations needed for a successful run (EVALUATIONS-COUNT) or the time taken to converge (RUNTIME), and how an increase in dimension affects this performance.

Once you have experimented each configuration in each problem, you can further study the differences in single-leader vs. multi-leader modes of operation. Is the multi-leader strategy better than the single-leader strategy? Which achieves a higher success rate? Is such behavior exhibited for the entire testbed suite? Do you get better results as the number of LEADERs increases? You can test the last hypothesis by testing different combinations of pair values (N-LEADERS, POP-SIZE): (1, 5), (2, 10), (4, 20), (8, 40). How does this effectiveness depend on the dimensionality of the problem? Note that an increase in the number of LEADERs or POP-SIZE also consumes MAX-EVALS budget evaluations faster and therefore a compromise may be required for the algorithm to succeed.

Other interesting questions to address are: Can you identify which search operator configuration improves the optimization effectiveness/efficiency of the FLW algorithm? Is there a minimum follower base size for multi-leader mode or a population size for single-leader mode to work properly? What search operator or component has more impact on the behaviour of the algorithm?

THINGS TO NOTICE

Each PROBLEM can exhibit different mathematical properties: multimodality, convexity, separability, multiple global or local minima, plateaus, ridges, valleys, etc. The advantage of swarm optimization methods is their ability to explore multiple regions of the search space simultaneously to avoid getting stuck in local minima due to such properties, unlike single-point metaheuristics. However, it is also known that these swarm-based methods can suffer from premature convergence where the entire population soon collapses into a single suboptimal solution or small region.

The FLW algorithm attempts to circumvent this drawback by means of two techniques. First, it allows for multiple leaders, which means you can choose between having a single population of agents with a single leader, or having multiple leaders with different subgroups of followers. By choosing multi-leader mode (controlled by the N-LEADERS slider), leaders spread out in separate regions of the search space looking for better solutions, and their followers likewise. You can verify this emergent behavior by experimenting with different values for the N-LEADERS and POP-SIZE sliders and by inspecting the different curves in the VALUE-OF-LEADERS plot and the simulation display area.

The second technique is intended to prevent premature convergence by dispersing agents with a warm reset of their locations every time MEAN-DIVERSITY drops below a certain threshold, or periodically once agents have aged a predetermined number of iterations (you can also activate the latter operation by pressing the RESET button at any time during the simulation).

Since relocated leaders can start exploring newer unknown regions, a learning mechanism allows the algorithm to keep track of the most promising solution found so far in previous resets (this is reminiscent of ELITISM in Genetic Algorithms). FLW-HD achieves this by forcing a subset of agents to move to the location of the BEST-SOLUTION-EVER; the choice of the subset ("the elite") is defined by the ELITISM chooser, among one of the following options: ANY-WALKER (an arbitrary agent from the WALKERs set moves to the best solution location), WALKERs (the entire set of WALKERs is moved to that location), EVERYBODY (the entire set of WALKERs and LEADERs, and thus FOLLOWERs, is relocated to that position), or simply NONE (no elitism is applied).

The ELITISM strategy can impact the emergent behavior of the algorithm in different ways, and such impact will depend on the properties of the problem, the dimensionality of the search space and the configuration of the search operators used during its execution. We encourage the user to experiment with these different strategies to see how the success of reaching the OPTIMUM is affected, as well as the efficiency of the algorithm, in terms of time taken to converge (RUNTIME) or number of function evaluations required (EVALUATIONS-COUNT).

EXTENDING THE MODEL

Some possible ideas for model extensions are:

• Expand the suite of testbed problems with additional cost functions (including combinations of existing ones).

• Extend the model to solve non-stationary problems, that is, problems where the cost function or its parameters can vary over time during the course of a run. In this sense, we believe that the mechanisms to avoid premature convergence implemented in the FLW-HD algorithm can be useful to adapt its search behavior to the dynamic changes in the optimization space.

• Implement an adaptive strategy of combining/applying search operators to allow the algorithm to take further advantage of the discovered properties of the problem during its execution, so as to perform more efficiently (just like the adaptive strategy currently implemented to sample the deviation of the WALKERs steps), that is, converging to the OPTIMUM solution in fewer cost function evaluations.

• Finally, the adaptation of the algorithm to handle non-continuous problem domains (where the variables in each dimension take binary, discrete or combinatorial values) is also an interesting path for future development.

RELATED MODELS

Modeling Commons -> Follow the Leader + Random Walk (FLW) Swarm Algorithm, see [1].

(http://modelingcommons.org/browse/one_model/6978)

CREDITS AND REFERENCES

Authors:

Sergio Rojas-Galeano

Copyright (c) December 2022

email: srojas@udistrital.edu.co

Version 1.12

Licenses:

• The model code is licensed as GNU General Public License (GPLv3) (see https://www.gnu.org/licenses/gpl-3.0.txt)

• This Info Tab document is licensed as CC BY-NC-ND (see https://creativecommons.org/licenses/by-nc-nd/4.0/)

References:

[1] Garzon, M., Alvarez-Pomar and Rojas-Galeano, S. (2023). An Agent-based Model of Follow-the-leader Search using Multiple Leaders. To appear in: Proceedings of the 14th Metaheuristic International Conference (MIC 2022).

There are 12 versions of this model.

Attached files

This model does not have any ancestors.

This model does not have any descendants.