VII. |
EC RELATED TECHNIQUES |
Tabu search (TS) has its antecedents in methods designed to cross boundaries of feasibility or local optimality normally treated as barriers, and systematically impose and release constraints to permit exploration of otherwise forbidden regions. Early examples of such procedures include heuristics based on surrogate constraint methods and cutting plane approaches that systematically violate feasibility conditions.
Webster's dictionary defines tabu or taboo as 'set apart as charged with a dangerous supernatural power and forbidden to profane use or contact...' or 'banned on grounds of morality or taste or as contituting a risk...'. Tabu search scarcely involves reference to supernatural or moral considerations, but instead is concerned with imposing restrictions to guide a search process to negotiate otherwise difficult regions. These restrictions operate in several forms, both by direct exclusion of certain search alternatives classed as 'forbidden', and also by translation into modified evaluations and probabilities of selection.
The purpose of this section is to introduce some of the fundamental points that characterize tabu search.
The philosophy of tabu search is to derive and exploit a collection of principles of intelligent problem solving. A fundamental element undelying tabu search is the use of flexible memory. From the standpoint of tabu search, flexible memory embodies the dual processes of creating and exploiting structures for taking advantage of history (hence combining the activities of acquaring and profiting from information).
The memory structures of tabu search operate by reference to four principal dimensions, consisting of recency, frequency, quality, and influence. These dimensions in turn are set against a background of logical structure and connectivity.
Figure 1. Tabu Search method.