An Analysis of Parameter Adaptation in
Reactive Tabu Search

Franco Mascia and Paola Pellegrini and Thomas Stützle and Mauro Birattari

1 Median steps to optimal solutions across 10 runs of RTS-MCP on DIMACS instances

PIC

Figure 1: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance C500.9.

PIC

Figure 2: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance C1000.9.

PIC

Figure 3: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance C2000.5.

PIC

Figure 4: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance C4000.5.

PIC

Figure 5: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance MANNa_45.

PIC

Figure 6: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock200_2.

PIC

Figure 7: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock200_4.

PIC

Figure 8: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock400_2.

PIC

Figure 9: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock400_4.

PIC

Figure 10: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance keller5.

PIC

Figure 11: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance p_hat1500-1.

PIC

Figure 12: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance p_hat1500-2.

PIC

Figure 13: Median number of steps to find the optimal solution across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance p_hat1500-3.

PIC

Figure 14: Median number of steps to find the non-optimal solution of size 21 across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock800_2.

PIC

Figure 15: Median number of steps to find the non-optimal solution of size 21 across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance brock800_4.

PIC

Figure 16: Median number of steps to find the non-optimal solution of size 344 across 10 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance MANN_a45.

PIC

Figure 17: Median number of steps to find the non-optimal solution of size 1098 runs of FixedTL-MCP, which corresponds to RTS-MCP with fixed parameter settings on instance MANN_a81.

2 Online parameter adaptation of RTS-MCP on DIMACS instances

PIC

Figure 18: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance C125.9.

PIC

Figure 19: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance C2000.5.

PIC

Figure 20: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance C250.9.

PIC

Figure 21: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance C500.9.

PIC

Figure 22: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance DSJC1000.5.

PIC

Figure 23: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance DSJC500.5.

PIC

Figure 24: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance MANN_a27.

PIC

Figure 25: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance brock200_2.

PIC

Figure 26: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance brock200_4.

PIC

Figure 27: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance gen200_p0.9_44.

PIC

Figure 28: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance gen200_p0.9_55.

PIC

Figure 29: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance gen400_p0.9_55.

PIC

Figure 30: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance gen400_p0.9_65.

PIC

Figure 31: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance gen400_p0.9_75.

PIC

Figure 32: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance hamming10-4.

PIC

Figure 33: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance keller5.

PIC

Figure 34: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat1500-1.

PIC

Figure 35: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat1500-2.

PIC

Figure 36: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat1500-3.

PIC

Figure 37: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat300-2.

PIC

Figure 38: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat300-3.

PIC

Figure 39: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat700-1.

PIC

Figure 40: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat700-2.

PIC

Figure 41: Comparison of the empirical distribution of the tabu list length and the number of steps to reach the optimum solutions for MCP instance p_hat700-3.

3 Comparisons on the median number of steps for the MCP

Instance
RTS-MCP
Random[1,MAXT]-MCP
C125.9 84.0 68.0
C250.9 1 147.0 1 157.0
C500.9 81 144.0 25 225.0
C1000.9 708 530.0 348 284.5
C2000.9 0.4% 0.5%
DSJC1000.5 34 560.0 22 452.0
DSJC500.5 1 400.5 1 347.0
C2000.5 32 772.0 22 939.0
C4000.5 3 677 632.0 2 356 013.0
MANN_a27 75 262.0 62 760.0
MANN_a45 0.2% 0.2%
MANN_a81 0.2% 0.1%
brock200_2 56 583.0 1 339 147.5
brock200_4 178 136.0 2 067 906.0
brock400_2 93.4% 16.8%
brock400_4 100.0% 99.4%
brock800_2 1.0% 0.0%
brock800_4 14.5% 2.2%
gen200_p0.9_44 1 429.0 1 825.0
gen200_p0.9_55 584.0 709.0
gen400_p0.9_55 21 150.5 27 503.0
gen400_p0.9_65 1 390.0 1 374.0
gen400_p0.9_75 1 583.0 1 417.0
hamming10-4 491.0 530.0
keller5 3 040.0 10 063.0
keller6 672 768.0 1 010 057.0
p_hat300-1 139.0 122.0
p_hat300-2 27.0 29.0
p_hat300-3 620.0 632.0
p_hat700-1 1 182.0 1 473.5
p_hat700-2 118.0 92.0
p_hat700-3 210.0 204.0
p_hat1500-1 139 617.0 153 983.0
p_hat1500-2 363.0 254.0
p_hat1500-3 1 229.0 708.0

