Shuffled Frog Leaping Algorithm in MATLAB

The Shuffled Frog Leaping Algorithm (SFLA) is a metaheuristic, or more precisely a memetic algorithm, inspired by frog leaping. It is based on the model of Shuffled Complex Evolution (SCE-UA) and adds memetic evolution to it. Different representations and operators are needed for discrete or mixed problems. The implementation here uses bounded continuous variables.

SFLA was proposed by Muzaffar Eusuff and Kevin Lansey in 2003, for the design of water distribution networks.

How SFLA works

The population is a group of frogs, and each frog is a candidate solution. The frogs are divided into groups called memeplexes. Each memeplex evolves on its own for a while, and then all the frogs are mixed again. The shuffling lets the ideas found in one memeplex spread to the others.

One iteration of SFLA has three steps:

1. Sort and partition. Sort all frogs from best to worst and deal them to the memeplexes like cards: frog 1 goes to memeplex 1, frog 2 to memeplex 2, and so on. Every memeplex gets a mix of good and poor frogs.
2. Local search in each memeplex. Run the frog leaping step below a few times in every memeplex.
3. Shuffle. Put all frogs back into one population and start the next iteration.

The frog leaping step

In each memeplex, a small group of $q$ frogs is selected at random, with a higher probability for the better frogs. Let $x_b$ be the best and $x_w$ the worst frog of this group. The worst frog tries to jump toward the best one:

where $r$ is a vector of uniform random numbers in $[0, 1]$, $\odot$ means element by element multiplication, and $\sigma$ is a step size factor. If the new position is outside the bounds or not better, the frog tries the same jump toward the best frog of the whole population, $x_g$. If that fails too, the worst frog is replaced by a random point inside the smallest box that contains the memeplex. This last step is called censorship.

What this post shares

This post shares an open-source MATLAB implementation of SFLA. The algorithm is implemented in a structured way, so if you know MATLAB, you can easily use the code in your research projects.

The SFLA folder holds these files:

• sfla.m: the main script, with the problem definition, the parameters and the main loop.
• RunFLA.m: the frog leaping step for one memeplex.
• Sphere.m: the sample cost function, $f(x) = \sum_{i=1}^{n} x_i^2$.
• SortPopulation.m, RandSample.m and IsInRange.m: helpers for sorting, weighted random selection and the bound check.
• main.m: a one line entry point that runs sfla.m.

To run the code, open the SFLA folder in MATLAB and run main.m. The program prints the best cost in every iteration and plots the best cost against the iteration on a logarithmic scale. The code uses unifrnd and randsample, functions of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Parameters in the code

The population size is nMemeplex*nPopMemeplex. To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar, VarMin and VarMax at the top of sfla.m.

Check the result

Use the Sphere example to check that the best cost approaches 0 and the returned variables approach the origin. When changing the number of variables, review both memeplex size and the total population size. Compare evaluation counts across settings because every memeplex runs several local steps inside one outer iteration. Repeated runs help distinguish a reliable setting from a favorable random start.

Applications

SFLA was first used for water distribution network design, and it has since been applied to other engineering design and scheduling problems. Like other population based methods, it needs only the values of the cost function.

Mostapha Kalami Heris, Shuffled Frog Leaping Algorithm in MATLAB (YPEA109), Yarpiz, 2015. https://yarpiz.com/shuffled-frog-leaping-algorithm-ypea109

@misc{yarpiz-ypea109,
  author = {{Mostapha Kalami Heris}},
  title = {{Shuffled Frog Leaping Algorithm in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA109},
  url = {https://yarpiz.com/shuffled-frog-leaping-algorithm-ypea109}
}