No subject

[Eric B. Baum]

    I've been holding off replying re tabu because I'm no
expert, but it appears that among connectionists few are, so here
goes. Tabu search was invented by Fred Glover, Center for Applied
Artificial Intelligence, Graduate School of Business, University of
Colorado, Boulder. A thumbnail sketch of the idea (as I recollect
it) is the following:

      We have a set of local search moves. So,
if we're solving TSP, we might use the set of one link interchanges.
At each step, we use the move in our set which produces the most optimum
solution (e.g. shortest tour) with one proviso. We are not allowed
to use a move which inverts one of our last x moves, where
x is a small, heuristically chosen, fixed integer (e.g. 7). 
(i.e. each time we do a move , we remove the first element from a 
TABU set and insert the inverse of the current move as the x-th 
element in the TABU set). Note that, if we're near a local
minimum for our search set, this procedure may force us to make a 
move which increases the tour length, since we must make
some move at each step. We keep in storage the best solution
yet found. We proceed till either a fixed number of
iterations have been performed, or a fixed number have occured since
last improvement in best value, halt and report the best value found.

    The general idea is that the TABU set prevents cycling, and otherwise one
tries to take a naive most direct path over hills. This not only seems
sensible, but is claimed to be extremely effective in many tests. 
One reference I have is:

Glover F. "Tabu Search Methods in Artificial Intelligence and Operations 
Research" ORSA Artificial Intelligence Newsletter V1 No 2. 6 1987.

Hopefully, somebody at Boulder reading this can encourage Prof Glover to
post a more recent bibliography, since all I know about the subject comes
from a talk I heard three years ago, and doubtless there have been improvements
in the art.
--
                                  Eric Baum
                                  NEC Research Institute
                                  4 Independence Way
                                  Princeton NJ 08540

Inet:   eric at research.nj.nec.com
UUCP:   princeton!nec!eric  
MAIL:   4 Independence Way, Princeton NJ 08540
PHONE:  (609) 951-2712
FAX:    (609) 951-2482