Table 1: Comparison on the median steps of RTS-MCP and Random[1,MAXT]-MCP. Statistically significant improvements are highlighted in boldface. Instances highlighted in italic are those that one of the two algorithms was not able to solve with 100% success rate.

PIC

Figure 42: Scatterplot of the median number of steps to converge to the best-known solutions for RTS-MCP and FixedTL-MCP. The instances for which neither algorithm reported a 100% success rate are not shown. The black dots correspond to the instances where the difference between the two empirical step distribution are statistically significant.

PIC

Figure 43: Scatterplot of the median number of steps to converge to the best-known solutions for RTS-MCP and Random[1,MAXT]-MCP. The instances for which neither algorithm reported a 100% success rate are not shown. The black dots correspond to the instances where the difference between the two empirical step distribution are statistically significant.

PIC

Figure 44: Scatterplot of the median number of steps to converge to the best-known solutions for RTS-MCP and RoTS-MCP. The instances for which neither algorithm reported a 100% success rate are not shown. The black dots correspond to the instances where the difference between the two empirical step distribution are statistically significant.

PIC

Figure 45: Scatterplot of the median number of steps to converge to the best-known solutions for RTS-MCP and RandomED-MCP. The instances for which neither algorithm reported a 100% success rate are not shown. The black dots correspond to the instances where the difference between the two empirical step distribution are statistically significant.

4 Comparisons on CPU-time for the MCP

Instance
RTS-MCP
FixedTL-MCP
C125.9 0.0 0.0
C250.9 0.0 0.0
C500.9 0.1 0.0
C1000.9 1.1 0.5
C2000.9 0.4% 0.2%
DSJC1000.5 0.2 0.1
DSJC500.5 0.0 0.0
C2000.5 0.3 0.2
C4000.5 50.8 53.9
MANN_a27 0.1 0.1
MANN_a45 0.2% 0.1%
MANN_a81 0.2% 0.0%
brock200_2 0.1 0.1
brock200_4 0.2 0.1
brock400_2 93.4% 99.1%
brock400_4 1.3 1.1
brock800_2 1.0% 2.1%
brock800_4 14.5% 21.6%
gen200_p0.9_44 0.0 0.0
gen200_p0.9_55 0.0 0.0
gen400_p0.9_55 0.0 0.0
gen400_p0.9_65 0.0 0.0
gen400_p0.9_75 0.0 0.0
hamming10-4 0.0 0.0
keller5 0.0 0.0
keller6 4.9 3.9
p_hat300-1 0.0 0.0
p_hat300-2 0.0 0.0
p_hat300-3 0.0 0.0
p_hat700-1 0.0 0.0
p_hat700-2 0.0 0.0
p_hat700-3 0.0 0.0
p_hat1500-1 1.3 1.0
p_hat1500-2 0.0 0.0
p_hat1500-3 0.0 0.0

Table 2: Comparison on the median time of RTS-MCP and FixedTL-MCP. Statistically significant improvements are highlighted in boldface. Instances highlighted in italic are those that one of the two algorithms was not able to solve with 100% success rate.

Instance
RTS-MCP
RandomED-MCP
C125.9 0.0 0.0
C250.9 0.0 0.0
C500.9 0.1 0.1
C1000.9 1.1 0.9
C2000.9 0.4% 0.0%
DSJC1000.5 0.2 0.2
DSJC500.5 0.0 0.0
C2000.5 0.3 0.3
C4000.5 50.8 78.5
MANN_a27 0.1 0.1
MANN_a45 0.2% 0.1%
MANN_a81 0.2% 0.0%
brock200_2 0.1 0.1
brock200_4 0.2 0.2
brock400_2 93.4% 92.7%
brock400_4 1.3 2.0
brock800_2 1.0% 1.3%
brock800_4 14.5% 14.0%
gen200_p0.9_44 0.0 0.0
gen200_p0.9_55 0.0 0.0
gen400_p0.9_55 0.0 0.0
gen400_p0.9_65 0.0 0.0
gen400_p0.9_75 0.0 0.0
hamming10-4 0.0 0.0
keller5 0.0 0.0
keller6 4.9 50.6
p_hat300-1 0.0 0.0
p_hat300-2 0.0 0.0
p_hat300-3 0.0 0.0
p_hat700-1 0.0 0.0
p_hat700-2 0.0 0.0
p_hat700-3 0.0 0.0
p_hat1500-1 1.3 1.0
p_hat1500-2 0.0 0.0
p_hat1500-3 0.0 0.0

