What is SDS?
Stochastic Diffusion Search (SDS) is a search algorithm that using swarm intelligence to achieve its outcome. The algorithm contains agents, that each have a hypothesis and a current state, and each of them communicate with each other.
How does it work?
In order for the swarm to find the model they are looking for in the search space, the swarm must communicate their hypothesis and their state to the other members of the swarm. This increases the speed of the algorithm and allows it to have a probability of one when solving a problem.
The algorithm can be described in steps and I have created a flow diagram for the restaurant game:
The steps are as follows.
For each agent:
- Select a random place in the search space. [This then becomes that agents hypothesis]
- Select a random section from the predicted model.
- If the hypothesis matches the model then go to step 2.
- If the hypothesis does not match the model then select a random agent that is not itself.
- If their the random agents hypothesis of matched the model then make their hypothesis the current agents hypothesis.
- If their the random agents hypothesis of does not match the model then go to step 1.
I have created the following video explaining further how SDS works in terms of the restaurant game:
There are several applications for SDS and these include:
- Text Analysis
- Image Processing
1. SDS has been used for MRI scans in order to detect where parts of the brain are defected. A paper from Mohammad Majid al-Rifaie, Ahmed Aber and Duraiswamy Jude Hemanth explores this further.
2. In the lab we found text from our model in the search space of a sentence. I think that this can be easily expanded to find all words in the model throughout all of a file.
3. It is possible to find the symmetry within an image, but I am currently not too sure how this is done.