Changes between Version 5 and Version 6 of Documentation/Reference/Robust Taboo Search

Timestamp:

07/25/11 18:05:08 (13 years ago)

Author:

abeham

Comment:

--

Documentation/Reference/Robust Taboo Search

@@ -13 +13 @@
 
 == Implementation in HeuristicLab ==
-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).
+The implementation in !HeuristicLab is closely related to the implementations given by Eric Taillard himself on his [http://mistic.heig-vd.ch/taillard/ webpage]. Taillard has given two implementations: An older one written for C++ compilers and a newer one written for C compilers. Apart from language 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 adaption scheme 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 (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).
+Apart from the approach itself some default values have also 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 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)]]