Tabu SearchTabu SearchTabu SearchTabu SearchTabu SearchTabu SearchTabu SearchAdvantages of Tabu SearchDisadvantages of Tabu SearchTabu Search•Tabu Search•Then the local search can be defined as an iteration in which we always move from the current point to its best neighbor, that is, to the one that offers the most improvement in the function value in the neighborhood. If no improvement is possible in the neighborhood, then the algorithm stops.Tabu Search•If we consider minimization, then local search can be visualized as sliding down on the steepest slope until we reach a local minimum.•The critical problem of greedy local search is that it may easily get stuck in a 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 principle is summarized below.Tabu Search•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 local optimum is reached. Thus, it can “climb out” from a local minimum. This would result, however, in cycling, since whenever it moves away from a local minimum, the next step could take it back if only the improvement is considered. This problem is handled by the rule that the points on the tabu list cannot be chosen as next steps. In the tabu list example mentioned above we can decrease the possibility of cycling by disallowing recently visited points.Tabu Search•The tabu list can also be more complicated than the example above. The algorithm may also maintain more than one tabu lists. For example, one list may contain the last k visited points, while another list can contain those points that are local minimums visited in the search. A third list can contain, for example, those points from which the search directly moved into a local minimum.Tabu Search•The rule that the points in the actual tabu list cannnot be visited may be too rigid in certain cases. To make it more flexible, it is usually allowed that under certain conditions a point may be removed from the tabu list. These conditions are called aspiration criteria. For example, if with respect to the current position a point on the tabu list offers an improvement larger than a certain treshold, then we may remove the point from the tabu list. Or, if all possible moves from the current position would be prohibited by the tabu list(s), then we can remove from the tabu list the point that offers the best move. In this way we can avoid getting “paralyzed” by the tabu list.Tabu Search•Stopping criterion. The search can, in principle, be continued indefinitely. A possible stopping criterion can be obtained in the following way. Let us keep (and refresh after each iteration) the best value that has been achieved so far. If during a certain number of iterations no improvement is found relative to the earlier best value, then we can stop the algorithmAdvantages of Tabu Search•Improves greedy local search by avoiding getting trapped in a local optimum too early.•Offers flexibility by the possibility of adjusting the tabu list structure and rules to the specific problem. If this is done well, good results can be achieved.Disadvantages of Tabu Search•Offers only heuristic improvement, but does not guarantee anything in a 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 no general rules that would tell how to do it, much is left to
View Full Document
Unlocking...