Free cookie consent management tool by TermsFeed Policy Generator
wiki:TS

Tabu Search

Tabu Search (TS) was invented by Fred Glover (Glover 1986). The underlying strategy of TS can be described as a best-improvement local search, and it is extended with a short term memory to escape local minima and to avoid cycling. This short term memory is called the tabu list. Its size, also called tenure is an important parameter that determines the success of the algorithm. In the selection phase of each iteration, where the TS chooses a new current solution, the tabu list is compared to a set of neighboring solutions and those that match the tabu conditions are ruled out. This reduced neighborhood set is called allowed set. The algorithm then accepts the best solution from the allowed set as the new current solution, which is in turn added to the tabu list.

Algorithm Parameters:

Parameter Description
Analyzer The operator used to analyze each generation.
MaximumIterations The maximum number of iterations which should be processed.
MoveEvaluator The operator used to evaluate a move.
MoveGenerator The operator used to generate moves to the neighborhood of the current solution.
MoveMaker The operator used to perform a move.
SampleSize The neighborhood size for stochastic sampling move generators
Seed The random seed used to initialize the new pseudo random number generator.
SetSeedRandomly True if the random seed should be set to a random value, otherwise false.
TabuChecker The operator to check whether a move is tabu or not.
TabuMaker The operator used to insert attributes of a move into the tabu list.
TabuTenure The length of the tabu list.

Is there a sample/tutorial?

Yes. HeuristicLab comes with a pre-configured TS that solves the "ch130" traveling salesman problem from the TSPLIB. Have a look at the description here.

References:

  • Glover F. 1986. Future paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. 5:533-549.
Last modified 13 years ago Last modified on 02/17/11 10:26:40