Stochastic Diffusion Search - A swarm intelligence algorithm using partial evaluation

INITIALISE (mappings);

REPEAT

    TEST (mappings);

    DIFFUSE (mappings);

UNTIL TERMINATION;
// SDS  as introduced by J.M. Bishop in 1989

Introduction

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

• Partial evaluation of solutions
• Diffusion of promising solutions throughout the swarm

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.

• The Restaurant Game
• The Mining Game

Pseudocode

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
            else
                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
        else
            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 simple_sds.py.

An implementation of the same application can be seen in the GitHub gist string_search.py 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.

Definitions

• An agent is an individual member of a swarm.
• A swarm is a collection of agents.
• A search space is the set of all possible hypotheses.
• A hypothesis is an element of the search space, or a pointer to a part of the search space.
• A microtest is a function which partially evaluates a hypothesis.
• The score of a hypothesis is equal to the probability of an agent with that hypothesis being active after the test phase.

Next step:

• SDS Library source
• SDS Library reference

Other Links:

• SDS Publication Repository - A list of publications (articles, dissertations, theses, conference papers, book chapters, etc.) on Stochastic Diffusion Search.
• Presentation slides - The slides for a lecture I gave introducing SDS in the context of natural computing are available here. The slides include SDS described with flowcharts and the introduction of some of the major SDS variants.
• Animation - A simple explanation of Stochastic Diffusion Search accompanied by a fairly confusing animation.