An Empirical Analysis of Tabu Lists

Metaheuristics, such as tabu search, simulated annealing, and ant colony optimization, have demonstrated remarkable success in solving combinatorial optimization problems across diverse domains. Despite their efficacy, the lack of understanding of why these metaheuristics work well has sparked criticism, emphasizing the need for a deeper exploration of their components. This paper focuses on the tabu list component within tabu search, aiming to unravel its relative importance in influencing overall algorithmic performance. We employ a white-box framework to investigate various methods for handling the tabu list, including short-term and long-term strategies. We conduct experiments to compare the performance of different tabu list strategies using a well-known benchmark problem, the Permutation Flow Shop Scheduling Problem. The results show that the tabu list component does not significantly differ from the final result. Nevertheless, the strategies exhibit diverse search trajectories related to distinct prohibition structures.