The Reactive Search (RS) Home Page
The focus of the Reactive Search framework is on wide spectrum
heuristic algorithms for discrete optimization,
in which local search is complemented by
feedback schemes ("reactive"),
the past history of the search to
increase their efficiency and efficacy.
In the history-sensitive Reactive Search
sub-symbolic machine learning techniques are used
to tune parameters and to determine an appropriate balance
of diversification versus intensification.
A tutorial introduction to the "reactive search" framework:
Reactive search: Toward self-tuning heuristics.
In V. J. Rayward-Smith, editor, Modern Heuristic Search
Methods, chapter 4, pages 61--83. John Wiley and Sons Ltd, 1996.
Abstract: Local (neighborhood) search can be guided to go
beyond local minima through meta-heuristic methods that use the information
obtained in the previous part of the run. The Reactive Search (RS) method
proposes the integration of simple memory-based feedback schemes in local
search for the on-line determination of free parameters, therefore endowing
the algorithm with the flexibility needed to cover a wide spectrum of
problems but avoiding a human trial-and-error adjustment. In particular, in
the Reactive Tabu Search (RTS) algorithm a simple feedback scheme influences
the value of the prohibition parameter in Tabu Search, so that a balance of
exploration versus exploitation is obtained that is appropriate for the local
characteristics of the task. This paper summarizes the Reactive Search
framework, reviews RTS and its applications, and presents novel results about
the behavior of different Tabu Search schemes when escaping from a local
R. Battiti and G. Tecchiolli. (Mar 10, 96)
Reactive Tabu Search: a vignette
Yet another trial at summarizing in two HTML pages the
reactive search framework (requested by prof. F. Glover).
The Reactive Tabu Search (RTS)
The Reactive Tabu Search
represents the first realization of the above
ideas in the framework of F. Glover's Tabu Search (TS).
TS is based on the temporary prohibition of moves in order to
avoid cycles in the search trajectory (henceforth the
term "tabu" or "taboo").
Some open problems of TS were: i) the determination of
an appropriate "prohibition period" for a given task,
ii) the adoption of minimal computational complexity algorithms
for using memory, iii) the robustness of the technique for
a wide range of different problems.
In RTS the "prohibition period" T is determined through feedback
(reactive) mechanisms during the search. T is one at the beginning
(the inverse of a given move is prohibited only at the
next step), it increases only when there is evidence that
diversification is needed, it decreases when this evidence
disappears. In detail: the evidence that diversification is needed
is signaled by the repetition of previously-visited configuration.
All configurations found during the search
are stored in memory. After a move is executed one checks
whether the current configuration has already been
found in memory and reacts accordingly.
The memory storage and access is executed through hashing or
digital-tree techniques in a CPU time that is constant with
respect to the number of iterations (for non-trivial tasks
the overhead caused by the use of memory is negligible).
The first reactive mechanism is not sufficient to guarantee
that the search trajectory is not confined in
a limited region of the search space. Robustness requires
a second "escape" mechanism, triggered when too many
configurations are repeated to often.
For more information about RTS:
R. Battiti and G. Tecchiolli.
The reactive tabu search.
ORSA Journal on Computing, 6(2):126--140, 1994.
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
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.
Basic Reactive Tabu Search software routines (in C) and
specific routines for the Quadratic Assignment Problem (QAP):
C source code
Reactive Local Search for MAX CLIQUE
A simple interactive environment where you can send the description
of a graph and receive the maximum clique
found by our heuristic algorithm is now available:
RLS in action (``clique here'') .
The algorithm is described in:
R. Battiti and M. Protasi.
(Back to Battiti Home Page)