The Reactive Search (RS) Home Page

organized by Roberto Battiti

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"), that use the past history of the search to increase their efficiency and efficacy.
In the history-sensitive Reactive Search algorithms simple sub-symbolic machine learning techniques are used to tune parameters and to determine an appropriate balance of diversification versus intensification.

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.

Reactive Local Search for MAX CLIQUE (``clique here'')

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)