tabusøk

Tabu search (tabusøk) is a metaheuristic optimization technique designed to solve combinatorial optimization problems by exploring neighboring solutions while avoiding cycles. It was introduced by Fred W. Glover in 1986. It uses memory structures to escape local optima and balance diversification and intensification.

The algorithm starts from an initial feasible solution. At each iteration it generates a neighborhood of solutions and selects the best move that is not tabu (or meets aspiration criteria). The tabu list records attributes of moves (for example swapped elements) to prevent reversing recent actions for a defined tenure. The aspiration criterion allows overriding tabu status if the move yields a solution better than the best found so far.

Key components include short-term memory (the tabu list), diversification strategies to explore new regions, and intensification strategies to hone in on promising regions. Long-term memory can support path relinking and selective search.

Applications include vehicle routing, scheduling, job shop problems, the traveling salesman problem, facility layout, and network design. Variants include adaptive tabu tenure, dynamic tabu lists, reactive tabu search, and hybrids with local search, genetic algorithms, or ant colony methods.

Strengths of tabu search include robustness against local optima and flexibility to handle different constraint types. Limitations involve sensitivity to parameter choices such as tabu tenure and aspiration rules, the risk of cycling if configured poorly, and computational overhead for large neighborhoods.