STOCHASTIC DIFFUSION: USING RECRUITMENT FOR SEARCH
Krisztina Mayer, J. Michael Bishop, Slawomir J. Nasuto · CentAUR (University of Reading) · 2003
ABSTRACT Stochastic Diffusion Search (SDS) is an efcient genericsearch method, originally developed as a population-basedsolution to the problem of best-t pattern matching. In re-cent years, similarities between previously unrelated searchmethods have been discovered [28] and further unicationand hybridisation is expected. In this context this paperseeks to establish links between SDS and Ant Algorithms,(AA). Contrary to the stigmergetic communication used inmost AA, SDS uses a one-to-one recruitment system akinto the tandem-running behaviour found in certain speciesof ants. With reference to SDS it is claimed that efcientglobal decision making can emerge from interaction andcommunication in a population of individuals each forminghypotheses on the basis of partial evidence. 1. INTRODUCTION In recent years there has been growing interest in a dis-tributed mode of computation utilising interaction betweensimple agents. Such systems have often been inspired byobserving interactions between social insects, such as antsand bees. Many algorithms inspired by the behaviour ofants, (Ant Algorithms, AA), use the principle of commu-nication via pheromone trails to successfully tackle hardsearch and optimisation problems, see Dorigo, [12], for a re-cent review. This indirect form of communication by mod-ication of physical environmental states has been termedstigmergetic communication. The problem solving abilityof these algorithms emerges from the positive feedback mech-anism and spatial and temporal characteristics of the pheromonemass recruitment system they employ. Other AA exploremechanisms for division of labour, brood sorting and co-operative transport as observed in real ant colonies, [6].Independently of these ant-inspired algorithms, Stochas-tic Diffusion Search (SDS) was proposed in 1989 as a population-based pattern-matching algorithm [3] [4]. Unlike stigmer-getic communication employed in AA, which is based onmodication of the physical properties of the environment,SDS uses a form of direct communication between the agentssimilar to the tandem calling mechanism employed by onespecies of ants, Leptothorax Acervorum, [17].SDS uses a population of agents. Each agent poses ahypothesis about the possible solution and evaluates it par-tially. Successful agents repeatedly test their hypothesiswhile recruiting unsuccessful agents by direct communica-tion. This creates a positive feedback mechanism ensuringrapid convergence of agents onto promising solutions in thespace of all solutions. Regions of the solution space la-belled by the presence of agent clusters can be interpretedas good candidate solutions. A global solution is thus con-structed from the interaction of many simple, locally oper-ating agents forming the largest cluster. Such a cluster isdynamic in nature, yet stable, analogous to, fia forest whosecontours do not change but whose individual trees dofl, [1].Section 2 discusses recruitment strategies in ants andbees. In Section 3, an in-depth account of SDS applied toa novel best-t search problem is given, together with anoverview of work on SDS. Section 4 describes the relation-ship between SDS and social insect algorithms. Section 5concludes by proposing SDS as a population-based meta-heuristic, based on partial evaluation of hypotheses and lo-cal, direct communication between agents.