Robust Taboo Search

Introduction

This algorithm was first described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455. It is among the most cited algorithms to solve instances of the quadratic assignment problem (QAP).

There are two main differences to a "standard" tabu search:

1. The tenure of tabu elements is a random variable instead of a static value.
2. The algorithm features a long-term diversification method which favors moves that have not been performed in a long time. If a move would assign to facilities to locations that both have not been assigned to for a long number of iterations then the move is performed regardless of quality. If there are multiple of these moves in one iteration the best one is performed.

The introduction of randomness in the tabu search makes the search more robust in that it can escape cycling (also see the [ReactiveTabuSearch Reactive Tabu Search]). Cycling is the behavior when the tabu search returns to the same solution over and over. The length of such a cycle is greater than the tabu tenure since during the tenure moves are prohibited.

The long-term diversification helps the algorithm when it is stuck in a certain sub-space of the fitness landscape. This could happen when single elements of the solution have a high weight on the fitness function and are thus very unlikely to be moved as soon as they're arranged "optimally" with respect to a number of options. By forcing the search to move to configurations that have not been visited a long time it is able to escape such sub-spaces.

Implementation in HeuristicLab

The implementation in HeuristicLab is closely related to the C and C++ implementation given by Eric Taillard himself at his ​webpage. He however lists two implementations, an older one written for C++ compilers and a newer one written for C compilers. The two algorithms also differ in the aspect of tabu tenure adaption.