Slime Mould Algorithm

Last updated: October 27, 2023

1. Introduction

Metaheuristics are optimization algorithms that use a set of high-level strategies, such as search and optimization, to explore the solution space. Metaheuristics have become popular in recent years because they can be applied to a wide range of complex problems that are difficult to solve using traditional mathematical optimization methods.

Nature-inspired metaheuristic algorithms aim to solve complex optimization problems by mimicking the behavior and processes found in nature. One such nature-inspired algorithm is the Slime Mould Algorithm (SMA), which is based on the behavior of the physical organism known as ”slime mould”.

In this tutorial, we’ll introduce SMA, its background, and how it works.

2. The Slime Mould Algorithm

The Slime Mould Algorithm (SMA) is an algorithm miming the behavior of the physical organism known as ”slime mould”. The “slime mould” demonstrates incredible problem-solving abilities, as seen in its application to path-finding and network optimization. This is the famous case of the Japanese railroad network reconstruction.

The SMA consists of multiple agents representing the spread of mould close to food sources in an environment. The agents compete for limited resources and cooperate to form a network connecting the food sources. The process is repeated several times, and the final network that emerges represents the optimal solution to the problem being solved.

SMA has been applied to a wide range of optimization problems, including network design, facility location, and scheduling, and has been shown to be an effective and efficient algorithm.

2.1. Phase-Based Learning

Like many metaheuristics, the algorithm consists of two main phases. These are a search phase and an optimization phase. The slime mould extends tendrils into the search. When a food source is found, the tendril will thicken based on the viability of the food source found.

Trading off against the potential threat of environmental hazards leads to the classic exploration-exploitation trade-off. The decision to leave a food source is naturally heuristic and depends on the quality of the food source.

It is also notable that the slime mould can exploit multiple food sources simultaneously by distributing its biomass. Natural heuristics, in this case, are to narrow the search space when high-quality food is found and to explore further when the quality of the food is less.

3. Mathematical Model

We now start constructing the algorithm. The two main phases are approach (search) food and wrap (exploit) food, respectively. The algorithm will then oscillate between these two phases.

Before we start searching, we need to initialize the algorithm. The slime mould is, in one sense, a single entity. It can, however, act at different locations along itself so that we will treat it as a fixed number of multiple entities or locations.

We initialize N locations to represent the slime mould. Then, for each N of these locations, we compute the fitness of the slime mould.

3.1. Approach Food and Wrap Food

The slime mould senses food through its odor in the air. We capture this approaching food through odor with the following equation:

(1)   \begin{equation*} X(t+1) = \begin{cases}x_{b}(t)+vb\cdot (W\cdot X_A(t)-X_B(t)),r \leq p \\ vc\cdot X(t),r\geq p \end{cases} \end{equation*}

Here two random locations of our mould are represented by X_A(t) and X_B(t). We also represent the best individual found so far as Xb . The first condition searches for food based on the best-discovered location and mixes two random locations. The second condition causes the slime mould to exploit the locally available food source instead.

3.2. Breaking Down the Formula

(2)   \begin{equation*} p = tanh|S(i)-DF| \end{equation*}

(3)   \begin{equation*} a = arctanh(-(\frac{t}{max_{t}})+1) \end{equation*}

With a defined above, we now define vb as a random sample from the range [−a, a]. We also define vc as a random variable chosen from the linearly decreasing range [-(1-\frac{i}{max_it}),(1-\frac{i}{max_it})]:

(4)   \begin{equation*} W(SmellIndex(i)) = \begin{cases} 1+r \cdot log(\frac{bF-S(i)}{bF-wF}+1),condition \\ 1-r\cdot log(\frac{bF-S(i)}{bF-wF}+1) \end{cases} \end{equation*}

W is the weight parameter. The condition is that S(i) is in the first half of the population. We define W in this way to mimic the oscillation pattern of slime moulds. W helps the slime mould move towards high-quality food sources quickly while slowing down the approach when food concentration is lower:

(5)   \begin{equation*} SmellIndex = sort(S) \end{equation*}

The SmellIndex is the ranking of the slime mould by fitness value. Fitness is the metric used to evaluate a given solution.

3.3. Oscillation

When running the full algorithm, a degree of random exploration is maintained. This is the first term in the full equation below. z is a hyperparameter that can be set according to the problem:

(6)   \begin{equation*} X{*} = \begin{cases}rand\cdot (UB-LB) + LB , rand<z\\ X_{b}(t) +vb\cdot (W\cdot X_{A}t) - X_{B}(t)), r < p \\ vc\cdot X(t), r \geq p \end{cases} \end{equation*}

The flow of food through the venous structure of the slime mould has a natural ebb and flow captured in the weight, W, and the random parameters, vb and, \boldsymbol{vc}.

This allows for an oscillation in the thickness of the venous structure of the slime mould, allowing more or less food to flow. This helps the slime mould to avoid local optima. Our modeled parameters allow our model to achieve a similar effect.

4. Pseudocode

Here is an example pseudocode of the algorithm:

\begin{tikzpicture} \begin{algorithm} \caption{Slime Mould Algorithm}\label{alg:two} \setcounter{algocf}{0} \SetAlgoLined \KwData{PopulationSize, MaxIters,z} \KwResult{The Optimal Agent} Initialize Slime Mould Positions, $ X_i |i = 1,2 ...PopulationSize$ \; $t \gets 0$\; \While{$t < MaxIters$}{ $Calculate Fitness $\; $Update bestFitness, X_b$\; $Calculate, W$\; $a \gets atanh( 1 -(\frac{t}{MaxIters}))$\; $b \gets 1 - \frac{t}{MaxIters}$\; $AgentIndex \gets 0$\; \While{$AgentIndex < PopulationSize$}{ Update $p,vb,vc$\; Update Mould Positions\; $AgentIndex \gets AgentIndex + 1$\; } \State $t \gets t + 1$\; } \end{algorithm} \begin{tikzpicture}

5. Computational Complexity

The algorithm runtime can be broken into five main operations. Those operations with their respective computation complexity are:

  • initialization O(D), D is dimension of functions
  • fitness evaluation O(N), N is the number of cells of slime mould
  • sorting O(N*LOG N)
  • weight update O(D x N)
  • location update O(D x N)

Total time complexity is O(D + T * N * (1 + Log N + D) ).

6. Conclusion

In this article, we discussed the slime mould algorithm – a powerful nature-inspired metaheuristic algorithm. We show the inspiration for the algorithm and how it was converted into a series of mathematical operations. The algorithm is presented with further material in the research paper introducing it.

Comments are closed on this article!