Tabu Search

Tabu Search

Tabu search (TS) behaves like a Local Search, but it accepts non-improving solutions in order to escape from local optima when all neighbours are non-improving solutions

To avoid cycles, Tabu Search ignores neighbours that have recently been visited, through

• Memorising the recent search trajectory

A short-term memory of the recently applied moves is maintained, called the tabu list, and undoing moves which is disallowed in this list.

During each iteration, this short-term memory is updated

Storing all moves performed is time-consuming and memory-consuming, because one would have to check during each iteration whether a generated move is the inverse of a move that belongs to the list of all moves performed

The tabu list therefore usually contains a pre-specified maximum number of tabu moves

Under some conditions, called aspiration criteria, tabu moves may nevertheless be performed (such as when the move would lead to a solution that is better than the incumbent)

Worked Example

$t$	${\text{s}}^{(t)}$	$z$	$\hat{z}$	$Neigbour$	$j$	$Newz$
0	[1,0,0,0]	12	12	[0,0,0,0]	1	0	$\leftarrow$
				[1,1,0,0]	2	inf
				[1,0,1,0]	3	inf
				[1,0,0,1]	4	inf
1	[0,0,0,0]	0	12	[1,0,0,0]	1	tabu
				[0,1,0,0]	2	7
				[0,0,1,0]	3	9	$\leftarrow$
				[0,0,0,1]	4	8
2	[0,0,1,0]	9	12	[1,0,1,0]	1	tabu
				[0,1,1,0]	2	16
				[0,0,0,0]	3	tabu
				[0,0,1,1]	4	17	$\leftarrow$
3	[0,0,1,1]	17	17	[1,0,1,1]	1	inf
				[0,1,1,1]	2	24	$\leftarrow$
				[0,0,0,1]	3	tabu
				[0,0,1,0]	4	tabu
4	[0,1,1,1]	24	24	[1,1,1,1]	1	inf
				[0,0,1,1]	2	tabu
				[0,1,0,1]	3	15	$\leftarrow$
				[0,1,1,0]	4	tabu
5	[0,1,0,1]	15	24	[1,1,0,1]	1	inf
				[0,0,0,1]	2	tabu
				[0,1,1,1]	3	tabu
				[0,1,0,0]	4	7	$\leftarrow$
6	[0,1,0,0]	7	24	STOP

Short-term memory

Maintaining a list of t edges and preventing them from being selected for consideration in moves over a duration of l iterations. After the l iterations (the tabu tenure), these edges are released again.

Medium-term memory

Maintaining a list of p edges that have been present in the last k best solutions and encouraging their selection in future solutions.

Long-term memory

Maintaining a list of q edges that have appeared the least frequently during the search and encouraging their selection in future solutions.

Aspiration criterion

Accepting tabu moves that have better objective function values than the best solution encountered during the search.