Table 3: Comparison on the median time of RTS-MCP and RandomED-MCP. Statistically significant improvements are highlighted in boldface. Instances highlighted in italic are those that one of the two algorithms was not able to solve with 100% success rate.

Instance
RTS-MCP
Random[1,MAXT]-MCP
C125.9 0.0 0.0
C250.9 0.0 0.0
C500.9 0.1 0.0
C1000.9 1.1 0.5
C2000.9 0.4% 0.5%
DSJC1000.5 0.2 0.1
DSJC500.5 0.0 0.0
C2000.5 0.3 0.2
C4000.5 50.8 50.3
MANN_a27 0.1 0.1
MANN_a45 0.2% 0.2%
MANN_a81 0.2% 0.1%
brock200_2 0.1 1.5
brock200_4 0.2 1.8
brock400_2 93.4% 16.8%
brock400_4 100.0% 99.4%
brock800_2 1.0% 0.0%
brock800_4 14.5% 2.2%
gen200_p0.9_44 0.0 0.0
gen200_p0.9_55 0.0 0.0
gen400_p0.9_55 0.0 0.0
gen400_p0.9_65 0.0 0.0
gen400_p0.9_75 0.0 0.0
hamming10-4 0.0 0.0
keller5 0.0 0.0
keller6 4.9 7.1
p_hat300-1 0.0 0.0
p_hat300-2 0.0 0.0
p_hat300-3 0.0 0.0
p_hat700-1 0.0 0.0
p_hat700-2 0.0 0.0
p_hat700-3 0.0 0.0
p_hat1500-1 1.3 1.3
p_hat1500-2 0.0 0.0
p_hat1500-3 0.0 0.0

Table 4: Comparison on the median time of RTS-MCP and Random[1,MAXT]-MCP. Statistically significant improvements are highlighted in boldface. Instances highlighted in italic are those that one of the two algorithms was not able to solve with 100% success rate.

Instance
RTS-MCP
RoTS-MCP
C125.9 0.0 0.0
C250.9 0.0 0.0
C500.9 0.1 0.0
C1000.9 1.1 0.5
C2000.9 0.4% 0.9%
DSJC1000.5 0.2 0.2
DSJC500.5 0.0 0.0
C2000.5 0.3 0.3
C4000.5 50.8 100.4
MANN_a27 0.1 0.1
MANN_a45 0.2% 0.3%
MANN_a81 0.2% 0.0%
brock200_2 0.1 0.2
brock200_4 0.2 0.3
brock400_2 93.4% 76.4%
brock400_4 1.3 3.8
brock800_2 1.0% 0.5%
brock800_4 14.5% 11.5%
gen200_p0.9_44 0.0 0.0
gen200_p0.9_55 0.0 0.0
gen400_p0.9_55 0.0 0.0
gen400_p0.9_65 0.0 0.0
gen400_p0.9_75 0.0 0.0
hamming10-4 0.0 0.0
keller5 0.0 0.0
keller6 4.9 2.4
p_hat300-1 0.0 0.0
p_hat300-2 0.0 0.0
p_hat300-3 0.0 0.0
p_hat700-1 0.0 0.0
p_hat700-2 0.0 0.0
p_hat700-3 0.0 0.0
p_hat1500-1 1.3 0.9
p_hat1500-2 0.0 0.0
p_hat1500-3 0.0 0.0

Table 5: Comparison on the median time of RTS-MCP and RoTS-MCP. Statistically significant improvements are highlighted in boldface. Instances highlighted in italic are those that one of the two algorithms was not able to solve with 100% success rate.