Changes between Version 5 and Version 6 of Documentation/Reference/Robust Taboo Search
 Timestamp:
 07/25/11 18:05:08 (9 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Documentation/Reference/Robust Taboo Search
v5 v6 13 13 14 14 == Implementation in HeuristicLab == 15 The implementation in !HeuristicLab is closely related to the C and C++ implementation given by Eric Taillard himself on his [http://mistic.heigvd.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 formthrough the option //!UseNewTabuTenureAdaptionScheme // (set it to false for the old minmax approach, true for the newer way).15 The implementation in !HeuristicLab is closely related to the implementations given by Eric Taillard himself on his [http://mistic.heigvd.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 minmax approach, true for the newer way). 16 16 17 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*N2274and was lowerbounded 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).17 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*N2274// and was lowerbounded 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). 18 18 19 19 [[Image(aspiration_default.png)]]