Applications of Reactive Search Optimization (RSO)
Reactive Search Optimization is not a rigid algorithm but a general framework: specific algorithms have
been introduced for unconstrained and constrained tasks, with different stochastic
mechanisms and rules for selecting neighbors. As it usually happens in heuristics, the more specific knowledge about
a problem is used, the better the results. Nonetheless, it was often the case that simple
RSO versions realized with very limited effort could duplicate the performance of more
complex schemes because of their simple embedded feedback loop,
and without intensive parameter and algorithm tuning. A long-term
goal of RSO is the progressive shift of the learning capabilities from the algorithm user to
the algorithm itself, through machine learning techniques.
The RSO framework and related algorithms and tools have been and are being applied to a
growing number of ``classical'' discrete optimization problems, continuous optimization tasks, and
real-world problems arising in widely different contexts. The Web, see for example Google scholar,
lists thousands of citations to the seminal papers, the following list is a selection of some
applications we are aware of. We are always happy to hear from users and developers interested in
RSO principles and applications.
If you have a new application, we will be happy to know about it and to list it here,
contact us .
Classic combinatorial tasks
The seminal paper about RSO for Tabu Search (Reactive Tabu Search)
presented preliminary experimental results on the 0-1 Knapsack Problem, and on the
Quadratic Assignment Problem [BT94a].
A comparison with
Simulated Annealing on QAP tasks is contained in [BT94b].
An early experimental comparison of Reactive Search Optimization with alternative heuristics (Repeated Local Minima Search, Simulated
Annealing, Genetic Algorithms and Mean Field Neural Networks) is presented in [BT95a].
An application of a self-controlling software approach to Reactive Tabu Search is presented in
[FUK08] with results on the QAP problem.
Knapsack and related problems
A reactive local search-based algorithm (adaptive memory search) for the
0/1-Multidemand Multidimensional knapsack problem (0/1-MDMKP) is proposed in [AHL06].
The 0/1-MDMKP represents a large class of important real-life problems, including portfolio selection, capital budgeting,
and obnoxious and semi-obnoxious facility location problems.
A different application is considered in [HM06] for the
disjunctively constrained knapsack problem (DCKP), a variant of the standard knapsack problem with
special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item
Problems on graphs
A reactive tabu search algorithm for Minimum Labeling Spanning Tree is considered
in [CFGV05,CFGV06], together with other meta-heuristics. The problem is as follows:
Given a graph G with a color (label) assigned to each edge one looks for a spanning tree of G with the
minimum number of different colors. The problem has several applications in telecommunication networks,
electric networks, multi-modal transportation networks, among others, where one aims at ensuring
connectivity by means of homogeneous connections.
The graph partitioning problem has been a test case for advanced local search heuristics
starting at least from the seminal Kernighan and Lin paper [KL70], which proposes
a variable-depth scheme. This is is fact a simple prohibition-based (tabu) scheme
where swaps of nodes among the two sets of the partitions are applied,
and the just swapped nodes are kept fixed during
a sequence of tentative moves in search of an improving chain.
Greedy, Prohibition-based, and Reactive Search Optimization Heuristics for Graph Partitioning
are proposed and compared in [BB99],
Multilevel Reactive Tabu Search techniques, based on producing coarse versions of very large graphs
are considered for Graph Partitioning in [BBC99].
An RSO scheme is applied to the Maximum Clique Problem (MCP) in graphs in [BP97a,BP01]. A clique is a subset of nodes which are mutually interconnected, the problem is related
to identifying densely interconnected communities and, in general, to clustering issues.
A relaxed quasi-clique version of the problem where some edged may be missing is addressed in
The work in [YE04]
introduces a new algorithm that combines the stigmergic capabilities of Ant
Colony Optimization (ACO) with local search heuristics to solve the maximum and maximum-weighted clique
problem. The introduced Reactive Prohibition-based Ant Colony Optimization for MCP (RPACOMCP) complements the
intelligent ant colony search with a prohibition-based diversification technique, where the amount of
diversification is determined in an automated way through a feedback (history-sensitive) scheme.
In [SSSG06] the authors address the problem of computing a graph similarity measure which
is generic in the sense that other well known graph similarity measures can be viewed as special cases
of it. They propose and compare two algorithms, an Ant Colony Optimization based algorithm and a
Reactive Search Optimization, and show that they obtain complementary results:
while the RSO technique
achieves good solutions in shorter times, the proposed ACO method eventually attains a better quality.
A classification of methods to manage the prohibition period (Tabu tenure) in the literature is
presented in [DMC08] together with a new reactive Tabu tenure adaptation mechanism. The
generic method is tested on the k-coloring problem.
A Reactive Tabu Search algorithm with variable clustering for the unicost Set Covering Problem (SCP)
is proposed in [KBC07].
Unicost SCPs arise in graph theory when one must select a minimum covering
of edges by nodes or nodes by cliques. In addition, in many practical applications (crew scheduling,
political redistricting, conservation biology, etc.) the relative variation in the weights may be small
enough to warrant a unicost model.
Vehicle routing problems
A reactive tabu search version for the vehicle
routing problem with time windows is designed in [CR97],
while a version of the Vehicle Routing Problem with Backhauls (VRPB) is considered in [CB01,OW02].
A heuristic approach based on a hybrid operation of RTS and Adaptive Memory
Programming (AMP) is proposed in [LA07] to solve the VRPB.
One is given a set of customers, some of which are linehauls (delivery points) and some are
backhauls (collection points), a set of homogeneous vehicles and a depot. A distinguishing feature of
this model is that all backhaul customers must be visited after all linehaul customers are served on
each route. RTS is used with an escape mechanism which manipulates different neighborhood schemes in
order to continuously balance intensification and diversification during the search process. The
adaptive memory strategy takes the search back to the unexplored regions of the search space by
maintaining a set of elite solutions and using them strategically with the RTS.
The authors in [NWB00] address the pickup and delivery problem with time windows using reactive tabu search.
A reactive VNS technique for VRPTW is also proposed in [Bra03].
Vehicle routing with soft time windows and Erlang travel times is studied in [RU07].
Satisfiability and related problems
Maximum satisfiability is considered in [BP97b,BP97c,MG04],
reactive Scaling and Probabilistic Smoothing (SAPS) in [TH02], constraint satisfaction in [NI98].
Reactive local search techniques for the Maximum k-Conjunctive Constraint Satisfaction Problem (MAX-k-CCSP) in [BP99].
A worst-case analysis of tabu search as a function of the tabu list length for the MAX-TWO-SAT problem
is presented in [MG04], with applications also to a reactive determination of the
Neural networks and VLSI systems with learning capabilities
While derivative-based methods for training
from examples have been used with success in many contexts (error back-propagation is an example in the
field of neural networks), they are applicable only to differentiable performance functions and are not
always appropriate in the presence of local minima. In addition, the calculation of derivatives is
expensive and error-prone, especially if special-purpose VLSI hardware is used. A radically
different approach is used in [BT95b]: the task is transformed into a combinatorial optimization problem (the points of the
search space are binary strings), and solved with the Reactive Search Optimization algorithm. To speed up the
neighborhood evaluation phase a stochastic sampling of the neighborhood is adopted and a ``smart''
iterative scheme is used to compute the changes in the performance function caused by changing a single
weight. RSO escapes rapidly from local minima, it is applicable to non-differentiable and
even discontinuous functions and it is very robust with respect to the choice of the initial
configuration. In addition, by fine-tuning the number of bits for each parameter one can decrease the
size of the search space, increase the expected generalization and realize cost-effective VLSI.
Reactive Tabu Search in Semi-supervised Classification is proposed in [ZEcL07]. With a
linear kernel their RTS implementation can effectively find optimal global solutions for the primal
Mixed Integer Programming Transductive Support Vector Machine (MIP-TSVM) with relatively large problem
In contrast to the exhaustive design of systems for
pattern recognition, control, and vector quantization, an appealing possibility consists of specifying a
general architecture, whose parameters are then tuned through Machine Learning (ML). ML becomes a
combinatorial task if the parameters assume a discrete set of values: the RTS
algorithm permits the training of these systems with low number of bits per weight, low computational
accuracy , no local minima ``trapping'', and limited sensitivity to the initial conditions
Special-purpose VLSI modules have been developed to be used as components of fully autonomous
massively-parallel systems for real-time adaptive applications. In contrast to many ``emulation'' approaches, the developed VLSI completely reflects the
combinatorial structure used in the learning algorithms.
Applications considered are in the area of pattern recognition
(Optical Character Recognition), event triggering in High Energy Physics [ABL+95a], control of
non-linear systems [BT95a], compression of EEG signals
[BST+95]. The first product
TOTEM chip [BLST94a,BLST95], and more general special-purpose VLSI realizations are described in [ABL+95a,ABL+95b].
A parallel neurochip for neural networks implementing the Reactive Tabu Search algorithm and application case studies are presented in [DDLL+01]. A Fast Programmable Gate Array (FPGA) implementation of the TOTEM chip is presented
A simple benchmark on a function with many suboptimal local minima is
considered in [BT95b], where a straightforward discretization of the domain is used. A novel algorithm
for the global optimization of functions (C-RTS) is presented in [BT96], in which a combinatorial
optimization method cooperates with a stochastic local minimizer. The combinatorial optimization
component, based on Reactive Search Optimization, locates the most promising boxes, where starting points for the
local minimizer are generated. In order to cover a wide spectrum of possible applications with no user
intervention, the method is designed with adaptive mechanisms: in addition to the reactive adaptation of
the prohibition period, the box size is adapted to the local structure of the function to be optimized
(boxes are larger in ``flat'' regions, smaller in regions with a ``rough'' structure).
An application of intelligent prohibition-based strategies to continuous optimization
is presented in [CS00].
A Reactive Affine Shaker method for continuous optimization is studied in [BB08,BBP06]. The work
presents an adaptive stochastic search algorithm for the optimization of functions of continuous
variables where the only hypothesis is the pointwise computability of the function. The main design
criterion consists of the adaptation of a search region by an affine transformation which takes into
account the local knowledge derived from trial points generated with uniform probability. Heuristic
adaptation of the step size and direction allows the largest possible movement per function evaluation.
The experimental results show that the proposed technique is, in spite of its simplicity, a promising
building block to consider for the development of more complex optimization algorithms, particularly in
those cases where the objective function evaluation is expensive.
A Gregarious Particle Swarm Optimizer (GPSO) is proposed in [PB06]. The particles (the
different local searchers) adopt a reactive determination of the step size, based on feedback from the
last iterations. This is in contrast to the basic particle swarm algorithm, in which no feedback is
used for the self-tuning of algorithm parameters. The novel scheme presented, when tested on a benchmark
for continuous optimization, besides generally improving the average optimal values found, reduces the
Reactive search schemes have been applied to a significant number of ``real-world'' problems; this term refers
to applications where domain-specific knowledge is required. Rather than defining classes with properties
common to many problems, these applications aim at the ``pointwise'' solution of a specific issue with detailed
modeling, therefore providing an essential benchmark for optimization techniques.
Power distribution networks
A real-world application in the area of electric power distribution, service restoration in distribution systems,
is studied in [TFG+02].
Fast optimal setting for voltage control equipment considering interconnection of distributed generators is proposed in [OGY+02],
service restoration in distribution systems in [GOM+03] and
distribution load transfer operation in [Fuk00].
Industrial production and delivery
A continuation of the previously mentioned work on VRPTW [CR97] is proposed in [RCZ08] to aid in the coordination and
synchronization of the production and delivery of multi-product newspapers to bulk delivery locations.
The problem is modeled as an open vehicle routing problem with time windows and zoning constraints. The
methodology is applied to the newspaper production and distribution problem in a major metropolitan
In the field of industrial production planning,
[FV99] studies applications of modern heuristic search methods to pattern sequencing problems.
Flexible job-shop scheduling is studied in [CB96,CB98].
The plant location problem is studied in [DDFO99].
The work in [FV03] is dedicated to solving the continuous flow-shop scheduling problem.
Adaptive self-tuning neurocontrol is considered in [PG00]. The objective is to construct an
adaptive control scheme for unknown time-dependent nonlinear plants.
Various applications of RSO focused on problems arising in the design
and management of telecommunication
RSO for traffic grooming in optical WDM networks is considered in [BB01].
Optimal conformance test selection is studied in [CKZS02]. Conformance testing is used to increase the reliability of telecommunication
applications. Locating hidden groups in communication networks
is addressed in [MIGWS03] by using hidden Markov models.
A communication network is a collection of social groups that communicate via an underlying communication medium. In such a network, a hidden group may try to camouflage its communications amongst the typical communications of the network. The task of increasing Internet capacity is considered in [FT04].
The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) with applications to service level agreements and multimedia
distribution is studied in [HM06,HMS06], where the dynamic adaptation of the resource allocation model is considered for multi-session multimedia.
High quality solutions, reaching the
for several instances, are obtained through a reactive local search scheme.
In the area of wireless and cellular communication networks,
the work in [BBD03] considers the optimal wireless access point placement for location-dependent services, and the work in [FHJ03] proposes a tabu search heuristic for the dimensioning of 3G multi-service networks.
Vehicle routing and dispatching
Real-time dispatch of trams in storage yards is studied in [WZ00].
In the military sector, simple versions of Reactive Tabu Search are considered in [KJHM05] in a comparison of
techniques dedicated to designing an unmanned aerial vehicle (UAV) routing system.
Hierarchical Tabu Programming is used in [Bal07] for finding underwater vehicle trajectories. Aerial reconnaissance simulations is the topic of [RBMC98].
The authors in [BWMR04] use an adaptive tabu search approach for solving the aerial fleet refueling problem.
Industrial and architectural design
In the automotive sector, RSO is used in [HSN03] for improving vehicle safety:
a mixed reactive tabu search method is used to optimize the design
of a vehicle B-pillar subjected to roof crush.
Reactive Tabu Search and sensor selection in active structural acoustic control problems
is considered in [KL98].
The solution of the engineering roof truss design problem is discussed in [HMS03]
An application of reactive tabu search for designing barrelled cylinders and domes of generalized
elliptical profile is studied in [Bla07]. The cylinders and domes are optimized for their
buckling resistance when loaded by static external pressure by using a structural analysis tool.
A reactive stochastic local search algorithm is used in [LSS+08] to solve the Genomic Median Problem (GMP),
an optimization problem inspired by a biological
issue. It aims at finding the chromosome organization of the common ancestor of multiple living species.
It is formulated as the search for a genome that minimizes a rearrangement distance measure among given
Additional applications in bio-informatics include for example [SH07], which proposes an adaptive
bin framework search method for a beta-sheet protein homopolymer model. A novel approach is studied
based on the use of a bin framework for adaptively storing and retrieving promising locally optimal
solutions. Each bin holds a set of conformations within a certain energy range and one uses an
adaptive strategy for restarting a given search process with a conformation retrieved from these bins
when the search stagnates. An adaptive mechanism chooses which conformations should be stored, based on
the set of conformations already stored in memory, and biases choices when retrieving conformations from
memory in order to overcome search stagnation. The energy and diversity thresholds for each bin are
dynamically modified during the search process.
An adaptive meta-search method that alternates between two distinct modes of the search process at
different levels is proposed
in [Shm06,Shm07] for protein folding. The high level process
ensures that unexplored promising parts of the search landscape are visited and the low-level search
provides the thorough exploration of local neighborhoods. Multiple search processes are used in an
Finally, visual representation of data through clustering is considered in [CDDG+08].