Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabu Search / 13
as good or better than all solutions in its neighborhood. The evident shortcoming of a Descent Method is that such a local optimum in most cases will not be a global optimum, ie., it usually will not minimize c(x) over all x E X.

Randomized procedures such as Monte Carlo methods, which include simulated annealing, similarly can be represented by adding a simple provision to Step 2.

Monte Carlo Method
Step 2 (Choice and tennination).

(A) Randomly select x_next from N(x_now).

(B) If c(x_next) S c(x_now) accept x_next (and proceed to the Update Step) .

(C) If c(x_next) > c(x_now) accept x_next with a probability that decreases with increases in the difference c(x_next) -c(x_now). If x_next is not accepted on the current trial by this criterion, return to Step 2(A).

(D) Tenninate by a chosen cutoff rule.
Monte Carlo methods continue to sample the search space until finally terminating by some fomt of iteration limit. Nomtally they use an exponential function to define probabilities, drawing from practice established in engineering and physical science. The Monte Carlo version represented by simulated annealing starts with a high probability for accepting nonimproving moves in Step 2(C) and decreases this probability over time as a function of a parameter called the "temperature," which monotonically diminishes toward 0 as the number of iterations grows. Such approaches offer a chance to do better than finding a single local optimum since they effectively terminate only when the probability of accepting a non-improving move in Step 2(C) becomes so small that no such move is ever accepted (in the finite time allowed). Hence, they may wander in and out of various intemtediate local optima prior to becoming lodged in a final local optimum, when the temperature becomes small.

Another randomizing approach to overcome the limitation of the Descent Method is simply to re-start the method with different randomly selected initial solutions, and run the method multiple times. Such a random restart approach (sometimes called Iterated Descent), may be contrasted with a random perturbation approach, which simply chooses moves randomly for a period after reaching each local optimum, and then resumes a trajectory of descent. Alternating threshold methods indicated in Section 2.7.1 provide a refmement of this idea.

14 / GLOVER and LAGUNA
2.4
Tabu Search Characteristics
Tabu search, in contrast to the preceding methods, employs a somewhat different philosophy for going beyond the criterion of tenninating at a local optimum. Randomization is deemphasized, and generally is employed only in a highly constrained way, on the assumption that intelligent search should be based on more systematic fonns of guidance. Randomization (pseudo- randomization) thus chiefly is assigned the role of facilitating operations that are otherwise cumbersome to implement or whose strategic implications are unclear. (In the latter case, a supplementary learning approach such as target analysis (Laguna and Glover, 1993) customarily is employed to detennine if such implications can be sharpened.) Accordingly, many tabu search implementations are largely or wholly detenninistic. An exception occurs for the variant called probabilistic tabu search, which selects moves according to probabilities based on the status and evaluations assigned to these moves by the basic tabu search principles. (A discussion of probabilistic convergence issues is provided by Faigle and Kern, 1992.)
2.4.1
Special TS Uses of Memory: Modifying Neighborhood Structures
The notion of exploiting certain forms of flexible memory to control the search process is the central theme underlying tabu search. The effect of such memory may be envisioned by stipulating that TS maintains a selective history H of the states encountered during the search, and replaces N(x_now) by a modified neighborhood which may be denoted N(H, x_now). History therefore determines which solutions may be reached by a move from the current solution, selecting x_next from N(H, x_now).

In the TS strategies based on short term considerations, N(H, x_now) characteristically is a subset of N(x_now), and the tabu classification serves to identify elements of N(x_now) excluded from N(H, x_now). In the intermediate and longer term strategies, N(H, x_now) may contain solutions not in N(x_now), generally consisting of selected elite solutions (high quality local optima) encountered at various points in the solution process. Such elite solutions typically are identified as elements of a regional cluster in intermediate term intensification strategies, and as elements of different clusters in longer term diversification strategies. In addition, elite solution components, in contrast to the solutions themselves, are included among the elements that can be retained and integrated to provide inputs to the search process.

TS also uses history to create a modified evaluation of currently accessible solutions. This may be expressed formally by saying that TS replaces the objective function c(x) by a function c(H, x), which has the purpose of evaluating the relative quality of currently accessible solutions. (An illustration is provided by the use of frequency based memory in the example of Section 2.1.) The relevance of this modified function occurs because TS uses aggressive choice criteria that seek a best x_next, ie., one that yields a best value of c(H, x_next), over a candidate set drawn from N(H, x_now). Moreover, modified evaluations often are accompanied by systematic alteration of