Stochastic diffusion search is an
agent based,
connectionist,
pattern matching, search
algorithm.
It can be thought of as a fully connected network of agents but I prefer to think of it as sporadically connected. It makes little difference really.
It works in an
atomic space. This means that the data with which it works consists of independant pieces of data. The simplest example of this is that
characters are atoms in the space of a
string.
It is a very
noise tolerant
algorithm and the time to
convergence (when it finds a match or matches) increases at most
linearly with
search space size.
It will find the best match with
probability one and many imperfect matches besides (depending on how the parameters are set).
It works very well in dynamic, constantly changing, search spaces such as sucessive video frames (an atom would be a pixel in this case).
The network has:
loads of agents, all initially inactive.
a target pattern for which the agents can search.
Each agent has:
activation:
boolean : This is simply whether the agent is active of not.
mapping : the agent's coordinates in the
search space.
Each agent goes through this cycle every
iteration:
while network is not
converged do
diffuse
test
relate
end while
Test Phase
The test phase is simply used to determine if an agent should be active for the next iteration.
1. The agent chooses a random offset into the target, measured from the start of the target, and looks at the atom in that position.
2. The agent looks at the atom in the search space that has the same offset from that agents mapping (or position)
3. If the two atoms are the same the agent becomes active otherwise it becomes inactive.
Diffuse Phase
This phase is used to move the agents around the search space so that they have a chance of discovering a match.
1. If the agent is active it does nothing (i.e. it holds its position so it can be tested again next iteration.)
2. If the agent is inactive it picks another agent at random (call it agent2)
3. If agent2 is active then its mapping is copied to this agent (the inactive agent moves to the active agent's position)
4. If agent2 is inactive a new random mapping is generated for this agent (this agent is randomly re-positioned in the search space).
Relate Phase
NB: The relate phase is entirely optional.
It is used to change the behaviour of the network. There are two standard rules for this phase. These two rules should, ideally, not be used together as you will probably see. They are very simple rules.
Context Free
This rule is used to ensure that even if one or many good matches are found about half of the agents will still be exploring the search space looking for other matches.
1. If the agent is active it picks another agent at random (agent2)
2. If agent2 is active the agent is deactivated.
Context Sensitive
This rule is used to ensure that even if a good match is found only half of the agents will be looking at this match. It is used to control cluster size in search spaces where many full or partial matches are expected.
1. If the agent is active it picks another agent at random (agent2)
2. If agent2 is active and has the same mapping (is in the same place) then the agent is deactivated.
Convergence
Convergence, also known as halting, is used to stop the search when a statistical equilibruim is achieved.
In terms of S.D.S. a statistical equilibrium is defined in terms of two values
1) A threshold of total activation of the network (i.e. how many agents are active) usually expressed as a percentage.
2) A number of iterations for which this threshold must be passed.
Once the network has an activation that passes the threshold for the number of iterations specified the search is stopped and you can start analysing the resulting clusters. This is generally done with another lower threshold.