7 Special Tabu Search Topics

Tabu Search1

7 SPECIAL TABU SEARCH TOPICS

In this chapter we begin by discussing probabilistic tabu search and the associated approach called tabu thresholding, which operates by reduced reliance on memory. Then we examine specialized memory mechanisms that have been used to enhance the performance of TS methods. We also discuss of approaches not yet widely considered. Finally, we examine basic strategies embodied in ejection chains, vocabulary building and parallel processing.

7.1 Probabilistic Tabu Search

In tabu search, randomization is de-emphasized, and generally is employed only in a highly constrained way, on the assumption that intelligent search should be based on more systematic forms of guidance. Randomization thus chiefly is assigned the role of facilitating operations that are otherwise cumbersome to implement or of assuming that relevant alternatives will not be persistently neglected (as a gamble to compensate for ignorance about a better way to identify and respond to such alternatives). Accordingly, many tabu search implementations are largely or wholly deterministic. However, as a potential hedge against the risks of strategic myopia, 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. The basic approach can be summarized as follows.

(a)Create move evaluations that include reference to tabu status and other relevant biases from TS strategies  using penalties and inducements to modify an underlying decision criterion.

(b)Map these evaluations into positive weights, to obtain probabilities by dividing by the sum of weights. The highest evaluations receive weights that disproportionately favor their selection.

Memory continues to exert a pivotal influence through its role in generating penalties and inducements. However, this influence is modified (and supplemented) by the incorporation of probabilities, in some cases allowing the degree of reliance on such memory to be reduced.

A simple form of this approach is to start by evaluating the neighborhood as customarily done in tabu search (including the use of candidate list strategies, special memory functions, and penalty and inducement values). Then, the best move can be selected by using a threshold so that probabilities are assigned to a subset of elements that consists of:

• the top k moves, or
• those moves having a value within % of the best.

Choosing a restricted subset of highest evaluation moves for determining a probability assignment already creates a disproportionate bias in favor of such evaluations. To avoid completely excluding other options, that subset may be enlarged by random inclusion of a small number of additional elements that would be admitted by a less restrictive threshold. However, it should be kept in mind that diversification strategies already should be designed to provide evaluations that will bring elements into the subset that would not be included using a standard decision criterion, such as one based solely on an objective function change. Whether the subset is enlarged therefore depends to the extent that the method incorporates a reasonably effective diversification approach.

The probabilistic selection from the chosen subset can be uniform or can follow a distribution function empirically constructed from the evaluation associated with each move. The latter is considered preferable, provided the evaluation is correlated with effective quality (Chapter 5). An example is provided by the neighborhood evaluation given in Table 2.1 of Chapter 2. If k is set to 6, then only swaps (5,6), (2,4), (3,4), (3,6), (1,4) and (1,2) will be considered for selection, as shown in Table 7.1. Since the set of top moves contains the move (1,2), which was previously identified to be nonimproving (in Table 2.1), one alternative may be to adjust k so the selection is not made within a mixed set. This reinforces the aggressive orientation of TS and introduces a regional dependency.

Tabu status can be included in two forms. One option is to eliminate all tabu moves before the selection is made. The other option is to use the remaining tenure of tabu-active attributes to bias the selection (e.g., by decreasing the probability of selecting a move). In the case where relatively simple rules are used to generate tabu status, the bias against selecting tabu moves may periodically be decreased, to compensate for limitations in the basis for classifying a move tabu.

An empirical probability distribution can be constructed using evaluations associated with each of the top moves. Suppose only improving moves are being considered for selection in Table 7.1, hence excluding the swap (1, 2). A cumulative probability function results from normalizing the cumulative absolute move values, as shown in the columns of Table 7.1 to the right of the Swap column. A uniform random number between zero and one is then generated to determine which move will be performed. For example, if 0.314 is generated, the swap (2,4) is selected.

In some situations, evaluations based on standard criteria do not sufficiently accentuate the relative differences in the effective quality of moves and it is preferable to modify quantities such as the absolute values in Table 7.1 by raising them to a power (e.g., by squaring or cubing) before generating the probability assignments (see Table 7.2). Such modification has been found particularly useful in scheduling applications where evaluations represent deviations from idealized “fits” or feasibility conditions (Glover and McMillan, 1986).

Table 7.2 shows the effect of squaring and cubing the absolute move values before calculating the empirical probability values for the swaps in Table 7.1. In this particular example, the only significant differences are observed in the probability values associated with the first and last swap. This is due to the fact that the three swaps between the first and the last all have the same absolute move value.

As in other applications of tabu search, the use of an intelligent candidate list strategy to isolate appropriate moves for consideration is particularly important in the probabilistic TS approach. Although a variety of ways of mapping TS evaluations into probabilities are possible (as illustrated above), an approach that sometimes performs well in the presence of “noisy” evaluations is as follows:

(1)Select the “r best” moves from the candidate list, for a chosen value of r, and order them from best to worst (where “evaluation ties” are broken randomly).

