Tabu Search method

MALLBA  (TIC1999-0754-C03)


This document resumes some work done by the MALLBA-BA team on the Tabu Search method.
 

Table of contents

Introduction

    In the Tabu Search method, in order to improve the efficiency of the exploration process, some historical information related to the evolution of the search is kept (basically the itinerary through the solutions visited). Such an information will be used to guide the search from one solution to the next one avoiding cycling. This is one of the most important features of this algorithm.

    Given an instance x, the algorithm starts from an initial solution   (typically a random one). At any iteration it has to find a new solution by making local movements over the current solution. The ``next solution'' is the best among all (or a subset of) possible solutions in the neighborhood  .  To carry out the exploration process, recently visited solutions should be avoided. To this aim a tabu list is maintained. Therefore once a solution is visited the movement from which it was obtained is considered tabu. Note that   will be changing along the exploration, so in a certain sense we have dynamic neighborhood as compared to the previous local search algorithms where   remains static.
    Typically there are two kinds of tabu lists, a long term memory maintaining the history through all the exploration process as a whole and a short term memory to keep the most recently visited tabu movements. A movement with a tabu status (tabu movement) is avoided to be applied, unless it satisfies certain aspiration criteria. This aims to avoid falling into local optima.

    Given that the tabu list size is fixed before the hand each element of the list belongs to it for a number of iterations bounded by given maximum and minimum values. The skeleton included in this documentation implements this option. The maximum and minimum values are supplied by the user.

    There are two kinds of stopping conditions in the Tabu Search algorithm. The first one has to do with the Tabu Search as a whole (when the algorithm finishes) and the second one is a stopping condition over the search of ``the best'' among all solutions in .
    Some typical stopping conditions are as follows:  is empty, the maximum number of solutions to be explored is fixed, the number of iterations since the last improvement is larger than a specified number, the total number of iterations of the TS algorithm is fixed.
 

Application Areas:

See [5,6,7] for more applications.
 

Implementation of the TS skeleton

  An implementation of the Tabu Search skeleton incorporating new features has been done in the last months.  This implementation allows the user to specify easily how to intensify and diversify the search.  In the previous release of the skeleton this point was not explicit.  These two funcionalitites (intensification and diversification) are inner to the Tabu Search method but it is not completely fixed where to apply them.  All the algorithms refering to Tabu Search applications that we have seen do it in a hidden way (basically beacause they are ad hoc implementations).  We have made these functionalities explicit and apply them in a structured way.

To intensify the search, the user has to implement how the solution is rewarded.  Rewarding will maintain as much as possible the current solution composition.  To diversify the search, the user has to implement how the solution is penalized. Penalizing will allow changes in the current solution easily.  Finaly, a stronger version of the diversification functionality can be implemented that allow exploraing less explored regions in the space of feasible solutions.  We have called this escape.  The search continues in a new random point of the search space when a escape is applied.

The following diagram shows how these functionalities have been incorporated in the current version of Tabu Search skeleton:
 
 









The implementation of the Tabu Search skeleton is contained in four files:

Filler user's part:
 
  • TabuSearch.hh :  The file containing the definition of classes needed.
  • TabuSearch.cc :  The source file where all the classes will be implemented.

  • Skeleton designer's part:
     

  • TabuSearch.imp.hh :  The file containing the definition of the classes needed for the internal implementation of the TabuSearch method.
  • TabuSearch.imp.cc :  The file containing the source code of the TabuSearch method.
  • Tabu1List.cc : Default implementation of the structure for maintaining and managing the tabu movements.
  • ( NOTE:  All files also available at newTabuSearch.tar.gz )


    Reference manual

    A short reference manual has been generated by the authomatic tool Doxygen.  It can be consulted in html and postscript format:

  • HTML Reference Manual
  • PS Reference Manual

  • Related Links

    1. Entornos Geográficamente Distribuidos:  Librería de Optimización Combinatoria (MALLBA Project  TIC1999-0754-C03)
    2. A C++ Implementation of a Skeleton for Tabu Search Method (M.Blesa and F.Xhafa)
    3. A C++ Implementation of Tabu Search for k-Cardinality Tree Problem Based on Generic Programming and Component Reuse (M.Blesa and F.Xhafa)
    4. Reactive Search:  Toward Self-Tuning Heuristics (Roberto Battiti)
    5. The Reactive Tabu Search (Roberto Battiti and Giampietro Tecchiolli)
    6. C code for Reactive Tabu Search(Roberto Battiti and Giampietro Tecchiolli)
    7. The Quadratic Assignment Problem:  A Survey and Recent Developments (Panos M. Pardalos, Franz Rendl, and Henry Wolkowicz)
    8. QAPLIB - A Quadratic Assigment Problem Libray (R.E. Burkard, S.E. Karisch, and F. Rendl)
    9. Tight QAP bounds via linear programming (K.G. Ramakrishnan, M.G.C. Resende, B. Ramachandran, and J.F. Pekny)


    References

    [1]  A. M. Geoffrion,
           An improved implicit enumeration approach for integer programming,
           Operations Research 17 (1969), 437-454

    [2]  L. Steinberg,
           The backboard wiring problem : A placement algorithm,
           SIAM Review 3 (1961), 37-50

    [3]   ---, Assignment problems in parallel and distributed computing,
           Kluwer Academic Publishers, Boston, 1987

    [4]  L.J. Hubert,
           Assignment methods in combinatorial data analysis,
           Marcel Dekker, Inc., New York, NY 10016, 1987

    [5]  R.L. Francis and J.A. White,
           Facility layout and location,
           Prentice-Hall, Englewood Cliffs, N.J., 1974

    [6]  J. Krarup and P.M. Pruzan,
           Computer-aided layout design,
           Mathematical Programming Study 9 (1978), 75-94

    [7]  E.J. McCormik,
           Human factors engineering,
           McGraw-Hill, New York, 1970

    [8]  Kurt Jörnsten and Arne Lokketangen,
           Tabu Search for Weighted K-Cardinality Trees,
           Asia-Pacific Journal of Operational Research 14 (1997) 9-26

    [9]  H.W. Hamacher, K. Joernsten and F. Maffioli,
           Weighted k-cardinality trees,
           Technical Report 91.023, Politecnico di Milano,
           Dipartamento di Electtronica, 1991.

    [10]   M. Fischetti, H. W. Hamacher, K. Joernsten and F. Maffioli,
               Weighted k-cardinality trees : Complexity and polyhedral structure,
               Networks, 24:11-21, 1994.

    [11]   H.W. Hamacher and K. Joernsten,
               Optimal relinquishment according to the norwegian petrol law :
               A combinatorial optimization approach,
               Technical Report 7/93, Norwegian School of Economics and Business
               Administration,  Bergen, 1993.
               Submitted to Applied Mathematical Modelling.

    [12]   L. R. Foulds and H. W. Hamacher,
               A new integer programming approach to (restricted) facilities layout
               problems allowing flexible facility shapes,
               Technical Report 1992-3, University of Waikato,
               Department of Management Science, 1992.

    [13]   M. Ehrgott, J. Freitag, H. W. Hamacher and F. Mafiioli ,
               Heuristics for the K-Cardinality Tree and Subgraph Problems,
               Universität Kaiserslautern, Colonia Insurance, Politecnico di Milano.
     


    MALLBA
    Last update: Wed Sep 06  2000