Reactive search is the common name for a family of optimization algorithms based on the local search techniques. It refers to a class of heuristics that automatically adjust their working parameters during the optimization phase.

Overview

Reactive search, like all local search techniques, is applied to the problem of finding the optimal configuration of a system; such configuration is usually composed of continuously or discretely varying parameters, while the optimality criterion is a numerical value associated to each configuration. In most cases, an optimization problem can be reduced to finding the (global) minimum of a function whose arguments are the configuration parameters, seen as free variables in the function's domain space.

Dependence on parameters

Most local search-based heuristics, such as tabu search and simulated annealing, though very efficient and useful in many practical applications, are very sensitive to their own internal parameters. For instance, simulated annealing depends on the annealing schedule, often described by a cooling rate parameter whose optimal value can differ according to the problem instance being solved. Therefore, the same algorithm requires precise fine tuning in order to be applied to a new problem. A typical optimization activity is actually a loop where the researcher performs short optimization runs followed by small adjustments in the algorithm's parameters in order to speed the system up.

It has been noted that many research papers on global optimization heuristics are biased by this problem, since the efficiency of an algorithm is sometimes measured only after parameter tuning has been performed, so that the overall effort of optimization (including the fine tuning phase) is not taken into account.

Parameter tuning as an integral component of the heuristic

Reactive search provides a solution to this problem by including the parameter tuning mechanism within the search algorithm itself: parameters are adjusted by an automated feedback loop that acts according to the quality of the solutions found, the past search history and other criteria.

Advantages

The main advantages of reactive search are:

* Automation of the complete optimization procedure, including the fine tuning phase;

* Dynamic adjustment of search parameters, possibly at every search step, leading to faster overall optimization time;

* Enhanced reproducibility of the results, due to a complete algorithmic description of parameter tuning.

Applications

The application field of reactive search is the same of all local search techniques. In particular, applications of reactive search to the following topics have been published in recent years:

* quadratic assignment
* training neural nets and control problems
* vehicle-routing
* structural acoustic control
* special-purpose VLSI realizations
* graph partitioning
* electric power distribution
* maximum satisfiability
* constraint satisfaction
* optimization of continuous functions
* traffic grooming in optical networks
* maximum clique
* real-time dispatch of trams in storage yards
* roof truss design
* increasing internet capacity
* improving vehicle safety
* aerial reconnaissance simulations

Reactive search and intelligent optimization, Roberto Battiti, Mauro Brunato, Franco Mascia

See also

* Global optimization
* Local search (optimization)
* Tabu search
* Simulated annealing
* Genetic algorithms

Links

* The Reactive Search website

* 2007 LION Workshop on Learning and Intelligent Optimization techniques