Kriss Jessop About Me Projects Personal Projects RPGs

Algorithm: Stochastic Diffusion Search

Posted on October 23rd, 2016

  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.

Performance

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))

Applications

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…

Exercise

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.