Back to heuristics for global optimisation
Tabu Search is also an heuristic search procedure in its own right, with a growing number of theoretical and practical articles investigating the method.
The Tabu Search method seeks to optimise a function under certain constraints. In the case of minimisation this amounts to minimisising c(x) where x is a member of X, and c(x) is the objective or cost function and the family of solutions X may include constraints on x.
In the quest for optimality the neighbourhood N(x) of each solution x in Xis searched. Another solution x' in this neighbourhood can be reached by a move.
Tabu Search uses randomisation selectively (or not at all), instead exploiting flexible memory to control the search process. Every solution has a modified neighbourhood so that history determines which solutions may be reached by a move from the current solution. For example x' in N(x) may be classified tabu (disallowed), when selecting a potential neighbour of x, due to memory considerations. Instead choose x'' in N(H,x) as an acceptable candidate to move to from x. N(H,x) contains all neighbourhood candidates that the memory (H) will allow the algorithm to consider. Generally, in the short-term, N(H,x) a subset of N(x), but in the mid-to-long-term N(H,x) is not necessarily a subset of N(x). Instead the neighbourhood may contain a set of elite solutions previously encountered, either in a regional cluster or in different clusters, depending on what the mid-to-long-term considerations are. The type of solutions in the modified neighbourhood change over time as the search progresses from a diverse search, looking at many areas of the search space, to a more intense search, concentrating on particular `good' regions.
Tabu Search also uses memory to modify the cost function, c(x), in a similar manner to the modification of the neighbourhood structure. So use c(H,x) instead of c(x) to measure the goodness of a solution, where history, H, may encourage or penalise solutions in the determination of the `best' x' in N(H,x).
When N(H,x) is large (or costly to examine) a subset of candidates representative of N(H,x) is created, called NC(H,x), which is examined for a new solution. The basic pseudo-algorithm for Tabu Search is now described, based on an algorithm presented by Glover [1], shown in figure 2.5.
The method depends largely on the definition of memory (or history),H, the candidate subset for neighbourhood selection, NC(H,x) a subset of N(H,x), and the (modified) cost function c(H,x).
It is often via move attributes that tabu restrictions are imposed in Tabu Search, preventing the search from reversing or repeating itself. Since a move is effectively represented by its attributes we record the opposite attributes to a move just completed and classify them tabu. Any move containing the tabu attributes is not available for selection as a neighbourhood candidate (unless certain aspiration criteria are first satisfied).
A tabu restriction is activated if attributes have occurred either recentlyfor short-term considerations or frequently for mid to long-term considerations thus classifying these attributes as tabu-active. The most common tabu restrictions are designed to prevent cycling and to introduce vigour into the search (however avoidance of cycles is not in itself a goal but is often useful in search techniques).
Consider a hypothetical example in which a solution to a problem consists of random permutations of 10 numbers such as a solution to a 10 city TSP. If the previous move consisted of swapping the cities 9 and 5 then the values involved in this swapping procedure could be used as a potential move attribute (other attributes could involve the costs of the respective solutions or the values of the city indices swapped). The move attribute of swapping 5 and 9 is now classified tabu-active (in the short-term).
This means that in the near future these two cities are not allowed to be swapped since the associated move attribute is on the tabu list. (The algorithm memory can be implemented in a number of ways, the simplest in a problem type such as this is as an n by n matrix, where $n$ is the number of cities, and each matrix element indicates how long (numbers of iterations) a particular swap is classified tabu.) However, the tabu status of a move attribute can be overridden in certain circumstances. If the aspiration criteria are met then the move can proceed as if it were not tabu.
On certain occasions in Tabu Search, active tabu restrictions can be overridden. Conditions that must be met before this can occur are called the aspiration criteria. For example a standard implementation is to override a tabu restriction if the potential move yields a solution better than the best solution found so far. Other aspiration criteria can also be considered. Aspiration by default is needed when all neighbourhood candidates are classified tabu, then the algorithm is forced to select the move that violates the tabu restrictions the least. Aspiration by region overrides the tabu restrictions when the potential move yields a better solution than previously found in a given region.
Two complementary ideas in Tabu Search memory concerned with short-term and mid-to-long-term memory are recency based memory and frequency based memory respectively.
Whereas recency based memory is invoked by means of a tabu list, frequency based memory is typically implemented by either penalising or giving incentives to certain move attributes. Returning to the previous example, look at what frequency based memory can mean. Consider a situation in which the move to swap 4 and 10 has been identified a potential candidate for selection.
The algorithm frequency memory may indicate that 4 and 10 have often been swapped (in some time interval) and if this move has been made more often than other potential moves then it is penalised to make it less appealing in the selection process. Conversely, if the move has been made relatively infrequently, then it becomes more attractive for selection. This holds true as long as diversification is most important, trying to push the search into unexplored areas, if intensification is being emphasised, then frequency based memory may indicate that swapping 4 and 10 is a common property leading to other good solutions.
It becomes apparent the the exact role of memory in Tabu Search depends on the stage the algorithm is at and whether diversification or intensification is more important. Intensification is designed to create better solutions by encouraging the inclusion of `good' attributes. Short-term this means incorporating attributes with the highest evaluations. Long-term this means incorporating attributes of solutions from elite subsets forcing the search into `good' subregions. To achieve this via frequency based memory, S can be considered to be a small subset of elite solutions (high quality local optima). These solutions share common attributes and are able to reach each other in a small number of moves (not to be confused with a concept of distance in the search space).
Opposed to the goal of intensification, diversification is needed to generate solutions that contain attributes different from those already encountered in the search so far. Using frequency based memory to achieve this goal, S is defined to be some significant subset of all solutions thus-far encountered. For example S can be selected to be a subsequence of all local optima that do not necessarily share common properties guiding the algorithm to different `good' areas in the search space. A penalty/incentive function can then be created which, when used in combination with c(H,x), can penalise or encourage a particular search strategy depending on whether at this stage of the search intensification or diversification is more desirable.
This page is under development. Last updated 17 January 1995
Grant Telfar
grant@isor.vuw.ac.nz