Stochastic diffusion search

Stochastic diffusion search (SDS) was first described in 1989 as a population-based, pattern-matching algorithm [Bishop, 1989]. It belongs to a family of swarm intelligence and naturally inspired search and optimisation algorithms which includes ant colony optimization, particle swarm optimization and genetic algorithms; as such SDS was the first Swarm Intelligence metaheuristic. Unlike stigmergetic communication employed in ant colony optimization, which is based on modification of the physical properties of a simulated environment, SDS uses a form of direct (one-to-one) communication between the agents similar to the tandem calling mechanism employed by one species of ants, Leptothorax acervorum.

In SDS agents perform cheap, partial evaluations of a hypothesis (a candidate solution to the search problem). They then share information about hypotheses (diffusion of information) through direct one-to-one communication. As a result of the diffusion mechanism, high-quality solutions can be identified from clusters of agents with the same hypothesis. The operation of SDS is most easily understood by means of a simple analogy – The Restaurant Game.

The restaurant game

A group of delegates attends a long conference in an unfamiliar town. Every night each delegate must find somewhere to dine. There is a large choice of restaurants, each of which offers a large variety of meals. The problem the group faces is to find the best restaurant, that is the restaurant where the maximum number of delegates would enjoy dining. Even a parallel exhaustive search through the restaurant and meal combinations would take too long to accomplish. To solve the problem delegates decide to employ a stochastic diffusion search.

Each delegate acts as an agent maintaining a hypothesis identifying the best restaurant in town. Each night each delegate tests his hypothesis by dining there and randomly selecting one of the meals on offer. The next morning at breakfast every delegate who did not enjoy his meal the previous night, asks one randomly selected colleague to share his dinner impressions. If the experience was good, he also adopts this restaurant as his choice. Otherwise he simply selects another restaurant at random from those listed in `Yellow Pages'. Using this strategy it is found that very rapidly significant number of delegates congregate around the 'best' restaurant in town.

Applications

SDS has been applied to diverse problems such as text search [Bishop, 1989], object recognition [Bishop, 1992], feature tracking [Grech-Cini, 1993], mobile robot self-localisation [Beattie, 1998] and site selection for wireless networks [Whitaker, 2002].

Analysis

Unlike many Nature Inspired Search techniques there is a comprehensive mathematical framework describing the behaviour of SDS. Analysis of SDS has investigated its global optimality and convergence [Nasuto, 1998], linear time complexity [Nasuto et al., 1999], robustness [Myatt, 2004], and resource allocation [Nasuto, 1999] under a variety of search conditions.

References

• Bishop, J.M., (1989). Stochastic Searching Networks. Proc. 1st IEE Conf. on Artificial Neural Networks, pp 329–331, London.
• Bishop, J.M. & Torr, P., (1992). The Stochastic Search Network. In R. Linggard, D.J. Myers, C. Nightingale (eds.), Neural Networks for Images, Speech and Natural Language, pp370–387, New York, Chapman & Hall.
• Beattie, P.D. & Bishop, J.M., (1998). Self-Localisation in the 'Senario' Autonomous Wheelchair. Journal of Intelligent and Robotic Systems 22, pp 255–267, Kluwer Academic Publishers.
• Grech-Cini, H.J. & McKee, G.T. (1993) Locating the Mouth Region in Images of Human Faces. In P.S.Schenker (Ed.), Proceedings of SPIE – The International Society for Optical Engineering, Sensor Fusion VI 2059, Massachusetts.
• Myatt, D.R., Bishop J.M. and Nasuto, S.J., (2004). Minimum Stable Convergence Criteria for Stochastic Diffusion Search To be published in Electronics Letters.
• Nasuto, S.J., (1999). Analysis of Resource Allocation of Stochastic Diffusion Search. PhD Thesis. University of Reading, UK.
• Nasuto, S.J. & Bishop, J.M., (1999). Convergence Analysis of Stochastic Diffusion Search. Journal of Parallel Algorithms and Applications 14:2, pp 89–107.
• Nasuto, S.J., Bishop, J.M. & Lauria, L., (1998). Time Complexity of Stochastic Diffusion Search. Neural Computation '98, Vienna, Austria.
• Whitaker, R.M., Hurley, S., (2002). An agent based approach to site selection for wireless networks. Proc ACM Symposium on Applied Computing (Madrid). 574–577.
• Jones, D. (2002). Constrained Stochastic Diffusion Search. SCARP 2002, University of Reading, UK.