Time-stepped Simulation
- PDF / 804,832 Bytes
- 43 Pages / 547.087 x 737.008 pts Page_size
- 51 Downloads / 145 Views
Tableau ▶ Simplex Tableau
Tabu Search Fred W. Glover OptTek Systems, Inc., Boulder, CO, USA
Introduction Tabu Search (TS) is a metaheuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality. Widespread successes in practical applications of optimization include finding better solutions to problems in scheduling, sequencing, resource allocation, investment planning, telecommunications and many other areas. Some of the diversity of tabu search applications is shown in Table 1. (For a more comprehensive list of applications, see the book by Glover and Laguna 1997.) Tabu search is based on the premise that methods for complex optimization problems, particularly those arising in real world applications, can function more effectively if they incorporate flexible and responsive memory. Accompanying this premise is the corollary that such memory is employed together with strategies expressly designed for exploiting it. More broadly, tabu search embodies the following principle: If a problem has exploitable features, but contains a structure sufficiently complex to prevent these features from being known in advance, then a method
can derive advantages by monitoring its behavior in relation to the space in which it operates. The purpose of the monitoring is effectively to generate a map of the regions the method has visited as a foundation for modifying its behavior, where this map can take multiple forms that ultimately become expressed in the decision rules employed to negotiate the solution space. The hallmark of a TS method is therefore a capacity to guide its progress by reference to its own unfolding history. Such a method evidently is implicitly or explicitly structured to employ learning. Based on this perspective, methods that incorporate a significant portion of the tabu search framework are sometimes called Adaptive Memory Programming (AMP) methods. The emphasis on responsive exploration (and hence purpose) in tabu search, whether in a deterministic or probabilistic implementation, derives from the supposition that a bad strategic choice can yield more information than a good random choice. In a system that uses memory, a bad choice based on strategy can provide useful clues about how the strategy may profitably be changed. Even in a space with significant randomness – which fortunately is not pervasive enough to extinguish all remnants of order in most real-world problems – a purposeful design can be more adept at uncovering the imprint of structure, and thereby at affording a chance to exploit the conditions where randomness is not all-encompassing. These basic elements of tabu search have several important features that are summarized in Table 2. Tabu search is concerned with finding new and more effective ways of taking advantage of the concepts embodied in Table 2, and with identifying associated principles that can expand the foundations
S.I. Gass, M.C. Fu (eds.), Encyclopedia of Operations Research and Management Science, DOI 10.1007/978-1-4419-1153-7,
Data Loading...
