Stochastic Diffusion Search - A swarm intelligence algorithm using partial evaluation

INITIALISE (mappings);


    TEST (mappings);

    DIFFUSE (mappings);

// SDS  as introduced by J.M. Bishop in 1989


Stochastic Diffusion Search (SDS) is a swarm intelligence algorithm characterised by two features.

If you're completely new to SDS the best way to start is to read the two "stories" in which a group of people perform the actions which implement SDS. They are both short and use no difficult technical concepts.


Simple pseudocode of SDS looks like this.

while halting criteria not met do

    # Diffusion phase
    for each agent in swarm do
        if agent is inactive then
            polled = randomly selected agent in swarm
            if polled is active then
                agent assumes the hypothesis of polled
                agent randomly selects a new hypothesis

    # Testing phase
    for each agent in swarm do
        microtest = randomly selected microtest
        agent performs the microtest against their hypothesis
        if the microtest passes then
            agent becomes active
            agent becomes inactive

return the hypothesis with the most active agents

Simple Example: String Search

A simple example of an application of SDS is to locate the closest instantiation of a 'model' substring in a larger 'search space' string.

For example, finding the location of the word 'circumambulate' in the text of Moby Dick, or the encoding of a protein in a string of DNA base pairs. A hypothesis denotes the location of the model in the search space. There is one test for each character in the model. Each test passes if the letter at a particular offset in the model is the same letter in the search space at the same offset to the hypothesised location. For example, when the model is 'hello' the tests will be:

  1. Is there an 'h' at the agent's hypothesis?
  2. Is there an 'e' one space along from the agent's hypothesis?
  3. Is there an 'l' two spaces along from the agent's hypothesis?
  4. Is there an 'l' three spaces along from the agent's hypothesis?
  5. Is there an 'o' four spaces along from the agent's hypothesis?

See a simple Python implementation of SDS String search in the GitHub gist

An implementation of the same application can be seen in the GitHub gist implemented with the SDS Library. Don't worry if this doesn't make sense yet, the SDS Library introduces some new concepts that have not yet been covered.


Next step:

Other Links: