Reactive search

Reactive search

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

ee also

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

External links

* [http://www.reactive-search.org/ The Reactive Search website]
* [http://www.intelligent-optimization.org/ 2007 LION Workshop on Learning and Intelligent Optimization techniques]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • C-reactive protein — C reactive protein, pentraxin related Constructed from 1B09 …   Wikipedia

  • Tabu Search — Tabu Suche ist ein iteratives metaheuristisches Verfahren zur Lösung oder Annäherung von komplexen Problemen. Der Algorithmus wurde von Fred Glover in den USA erfunden und seither ständig weiterentwickelt. So wie Genetische Algorithmen (GA) ist… …   Deutsch Wikipedia

  • Deep Reactive Ion Etching — Reaktives Ionentiefenätzen (engl. Deep Reactive Ion Etching, DRIE), eine Weiterentwicklung des reaktiven Ionenätzen (RIE), ist ein hoch anisotroper Trockenätzprozess für die Herstellung von Mikrostrukuren in Silicium mit Aspektverhältnissen (das… …   Deutsch Wikipedia

  • Metaheuristic — In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the… …   Wikipedia

  • Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… …   Wikipedia

  • Data mining — Not to be confused with analytics, information extraction, or data analysis. Data mining (the analysis step of the knowledge discovery in databases process,[1] or KDD), a relatively young and interdisciplinary field of computer science[2][3] is… …   Wikipedia

  • Hyper-heuristic — A hyper heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics (or components of such… …   Wikipedia

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • Simulated annealing — (SA) is a generic probabilistic meta algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete (e.g.,… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”