**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Tabu search

Summary

Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989.
Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.
Tabu search enhances the performance of local search by relaxing its basic rule. First, at each step worsening moves can be accepted if no improving move is available (like when the search is stuck at a strict local minimum). In addition, prohibitions (hence the term tabu) are introduced to discourage the search from coming back to previously-visited solutions.
The implementation of tabu search uses memory structures that describe the visited solutions or user-provided sets of rules. If a potential solution has been previously visited within a certain short-term period or if it has violated a rule, it is marked as "tabu" (forbidden) so that the algorithm does not consider that possibility repeatedly.
The word tabu comes from the Tongan word to indicate things that cannot be touched because they are sacred.
Tabu search is a metaheuristic algorithm that can be used for solving combinatorial optimization problems (problems where an optimal ordering and selection of options is desired).
Current applications of TS span the areas of resource planning, telecommunications, VLSI design, financial analysis, scheduling, space planning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management, mineral exploration, biomedical analysis, environmental conservation and scores of others.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (14)

Related people (46)

Related concepts (18)

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored.

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete (for example the traveling salesman problem, the boolean satisfiability problem, protein structure prediction, and job-shop scheduling).

Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit.

Related courses (4)

Related lectures (30)

CS-330: Artificial intelligence

Introduction aux techniques de l'Intelligence Artificielle, complémentée par des exercices de programmation qui montrent les algorithmes et des exemples de leur application à des problèmes pratiques.

CS-627: Algorithmic Toolbox

This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as t

ENG-466: Distributed intelligent systems

The goal of this course is to provide methods and tools for modeling distributed intelligent systems as well as designing and optimizing coordination strategies. The course is a well-balanced mixture

Optimization and Simulation: Heuristics Intensification

Explores optimization and simulation techniques, emphasizing heuristics intensification for efficient solution finding.

Constraint Satisfaction: Formulation and Algorithms

Covers the formulation of constraint satisfaction problems and systematic algorithms for solving them efficiently.

Optimization Techniques: Local Search, VNS, Simulated Annealing

Explores optimization techniques like local search, VNS, and simulated annealing.

Nicolas Zufferey, Patrick Amstutz, Philippe Giaccari

A goal of this paper is to efficiently adapt the best ingredients of the graph colouring techniques to an NP-hard satellite range scheduling problem, called MuRRSP. We propose two new heuristics for t

2008Due to the increasing number of radio technologies, the available frequency spectrum becomes more and more utilized, hence its clever use becomes a critical issue. Among many proposed solutions, the f

2006Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of

2008