Exploring SDS with text search

Stochastic Diffusion Search (SDS) is a form of Swarm Intelligence devised by John Mark Bishop and Mohammad Majid al-Rifae that focuses around iterations of actions between agents. This is modelled after social interactions between swarms of insects which is heavily influenced by their environments as well as their individual interaction with one another. But how exactly does it work?

Each agent of a given SDS population is initially assigned a random hypothesis which represents a possible solution to the relevant problem. SDS then loops through two different phases, the test phase and the diffusion phase. In the test phase, each agent’s hypothesis is put to the test and returns a boolean value to determine whether or not it has found the solution. In the diffusion phase, the social communication of agents is taken advantage of as each agent interacts with another agent to exchange hypotheses with one another.

Outside of learning the fundamentals of SDS, we were assigned a task during our lab session to better understand it’s implementation. For this task, we were required to find all instances of the string “Denmark” in a provided body of text using SDS. Most of work was done for us within processing and all we had to do was to implement the diffusion phase of the algorithm where the agents communicate with one another to determine the best path towards a solution.

The way I had implemented this goes as follows: For each agent in the population, if an agent’s hypothesis returned false, it would be assigned a new hypothesis derived from either another random agent in the population given that they’re hypothesis returns true, or (if the new chosen agent’s hypothesis returns false) it would be assigned a new random hypothesis. If this agent’s hypothesis returned true, it’s values would be stored for evaluation in the next testing phase and become inactive for other agents to refer by in order to reach an optimal consensus across the population.

This enabled the system to successfully find any instance of Denmark with a reasonable population size of 20 and iteration values ranging between roughly 20–50.