The Reactive Tabu Search

TLDR

We propose an algorithm for combinatorial optimization that adds an explicit check for repeated configurations to the basic Tabu search scheme. The reactive Tabu scheme automatically adjusts the tabu list size by monitoring cycles, diversifies the search with random moves proportional to a moving average of cycle length, and is compared to strict, fixed, and randomly varying list-size schemes, while employing hashing or digital-tree techniques for constant‑time repetition detection. Computational tests on a benchmark function, the 0‑1 Knapsack Problem, and the Quadratic Assignment Problem demonstrate the algorithm’s performance. Published in the INFORMS Journal on Computing (ISSN 1091‑9856), formerly the ORSA Journal on Computing (ISSN 0899‑1499, 1989‑1995).

Abstract

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.