Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabu Search I 19
earlier value without visiting values that were successively generated at intermediate points (e.g., going from 5 to 10 to 15 and then back to 5, jumping over the reverse move from 15 to 10).

Cycle avoidance can easily be achieved over the duration of tabu tenure, however, by focusing specifically on from-attributes and to-attributes rather than on their ordered pair combinations. More precisely, as long as at least one to-attribute of a current move is not afrom- attribute of a previous move, cycling cannot occur. Examination of the preceding restrictions shows that all except (R5) and (R7) implicitly are based on the requirement that specified from- attributes of previous moves must not be to-attributes of the current move, or else the move is tabu. (The only component attributes of the present move that are relevant to its tabu classification are its to-attributes, which to prevent reversals must be from-attributes of previous moves.)

It should be pointed out, however, that cycle avoidance is not an ultimate goal of the search process. In some instances, a good search path will result in revisiting a solution encountered before. The broader objective is to continue to stimulate the discovery of new high quality solutions. Hence in the longer term the issue of cycle avoidance is more subtle than simply preventing a solution from being revisited. The way that tabu restrictions depend on different choices of move attributes, and the consequences of this dependency, are examined in the following example.
An Example. Consider a past move that involves a change from Xj = P to Xj = q. To avoid a reversal. we stipulate that the from-attribute of this move. Xj = p, is tabu-active. thus allowing the possibility of preventing a move with a change in which Xj = P is the to-attribute. But Xj = P is not the only component of the past move that can qualify as a from-attribute, and hence that can be the basis for defining a tabu-active status.

By conceiving an attribute change implicitly to involve replacing an attribute e by a complementary attribute e. the change from Xj = P to Xj = q in fact may be viewed as composed of two such attribute changes: from Xj =p to Xj ~p, and from Xj ~ q to Xj = q. Thus. Xj ~ q also can be regarded as afrom-attribute of this change. By avoiding either of the tabu-active reverse attributes. to Xj = P or to Xj ~ q, the present move will not be able to revisit the solution that initiated the past move. (Note that avoiding Xj ~ q is the same as compelling Xj = q, which is more restrictive than avoiding Xj = p.)

The problem illustrated at the start of this chapter gives an instructive example of options created by identifying tabu attributes in this way. The swap moves of the illustration consist of selecting two items. j and k, where item j occupies position p and item k occupies position q, and then exchanging their positions. Let Xu = v denote the statement "item u is assigned to position v." Hence the the swap move for interchanging the positions of items j and k can be represented as consisting of the two operations "from Xj =p to Xj = q" and "from Xk = q to Xk =p." Subdividing these operations into their components. we can express the outcome as consisting of the following changes:
20 I GLOVER and LAGUNA
from Xj =p toXj ~ p from Xj ~ q to Xj = q from Xk = q to Xk ~ q from Xk ~ P to Xk =p,
Thus, any combination of the preceding from-attributes can be selected to represent corresponding to-attributes of a move currently under consideration, for the purpose of defIning a tabu restriction applicable to this move. We may elect, for instance, to rely on just the first and third of the preceding from-attributes, using the tabu restriction that classifies a move tabu only if it contains both Xj = P and xl = q as to-attributes. (Hence this prevents the current move if it transfers item j to position p and item k to position q, where items j and k were respectively moved out of these two positions in the past, though not necessarily on the same move.) This is a weaker restriction than one based on either the second or fourth from-attribute above, rendering a move tabu if it contains Xj :to q or xl :to p as a to-attribute, hence essentially compelling the current move to result in Xj = q or xl = P (or at least one or both, depending on the restriction chosen). One implication of choosing stronger or weaker tabu restrictions is to render smaller or larger tabu tenures appropriate.
Effect of Variable Codings. Different codings of variables also lead to different consequences for creating tabu restrictions. For example, if Xu = v instead is given the interpretation "item u immediately precedes item v," then the swap of items j and k yields an altered set of attributes with different associated possibilities. Denoting the two items that immediately precede and immediately follow j by p and q, and the two items that immediately precede and immediately follow k by rand s, we see that the swap creates the following changes:
fromx.=qtox.=s

:I :I

from Xk = S toxk = q from Xp = j to xp = k from x, = k to x, = j.
Moreover, each of these subdivides into two additional components (for example, the first becomes "from Xj = q to Xj * q" and "from Xj * S to Xj = sIt), yielding a set of options for defIning tabu restrictions that is considerably expanded over those of the preceding coding of the

variables. Representationally, there may be multiple options for characterizing the same set of attributes, and it is appropriate to use one that is natural for the problem setting. In this case, for example, it is convenient to represent the condition "item u immediately precedes item v" as an arc (u, v) from node u to node v in a directed graph, and by this convention the statement "from