Changes between Version 7 and Version 8 of Documentation/Reference/Robust Taboo Search
- Timestamp:
- 07/25/11 18:21:26 (13 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Documentation/Reference/Robust Taboo Search
v7 v8 2 2 = Robust Taboo Search = 3 3 == Introduction == 4 This algorithm was first described in [ [#Tai91 Tai91]]. It is among the most cited algorithms to solve instances of the quadratic assignment problem (QAP).4 This algorithm was first described in [#Tai91 |Tai91|]. It is among the most cited algorithms to solve instances of the quadratic assignment problem (QAP). 5 5 6 6 There are two main differences to a "standard" tabu search: … … 8 8 2. The algorithm features a long-term diversification method which favors moves that have not been performed in a long time. If a move would assign to facilities to locations that both have not been assigned to for a long number of iterations then the move is performed regardless of quality. If there are multiple of these moves in one iteration the best one is performed. 9 9 10 The introduction of randomness in the tabu search makes the search more robust in that it can escape cycling (also see the [ReactiveTabuSearch Reactive Tabu Search]). Cycling is the behavior when the tabu search returns to the same solution over and over. The length of such a cycle is greater than the tabu tenure since during the tenure moves are prohibited.10 The introduction of randomness in the tabu search makes the search more robust in that it can escape cycling (also see the [ReactiveTabuSearch Reactive Tabu Search]). Cycling is the behavior when the tabu search returns to the same solution over and over. The length of such a cycle is greater than the tabu tenure since during the tenure reverting certain moves are prohibited. If the tabu tenure is sometimes higher and sometimes lower the search is more likely to take different directions and thus escape the cycling trap. 11 11 12 12 The long-term diversification helps the algorithm when it is stuck in a certain sub-space of the fitness landscape. This could happen when single elements of the solution have a high weight on the fitness function and are thus very unlikely to be moved as soon as they're arranged "optimally" with respect to a number of options. By forcing the search to move to configurations that have not been visited a long time it is able to escape such sub-spaces. 13 13 14 14 == Implementation in HeuristicLab == 15 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).15 The implementation in !HeuristicLab is 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 a max value. 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). 16 16 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*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).17 Apart from the approach itself some default values have also changed. In the C++ implementation the aspiration parameter (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, as the values felt too high for small problems, 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). To determine even better default values requires extensive paramter tests on a number of benchmark problems of different size and is work for the future. 18 18 19 19 [[Image(aspiration_default.png)]] … … 34 34 35 35 == References == 36 [ [=#Tai91 Tai91] ]Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. //Parallel Computing// 17, pp. 443-455.36 |[=#Tai91 Tai91]| Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. //Parallel Computing// 17, pp. 443-455.
