Reactive search optimization
Encyclopedia
Reactive search optimization (RSO) defines local-search heuristics based on machine learning
, 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.
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.
Reactive Search Optimization advocates the integration of sub-symbolic machine learning techniques into
search heuristics for solving complex optimization problems. The word reactive hints at a ready response
to events during the search through an internal feedback loop for online self-tuning and dynamic
adaptation. In Reactive Search the past history of the search and the knowledge accumulated while
moving in the configuration space is used for self-adaptation in an autonomic manner: the algorithm
maintains the internal flexibility needed to address different situations during the search, but the
adaptation is automated, and executed while the algorithm runs on a single instance and reflects on its
past experience.
The metaphors for reactive search derive mostly from the individual human experience. Its motto can be
"learning on the job". Real-world problems have a rich structure. While many alternative solutions are
tested in the exploration of a search space, patterns and regularities appear. The human brain quickly
learns and drives future decisions based on previous observations. This is the main inspiration source
for inserting online machine learning
techniques into the optimization engine of Reactive Search Optimization.
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.
Machine learning and Neural Networks.
Its specific objective is the study of online learning schemes applied to problem-solving
and optimization, according to a learning while optimizing principle.
The learning signals for adapting the internal parameters of the solution technique
derive from three sources:
Intelligent optimization, a superset of Reactive Search, refers to a more extended area of
research, including online and off-line schemes based on the use of memory, adaptation, incremental
development of models, experimental algorithmics applied to optimization, intelligent tuning and design
of heuristics. In some cases the work is at an upper level, where basic methods are properly guided and
combined, and the term meta-heuristics has been proposed in the past.
Reactive Business Intelligence
advocates RSO principles for applications in the area
of data mining
, business analytics
, and interactive visualization
.
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
, a family of optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
algorithms based on the local search
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
techniques. It refers to a class of heuristics that automatically adjust their working parameters during the optimization phase.
RSO Overview: Learning while Optimizing
Reactive Search Optimization (RSO), like all local searchLocal search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
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.
Reactive Search Optimization advocates the integration of sub-symbolic machine learning techniques into
search heuristics for solving complex optimization problems. The word reactive hints at a ready response
to events during the search through an internal feedback loop for online self-tuning and dynamic
adaptation. In Reactive Search the past history of the search and the knowledge accumulated while
moving in the configuration space is used for self-adaptation in an autonomic manner: the algorithm
maintains the internal flexibility needed to address different situations during the search, but the
adaptation is automated, and executed while the algorithm runs on a single instance and reflects on its
past experience.
The metaphors for reactive search derive mostly from the individual human experience. Its motto can be
"learning on the job". Real-world problems have a rich structure. While many alternative solutions are
tested in the exploration of a search space, patterns and regularities appear. The human brain quickly
learns and drives future decisions based on previous observations. This is the main inspiration source
for inserting online machine learning
Online machine learning
In machine learning, online learning is a model of induction that learns one instance at atime. The goal in online learning is to predict labels for instances.For example, the instances could describe the current conditions of...
techniques into the optimization engine of Reactive Search Optimization.
The issue of parameter tuning in heuristics
Most local search-based heuristics, such as tabu searchTabu search
Tabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
and simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of 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...
, though very efficient and useful in many practical applications, are very sensitive to their own internal parameters. For instance, simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of 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...
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
Global optimization
Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.- General :The most common form is the minimization of one real-valued function...
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 optimization 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 optimization 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.
RSO and Intelligent Optimization
RSO is a multi-disciplinary research area between Operations Research (optimization), Computer Science,Machine learning and Neural Networks.
Its specific objective is the study of online learning schemes applied to problem-solving
and optimization, according to a learning while optimizing principle.
The learning signals for adapting the internal parameters of the solution technique
derive from three sources:
- The optimization problem. For example, parameters and choices for local search applied to the Travelling salesman problemTravelling salesman problemThe travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
(TSP) can be very different from choices for local search applied to Satisfiability problem. - The specific instance. For example, solving a TSP problem for cities in the Alps may require different parameters than those appropriate for cities in a flat region.
- The local characteristics in the configuration space around a given candidate solution. For example, if the current solution is confined in an attraction basin around a locally optimal point (a.k.a. local optimumLocal optimumLocal optimum is a term in applied mathematics and computer science.A local optimum of a combinatorial optimization problem is a solution that is optimal within a neighboring set of solutions...
), characteristics of the attraction basin (like its dimension and height of barriers) can be used to fine-tune the diversification (escape) methods.
Intelligent optimization, a superset of Reactive Search, refers to a more extended area of
research, including online and off-line schemes based on the use of memory, adaptation, incremental
development of models, experimental algorithmics applied to optimization, intelligent tuning and design
of heuristics. In some cases the work is at an upper level, where basic methods are properly guided and
combined, and the term meta-heuristics has been proposed in the past.
Reactive Business Intelligence
Reactive Business Intelligence
Reactive Business Intelligence advocates an holistic approach that integrates data mining, modeling and interactive visualization, into an end-to-end discovery and continuous innovation process powered by human and automated learning....
advocates RSO principles for applications in the area
of data mining
Data mining
Data mining , a relatively young and interdisciplinary field of computer science is the process of discovering new patterns from large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and database systems...
, business analytics
Business analytics
Business analytics refers to the skills, technologies, applications and practices for continuous iterative exploration and investigation of past business performance to gain insight and drive business planning. Business analytics focuses on developing new insights and understanding of business...
, and interactive visualization
Interactive visualization
Interactive visualization is a branch of graphic visualization in computer science that involves studying how humans interact with computers to create graphic illustrations of information and how this process can be made more efficient....
.
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
See also
- Global optimizationGlobal optimizationGlobal optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.- General :The most common form is the minimization of one real-valued function...
- Local search (optimization)Local search (optimization)In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
- Guided local searchGuided Local SearchGuided Local Search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behaviour....
- Iterated local searchIterated local searchIterated local search is a term in applied mathematics and computer sciencedefining a modification of local search or hill climbing methods for solving discrete optimization problems.Local search methods build a trajectory in configuration...
- Tabu searchTabu searchTabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
- Simulated annealingSimulated annealingSimulated annealing is a generic probabilistic metaheuristic for the global optimization problem of 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...
- Genetic algorithmGenetic algorithmA genetic algorithm 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...
- Reactive Business IntelligenceReactive Business IntelligenceReactive Business Intelligence advocates an holistic approach that integrates data mining, modeling and interactive visualization, into an end-to-end discovery and continuous innovation process powered by human and automated learning....