Generic Tabu Search

Abstract

The Multiple Sequence Alignment problem is considered to be an NP-Hard problem, requiring initially a specific encoding schema and design, as for any other of its siblings, to implement and run any of the main categories of heuristic. This paper intends to discuss our proposed generic implementation of the Tabu Search algorithm, a heuristic procedure proposed by Fred Glover to solve discrete combinatorial optimization problems. In this research, we try to coordinate and synchronize different designs/implementations discussed in many literatures, with some of the references mentioned in this paper. The basic idea is to avoid that the search for best solutions stops when a local optimum is found, by maintaining a list of non-acceptable or forbidden (taboo) solutions/costs, called Tabu list or Short-Term Memory (STM). In our algorithm, we attempt to add some executions tracing functionalities in order to help later analysis for initial parameters tuning. On the other hand, we propose to include the concept of a list called Long-Term Memory (LTM), so that some of the best solutions found so far can be saved, for search diversification.