# Clarification on Tabu Search

I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia)

I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding.

This is what I'm trying to 'digest':

• Tabu Search is an improvement over the Hill Climbing algorithm (Ref-1).

• The problem with Hill Climbing is that it does not guarantee about reaching the global optimum, because it only searches on a subset of the whole solution space. It will find the local optimum.

• To get rid of this issue, Tabu Search maintains a 'Tabu List' of previously visited states that cannot be revisited (Ref-2).
• If the tabu list is too large, the oldest candidate solution is removed and it’s no longer tabu to reconsider (Ref-3).

My questions are,

1. How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?

2. What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?

3. When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

If anyone could explain Tabu Search algorithm using an example, I'm sure these questions would be automatically answered.

References:

• (Ref-1) Hill Climbing, Wikipedia Article (link)

• (Ref-2) Russell, Stuart Jonathan, et al. Artificial intelligence: a modern approach. Vol. 74. Englewood Cliffs: Prentice hall, 1995. (WorldCat)

• (Ref-3) Luke, Sean. "Essentials of Metaheuristics.". (pdf)

How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?

First, the search method does not affect the size of the search space; it depends only on the problem and it simply contains all possible states. Tabu search (TS) does what local search methods often do: when you get stuck, you allow a non-improving move in the hopes of getting unstuck. TS, in particular, maintains a tabu list. When we do a non-improving move, the tabu list ensures we never move to a previously visited state.

What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?

As explained, the need of maintaining a list is guiding the search in an "intelligent" way. If you just remembered one state (perhaps that is the best solution found so far), you would be getting out of a local optimum in a "blind way". That is, it is possible you would simply trace your steps back, and then walk into the same local optimum again!

When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

If the global optimum is not in tabu list, then it is possible you will find it later. In short, the tabu list (as the name implies) contains all states you for some reason do not want to backtrack to.

• Thank you very much Juho, for the answer... Regarding the third point: After all the iterations, we select the best candidate out from the Tabu list,don't we? So incase we have once encountered the global optimum, but later have thrown it away, and do not encounter it again, haven't we done something bad in the first place, by throwing away the oldest entry (global optimum)? – Dilini Dec 6 '13 at 13:37
• Also, regarding the 1st point: It seems that I have misused the word "search space" in my question. If I adopt your definition to search space, what I meant was that Hill Climbing uses a subset of the search space. Please have a look at this image which shows what I mean: tinypic.com/r/dcqydk/5 What I would like to know is how Tabu Search selects a subset from the whole search space; What is the difference? Is it a contiguous chunk too? – Dilini Dec 6 '13 at 14:00
• @bird234 I think usually, we simply remember the best solution seen so far, and when the search ends, we simply return that. That is to say, the tabu list only guides the search so that it would find better and better solutions. For the image: seems like we are dealing with a minimization problem, where $A$ is a local optimum. Hill climbing gets stuck in there, while $B$ would be the global optimum. TS might find $A$ as well, but because of the tabu list, it tries to get out of it in an intelligent way in the hopes of finding better solutions. Does that make sense? – Juho Dec 6 '13 at 14:59
• Thanks a lot Juho, for the clarifications. Yes, now it makes sense. – Dilini Dec 6 '13 at 16:35