Tech. Reports about REACTIVE TABU SEARCH (RTS)

[BATTITI@itnvax.science.unitn.it]

The following technical reports in the area of combinatorial optimization
and neural nets training are available by anonymous ftp from the Mathematics 
Department archive at Trento University.

_______________________________________________________________________

                         The Reactive Tabu Search

                 Roberto Battiti and Giampietro Tecchiolli

                  Technical Report UTM 405, October 1992
	       Dipartimento di Matematica, Univ. di Trento
		     38050 Povo (Trento) - Italia

                             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.

_______________________________________________________________________

             Training Neural Nets with the Reactive Tabu Search
             
                  Roberto Battiti and Giampietro Tecchiolli

                   Technical Report UTM 421, November 1993
                Dipartimento di Matematica, Univ. di Trento
                       38050 Povo (Trento) - Italia

                             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.
_______________________________________________________________________

******> how to obtain a copy via FTP:

unix> ftp volterra.science.unitn.it (130.186.34.16)
Name: anonymous
Password: (type your email address)
ftp> cd pub
ftp> binary
ftp> get reactive-tabu-search.ps.Z
ftp> get rts-neural-nets.ps.Z
ftp> quit
unix> uncompress *.ps.Z
unix> lpr *.ps (or however you print PostScript)

note: gnu-zipped files are available as file.gz
      reactive-tabu-search.ps : 27 pages
      rts-neural-nets.ps : 45 pages
      both papers contain complex figures so that printing can be slow
      on some printers

******> A limited number of hardcopies are available (only if you don't have
        access to FTP!) from:

Roberto Battiti
Dip. di Matematica
Universita' di Trento
38050 Povo (Trento)
Italy

e-mail: battiti at itnvax.science.unitn.it