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,
How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?
What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?
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.