Introducing Stochastic Diffusion Search

Hi and welcome to this weeks post on algorithms inspired by nature. The previous weeks can be found the following links:

1. The No Free Lunch Theorem
2. Optimising Neural Nets With Biomimicry
3. Fine Tuning Dispersive Flies Optimisation

The full code for this week (C++ using the openFrameworks library) can be found at the github repository here.

Stochastic Diffusion Search (SDS) belongs to the wider family of swarm intelligence algorithms. The difference between SDS and many other inspired-by-nature algorithms is that a mathematical framework has been developed that shows it’s convergence (with the caveat of enough time and compute power) and linear time complexity.

SDS introduces a new probabilistic multi-agent approach to finding the global optimum. There are two competing metaphors which are high level descriptors for the algorithm (mining and restaurants), of which I’ll repeat my favourite, along with corresponding code:

A group of miners have discovered there are rich veins of gold (global optima) running through the nearby hills (discrete feature/search space). The greedy gold-rushing miners scratch their heads individually and each come up with a random hypothesis for which hill they think the gold is in. The hills all contain multiple potential dig sites, of which the miners will randomly choose one (the hill can be split into multiple partials). Over the day, they go to their dig site, and check whether their hypothesis was correct. This part of the search is called the test phase.

Rough code for the test phase

That evening, the miners convene at the local tavern and drink, chatting in earnest about who found the gold. Each miner who didn’t find any gold is desperate, and asks a random other miner if they found gold on their hill. If they did, and they were happy, the unhappy makes a new hypothesis somewhere randomly on the hill. If they speak to another unhappy miner, they resolve to find gold with a new entirely random hypothesis. This part of the search is called the diffusion.

Rough code for the diffusion step.

We can see SDS optimising to find the highest concentration of gold. Any of the four central hills (squares) have the same amount.

The testing and diffusion phases are repeated as necessary until a solution is found. Exiting or termination strategies for SDS are a little more ambiguous, some of which are:

1. The first way of stopping the program is not to implement anything for termination, and allow the user to interrupt the search manually. This is usually preferred if the problem space is dynamically changing or there isn’t any predefined pattern.
2. The termination could have a time-based criterion, whereby if the algorithm passes a set amount of time / iterations the program stops.
3. Halt the process via a cluster-based criterion that tracks of the formation of stable clusters.

When the solution space changes over time, the problem is made harder. Below is a modified version of SDS running on a problem space generated by thresholded three dimensional perlin noise. Note that SDS is only guaranteed to find the global optimum given enough time, which for each new frame the algorithm definitely isn’t given!

A problem with the moving problem space is that the agents can exploit a given hill too much, when there are better hills / solutions emerging. Introducing a context sensitive mechanism as a modification to the algorithm helps to free up resources needed to improve the exploration in the search. The essence of the idea is when an unhappy agent copies a happy agents hypothesis, and selects a random dig site on the given hill, if it is already occupied then an entirely new and random site in the problem space will be selected to explore.

Check out the code and have a hack on the program if you want to take it further — there aren’t that many lines!

Next time we’ll be looking at Genetic Algorithms. You can find that here!

Thanks for reading :)