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

Timestamp:

07/25/11 10:43:47 (13 years ago)

Author:

abeham

Comment:

--

Documentation/Reference/Robust Taboo Search

@@ +1 @@
+[[PageOutline]]
 = Robust Taboo Search =
 == Introduction ==
@@ -14 +15 @@
 The 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).
 
-Apart 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).
+Apart 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 (see Fig. 1). 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 when the old adaption scheme is used, min = 0, max = 8*N when !UseNewTabuTenureAdaptionScheme is set to true).
+
+[[Image(aspiration_default.png)]]
+Fig. 1