What are the advantages and disadvantages of using aspiration criteria in tabu search?

1 Aspiration criteria

Sometimes, a move that is forbidden by the tabu list may actually lead to a better solution than the current one. This is especially likely when the tabu list is too long or the problem is highly constrained. To overcome this limitation, tabu search can use aspiration criteria, which are rules that allow a tabu move to be accepted if it satisfies some condition. For example, a common aspiration criterion is to accept a tabu move if it improves the best solution found so far.

2 Advantages of aspiration criteria

Using aspiration criteria can have several advantages for tabu search. First, they can help to diversify the search and explore new regions of the solution space, by breaking the tabu restrictions when they are too rigid or counterproductive. Second, they can help to intensify the search and exploit promising solutions, by allowing the tabu search to follow an improving path when it finds one. Third, they can help to reduce the computational cost and complexity of tabu search, by avoiding unnecessary moves and iterations that do not improve the solution quality.

3 Disadvantages of aspiration criteria

Using aspiration criteria can also have some disadvantages for tabu search. First, they can introduce some randomness and uncertainty in the search process, by making the tabu list less effective and predictable. This can affect the convergence and stability of tabu search, especially if the aspiration criteria are too weak or too frequent. Second, they can create some conflicts and trade-offs with the tabu list, by making the tabu search choose between following a tabu move or a non-tabu move. This can affect the balance and efficiency of tabu search, especially if the aspiration criteria are too strong or too rare. Third, they can increase the design and implementation difficulty of tabu search, by requiring additional parameters and rules to define and apply the aspiration criteria.

5 How to choose aspiration criteria

Choosing the right aspiration criteria for tabu search is not a trivial task. It depends on several factors, such as the problem characteristics, the solution representation, the neighborhood structure, the tabu list length, and the search strategy. There is no universal or optimal aspiration criterion that works for all problems and situations. Therefore, it is important to experiment and compare different aspiration criteria and evaluate their impact on the performance and behavior of tabu search.

6 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?