Cycling is repetitive search behavior: an algorithm keeps performing the same moves or revisiting the same solutions instead of reaching new regions. In tabu search, cycling wastes iterations, narrows exploration, and can block optimal or near-optimal solutions. section 6.2.1 section 6.2.3
Tabu search counters cycling with memory. Recency-based memory records recently used moves in a tabu list and temporarily prohibits them through a tabu tenure. Frequency-based memory counts how often moves occur and penalizes frequently repeated swaps. Together, these mechanisms discourage reversal and repetition while guiding the search between promising regions and less-explored areas. section 6.2.1 section 6.2.1
A four-city routing search
For a four-city traveling-salesperson problem, a tabu structure can store both the remaining prohibition time for each swap and the number of times each move has been used. A move marked tabu cannot be selected during the current iteration, reducing repeated tours and reversals while frequency counts steer the search toward less-used swaps. section 6.2.1
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.
Inspect the four-city TSP tabu structure to compare recency durations with long-term move frequencies. section 6.2.1
Tabu tenure requires tuning. A tenure that is too short permits frequent cycling because restrictions expire quickly; one that is too long can cause stagnation, enlarge memory demands, and block promising regions. Adaptive control can vary tenure between lower and upper bounds, intensifying search near promising improvements and promoting diversification when progress is weak or a local optimum appears. section 6.2.3 section 6.2.3
Figure 6.7 Dynamically controlling the tabu tenure
Use the dynamic-tenure illustration to see how tabu restrictions can respond to search progress. section 6.2.3
