Kriss Jessop About Me Projects Personal Projects RPGs

Algorithm: Stochastic Diffusion Search

Posted on October 23rd, 2016

Stochastic Diffusion Search is a search algorithm that can take the form of either a neural network or a swarm and attempts an optimal application of resources. The agents scatter randomly across the search area and keep searching random locations until either they or one of their neighbours find a location that they determine to be good. An agent that finds a good location tries to take a neighbour to that location (which will in-turn judge whether it believes the location to be good, or bad, and do the same), while an agent that fails to find a good location will follow a neighbour that has, given the opportunity.

  1. Choose a random place.
  2. Is this a good place?
  3. If yes, go back and judge a location adjacent along one dimension.
  4. If no, goes a neighbour have a good location? Go there.
  5. Otherwise, go back to step one.

In the Restaurant Game, the list of restaurants would represent either a one or two dimensions (either as a list of places, or points on a map) with the menu being an extra dimension being considered.


At worst, Stochastic Diffusion Search has linear performance; at best, logarithmic. The algorithm can be applied both sequentially and in parallel. Naturally, parallel has better performance.

Sequential: O(n/log(n))

Parallel: O(1/log(n))


Outside of the given examples of searching for a restaurant that everybody loves and aiding with the reading of MRI scans (which I’m quite sure is  a thing I saw on the news once), I can’t easily think of a situation where it would be used that Distributed Flies Optimisation wouldn’t also work for.

We’ve seen it demonstrated in the terms of text search, and I have recently being feeling pain with how slow PDF’s are to search, but I would have serious questions regarding its suitability for searching a text document outside of an example. Assuming Acrobat reader uses a kind of linear search ( O(n) ), then a fraction of a logarithm ( ideally O(1/log(n)) ) should be faster. Still, it would require further thinking for me to have any confidence in the idea.

There’s also been suggestion that this can be used to find symmetry…


The task associated with this algorithm was writing the agent diffusion behaviours for the aforementioned  string search. Any agent that successfully found the target word should remain at that position, while any agent that failed to find the word should then check with it’s neighbours to see if either of them have found the word. If they have, the agent can just go there, but otherwise they go to a random location. This method is Active Recruitment.

Passive Recruitment is also a thing. With this method, an agent looking for a new hyupothesis will look at a random other agent. If the random agent has found a location it’ll aquire it’s hypothesis, while if the random agent itself is still searching, then the current agent will just choose a new hypothesis at random.

More about these diffusion strategies can be read on page 7 of this paper.