Tabu Search Parameterization and Implementation in a Constraint Programming Library

摘要

Tabu Search is a metaheuristic that guides a local heuristic search procedure. The goal is to efficiently explore the search space of a problem by using memory structures to prevent the search from being stuck in local optima. In this paper, we give an overview of a C# based, multithreaded, tabu search implementation within a Constraint Solving Engine. The engine is designed for modeling and solving problems that can be defined as Constraint Satisfaction Problems. Here we elaborate some Tabu Search adaptation issues and some experimental results obtained via parameterization of tabu tenure, number of iterations, and number of threads. The problem used to evaluate the implementation was the Traveling Salesman Problem.