Natural Computing Blog

Playing Around With The SDS Algorithm

Stochastic Diffusion Search, first incepted in 1989 by John Mark Bishop, belongs to the extended family of swarm intelligence algorithms.[1]

SDS leverages the power of emergent “intelligence” from a swarm of simple agents, in which interactions between the latter cause the population of agents to evolve towards potential solution states. Each agent can be seen (and constructed) as a simple computer program that follows a few hard-coded instructions. The strength of the algorithm, however, lies in its combining a controlled level of stochasticity with certain unique rules that allow for local feedback among the units. The result of such a combination makes the algorithm behaves like a population of ants foraging, and it allows the program to find local or even global optima within a reasonable search time.

One species of ants in particular, the Leptothorax acervorum, uses a a ‘tandem calling’ mechanism (one-to-one communication) similar to the way SDS works. By means of this system, ants are able to recruit other agents and make the swarm converge to optimal solutions found.

In the last few days, I have had a play around with SDS, especially with a Processing implementation which I had to complete myself in order to carry out a text-search. I also had some fun tweaking the parameters of a simple game featuring virtual “miners” on the look out for “gold” dots on a 2D chequerboard.

In the Processing implementation example, I started out with a sketch that was already able to load a texts as a string of character, and generate a container (Java array) of agents.

The class defining the agent-object was nothing more than a custom type having 2 features: a “status” stored as a boolean variable, and working “hypothesis” defined as by number (integer) variable. The class also had a couple of simple methods to return or change the value of the 2 features.

Using a simple interface, the program was also set up so that it could display the text to search in (search-space), the position of the agents across the text (each agent could “bind” to one character at a time) and receive a string of characters as the “model”: the traget “word” to be looked for.

In terms of the actual SDS implementation, the swarm initialises so that each agent would be assigned to a random location across the search space with an initial activity status set to FALSE (inactive).

 // INITIALISATION PHASE
 for ( int i = 0; i < agentSize; i++ )
 {
 agent[i] = new Agent( r.nextInt( s.length() - modelSize + 1), false );
 ...
 }

// where s = string defining the search space // r = random number generator
// & Agent's constructor : (int hypothesis, boolean status)

At each cycle, the program then starts by testing the spot where each agent is at. It does so by finding the character in the text where the agent is at (position = value of its hypothesis), then comparing a random character from the model (target word) to the character whose position would correspond to such random character. If the comparison returns a positive match, the agent assumes it has possibly found the beginning character of the searchd for word and it turns active.

 // TEST PHASE
 for ( int i = 0; i < agentSize; i++ )
 {
     ...
     int randMicroFeature = r.nextInt( modelSize );
     int h = agent[i].getHypo();
     if ( s.charAt(h+randMicroFeature) == model.charAt(randMicroFeature) )
     {
         agent[i].setStatus( true );
         activeAgent++;
     } else
         agent[i].setStatus( false );
 }

Finally, during the diffusion phase, the agents communicate with and recruit one another according to the specific model employed by the algorithm. SDS can be implemented in various ways, depending on the specific model used in the diffusion phase, and for this implementation I had to code this part myself.

I referred to a paper co-authored by the creator of SDS and by my Natural Computing lecturer at Goldsmiths University of London [2], to have a better understanding of the ways I could tackle this task. As the paper itself notes:

One of the issues related to SDS is the mechanism behind allocating resources to ensure that while potential areas of the problem space are exploited, exploration is not ignored. For this purpose, different recruitments methods, where one agent recruits another one, are investaged:

Three recruitment strategies are presented in the paper: active, passive and dual. The standard SDS algorithm [3] uses the passive recruitment mode. However, after trying out the three types, I decided to code a dual one for my implementation as it managed to find all the word matches faster and more reliably than the other two.

In the passive recruitment mode, if the agent is not active, another agent is randomly selected and if the randomly selected agent is active, the hypothesis of the active agent is communicated (diffused) to the inactive one. Otherwise a new random hypothesis is generated for the inactive agent and there will be no flow of information.

In the active recruitment mode, active agents are in charge of communication with other agents. An active agent ran- domly selects another agent. If the randomly selected agent is neither active nor engaged in communication with an- other active agent, then the hypothesis of the active agent is communicated to the inactive one and the agent is flagged as engaged. The same process is repeated for the rest of the active agents. However if an agent is neither active nor engaged, a new random hypothesis is generated for it.

