Tabu Search, Live

Eight posts in, every escape from a trap in this series has been some flavour of randomness:

• simulated annealing gambles: while it's hot it accepts bad moves at random and hopes for betterment
• the ant colony wanders its way out
• the genetic algorithm and its program-breeding cousin mutate their way out
• the swarm jitters
• CMA-ES and differential evolution sample their way out of trouble
• even variable neighbourhood search, the most systematic escape artist so far, opens every escape with a random shake

Tabu search is the odd one out, escaping traps by remembering them: it keeps a short list of places it has just been and refuses to go back, even when going back looks like the best move on the board.

Fred Glover sketched the idea in 1986^[1] and built it out properly in 1989^[2]. The core of it is simple: run a greedy search, but make the recent past forbidden. That one addition turns the dumbest search strategy going into something that can walk out of a local optimum, cross a plateau, and keep improving. It needs no temperature and no coin to flip, which makes it something of an oddity in this series.

Greed with amnesia

Steepest descent is the greediest search there is: look at every neighbour of your current solution, take the best one, repeat. It's fast, it's simple, and it's doomed: sooner or later it reaches a solution where no neighbour is better, and there it sits. That was covered that failure in the annealing post, where the cure was randomness on a cooling schedule.

Allow sideways moves (neighbours that are no worse, a common tweak for crossing flat regions) and the search steps from board A to board B, surveys the neighbourhood, and concludes that the best move from B is... back to A.

So it goes back, and then the best move from A is back to B. It will do this until all the coal mines and oil refineries run dry.

This is cycling, the signature failure of memoryless search, where every step the algorithm wakes up fresh with no idea it has been here before. Whether three times or over nine thousand times.

A ban list and a countdown

In tabu search, after each move, an attribute of the position you just left (in our demo, the square a queen just vacated) goes on a ban list for a handful of iterations, called its tenure.

While it's on the list, the search may not move a queen back there, however tempting the move looks, and with the recent past fenced off the only direction available is somewhere new. So the ban list turns "best move" into "best move I haven't just made", a small change that punches through plateaus which hold a hill climber forever.

There is one safety valve: if a banned move would produce the best solution ever seen, the ban is waived. This is the aspiration criterion, and it exists because tabu attributes are deliberately crude: banning a square bans every future board that would use it, including, occasionally, a record-breaking one. When the forbidden move beats anything in the run so far, take it.

Glover's tug-of-war

Glover framed the wider method as a balance between intensification (search hard near the good solutions you already have) and diversification (force yourself into regions you have never visited). Serious implementations layer on frequency memory (penalise moves you make too often), long-term restarts, and cleverer aspiration rules. It all grows from the same seed: the search takes notes on itself, and then obeys them. The demo here is a simple version.

Eight queens, no peace

The playground this time is the N-Queens problem: place N queens on an N×N chessboard so that none attacks another, meaning no two share a row, column, or diagonal. Our queens start one per column, so columns are handled for free, and a move relocates one queen within her own column. The score is the number of attacking pairs, and zero means solved.

It's a lovely testbed for tabu search because the landscape is nothing but plateaus. Near the end you are almost always sitting at one or two conflicts, surrounded by equally mediocre neighbours. That's the terrain where greedy search paces in circles, like me trying to find my car in the multistory car park outside my work (I have the memory of a pigeon with some things).

Below, a tabu search is solving the board live, and red lines join queens that currently attack each other.

The frost is the memory: when a queen leaves a square that square ices over, and the frost fades as its tenure counts down, so you're watching the algorithm's short-term memory dissolve in real time. The readout underneath lists the banned squares with their countdowns. When the search overrides a ban because the move would break a record, an "aspiration!" badge lights up next to the toolbar.

Tenure, at zero and at twenty

Switch the memory off. The search becomes plain steepest descent with sideways moves, and on a lucky board it solves anyway. Most of the time it drops to one or two conflicts and then starts pacing, and the "revisited states" counter begins to climb as it bounces between the same handful of boards, forever, at whatever speed you set. The chart flatlines with a tiny shimmer, which is the cycle itself.

Flip the memory back on and the search usually punches out within a few dozen steps. One counter, and it makes the case for tabu search better than I can.

Set tenure to 0. A ban that expires instantly is not a ban, so this is hill climbing again, cycle and all, even with the memory checkbox ticked. Tenure is the memory. The checkbox just decides whether anyone writes to it.

Set tenure to 20. Now the search forbids so much of its own neighbourhood that it can barely exploit anything. It reaches a promising region, is immediately banned from refining it, and lurches away, sometimes abandoning a one-conflict board it could have finished in a step or two.

Grow the board. Bigger boards mean bigger neighbourhoods and longer plateaus, and the sweet-spot tenure grows with them. Around 7 suits the 8×8 board, and at 16×16 you'll want noticeably more. The literature's rule of thumb is that tenure should scale with problem size.

Remembering the good and remembering the bad

There's some interesting debates I have in my mind about this concept, because it's somewhat philosophical. Our human memories are odd, we often think of periods of time that are difficult and we dislike fondly later in life, like times in the military - we remember the fun moments and forget the 5am wake up time, endless PT and drills. But we also remember specific jarring, horrible moments with great clarity - PTSD is exactly a big warning marker left with the intent to protect us, and let us remember what was bad.

Maybe there's something to take from this: it's actually efficient to remember the bad things, but at some point to let them go, and perhaps similar can be said about remembering the good things, when trying to move towards a better future.

References

1. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533–549. https://doi.org/10.1016/0305-0548(86)90048-1
2. Glover, F. (1989). Tabu Search - Part I. ORSA Journal on Computing, 1(3), 190–206. https://doi.org/10.1287/ijoc.1.3.190