preprints available: optimization & neural nets
Roberto Battiti
battiti at volterra.science.unitn.it
Mon May 9 10:23:32 EDT 1994
*** PREPRINTS AVAILABLE: ***
OPTIMIZATION & NEURAL NETS
The following technical reports are available by anonymous ftp at our local
archive: volterra.science.unitn.it (130.186.34.16).
The subjects are combinatorial and continuous optimization algorithms, and
their application to neural nets.
Two papers (battiti.neuro-hep.ps.Z, battiti.reactive-tabu-search.ps.Z)
are also available from the neuroprose archive.
A limited number of hardcopies can be obtained from:
Roberto Battiti
Dip. di Matematica Univ. di Trento
38050 Povo (Trento) - ITALY
email: battiti at science.unitn.it
or:
Giampietro Tecchiolli
Istituto per la Ricerca Scientifica e Tecnologica
38050 Povo (Trento) - ITALY
email: tec at irst.it
________________________________________________________________________________
ARCHIVE-NN-1
title: The Reactive Tabu Search
author: Roberto Battiti and Giampietro Tecchiolli
number: UTM 405 Ottobre 1992
note: 27 pages, to appear in: ORSA Journal on Computing, 1994
abstract:
We propose an algorithm for combinatorial optimization where an explicit
check for the repetition of configurations is added to the basic scheme of
Tabu search. In our Tabu scheme the appropriate size of the list is learned
in an automated way by reacting to the occurrence of cycles. In addition, if
the search appears to be repeating an excessive number of solutions excessively
often, then the search is diversified by making a number of random moves
proportional to a moving average of the cycle length.
The reactive scheme is compared to a strict Tabu scheme, that forbids the
repetition of configurations and to schemes with a fixed or randomly varying
list size. From the implementation point of view we show that the Hashing or
Digital Tree techniques can be used in order to search for repetitions in a
time that is approximately constant.
We present the results obtained for a series of computational tests on a
benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic
Assignment Problem.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/reactive-tabu-search.ps.Z
________________________________________________________________________________
ARCHIVE-NN-2
title: Local Search with Memory: Benchmarking RTS
author: Roberto Battiti and Giampietro Tecchiolli
number: UTM Ottobre 1993
note: 34 pages
abstract:
The purpose of this work is that of presenting a version of the Reactive Tabu
Search method (RTS) that is suitable for constrained problems, and that of
testing RTS on a series of constrained and unconstrained Combinatorial Optimi-
zation tasks. The benchmark suite consists of many instances of the N-K model
and of the Knapsack problem with various sizes and difficulties, defined with
portable random number generators.
The performance of RTS is compared with that of Repeated Local Minima Search,
Simulated Annealing, Genetic Algorithms, and Neural Networks. In addition,
the effects of different hashing schemes and of the presence of a simple
`aspiration' criterion in the RTS algorithm are investigated.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/rts-benchmark.ps.Z
________________________________________________________________________________
ARCHIVE-NN-3
title: Training Neural Nets with the Reactive Tabu Search
author: Roberto Battiti and Giampietro Tecchiolli
number: UTM 421 Novembre 1993
note: 45 pages, shorter version to appear in:
IEEE Trans. on Neural Networks
abstract:
In this paper the task of training sub-symbolic systems is considered as a
combinatorial optimization problem and solved with the heuristic scheme of
the Reactive Tabu Search (RTS) proposed by the authors and based on F. Glover's
Tabu Search. An iterative optimization process based on a ``modified greedy
search'' component is complemented with a meta-strategy to realize a discrete
dynamical system that discourages limit cycles and the confinement of the
search trajectory in a limited portion of the search space. The possible
cycles are discouraged by prohibiting (i.e., making tabu) the execution of
moves that reverse the ones applied in the most recent part of the search,
for a prohibition period that is adapted in an automated way. The confinement
is avoided and a proper exploration is obtained by activating a diversification
strategy when too many configurations are repeated excessively often.
The RTS method is applicable to non-differentiable functions, it is robust
with respect to the random initialization and effective in continuing the
search after local minima. The limited memory and processing required make RTS
a competitive candidate for special-purpose VLSI implementations. We present
and discuss four tests of the technique on feedforward and feedback systems.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/rts-neural-nets.ps.Z
________________________________________________________________________________
ARCHIVE-NN-4
title: Learning with first, second, and no derivatives:
a case study in High Energy Physics
author: Roberto Battiti and Giampietro Tecchiolli
note: 36 pages, to appear in Neurocomputing 6, 181-206, 1994
abstract:
In this paper different algorithms for training multi-layer perceptron
architectures are applied to a significant discrimination task in High Energy
Physics. The One Step Secant technique is compared with On-Line Backpropagation
, the 'Bold Driver' batch version and Conjugate Gradient methods. In addition,
a new algorithm (Affine Shaker) is proposed that uses stochastic search based
on function values and affine transformations of the local search region.
Although the Affine Shaker requires more CPU time to reach the maximum genera-
lization, the technique can be interesting for special-purpose VLSI implementa-
tions and for non-differentiable functions.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/neuro-hep.ps.Z
________________________________________________________________________________
ARCHIVE-NN-5
title: Simulated Annealing and Tabu Search in the Long Run:
a Comparison on QAP Tasks
author: Roberto Battiti and Giampietro Tecchiolli
number: UTM 427 Febbraio 1994
note: 11 pages, to appear in:
Computer and Mathematics with Applications
abstract:
Simulated Annealing (SA) and Tabu Search (TS) are compared on the Quadratic
Assignment Problem. A recent work on the same benchmark suite argued that SA
could achieve a reasonable solution quality with fewer function evaluations
than TS. The discussion is extended by showing that the conclusions must be
changed if the task is hard or a very good approximation of the optimal
solution is desired, or if CPU time is the relevant parameter. In addition,
a recently proposed version of TS (the Reactive Tabu Search) solves the
problem of finding the proper list size with an automatic memory-based
reaction mechanism.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/rts-versus-sa.ps.Z
________________________________________________________________________________
ARCHIVE-NN-6
title: The continuous reactive tabu search: blending combinatorial
optimization and stochastic search for global optimization
author: Roberto Battiti and Giampietro Tecchiolli
number: UTM 432 Maggio 1994
note: 28 pages
abstract:
A novel algorithm for the global optimization of functions (C-RTS) is
presented, in which a combinatorial optimization method cooperates with a
stochastic local minimizer. The combinatorial optimization component, based
on the Reactive Tabu Search recently proposed by the authors, 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: the box
size is adapted to the local structure of the function to be optimized, the
search parameters are adapted to obtain a proper balance of diversification
and intensification. The algorithm is compared with some existing algorithms,
and the experimental results are presented for a suite of benchmark tasks.
FTP-host: volterra.science.unitn.it
FTP-file: pub/neuronit/crts.ps.Z
________________________________________________________________________________
More information about the Connectionists
mailing list