(2)Assign a probability p to selecting each move as it is encountered in the ordered sequence, stopping as soon as a move is chosen. (Thus, the first move is selected with probability p, the second best with probability (1-p)p, and so forth.) Finally, choose the first move if no other moves are chosen.

The effect of the approach can be illustrated for the choice p = 1/3. Except for the small additional probability for choosing move 1, the probabilities for choosing moves 1 through k are implicitly:

.

The probability of not choosing one of the first k moves is (1 - p)k, and hence the value p = 1/3 gives a high probability of picking one of the top moves: about 0.87 for picking one of the top 5 moves, and about 0.98 for picking one of the top 10 moves.

Experimentation with a TS method for solving 0-1 mixed integer programming problems (Lokketangen and Glover, 1996) has found that values for p close to 1/3, in the range from 0.3 to 0.4, appear to be preferable. In this application, values less than 0.3 resulted in choosing “poorer” moves too often, while values greater than 0.4 resulted in concentrating too heavily on the moves with highest evaluations.

Basing probabilities on relative differences in evaluations can be important as a general rule, but the simplicity of the ranking approach, which does not depend on any “deep formula,” is appealing. It still can be appropriate, however, to vary the value of p. For example, in procedures where the number of moves available to be evaluated may vary according to the stage of search, the value of p should typically grow as the alternatives diminish. In addition, making p a function of the proximity of an evaluation to a current ideal shows promise of being an effective variant (Xu, Chiu and Glover, 1996a).

The motivation for this type of approach, as already intimated, is that evaluations have a certain noise level that causes them to be imperfect  so that a “best evaluation” may not correspond to a “best move.” Yet the imperfection is not complete, or else there would be no need to consider evaluations at all (except perhaps from a thoroughly local standpoint, keeping in mind that the use of memory takes the evaluations beyond the “local” context). The issue then is to find a way to assign probabilities that appropriately compensates for the noise level.

A potential germ for theory is suggested by the challenge of identifying an ideal assignment of probabilities for an assumed level of noise. Alternative assumptions about noise levels may then lead to predictions about expected numbers of evaluations (and moves) required to find an optimal solution under various response scenarios (e.g., as a basis for suggesting how long a method should be allowed to run).

7.2 Tabu Thresholding

There is an appeal to methods like simulated annealing and threshold acceptance that make no recourse to memory, but that operate simply by imposing a monotonically declining ceiling on objective function levels or degrees of disimprovement (treated probabilistically or deterministically). The framework embodied in tabu search instead advocates a nonmonotonic form of control, keyed not only to the objective function but to other elements such as values of variables, direction of search, and levels of feasibility and infeasibility. This creates a more flexible search behavior.

The question arises whether the nonmonotonic controls by themselves offer a sufficiently rich source of search trajectories to be relied upon as a primary guidance mechanism, with greatly reduced reliance on form of memory customarily used in tabu search.

Tabu thresholding was proposed to provide an easily implemented method of this type, which joins prescriptions of strategic oscillation with candidate list strategies. The candidate list and tabu search philosophies are mutually reinforcing, and the computational advantages contributed by these elements motivate a closer look at combining them. The result yields a method with a useful potential for variation and an ability to take advantage of special structure, yet which avoids some of the challenge of dealing with memory.

Tabu thresholding methods specifically embody the principle of aggressively exploring the search space in a nonmonotonic way. The motivation for using a nonmonotonic search strategy, in contrast to relying on a unidirectionally modified temperature parameter as in simulated annealing, derives from the following observation (Glover, 1986):

... the human fashion of converging upon a target is to proceed not so much by continuity as by thresholds. Upon reaching a destination that provides a potential “home base” (local optimum), a human maintains a certain threshold not a progressively vanishing probability for wandering in the vicinity of that base. Consequently, a higher chance is maintained of intersecting a path that leads in a new improving direction.

Moreover, if time passes and no improvement is encountered, the human threshold for wandering is likely to be increased, the reverse of what happens to the probability of accepting a nonimproving move in simulated annealing over time. On the chance that humans may be better equipped for dealing with combinatorial complexity than particles wandering about in a material, it may be worth investigating whether an “adaptive threshold” strategy would prove a useful alternative to the strategy of simulated annealing.

Nonmonotonic guidance effects can be accomplished either deterministically or probabilistically, and in the following development we specifically invoke elements of probabilistic tabu search. That is, we use controlled randomization to fulfill certain functions otherwise provided by memory, assigning probabilities to reflect evaluations of attractiveness, dominantly weighted over near best intervals, and exerting additional control by judiciously selecting the subsets of moves from which these intervals are drawn. These linked processes create an implicit tabu threshold effect that emulates the interplay of tabu restrictions and aspiration criteria in TS procedures that are designed instead to rely more fully on memory.

