Tabu search

Tabu search is a metaheuristic to avoid getting stuck in local optimum during a neighborhood search.

For example, if you use the basic rule of the "first improvement" among the neighbours, there is chances you're missing potential good solutions that need to go through a temporary none-improving path.

Tabu search impose one or many rules to prohibit movements and relax the basic rule.

• Maximum iterations (stopping criteria)
• No inverse movements
• Avoid doing $x$ time the same movement
• Force movement that never occurs
• …, etc.

Problems

Here is some problems you can apply tabu search to.

• Knapsack
• Traveling Salesman