Tabu search

From Glossary

Jump to: navigation, search

This is a metaheuristic to solve global optimization problems, notably combinatorial programs, based on multi-level memory management and response exploration. It requires the concept of a neighborhood for a trial solution (perhaps partial). In its simplest form, a tabu search appears as follows:

  • Initialize. Select LaTeX: x and set Tabu List LaTeX: T = null. If LaTeX: x is feasible, set LaTeX: x^* = x and LaTeX: f^* = f(x^*); otherwise, set LaTeX: f^* = -\infty (for minimization set LaTeX: f^* = \infty).
  • Select move. Let LaTeX: S(x) = set of neighbors of LaTeX: x. If LaTeX: S(x)\setminus T is empty, go to update. Otherwise, select LaTeX: \textstyle y \in \argmax \left \{E(v): v \in S(x)\setminus T \right \}, where E is an evaluator function that measures the merit of a point (need not be the original objective function, LaTeX: f). If y is feasible and LaTeX: f(y) > f^*, set LaTeX: x^*=y and LaTeX: f^*=f(x^*). Set LaTeX: x=y (i.e., move to the new point).
  • Update. If some stopping rule holds, stop. Otherwise, update LaTeX: T (by some tabu update rule) and return to select move.

There are many variations, such as aspiration levels, that can be included in more complex specifications.

Personal tools