Download A user's guide to tabu search

6
F. Glover et al., A user's guide to tabu search
To circumvent such an outcome, a guidance procedure must be able to accept
a move from s to s' (in V*) even iff(s') >f(s). But when a solution s" worse than
s may be accepted, cycling may occur, causing the process again to be trapped by
returning repeatedly to the same solution (perhaps after some interval of intermediate
solutions). Simulated annealing attempts to provide guidance by accepting a
disimproving s' (if it happens to be the one currently sampled) with a certain
probability that depends uponf(s), f(s') and a parameter identified with temperature.
The tabu search approach, by contrast, seeks to counter the danger of entrapment
by incorporating a memory structure that forbids or penalizes certain moves that
would retum to a recently visited solution. The variant called probabilistic tabu
search creates probabilities for accepting moves as a monotonic function of evaluations
created by a penalty of the method.
The notion of using memory to forbid certain moves (i.e. to render them tabu)
can be formalized in general by saying that the solution neighborhood depends on
the time stream, hence on the iteration number k. That is, instead of N(s) we may
refer to a neighborhood denoted N(s, k). (More precise notation would indicate that
N(s,k) depends on solutions and neighborhoods encountered on iterations prior
to k.) For instance, suppose memory is employed that recalls solution transitions
over some time horizon, and creates N(s,k) by deleting from N(s) each solution that
was an immediate predecessor of s in one of these transitions. We may express the
form of the procedure that uses the modified (tabu) neighborhoods as follows.
(a)
(b)
Choose an initial solution s in X
s*:=s and k:= 1
While the stopping condition is not met do
k:=k+ l
Generate V* ~ N(s, k)
Choose the best s' in V*
S :=S
p
i f f ( s ' ) <f(s*), then s* := s'
end while
(2.2)
There may be several possible stopping conditions, but simplest is some logical
combination of the following:
•
•
•
•
An optimal solution is found.
N(s,k+l)=O.
k is greater than the maximum number of iterations allowed.
The number of iterations performed since s • last changed is greater than a
specified maximum number of iterations.
It is to be emphasized again that a nontrivial, strategically generated sample
of the solution neighborhood is examined at each step, and a best element from the