Tabu Search

In the tabu search category of meta-heuristics, the essential idea is to 'forbid' search moves to points already visited in the (usually discrete) search space, at least for the upcoming few steps. That is, one can temporarily accept new inferior solutions, in order to avoid paths already investigated. This approach can lead to exploring new regions of , with the goal of finding a solution by "globalized" search. Tabu search has traditionally been applied to combinatorial optimization (e.g., scheduling, routing, traveling salesman) problems. The technique can be made, at least in principle, directly applicable to continuous global optimization problems by a discrete approximation (encoding) of the problem, but other extensions are also possible (Glover and Laguna 1993, Osman and Kelly 1996, Voss et al. 1999).

REFERENCES:

Glover, F. and Laguna, M. Tabu Search. Dordrecht, Netherlands: Kluwer, 1996.

Glover, F.; Taillard, E.; and De Werra, D. "A User's Guide to Tabu Search." Ann. Oper. Res. 41, 3-28, 1993.

Osman, I. H. and Kelly, J. P. (Eds.). Meta-Heuristics: Theory and Applications. Dordrecht, Netherlands: Kluwer, 1996.

Piwakowski, K. "Applying Tabu Search to Determine New Ramsey Numbers." Electronic J. Combinatorics 3, No. 1, R6, 1-4, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r6.html.

Voss, S.; Martello, S.; Osman, I. H.; and Roucairol, C. (Eds.). Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Dordrecht, Netherlands: Kluwer, 1999.