Stochastic Diffusion Search
Encyclopedia
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 algorithm
s. 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.
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.
Swarm intelligence
Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
and naturally inspired search and optimisation algorithms which includes ant colony optimization
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
, particle swarm optimization
Particle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
and genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s. Unlike stigmergetic communication employed in ant colony optimization
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
, 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.