Foundations of Stochastic Diffusion Search
Kris De Meyer · 2004
Stochastic Diffusion Search (sds) was introduced by Bishop (1989a) as an algorithm to solve pattern matching problems. It relies on many concurrent partial evaluations of candidate solutions by a population of agents and communication between those agents to locate the optimal match to a target pattern in a search space. In subsequent research, several variations on the original algorithmic formulation were proposed. It also became evident that its main principles – partial evaluation and communication between agents – can be employed to problems outside the pattern matching domain. The primary aim of this dissertation is to develop these expansive views further: sds is proposed as a metaheuristic, a generic heuristic procedure for solving problems through search. Furthermore, it is proposed as a challenge to the dominant metaphor in computer science: sequential computation. The thesis proceeds in a structured way by first considering all questions that can be asked about a heuristic procedure like sds: questions of a foundational nature, questions pertaining to mathematical analysis, questions about application domains and questions about physical implementation. It is to the foundational issues that most attention is devoted. Analogies with selective processes in natural and social systems are investigated, as well as analogies with other metaheuristic techniques from artificial intelligence. An attempt is made to categorise potential variants, and to establish what kind of problems sds would be the optimal problem-solving method for. The work aims to provide an expanded but structured understanding of sds, to give guidelines for future work, and to establish how progress in other scientific disciplines can be of use in the study of sds, and vice versa. Preface All sciences characterise the essential nature of the systems they study. These characterisations are invariably qualitative in nature, for they set the terms with which more detailed knowledge can be developed. A. Newell and H. Simon (Newell and Simon, 1976) Cybernetics is the science of defensible metaphors.