On the Value of Aspiration Criteria in Tabu Search

On the Value of Aspiration Criteria in Tabu Search

Lars Magnus Hvattum (Faculty of Logistics, Molde University College, Molde, Norway)
Copyright: © 2016 |Pages: 11
DOI: 10.4018/IJAMC.2016100103


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.
Article Preview

2. Aspiration Criteria

Many aspiration criteria have been proposed for TS, and the following describes those being tested in this work. The most naïve option is simply to exclude aspiration; if a move is tabu it will not be allowed, even if there could be ways of detecting that it would lead to a previously unvisited solution. This option will be labeled as NO (no aspiration). This appears to be perhaps the second most commonly used aspiration criterion, although as already noted in (Glover, 1986) other alternatives have produced solutions of better quality.

The aspiration criterion that seems to be most commonly used will be labeled as NB (new best aspiration). It was described in (Glover, 1986) and appears both simple and reasonable: the tabu status of a move can be revoked whenever the move leads to a solution that is better than any solution recorded during the search so far.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing