On the Value of Aspiration Criteria in Tabu Search

Tabu search is a greatly successful metaheuristics, as illustrated through numerous publications showing its use for a range of difficult optimization problems. The tabu search literature is to a certain degree characterized by papers introducing new variations of the search, either presenting new components or proposing changes to existing components. Most often, these new variations are shown to perform well on a particular optimization problem, but are rarely thoroughly analyzed in terms of how they change the search characteristics. This work focuses on the aspiration criterion: A large number of possible variations of aspiration criteria exist, many different variations have been used successfully, and almost no results exist that directly compare the different variations in terms of their performance or behavior. Eight different aspiration criteria are considered, and computational experiments are performed to assess their merit within tabu search implementations for two different combinatorial optimization problems.