[Solved]: Clarification on Tabu Search

Problem Detail: 

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)

Asked By : Dilini

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18582

 Ask a Question

 Download Related Notes/Documents