Changes between Version 1 and Version 2 of Documentation/Reference/Robust Taboo Search


Ignore:
Timestamp:
07/25/11 10:38:59 (8 years ago)
Author:
abeham
Comment:

updated RTS

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/Robust Taboo Search

    v1 v2  
    1212
    1313== Implementation in HeuristicLab ==
    14 The implementation in !HeuristicLab is closely related to the C and C++ implementation given by Eric Taillard himself at his [http://mistic.heig-vd.ch/taillard/ webpage]. He however lists two implementations, an older one written for C++ compilers and a newer one written for C compilers. The two algorithms also differ in the aspect of tabu tenure adaption.
     14The implementation in !HeuristicLab is closely related to the C and C++ implementation given by Eric Taillard himself on his [http://mistic.heig-vd.ch/taillard/ webpage]. There are two implementations: An older one written for C++ compilers and a newer one written for C compilers. Apart from programming specific differences, the two algorithms mainly differ in the aspect of tabu tenure adaption. In the C++ version the tabu tenure is set as described in the original publication as a uniformly distributed random variable between min and max. In the newer C version however the tabu tenure is set to //x^3^ * max// and rounded down with //x// being a uniformly distributed random variable in the interval (0;1]. The final interval thus is between [0;max], but skewed towards lower values. In !HeuristicLab you can choose between either form through the option //!UseNewTabuTenureAdaptionScheme // (set it to false for the old min-max approach, true for the newer way).
     15
     16Apart from the approach itself also some default values have changed. In the C++ implementation the aspiration tenure (called //!AlternativeAspirationTenure //in !HeuristicLab) is set to N^2^/2, while in the C implementation it is set to 5*N^2^. In !HeuristicLab however we did not use either scheme, but performed a linear regression on the parameters Taillard has given in his results tables. The regression model and thus the parameter is determined by 203*N-2274 and was lower-bounded by 100 for small N. The min and max parameters are adapted similar to the implementations (min = 0.9*N, max = 1.1*N in the C++ case, min = 0, max = 8*N in the C case).