# 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.