The animation below is a representation of a Stochastic Diffusion Search. In this example the agents are searching the search space for the word "HELLO".
The boxes along the bottom represent the search space and the moving boxes are agents. The agents position themselves over the letter where they think the word "HELLO" starts. As the word "HELLO" never fully appears in the sequence of letters, they will eventually cluster over the best match, which in this case is "HXLLO".
The search continuously loops between two phases, the Diffusion Phase, and the Test Phase.
Every inactive agent (grey box) selects an agent at random, this is called "polling".
If the polled agent is active (a yellow arrow pointing to a yellow agent) then the polling agent will move to hover over the same letter as the active agent. The arrow pointing from the inactive polling agent to the active polled agent will be yellow.
If the polled agent is inactive (a black arrow pointing to a grey agent) then the polling agent will select a letter at random (a green arrow pointing to a letter).
Active agents (yellow boxes) do not do anything in the diffusion phase.
All agents move at the same time.
Every agent selects one of the five microtests at random.
If the test is successful the agent becomes active (a yellow box).
If the test is not successful the agent becomes inactive (a grey box).
The agents may cluster over the next best match "HELHX", and even at the poorer matches "HXLXH" and "XLLOO" very briefly, but will eventually move to the better match.
In a real world application, the search can be very fast indeed as each agent stores a tiny amount of information, just a location, and its activity, and each individual test is very simple.
This is a very simple and crude animation, I welcome offers to improve it, or to reimplement it entirely. I would like to make it interactive, so the user can change the search space, easier to understand, and with the option of performing Context-Free and Context-Sensitive Diffusion Phases.
In Context-Free Diffusion, active agents also poll random agents, if the polled agent is active, then the polling agent becomes inactive.
In Context-Sensitive Diffusion, active agents also poll random agents, if the polled agent is active and both agents share the same hypothesis, then the polling agent becomes inactive.
Both Context-Free Diffusion and Context-Sensitive Diffusion help reduce the number of active agents, which increases the number of inactive agents performing searches around the entire search space.