Tabu search is a memory-guided local search. At each iteration it evaluates every move in the current neighborhood, then takes the best non-tabu move — even if that move is worse than the current point — instead of always climbing downhill like plain hill-climbing or gradient descent:
x(t+1) = argmin_{m in N(x(t)), m not in Tabu} f(m)
Tabu list: last K accepted moves are forbidden for K iterations
Aspiration: allow a tabu move anyway if it beats the best-ever f found
Every accepted move (a grid cell relative to the current point) is pushed onto a fixed-length tabu list; the oldest entry falls off once the list reaches the tenure length K. This short-term memory stops the search from immediately undoing its own last move and cycling between the same two points — the main failure mode of naive local search on a bumpy landscape.
- Tabu list length — how many recent moves stay forbidden. Too short and the search re-cycles; too long and it can't backtrack through a narrow valley.
- Neighborhood radius — how far the candidate moves reach from the current point each step.
- Aspiration criterion — a tabu move is allowed anyway when it would set a new global-best f(x), so the list never blocks genuine progress.
- Unlike simulated annealing (which accepts worse moves with a shrinking random probability) or a genetic algorithm (which evolves a population), tabu search deterministically always takes the single best legal move — its intelligence is entirely in what it remembers, not in randomness.
The top map is a straight-down contour view of the same benchmark surface the 3D version renders in relief — color still encodes height (teal = low, warm = high), but you now read it like a topographic map. Drag to pan, scroll/pinch to zoom in on a valley the search is exploring. The strip chart below tracks f(current) and f(best) every iteration, so you can see convergence (or stalling) as a curve, not just a moving dot.
Real-world relevance: tabu search is a workhorse for combinatorial and scheduling problems — job-shop scheduling, vehicle routing, VLSI circuit placement — anywhere a smooth gradient doesn't exist and a search needs to escape plateaus and local optima using memory rather than luck.