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.
  • Log in or register to write something here or to contact authors.