An aspiration criterion is an exception to a tabu-search restriction. A tabu list prevents recent moves from being reconsidered, helping the search avoid cycling. But rejecting every tabu-active move can also block a promising solution and contribute to stagnation. Aspiration lets a qualifying move through before its tabu tenure expires. section 6.2.2 section 6.7
To apply the exception during a search:
- Generate and evaluate neighboring solutions, then check which moves are tabu-active. section 6.2
- Allow a tabu-active move when it produces a solution better than the best found so far. The described criterion also considers whether few iterations remain before the move leaves the tabu list. section 6.2.2
- Choose the best admissible candidate and update the best-known solution, tabu restrictions, and aspiration criterion. section 6.2
A seven-queens swap
In a hand-worked seven-queens search, improving swaps are tabu-active. A swap is nevertheless selected under the aspiration criterion when only one iteration remains before it leaves the tabu list. This illustrates why a temporary restriction need not rule out every useful move. section 6.3
Algorithm 6.2 Tabu search
Input: an initial feasible solution
Output: optimal solution
Begin
While termination criteria not met do
Choose the best: s’∈N(s) ← N(s)-T(s)+A(s)
Memorize s’ if it improves the best known solution
s←s’
Update Tab list T(S) and Aspiration criterion A(s)
The pseudocode places aspiration alongside the neighborhood and tabu list when choosing a move, then updates the criterion after each iteration. section 6.2
For experiments, the generic Python tabu-search solver exposes use_aspiration and aspiration_limit, the latter specifying the remaining iterations before a move leaves tabu status. Examples enable aspiration while solving a continuous function and routing problems. Tune the exception alongside tabu tenure and neighborhood size: it is a way to admit promising candidates, not a guarantee of an optimal result. section 6.4 section 6.5
