Tabu SearchLet us first consider the simplest strategy to optimize a function f (x) overa discrete domain x ∈ D, the (greedy) local search. This can be defined asfollows.Let us define a neighborhood N(x) for each x ∈ D. For example, if D isthe set of n-dimensional binary vectors, then an example of a neighborho oddefinition isN(x) = {y | y differs from x in at most 2 bits}.Then the lo cal search can be defined as an iteration in which we alwaysmove from the current point to its best neighbor, that is, to the one thatoffers the most improvement in the function value in the neighborhood. Ifno improvement is possible in the neighborhood, then the algorithm stops.If we consider minimization, then local search can be visualized as slidingdown on the steepest slope until we reach a local minimum.The critical problem of greedy local search is that it may easily get stuck ina local optimum, which can be very far from the global optimum.Tabu search offers an approach that diminishes (but does not eliminate!)the danger of getting stuck in a local optimum. The fundamental principleis summarized below.• The algorithm maintains a tabu list that contains disallowed moves.For example, a simple tabu list can contain the last k visited points,for some constant k.• The algorithm does local search, but it keeps moving even if a localoptimum is reached. Thus, it can “climb out” from a local minimum.This would result, however, in cycling, since whenever it moves awayfrom a local minimum, the next step could take it back if only theimprovement is considered. This problem is handled by the rule thatthe points on the tabu list cannot be chosen as next steps. In the tabulist example mentioned above we can decrease the possibility of cyclingby disallowing recently visited points.• The tabu list can also be more complicated than the example above.The algorithm may also maintain more than one tabu lists. For exam-ple, one list may contain the last k visited points, while another list cancontain those points that are local minimums visited in the search. Athird list can contain, for example, those points from which the searchdirectly moved into a local minimum.• The rule that the points in the actual tabu list cannnot be visitedmay be too rigid in certain cases. To make it more flexible, it is usuallyallowed that under certain conditions a point may be removed from thetabu list. These conditions are called aspiration criteria. For example,if with respect to the current position a point on the tabu list offersan improvement larger than a certain treshold, then we may removethe point from the tabu list. Or, if all possible moves from the currentposition would be prohibited by the tabu list(s), then we can removefrom the tabu list the point that offers the best move. In this way wecan avoid getting “paralyzed” by the tabu list.• Stopping criterion. The search can, in principle, be continued indefi-nitely. A possible stopping criterion can be obtained in the followingway. Let us keep (and refresh after each iteration) the best value thathas been achieved so far. If during a certain number of iterations noimprovement is found relative to the earlier best value, then we canstop the algorithm.Advantages of Tabu Search• Improves greedy local search by avoiding getting trapped in a localoptimum too early.• Offers flexibility by the possibility of adjusting the tabu list structureand rules to the specific problem. If this is done well, good results canbe achieved.Disadvantages of Tabu Search• Offers only heuristic improvement, but does not guarantee anything ina strict sense: there is no guaranteed convergence to a global optimum(as opposed to simulated annealing).• Usually requires heavy problem-specific adjustment and there are nogeneral rules that would tell how to do it, much is left to
View Full Document
Unlocking...