Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabu Search
Modern Heuristic Techniques for Combinatorial Problems, Colin R. Reeves (Ed.), 70-150, Blackwell Scientific Publications, Oxford, 1993.
FRED GLOVER¹ and MANUEL LAGUNA ²
1 US West Chair in Systems Science, Graduate School of Business and Administration, Campus Box 419, University of Colorado. Boulder, CO 80309-0419. [e-mail].
2 Graduate School of Business and Administration, Campus Box 419. University of Colorado, Boulder. CO 80309-0419, [e-mail].
Tabu Search / 1
1. Introduction
Tabu search (TS) has its antecedents in methods designed to cross boundaries of feasibility or local optimality standardly treated as barriers, and to 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 (Glover, 1977). The modern form of tabu search derives from Glover (1986). Seminal ideas of the method are also developed by Pierre Hansen (1986) in a steepest ascent / mildest descent formulation. Additional contributions, such as those cited in the following pages, are shaping the evolution of the method and are responsible for its growing body of successful applications.

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 constituting 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 search alternatives classed as "forbidden," and also by translation into modified evaluations and probabilities of selection.

The purpose of this chapter is to integrate some of the fundamental ways of viewing and characterizing tabu search, with extended examples to clarify its operations. We also point to a variety of directions for new applications and research. Our development includes comparisons and contrasts between the principles of tabu search and those of simulated annealing (SA) and genetic algorithms (GAs). Computational implications of these differences, and foundations for creating hybrid methods that unite features of these different approaches are also discussed. In addition, we examine special designs and computational outcomes for incorporating tabu search as a driving mechanism within neural networks.

The philosophy of tabu search is to derive and exploit a collection of principles of intelligent problem solving. A fundamental element underlying 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 acquiring 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. The role of these elements in creating effective problem solving processes provides the focus of our following development
2 / GLOVER and LAGUNA
2. The Tabu Search Framework
To provide a background for understanding some of the fundamental elements of tabu search, we illustrate its basic operation with an example.
2.1 An Illustrative Example
Pemutation problems are an important class of problems in optimization, and offer a useful vehicle to demonstrate some of the considerations that must be faced in the combinatorial domain. Classical instances of permutation problems include traveling salesman problems, quadratic assignment problems, production sequencing problems, and a variety of design problems. As a basis for illustration, consider the problem of designing a material consisting of a number of insulating modules. The order in which these modules are arranged determine the overall insulating property of the resulting material, as shown in Figure 1.
Fig. 1 Modules in an insulating material.
Material



~ Modules
The problem is to find the ordering of modules that maximizes the overall insulating property of the composite material. Suppose that 7 modules are considered for a particular material, and that evaluating the overall insulating property of a particular ordering is a computationally expensive procedure. We desire a search method that is able to fmd an optimal or near-optimal solution by examining only a small subset of the total possible permutations (in this case, numbering 5040, though for many applications the number can be astronomical).

Closely related problems that can be represented in essentially the same way include serial fIltering and job sequencing problems. Serial fIltering problems arise in pattern recognition and signal processing applications, where a given input is to be subjected to a succession of fIlters (or screening tests) to obtain the "best" output. Filters are sequentially applied to the input signal, and the quality of the output is determined by the order in which they are placed (see Figure 2). In this case, the search method must be designed to find the best filtering sequence. Such filtering

Tabu Search /
3
processes are also relevant to applications in chemical engineering, astronomy, and biochemistry.