Clarification on Tabu Search
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.