In order to design a simple procedure that does not rely on memory, we start from the premise that a solution trajectory should be adaptively determined by reference to the regions it passes through. Thus, instead of obeying an externally imposed guidance criterion, such as a monotonically changing temperature, we seek to reinforce the tabu search strategy of favoring behavior that is sensitive to the current search state, accepting (or inducing) fluctuations while seeking best moves within the limitations imposed. Evidently, this must frequently exclude some subset of the most attractive moves (evaluated without reference to memory), because repeated selection of such moves otherwise may result in repeating the same solutions.

The probabilistic TS orientation suggests that choosing moves by reference to probabilities based on their evaluations (attaching high probabilities for selecting those that are near best) will cause the length of the path between duplicated solutions to grow, and this will provide the opportunity to find additional improved solutions, as with deterministic TS methods. By the same orientation, a probabilistic element can be injected into the manner of choosing move subsets in a candidate list approach, to create a reinforcing effect that leads to more varied selections.

The skeletal form of a tabu thresholding method is easy to describe, as shown in Figure 7.1. The method may be viewed as consisting of two alternating phases, an Improving Phase and a Mixed Phase. The Improving Phase allows only improving moves, and terminates with a local minimum, while the Mixed Phase accepts both non-improving and improving moves.

Fig. 7.1 Tabu thresholding procedure in overview.

Improving Phase

(a)Generate a subset S of currently available moves, and let S* be the set of improving moves in S. (If S* is empty and S does not consist of all available moves, expand S by adjoining new subsets of moves until either S* is nonempty or all moves are included in S.)

(b)If S* is nonempty, choose a probabilistic best move from S* to generate a new solution, and return to (a).

(c)If S* is empty, terminate the Improving Phase with a locally optimal solution.

Mixed Phase

(a)Select a tabu parameter t (randomly or pseudo randomly) between lower and upper bound tmin and tmax.

(b)Generate a subset S of currently available moves, and select a probabilistic best move from S to create a new solution.

(c)Continue step (b) for t iterations, or until an aspiration criterion is satisfied, and then return to the Improving Phase.

Choices of moves in the two phases are governed by employing candidate list strategies to isolate subsets of moves to be examined at each iteration, and by a probabilistic best criterion. The thresholding effect of the choice criterion is further influenced by a tabu timing parameter t which determines the number of iterations of the Mixed Phase, analogous to maintaining a tenure for tabu status in a more advanced system. Control over t is exerted by selecting lower and upper bounds, tmin and tmax, between which t is permitted to vary randomly, or according to a selected distribution. The form of the method given in Figure 7.1 assumes that a initial solution is constructed by an unspecified procedure and the best solution found is retained throughout the process.

Termination of the foregoing procedure occurs after a selected total number of iterations. The set S in these phases may consist of all available moves in the case of small problems, or where the moves can be generated and evaluated with low computational expense. In general, however, S will be selected by a candidate list strategy to assure that relevant subsets of moves are examined. Randomization is used to change the order in which the subsets are scanned.

The Mixed Phase may be expressed in a format that is more nearly symmetric to that of the Improving Phase, by identifying a subset S* of S that consists of moves satisfying a specified level of quality. However, the determination of S* can be implicit in the rules of the candidate list strategy for selecting S, and further can be controlled by the probabilistic best criterion, which itself is biased to favor choices from an elite subset of moves. We introduce S* as distinct from S in the Improving Phase to emphasize the special role of improving moves in that phase.

As noted, this overview procedure is a direct embodiment of the strategic oscillation approach, keying on the movement of the objective function rather than that of other functional forms that combine cost and feasibility, or distances from boundaries or stages of construction. In spite of this narrowed focus, it is apparent that a significant range of strategic possibilities present themselves, drawing on standard ideas from the tabu search framework. For example, we observe that the method offers immediate strategic variability by permitting the Improving Phase to terminate at various levels other than local optimality, passing directly to the Mixed Phase at each such point. In this instance, the Improving Phase need not rigidly adhere to a policy of expanding S to include all moves, when no improving moves can be found. At an extreme, by suitably controlling nonimproving moves, the method can operate entirely in the Mixed Phase, or alternately, the Improving Phase can be given a more dominant role and the Mixed Phase can be replaced by a Nonimproving Phase.

Temporarily disregarding these supplementary considerations, the simple tabu thresholding approach outlined in Figure 7.1 is governed by three critical features: determining the subset S of the candidate moves to be considered, defining the probabilistic best criterion for choosing among them, and selecting the bounds tmin and tmax that affect the duration of the Mixed Phase.

7.2.1 Candidate Lists and Scanning

Studies of linear and continuous optimization problems sometimes contain useful implications for solving nonlinear and discrete optimization problems. An instance of this is an investigation of linear network optimization approaches for selecting pivot moves in basis exchange algorithms (Glover, et al. 1974). Two findings emerged that are relevant for our present purposes: first, a best evaluation rule, which always selects a move with the highest evaluation, produced the fewest total pivot steps (from a wide range of procedures examined); and second, a straightforward candidate list strategy proved notably superior in overall efficiency for problems of practical size (in spite of requiring more iterations). The first finding was consistent with outcomes of related studies. The second finding, however, was contrary to the accepted folklore of the time.