Tabu tenure is the number of iterations a move or solution stays restricted after entering a tabu list. In tabu search, this short-term memory discourages an immediate return to a recent choice, helping local search explore other neighbors rather than repeat the same moves. Tenure controls how long that restriction lasts; it does not permanently rule out the move. section 6.2.1 section 6.7
Three iterations in a small route
Suppose a four-city traveling-salesman search generates a route by swapping cities 1 and 4. With tenure set to 3, that swap is tabu-active for the next three iterations. Each iteration reduces its remaining count by one; when the count reaches zero, the swap leaves the tabu list. The same three-iteration rule can restrict a recently selected queen swap in a seven-queens search or a feasible task swap in assembly-line balancing. section 6.2.1 section 6.3 section 6.6
Figure 6.5 Tabu structure for the 4-city TSP. The numbers in recency-based memory represent the number of iterations remaining for tabu-active moves; the numbers in long-term memory represent the frequency count of using the move.
The four-city tabu structure shows remaining iterations for restricted swaps alongside a separate count of how often each swap has been used. section 6.2.1
Choose and maintain tenure as a search parameter:
- For a static setting, hold tenure constant. Suggested starting guidelines include √N or N/10 iterations for problem size N, but a fixed value does not always prevent cycling. section 6.2.1
- For a dynamic setting, vary tenure within a range that can respond to search progress. Tenure can also be pretuned or adjusted during a run as part of broader parameter tuning. section 6.2.1 section 6.2.3
- As iterations advance, reduce remaining restrictions and remove expired moves. Keep this recency rule distinct from frequency-based memory, which counts repeated moves and can penalize frequently visited choices. section 6.2.1
Tune against two failures. Too short a tenure permits cycling and can cut short exploration of alternatives. Too long a tenure can cause stagnation as restrictions accumulate. Aspiration criteria offer an exception: a tabu-active move may still be selected when the restriction is relaxed. In a hand-worked seven-queens search, an improving swap is selected through aspiration with one iteration left on its restriction. section 6.2.3 section 6.3 section 6.7
In Python, `optalgotools.algorithms.TabuSearch` accepts `tabu_tenure` alongside iteration count, neighborhood size, aspiration settings, and optional long-term memory. A continuous-function example sets `tabu_tenure=5`; an assembly-line benchmark sets it to 4. Compare settings on the problem at hand rather than treating either value as universal: solution quality also depends on the neighborhood and other search parameters, and a global optimum is not guaranteed. section 6.4 section 6.6 section 6.2.3
