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.