Stochastic diffusion search

Stochastic diffusion search (SDS) was first described in 1989 as a population based, pattern matching algorithm. 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.

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.

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].

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.