In dual recruitment mode, both active and inactive agents select agents. There may be different ways in which the two agents engage with others and the methods can be assigned at random or dependent on the state of the agents. The paper I was referring to specified that in a standard dual recruitment mode agents are randomely selected both on the active and inactive sides. When the selected agent is active, another agent is randomly selected. If the randomly selected agent is neither active nor engaged, then the hypothesis of the active agent is shared with the inactive one. Also, if there is an agent which is neither active nor engaged, it selects another agent randomly. If the newly selected agent is active, there will be a flow of information from the active agent to the inactive one and the inactive agent is flagged as engaged. Nevertheless, if there remains an agent that is neither active nor engaged, a new random hypothesis is chosen for it.

In my implementation, however, I slighlty adapted such dual mechanism so that all agents would be asked in turn to communicate with one another. Furthermore, their behaviour would change depending on their status:

If they are active, they will choose another agent at random and see whether such agent is also active. If it is, the current agent will check whether their hypothesis are the same and if so, it will turn inactive and change its own hypothesis to a new random one.

If they are inactive, they will choose another agent at random and copy its hypothesis in case such agent was active, or generate a new hypothesis in case such agent was inactive.

 // DIFFUSION PHASE
 for ( int i = 0; i < agentSize; i++ )
 {
   if (agent[i].getStatus()) { // if the agent is active
     engageWithOther(i); // find other active agent 
   } else {
     findBetterHypo(i); // if inctive, try and find an active hypo
   }
 }
...
// -----------------------------------------------
void findBetterHypo(int i) {
 int new_agent_index = int(random(agentSize));
 if (agent[new_agent_index].getStatus()){
   agent[i].setHypo(agent[new_agent_index].getHypo());
 } else {
   agent[i].setHypo(int(random(s.length() - modelSize + 1)));
 }
}
...
void engageWithOther(int i){
 int new_agent_index = int(random(agentSize));
 if(new_agent_index == i){
   engageWithOther(i);
   return;
 }
 if(agent[new_agent_index].getStatus() && agent[i].getHypo() == agent[new_agent_index].getHypo()){
   agent[i].setStatus(false);
   agent[i].setHypo( int(random(s.length() - modelSize + 1)) );
 }  
}

In the ideation of such model, I got inspired by what the paper describes as Context Sensitive recruitment model. In the context sensitive mechanism if an active agent randomly chooses another active agent that maintains the same hypothesis, the selecting agent is set inactive and adopts a random hypothesis. This mechanism frees up some of the resources in order to have a wider exploration throughout the search space as well preventing cluster size from overgrowing, while ensuring the formation of large clusters in case there exists a perfect match or good sub-optimal solutions.

The paper also describes another mechanism, the Context Free recruitment model, where each active agent randomly chooses another agent as in the Context Sensitive one. However, in the Context Free one, if the selected agent is active (irre- spective of having the same hypothesis or not), the selecting agent becomes inactive and picks a new random hypothesis. This mechanism ensures that even if one or more good solutions exist, about half of the agents explore the problem space and investigate other possible solutions.

In the particular example of my implementation within a text-search problem, I found that a simple active recruitment, as well as the context free mechanism and the simple dual recruitment mechanism, remained a bit unstable. They would find multiple solutions in case of a word being present more than once, but the clusters would break up before forming again.

The standard passive recruitment and the simple context sensitive model instead did not manage to find all the instances of a certain word if it appeared multiple times (at least not always). After experimenting a little with a couple of mixed verison, I eventually set for my “hybrid” as it turned out to be very fast, reliable (all solutions found quickly) but also stable. As a matter of fact, despite a potion of the population being kept searching even after finding solutions, the clusters indicating word matches would not break even in case of several repetitions and a population of 20 agents.

After having a go at my custom implementation, I explored the SDS investigator through a Mining Game Simulator 2D game, where I could visualise the agents’ behaviour whilst changing the standard recruitment models on the fly.

By observing several runs, I could not notice much of a difference by switching among active, passive, or dual, other than the passive model tended to be more stable if I went taken away “gold spots” after the algorithm had found a “quadrant” (hill) with the highest (or among the highest) concentration of gold spots.

I did find instead a clear difference between enabling a context sensitive, a context free or enabling none of them. In the first instance, there would be always some agents exploring, even if a quandrant with a lot of gold spots had been found. With the context free enabled, even more agents would be freed and look out for different solutions, which could sometimes undermine the stability of less then well-defined findings (for instance if the hill with the most gold spots is not that full of them). Finally, without any of the two enabled, the agents would always tend to collapse and get stuck onto a promising spot, irrispectively of whether this might or might not be the global optima.

Leave a Reply

Your email address will not be published. Required fields are marked *