INITIALISE (mappings); REPEAT TEST (mappings); DIFFUSE (mappings); UNTIL TERMINATION; // 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 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
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:
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
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.