More reading/writing about stochastic diffusion search today.
Quick note to self regarding topology: if you think about it, each agent in the SDS population is connected to every other agent in the population… however the connection only becomes “active” randomly so it is not a permanent neighbourhood.
Another quick note, look at page 62 of Nasuto’s thesis as he mentions the convergence from SDS. He also has an interesting worked example of how an SDS search progresses.
— Quick notes —
Stochastic diffusion search is a parallel based search algorithm, developed by Bishop in 1988. The algorithm achieves a linear time complexity (Nasuto thesis). Stochastic diffusion search attempts to solve inexact matching (stimulus equivalence) with less computational expense than that of Neocogntion or Hinton mapping methods (Bishop 1988). The algorithm has four distinct parts: initialisation, testing, diffusion, and termination.
Method of action
Stochastic diffusion search uses individual elements called “agents” to store positional mappings, the agent’s current position in the search space. During the testing phase each agent compares its mapping with that of another randomly selected mappings elsewhere in the search space.
During initialisation, each agent is randomly assigned a mapping into the search space. The testing and diffusion phases then loop until the termination conditions are discovered. In the diffusion phase, information is transferred between agents, enabling communication regarding possible solutions. Agents can become “active” they point to possible solutions in the search space, and remain “in-active” if else. Through agents independently searching for partial, possible solutions, a competitive, co-operative process emerges. As partial solutions are identified by the population of agents, and other positions are identified as incorrect, the partial solutions “compete” to have additional agents allocated to their positions. Through this, competition changes into co-operation, with increasing numbers of agents attracted to explore the potential solution.
As the process continues, more dimensions of possible solutions are analysed, hence identifying incorrect solutions, which are removed from the set of possible solutions. Through this process and the above-mentioned competition, all potential solutions will be independently evaluated, and after a number of iterations most promising one will attract the majority of the computational resources, with the position of the best fits the data model emerging.
