Companion to:
On the Sensitivity of Reactive Tabu Search to its Meta-parameters
Paola Pellegrini, Franco Mascia , Thomas Stützle and Mauro Birattari
IRIDIA, CoDE, Université Libre de Bruxelles, Brussels, Belgium
Abstract:
In this paper, we assess the sensitivity of reactive tabu search to its meta-parameters. With a thorough experimental analysis, based on the quadratic assignment and the maximum clique problem, we show that the performance of reactive tabu search is relatively insensitive to its meta-parameters. This is particularly evident when compared to the sensitivity of tabu search to its parameters: tabu search is rather penalized if used with sub-optimal parameter settings. Reactive tabu search does not strongly pay its high parameter robustness in terms of performance, although it does not improve the peak performance of tabu search.
Parameter and meta-parameters landscape analysis: QAP
Parameter and meta-parameters landscape analysis: MCP
Conclusions
In this paper, we have compared the sensitivity of RTS to its meta-parameters with the sensitivity of TS to its parameters. We made this comparison on two combinatorial optimization problems, namely the QAP and the MCP using instances with different characteristics. We also performed an ANOVA analysis for studying the main effect of the parameters of TS and the meta-parameters of RTS, as well as their interactions. The results of these analyses lead to the same conclusion: RTS is less sensitive than TS to settings of its parameters, and there are no significant interactions according to the ANOVA analysis. We measured the sensitivity by observing the difference in the performance achieved by the algorithms with different meta-parameter (RTS) or parameter (TS) settings. If we consider only the best settings for TS and RTS, in the QAP, TS performs better than RTS when only structured instances are tackled, and the opposite holds when also unstructured instances are involved in the computation. In the MCP, TS typically performs better than RTS when the best settings are selected on an instance basis, and the opposite holds when the best setting is selected across multiple instances. If non-optimal parameter settings are fixed for TS, the performance can strongly worsen both on single and across multiple instances. This is not the case if non-optimal meta-parameter settings are fixed for RTS. Moreover, the best parameter setting for TS is strongly dependent on the characteristics of the instances tackled. Instead, in RTS, many meta-parameter settings perform similarly good on all the instances tested. In the analysis for the QAP, we get to conclusions that are rather different from those drawn by Battiti and Tecchiolli: from our results we would suggest to take a value larger than the originally suggested value of 1.1 for Tincr, and a value smaller than the originally suggested one of $0.9$ for Tdecr. In particular, Tincr=2.0 and Tdecr=0.5 are good settings across all the sets of instances considered. It is not possible to identify a best overall setting for chaos, where the default value is a good compromise. In the analysis for the MCP, instead, the default values proposed by Battiti and Mascia (Tincr=1.1 and Tdecr=0.9) turned out to be very good on the set of all instances. Our results show that, if one aims at generally good results, or if it is not clear what are the characteristics of the instances that need to be considered for determining the appropriate parameter settings for TS, RTS is a very good option, and it can be used without any previous tuning of the meta-parameters: despite the default meta-parameter settings are typically not the best ones, their use does not have a strong negative impact on the performance of the algorithm. On the other side, they also show that there is potential for the usage of parameter selection strategies where, depending on instance characteristics, fixed instance-specific parameter values are chosen. This is an option we will explore further in follow-up research.