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 its nolonger tabu to reconsider (Ref-3).My questions are, How does Tabu Search cure the problem of getting stuck in a localoptimum? Does it increase the search-space?What is the need of maintaining a list (i.e. Tabu List)? Why notjust remember the optimum solution found so far?When the Tabu List is too large, the oldest candidate will beremoved. 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)
Clarification on Tabu Search
optimization;artificial intelligence;search algorithms
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.