Reactive search optimization

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.

RSO overview: learning while optimizing

RSO learning loop

Reactive Search Optimization (RSO), like all local search techniques, is applied to the problem of finding the optimum configuration of a system; such a configuration is usually composed of continuously or discretely varying parameters, while the optimality criterion is a numerical value associated with 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 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.

Da Vinci's man, RSO inspiration

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.

The issue of parameter tuning in heuristics

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^{[citation needed]}. 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 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 multi-disciplinary

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:

1. The optimization problem. For example, parameters and choices for local search applied to the Travelling salesman problem (TSP) can be very different from choices for local search applied to Satisfiability problem.
2. 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.
3. 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 optimum), 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 advocates RSO principles for applications in the area of data mining, business analytics, and interactive visualization.

Basic references

• Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0.  Cite uses deprecated parameters (help)

• Battiti, Roberto; Mauro Brunato (2011). Reactive Business Intelligence. From Data to Models to Insight.. Trento, Italy: Reactive Search Srl. ISBN 978-88-905795-0-9.  Cite uses deprecated parameters (help)

• Battiti, Roberto; Gianpietro Tecchiolli (1994). "The reactive tabu search." (PDF). ORSA Journal on Computing 6 (2): 126–140  Cite uses deprecated parameters (help)

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 optimization
• Local search (optimization)
• Iterated local search
• Tabu search
• Simulated annealing
• Genetic algorithm
• Reactive business intelligence, RSO applied in the context of business intelligence
• LIONsolver, an integrated software using RSO for data mining, business intelligence, analytics

v t e Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling ... ... functions Golden section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation ... and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient ... and Hessians Newton's method   Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming   Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Criss-cross algorithm Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push-relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software