# 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.

### 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.